Online bipartite matching with imperfect advice

Davin Choo, Themis Gouleakis, Chun Kai Ling, Arnab Bhattacharyya

Introduction

Online bipartite matching is a fundamental problem in computer science with significant applications in internet advertising and ride-sharing. The task involves matching a set of fixed "offline" resources (e.g., ad slots) with "online" items (e.g., users) that arrive sequentially. Upon arrival, a decision to match must be made immediately and irrevocably. While traditional algorithms like RANKING provide strong worst-case guarantees, they often ignore available historical data or predictions. This paper investigates how to leverage such "advice" to improve performance while maintaining robustness against prediction errors.

The Challenge of Imperfect Advice

The primary goal is to design algorithms that are both 1-consistent (achieving a perfect matching if advice is accurate) and $β$-robust (never performing worse than the best advice-free algorithm). However, the utility of advice depends heavily on the arrival model.

Adversarial Random Order
det. algo. 1/2 $1 - 1/e$
det. hardness 1/2 3/4
rand. algo. $1 - 1/e$ 0.696
rand. hardness $1 - 1/e + o(1)$ 0.823
Table 1: Competitive ratios and hardness results for different arrival models and algorithm types.

In a strictly Adversarial Arrival model, the authors prove a "no-free-lunch" theorem: it is mathematically impossible to be 1-consistent and better than 0.5-robust. Since 0.5 is inferior to the standard $1 - 1/e$ ratio, the research focuses on the more realistic Random Order Arrival model.

The TestAndMatch Framework

The authors propose a meta-algorithm called TestAndMatch designed for the Random Order model. The algorithm operates in three distinct phases:

  1. Sampling: It uses a small, sublinear portion of initial arrivals to sample the actual distribution of user types.
  2. Distribution Testing: Using $L_1$ distance estimators, it compares the sampled distribution against the predicted advice (provided as a histogram of expected types).
  3. Decision: If the advice is statistically likely to be accurate (low $L_1$ distance), the algorithm follows the advice-based matching strategy ("Mimic"). If the advice appears corrupted, it reverts to a safe "Baseline" algorithm like RANKING.

Key Results and Graceful Degradation

TestAndMatch successfully achieves 1-consistency and $(β - o(1))$-robustness. A critical insight is the algorithm's ability to handle "noisy" advice through graceful degradation. Rather than a binary failure, the competitive ratio decreases smoothly as the error in the advice increases.

Figure 5: The lower bound on the achieved competitive ratio as a function of the L1 distance between the predicted and actual distributions.

Empirical tests on synthetic datasets confirm these theoretical bounds. When advice is perfect, the algorithm achieves near-optimal matching. When advice is completely corrupted, the distribution tester successfully detects the error, allowing the algorithm to maintain a competitive ratio of approximately 0.8 by reverting to the baseline, whereas a naive approach would fail entirely.

Conclusion

By integrating property testing into online matching, this work provides a robust framework for using machine-learned predictions. While adversarial settings remain a barrier, the TestAndMatch approach demonstrates that in random-order environments, we can achieve the "best of both worlds": significant gains from good advice without the risk of catastrophic failure from bad advice.

Summary updated

BibTeX
@inproceedings{choo2024online,
  author = {Davin Choo and Themis Gouleakis and Chun Kai Ling and Arnab Bhattacharyya},
  title = {{Online bipartite matching with imperfect advice}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=61WtHsVKWF},
}
Figure