Abstract
We consider the online stochastic matching problem proposed by Feldman et al. [FMMM09] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribution and it needs to be matched upon its arrival to an empty bin. The goal is to maximize the number of allocations. We present an online algorithm for this problem with a competitive ratio of 0.702. Before our result, algorithms with a competitive ratio better than $1-1/e$ were known under the assumption that the expected number of arriving balls of each type is integral. A key idea of the algorithm is to collect statistics about the decisions of the optimum offline solution using Monte Carlo sampling and use those statistics to guide the decisions of the online algorithm. We also show that our algorithm achieves a competitive ratio of 0.705 when the rates are integral. On the hardness side, we prove that no online algorithm can have a competitive ratio better than 0.823 under the known distribution model (and henceforth under the permutation model). This improves upon the 5/6 hardness result proved by Goel and Mehta [GM08] for the permutation model.
Introduction
The online stochastic matching problem is a fundamental model for real-time resource allocation, such as matching internet users to display advertisements. In this setting, a bipartite graph consists of fixed "bins" (ad slots) and incoming "balls" (users). Balls arrive according to a known probability distribution, and the algorithm must immediately decide whether to match an arriving ball to an adjacent empty bin. Once a bin is matched, it is unavailable for future arrivals. The objective is to maximize the total number of matches.
Historically, the competitive ratio for this problem was bounded by $1 - 1/e \approx 0.632$ in adversarial settings. While stochastic assumptions offered a path forward, previous improvements often relied on the restrictive assumption of "integral rates"—where the expected number of arrivals for each ball type is an integer. This paper breaks this barrier for the general case of arbitrary arrival rates.
Methodology: Online Actions Based on Offline Statistics
The authors introduce a strategy that uses statistics from an optimal offline solver to guide online decisions. This approach consists of two primary phases: statistical estimation and adaptive sampling.
Offline Statistics via Monte Carlo
Since the future sequence of arrivals is unknown, the algorithm uses Monte Carlo sampling to simulate many potential arrival sequences. For each sequence, it computes the optimal offline matching. By averaging these results, the algorithm estimates $f_{(y,z)}$, the probability that an optimal offline solver would match a ball of type $y$ to bin $z$. These probabilities form a "fractional matching" that serves as a probabilistic roadmap.
The Adaptive Two-Choice Algorithm
When a ball of type $y$ arrives, the algorithm does not simply pick a bin greedily. Instead, it samples two potential bins, $z_1$ and $z_2$, from a carefully constructed joint distribution based on the offline statistics $f$. The algorithm first attempts to match the ball to $z_1$; if $z_1$ is already occupied, it attempts to match with $z_2$.
This joint distribution is designed to minimize the overlap between the two choices (as seen in the disjoint intervals for $I_{e_1}$ and $J_{e_1}$ in Figure 5), ensuring that the second choice provides a meaningful "backup" if the first bin is full. This adaptivity is the key mechanism for surpassing the $1-1/e$ performance ceiling.
Key Insights
- Adaptivity vs. Non-Adaptivity: The paper proves that non-adaptive algorithms—those that do not check bin status before matching—cannot exceed a $1 - 1/e$ ratio when arrival rates are small. Adaptivity is essential for higher performance.
- Cuckoo Hashing Connection: The authors establish a new hardness upper bound of 0.823 by linking the limits of online matching to the load thresholds of random hash tables in Cuckoo Hashing theory.
Results
The adaptive algorithm achieves a competitive ratio of 0.702 for arbitrary arrival rates, and 0.705 when rates are integral. A simpler non-adaptive version still achieves 0.684, which is a significant improvement over the standard $1 - 1/e$ baseline. Furthermore, the authors prove a theoretical hardness bound of 0.823, narrowing the gap between the best known algorithm and the theoretical limit.
Conclusion
By leveraging offline statistics through Monte Carlo sampling and employing an adaptive two-choice strategy, this work provides a new benchmark for online stochastic matching. Future work may explore the algorithm's sensitivity to errors in the arrival distribution estimates and investigate more complex adaptive strategies to further close the gap toward the 0.823 theoretical limit.
Summary updated