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 |
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:
- Sampling: It uses a small, sublinear portion of initial arrivals to sample the actual distribution of user types.
- Distribution Testing: Using $L_1$ distance estimators, it compares the sampled distribution against the predicted advice (provided as a histogram of expected types).
- 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.
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