Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation

Vineet Goyal, Rajan Udwani

Abstract

Online matching with stochastic rewards is a fundamental problem in resource allocation where matches succeed with a certain probability. Traditional analysis using Expectation Linear Programming (LP) benchmarks has been limited by an integrality gap, preventing researchers from achieving the optimal $1-1/e$ competitive ratio. This paper introduces a novel "path-based" analytical framework that considers all possible success/failure paths. Using this framework, the authors achieve the optimal $1-1/e$ ratio for decomposable edge probabilities and improve the ratio for general vanishingly small probabilities to 0.596, breaking the long-standing 0.5 barrier.

Introduction

In online resource allocation problems, such as matching advertisements to users or drivers to riders, uncertainty is a primary challenge. Unlike classic models where a match is guaranteed, real-world applications involve stochastic rewards: a user might not click an ad, or a rider might cancel. This is modeled as Online Bipartite Matching with Stochastic Rewards. A set of resources is known offline, and arrivals appear sequentially. A match between resource $i$ and arrival $t$ succeeds with probability $p_{it}$. If successful, the resource is consumed; if not, it remains available for future arrivals.

The performance of algorithms is measured by the competitive ratio—the ratio of the algorithm's expected reward to the optimal offline reward. For years, the general stochastic case was stuck at a competitive ratio of 0.5, primarily due to the "looseness" of standard Linear Programming (LP) benchmarks.

Methodology and Path-Based Formulation

The authors identify that the standard "Expectation LP" benchmark is fundamentally limited by an integrality gap of $1/(1-1/e)$, making it impossible to prove optimal ratios using that tool. To overcome this, they propose a Path-Based Program (PBP). Unlike the Expectation LP which only considers average outcomes, the PBP accounts for every possible "sample path" (the sequence of successes and failures). This provides a much tighter upper bound on the offline optimum.

Two primary algorithms are developed:

  1. Generalized Perturbed-Greedy: Designed for "decomposable" probabilities ($p_{it} = p_i \cdot p_t$). It uses a randomized approach where resources are assigned random "seeds" to determine matching priority, mimicking the optimal deterministic "Ranking" algorithm.
  2. Generalized Fully-Adaptive: Designed for general but vanishingly small probabilities ($p_{it} \to 0$). This deterministic algorithm tracks the cumulative probability of failed matches for each resource to adjust matching priorities dynamically.

Key Results

The path-based framework allows for significantly tighter bounds across various probability regimes. The authors achieve the "gold standard" competitive ratio of $1 - 1/e \approx 0.632$ for decomposable probabilities. For the more challenging case of general vanishing probabilities, they improve the state-of-the-art ratio from 0.534 to 0.596.

Summary of competitive ratios achieved using the path-based formulation compared to previous benchmarks.

The research also clarifies why simpler tools worked in specific sub-cases, such as the "large inventory" regime. They demonstrate that as the number of resource copies increases, the path-based benchmark and the standard expectation LP converge.

Conclusion

This work bridges the gap between deterministic and stochastic online matching by introducing a powerful new analytical tool. While the path-based formulation is primarily a tool for theoretical analysis due to its exponential complexity, the insights it provides lead to algorithms that break long-standing performance barriers. Future research remains focused on the general case of arbitrary edge probabilities that are neither small nor decomposable, which remains one of the most significant open challenges in the field.

Summary updated

BibTeX
@inproceedings{goyal2020online,
  author = {Vineet Goyal and Rajan Udwani},
  title = {{Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation}},
  booktitle = {EC},
  year = {2020},
  doi = {10.1145/3391403.3399531},
}
Figure