Stochastic Online Correlated Selection
Ziyun Chen, Zhiyi Huang, Enze Sun
Abstract
We initiate the study of Stochastic Online Correlated Selection (SOCS), a family of online rounding algorithms for the general Non-IID model of Stochastic Online Submodular Welfare Maximization and its special cases such as unweighted and vertex-weighted Online Stochastic Matching, Stochastic AdWords, and Stochastic Display Ads. At each time step, the algorithm sees the type of an online item and a fractional allocation of the item, then immediately allocates the item to an agent. We propose a metric called the convergence rate that measures the quality of SOCS algorithms in the above special cases. This is cleaner than most metrics in the related Online Correlated Selection (OCS) literature and may be of independent interest.
We propose a Type Decomposition framework that reduces the design of SOCS algorithms to the easier special case of two-way SOCS. First, we sample a surrogate type whose fractional allocation is half-integer. The rounding is trivial for a one-way surrogate type fully allocated to one agent. For a two-way surrogate type split equally between two agents, we round it using a two-way SOCS. We design the distribution of surrogate types to get two-way types as often as possible, while respecting the original fractional allocation in expectation.
Following this framework, we make progress on numerous problems including two open questions related to AdWords:
• Online Stochastic Matching: We improve the state-of-the-art 0.666 competitive ratio for unweighted and vertex-weighted matching by Tang, Wu, and Wu (STOC 2022) to 0.69.
• Query-Commit Matching: We further enhance the above competitive ratio to 0.705 in the random-order relaxation. Using a known reduction, we get that same ratio in the Query-Commit model. This result improves the best previous ratios 0.696 for unweighted matching by Mahdian and Yan (STOC 2011) and 0.662 for vertex-weighted matching by Jin and Williamson (WINE 2021).
• Stochastic AdWords: We give a 0.6338 competitive algorithm for Stochastic AdWords, breaking the 1 -1 e barrier for the first time. This answers a decade-old open question from the survey by Mehta (2013) about breaking this barrier in the IID special case.
• AdWords: The framework of Type Decomposition can also be applied to the adversarial model if the two-way rounding algorithm is oblivious to the distribution of future items.
From the two-way algorithm's viewpoint, the fixed adversarial sequence of items is a non-IID distribution that is a point mass, and the stochasticity comes from sampling surrogate types. Following this framework, we get the first multi-way OCS for AdWords, addressing an open question in the OCS literature. This further leads to a 0.504 competitive ratio for AdWords, improving the previous 0.501 ratio by Huang, Zhang, and Zhang (FOCS 2020).
• Stochastic Display Ads: We design a 0.644 competitive online algorithm for Stochastic Display Ads, breaking the 1 -1 e barrier for the first time.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- The power of multiple choices in online stochastic matching cites Online stochastic matching, poisson arrivals, and the natural linear program
- The power of multiple choices in online stochastic matching cites Multiway Online Correlated Selection
- The power of multiple choices in online stochastic matching cites Edge-Weighted Online Bipartite Matching
- The power of multiple choices in online stochastic matching cites AdWords in a Panorama
- Online stochastic matching, poisson arrivals, and the natural linear program cites Edge-Weighted Online Bipartite Matching
- Online stochastic matching, poisson arrivals, and the natural linear program cites AdWords in a Panorama
- Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum cites The power of multiple choices in online stochastic matching
- Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum cites Online stochastic matching, poisson arrivals, and the natural linear program
- Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum cites Multiway Online Correlated Selection
- Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum cites Edge-Weighted Online Bipartite Matching
- Multiway Online Correlated Selection cites Edge-Weighted Online Bipartite Matching
- AdWords in a Panorama cites Edge-Weighted Online Bipartite Matching
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models cites Edge-Weighted Online Bipartite Matching
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models cites AdWords in a Panorama
- Optimal Rounding for Two-Stage Bipartite Matching cites The power of multiple choices in online stochastic matching
- Optimal Rounding for Two-Stage Bipartite Matching cites Online stochastic matching, poisson arrivals, and the natural linear program
- Optimal Rounding for Two-Stage Bipartite Matching cites Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum
- Optimal Rounding for Two-Stage Bipartite Matching cites Multiway Online Correlated Selection
- Optimal Rounding for Two-Stage Bipartite Matching cites Edge-Weighted Online Bipartite Matching
- Edge-weighted Matching in the Dark cites Multiway Online Correlated Selection
- Edge-weighted Matching in the Dark cites Edge-Weighted Online Bipartite Matching
Cited by top-tier papers4
- Edge-weighted Matching in the DarkZhiyi Huang, Enze Sun, Xiaowei Wu, Jiahao ZhaoFOCS 2025 · 5 citations
- Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online OptimumEnze Sun, Zhihao Gavin Tang, Yifan WangSTOC 2025 · 1 citation
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion ModelsBoyu Zhang, Aocheng Shen, Bing Liu, Qiankun Zhang et al.ICML 2025
- Optimal Rounding for Two-Stage Bipartite MatchingTristan Pollner, Amin Saberi, Anders WikumSODA 2026
Builds on8
- AdWords in a PanoramaZhiyi Huang, Qiankun Zhang, Yuhao ZhangFOCS 2020 · 38 citations
- Edge-Weighted Online Bipartite MatchingMatthew Fahrbach, Zhiyi Huang, Runzhou Tao, Morteza ZadimoghaddamFOCS 2020 · 33 citations
- Online stochastic matching, poisson arrivals, and the natural linear programZhiyi Huang, Xinkai ShuSTOC 2021 · 22 citations
- The power of multiple choices in online stochastic matchingZhiyi Huang, Xinkai Shu, Shuyi YanSTOC 2022 · 20 citations
- Multiway Online Correlated SelectionGuy Blanc, Moses CharikarFOCS 2021 · 16 citations
Related papers
- (Fractional) online stochastic matching via fine-grained offline statisticsZhihao Gavin Tang, Jinzhao Wu, Hongxun WuSTOC 2022 · 9 citations
- Improved Online Correlated SelectionRuiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie et al.FOCS 2021 · 12 citations
- Edge-weighted Online Stochastic Matching: BeatingShuyi YanSODA 2024 · 7 citations
- Fully Online Matching with Stochastic Arrivals and DeparturesZihao Li, Hao Wang, Zhenzhen YanAAAI 2023 · 4 citations
- Class Fairness in Online MatchingHadi Hosseini, Zhiyi Huang, Ayumi Igarashi, Nisarg ShahAAAI 2023 · 21 citations
