TL;DR
This paper breaks long-standing performance barriers in online bipartite matching with stochastic rewards (such as ad clicks or ridesharing allocations). By introducing a novel path-based analysis framework that bypasses loose linear programming benchmarks, the authors achieve the optimal $(1-1/e)$ competitive ratio for decomposable probabilities and a record-breaking $0.596$ ratio for vanishingly small heterogeneous probabilities.
What Problem Does This Paper Address?
In classical online bipartite matching, an algorithm allocates an available resource (like an ad slot or a rideshare driver) to an arriving user, assuming the match succeeds immediately. In the real world, however, matches often involve stochastic rewards: an advertiser only pays if a user actually clicks the ad, and a ride is only booked if the passenger accepts the price. Crucially, this success or failure is only revealed after the allocation decision is made.
Evaluating online algorithms in this setting requires comparing them against an optimal offline benchmark. For years, researchers relied on an "expectation Linear Program (LP)" as the standard baseline. However, this baseline is inherently loose because it only enforces resource constraints in expectation across all scenarios, rather than on a per-scenario basis. Because of this loose benchmark, previous algorithms for vertex-weighted rewards were stuck at a competitive ratio of $1/2$. This paper aims to break through this $1/2$ barrier by designing better algorithms and tighter analysis frameworks.
Methods
The authors introduce two distinct algorithms tailored to different probability structures, alongside a brand-new mathematical analysis framework:
- Algorithm 1 (Generalized Perturbed-Greedy): Designed for decomposable edge probabilities (where the probability of a match succeeding can be split into a resource factor and an arrival factor, $p_{it} = p_i \cdot p_t$). It assigns a random "seed" to each resource and matches arrivals greedily based on a perturbed expected reward.
- Algorithm 2 (Generalized Fully-Adaptive): A deterministic algorithm designed for vanishingly small heterogeneous probabilities ($p_{it} \to 0$). Here, the algorithm tracks failed matches and systematically lowers the expected reward of a resource over time using a deterministic scaling function.
- Path-Based Program (PBP) & LP-Free Framework: Instead of using the standard expectation LP, the authors construct a tighter benchmark that enforces capacity constraints on every single sample path of the stochastic process. For the vanishing probabilities case, they bypass LPs entirely, utilizing a path-based framework inspired by duality to directly compare the online algorithm against the offline benchmark.
Datasets
Not discussed in the paper. This is a purely theoretical paper containing mathematical proofs and numerical evaluations of scaling functions; no empirical datasets or real-world benchmarks were used.
Key Insights and Ideas
- The Expectation LP is Too Strong: The standard expectation LP allows the offline benchmark to over-allocate resources in some sample paths as long as it balances out on average. This creates an unrealistically high bar for online algorithms to compete against.
- Path-Based Dual Fitting: By writing dual constraints for individual sample paths, the authors can correlate their mathematical dual variables with the actual success or failure of specific matches. This correlation resolves the primary hurdle that caused previous primal-dual analyses to fail.
- The Threshold/Budget Viewpoint: For vanishing probabilities, the authors generalize an elegant perspective: instead of coin flips determining edge success, each resource can be thought of as having a hidden "budget" drawn from an exponential distribution. A match succeeds when the accumulated allocation probability finally exhausts this budget.
Key Results
The paper's quantitative improvements are summarized in the table below, showing how the new path-based approaches push past the historical $1/2$ competitive ratio barrier:
- Decomposable Probabilities: Algorithm 1 achieves a competitive ratio of $(1 - 1/e) \approx 0.632$. This is mathematically optimal, matching the upper bound of the classical, non-stochastic online matching problem.
- Vanishing Heterogeneous Probabilities: Algorithm 2 achieves a competitive ratio of $0.596$ when edge probabilities are small ($p \le 0.38$), significantly beating the previous best guarantee of $0.534$.
- Large Inventory Convergence: The authors prove that when resources have a large capacity ($c_i \to \infty$), the path-based program and the expectation LP converge to the exact same optimal value, explaining why older LP-based methods only worked well in large-capacity regimes.
Limitations and Future Work
While this paper marks a significant leap forward, a few open challenges remain:
- General Probabilities: Beating the naive $1/2$ greedy baseline for general, non-decomposable, and non-vanishing edge probabilities remains an open problem.
- Online Assortments: The authors note that achieving a competitive guarantee better than $1/2$ in the more complex setting of online assortments (where a menu of options is offered to a user instead of a single item) is still an unresolved challenge.
Summary updated