Optimal online matching achieves new performance limit with known arrivals

Optimal Online Stochastic Matching

Data Structures and AlgorithmsComputer Science and Game Theory

Summary

This paper tackles the challenge of matching incoming requests to available resources in real time when the pattern of arrivals is known in advance. The authors find the best possible way to do this for arrivals that follow a particular random process called Poisson, reaching a performance limit that was previously known but not proven achievable. They show their method is nearly as good when there are exactly n arrivals too. To prove their results, they connect this matching problem to a scheduling problem and use mathematical properties of certain set functions. They also demonstrate that if the arrival pattern is unknown, the best possible performance is strictly worse, highlighting the value of knowing the arrival distribution.

What this means in practice

  • For online marketplace operators: Implement matching systems that optimally assign buyers to sellers in real time when the demand pattern is known.
  • For cloud resource schedulers: Design scheduling algorithms that assign computational tasks with stochastic arrivals more efficiently using insights from exponential scheduling.

Authors

Paul Duetting, Michal Feldman, Mathieu Molina

Abstract

We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio. For Poisson arrivals, we achieve $1-e/e^e\approx0.8206$, matching the upper bound of Chierichetti, Giacchini, Panconesi, and Vattani [ICALP 2025]. For exactly $n$ i.i.d.~arrivals, we obtain the same guarantee up to an additive $O(n^{-1/2})$ loss. Our key technical contribution is an exact correspondence between Poisson matching and exponential scheduling, preserving both online performance and the expected offline optimum. To prove the latter, we show that the distribution of the maximum of a random supermodular set function is determined by its joint distributions along chains of nested sets, a result of independent interest. This reduces the analysis to chains, where classical Poisson--exponential duality applies. The offline equivalence extends to arbitrary nonnegative edge weights. We then design a posterior allocation policy for exponential scheduling and use the correspondence to transfer its optimal competitive guarantee to online matching. Additionally, we show that the optimal competitive ratio under an unknown arrival law is strictly lower than $1-e/e^e$, establishing a strict separation between the known and unknown arrival models.
View PDFOpen arXiv