Optimal Online Stochastic Matching

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Optimal Online Stochastic Matching

# 概要
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$,…

# 原典
https://arxiv.org/abs/2610.19866

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。