Stochastic Online Correlated Selection

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.