Online Stochastic Matching: Online Actions Based on Offline Statistics

Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi

TL;DR

This paper breaks the long-standing $1 - 1/e \approx 0.632$ competitive ratio barrier for the general online stochastic matching problem. By using Monte Carlo sampling to extract statistics from an "optimal offline" solver, the authors develop an adaptive algorithm that achieves a competitive ratio of 0.702, significantly narrowing the gap between online performance and offline perfection.

What Problem Does This Paper Address?

The paper tackles the Online Stochastic Matching problem, a theoretical framework for real-world tasks like display advertisement allocation. Imagine a bipartite graph where one side consists of fixed "bins" (ad slots) and the other side consists of "ball types" (types of users). At each time step, a ball arrives, sampled independently from a known probability distribution. The algorithm must immediately decide whether to match this ball to an adjacent empty bin or discard it. Once a bin is matched, it’s gone.

The goal is to maximize the total number of matches. The challenge lies in the "online" nature: you don't know which balls will arrive in the future, but you do know the likelihood of their arrival. Previous work had shown that if the arrivals are adversarial, you can't do better than a $1 - 1/e$ ratio. While some progress had been made in the stochastic setting, those improvements usually relied on "integral rates"—the unrealistic assumption that the expected number of arrivals for each type is a whole number. This paper seeks a solution for the general case with arbitrary arrival rates.

Methods

The authors introduce a novel approach: Online Actions Based on Offline Statistics.

  1. Offline Statistics via Monte Carlo: The core idea is to "peek" at what an optimal offline algorithm (which sees the whole sequence of arrivals at once) would do. Since we can't see the future, the authors use Monte Carlo sampling to simulate many possible arrival sequences. They calculate $f_{(y,z)}$, the probability that an optimal offline solver would match a ball of type $y$ to bin $z$.
  2. The Fractional Matching Guide: This collection of probabilities $f$ forms a "fractional matching." The online algorithm uses this as a roadmap.
  3. The Adaptive Algorithm: When a ball of type $y$ arrives, the algorithm doesn't just pick a bin greedily. Instead, it samples two potential neighbor bins, $z_1$ and $z_2$, from a carefully constructed joint distribution based on the offline statistics $f$.
  4. It first tries to match the ball to $z_1$.
  5. If $z_1$ is already full, it tries $z_2$.
  6. The joint distribution is designed to minimize the overlap between $z_1$ and $z_2$, maximizing the "backup" utility of the second bin.

Datasets

As a theoretical computer science paper, it does not use empirical real-world datasets. Instead, the authors evaluate their algorithms through mathematical proofs and specialized graph structures:

  • Complete Bipartite Graphs: Used to prove the $1 - 1/e$ upper bound for non-adaptive algorithms.
  • Random Bipartite Graphs: Used in conjunction with thresholds from cuckoo hashing and random SAT theory to establish the new hardness upper bound of 0.823.

Key Insights and Ideas

  • Breaking the Non-Adaptive Ceiling: The authors prove that "non-adaptive" algorithms—those that decide where a ball goes without checking if the bin is already full—can never beat $1 - 1/e$ if arrival rates are small. Adaptivity (checking bin status) is the key to higher performance.
  • The Power of Two Choices: By sampling two bins instead of one, the algorithm creates a safety net. The sophisticated part is the "joint distribution," which ensures that the second choice isn't just a redundant version of the first.
  • Cuckoo Hashing Connection: One of the most elegant "aha moments" is the use of Cuckoo Hashing theory to prove hardness. The authors show that the limits of online matching are deeply related to the load thresholds of random hash tables, allowing them to improve the theoretical upper bound on the competitive ratio from 0.833 down to 0.823.

Key Results

  • Main Result: The adaptive algorithm achieves a competitive ratio of 0.702 for arbitrary arrival rates.
  • Integral Rates: If the arrival rates are restricted to integers, the ratio improves slightly to 0.705.
  • Non-Adaptive Performance: A simpler, non-adaptive version of their algorithm still achieves 0.684, which is better than the standard $1 - 1/e \approx 0.632$.
  • Hardness Bound: They prove that no online algorithm, no matter how clever, can achieve a ratio better than 0.823 in this model.

Limitations and Future Work

  • Computational Overhead: The algorithm requires pre-computing offline statistics via Monte Carlo sampling. While polynomial-time, the number of samples required for high accuracy could be significant in very large-scale systems.
  • Known Distributions: The model assumes the arrival distribution is known perfectly beforehand. In practice, these distributions are often estimated, and the algorithm's sensitivity to estimation errors is not explored here.
  • The Gap: There is still a gap between the 0.702 achieved and the 0.823 theoretical limit. The authors suggest that more complex adaptive strategies (perhaps picking from more than two bins) could potentially close this gap.

Summary updated

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 \cite{GM08} for the permutation model.
BibTeX
@inproceedings{manshadi2012online,
  author = {Vahideh H. Manshadi and Shayan Oveis Gharan and Amin Saberi},
  title = {{Online Stochastic Matching: Online Actions Based on Offline Statistics}},
  booktitle = {Math. Oper. Res},
  year = {2012},
  url = {https://openreview.net/forum?id=eEdm361xwO},
}

Loading related content...

Figure