Source-linked AI summary
Online Stochastic Matching: Online Actions Based on Offline Statistics
Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi
TL;DR
The paper studies online stochastic matching with independently sampled ball types and known arrival distributions, seeking allocations to empty adjacent bins. It uses Monte Carlo statistics from the optimum offline solution to guide an adaptive online algorithm, achieving a 0.702 competitive ratio for arbitrary rates and 0.705 for integral rates, while proving a 0.823 hardness bound.
Problem
Online stochastic matching seeks to maximize allocations of independently sampled ball types to empty adjacent bins, while improving beyond 1 −1/e without assuming integral expected arrival rates.
Method
The algorithm estimates the optimum offline solution’s edge-allocation probabilities by Monte Carlo sampling and uses them to guide adaptive first- and second-choice bin assignments.
Results
The algorithm achieves a 0.702 competitive ratio for arbitrary rates and 0.705 for integral rates, while no online algorithm can exceed 0.823 on some known-distribution instances.
Takeaways & Limitations
The paper establishes improved stochastic matching guarantees beyond 1 −1/e in the general known-distribution model, together with a matching scope-defining hardness bound of 0.823.
Takeaways & Limitations
Computing the optimal allocation policy is NP-hard, and the paper leaves open whether a polynomial-time algorithm can surpass the best competitive ratio.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies online stochastic matching with known arrivals and presents an adaptive algorithm that improves on 1 −1/e beyond integral-rate assumptions, while establishing a 0.823 hardness bound.
- Problem and motivation: The known-distribution model samples ball types independently from a given distribution and matches each arrival to an adjacent empty bin.The objective is to maximize the expected number of non-empty bins after b arrivals.
- Contribution: The paper gives the first general stochastic algorithm improving the 1 −1/e competitive ratio without requiring every expected arrival rate to be integral.Earlier improvements applied under the i.i.d. model with integral arrival rates, an assumption described as somewhat unnatural in some distributions.
- Method: Monte Carlo estimates of the optimum offline allocation guide the online algorithm’s decisions through probabilities of assigning each ball type to each bin.These probabilities form a fractional matching used to construct the algorithm.
- Contribution: 0.702 is the competitive ratio achieved for arbitrary rates, while 0.705 is achieved in the i.i.d. integral-rate model.The adaptive algorithm selects first- and second-priority neighbor bins based on the current allocation state.
- Hardness: 0.823 is an upper bound on the competitive ratio of any deterministic or randomized online algorithm in the known-distribution model.Because the known-distribution model is a special case of the random permutation model, this also improves the corresponding hardness bound there.
2 Problem Definition
The problem is formalized on a bipartite graph with stochastic ball types and non-stochastic bins, and performance is compared with an offline maximum-matching benchmark summarized by a fractional matching.
- Problem definition: Each ball type y has rate r_y, and at each of b times an independently sampled ball is matched to at most one adjacent empty bin.The goal is to maximize the expected number of non-empty bins at time b.
- Assumptions: The analysis assumes the total rates sum to b and may split any type with rate greater than one into identical types with rates at most one.These are normalization and preprocessing assumptions used throughout the paper.
- Algorithm classes: Non-adaptive algorithms predetermine neighbor assignments by arrival number, whereas adaptive algorithms choose each assignment when the ball arrives.Adaptive choices can depend on which bins are currently occupied.
- Benchmark: For an arrival sequence, the offline benchmark is a maximum matching, and its used-edge indicator vector F(ω) records the selected optimal allocation.The competitive ratio compares the online algorithm’s expected allocation with E[OPT].
- Offline statistics: The fractional matching f assigns each edge the probability that the fixed optimum offline algorithm uses that edge over random arrival sequences.It is a convex combination of integral matchings and can be decomposed and sampled efficiently.
- Offline statistics: For edge e=(y,z), the offline-use probability satisfies f_e ≤ 1 − e^(-r_y) + o(1/b).The paper assumes b is sufficiently large so that the o(1/b) term is negligible, and estimates these quantities using Monte Carlo methods.
3 A Non-adaptive algorithm
For unit rates, the paper presents a simpler non-adaptive algorithm that samples two priority matchings from the optimum-induced distribution and uses them for first and second arrivals. Its analysis establishes a 0.684 approximation ratio.
- Setting: The unit-rate setting assumes r_y = 1 for every ball type and admits a simpler analysis than prior work.The section studies the special case analyzed by Feldman et al. and reports a slightly better competitive ratio.
- Algorithm: First arrivals use M1 and second arrivals use M2; balls are dropped when their corresponding bins are already full.The two matchings are used according to arrival count rather than adapting to the current bin allocation.
- Algorithm: The algorithm computes the fractional matching f and distribution μ, then independently samples two matchings M1 and M2 as priority matchings.M1 handles first arrivals of each type, while M2 handles second arrivals.
- Analysis: The analysis conditions on M1 and M2 and evaluates each bin through cases determined by whether it is saturated in either matching and whether both matchings assign it the same type.If M1(z) = M2(z), the bin is effectively available only for the first arrived ball.
- Guarantee: 0.684 is the approximation ratio proved for Algorithm 1 relative to the optimum offline solution when all rates are 1.The proof lower-bounds the per-bin expression and identifies its minimum value as 0.684.
4 The Adaptive Algorithm
The adaptive algorithm uses Monte Carlo-derived fractional matching statistics and two carefully coupled priority-bin choices to allocate arriving balls adaptively. It achieves a competitive ratio of 0.702 for arbitrary rates and 0.705 when rates are integral.
- Motivation: Non-adaptive algorithms cannot beat 1 −1/e when sampling rates are not necessarily integral, motivating the adaptive design.For small rates, receiving a second ball of the same type can become arbitrarily unlikely, bringing non-adaptive performance close to 1 −1/e.
- Online phase: Each arriving ball is matched to its first sampled neighboring bin when empty, and otherwise the algorithm tries the second sampled bin.The adaptive procedure bases each allocation on the current occupancy of bins.
- Algorithm: Two partitions, Iy and Jy, define first- and second-priority bins for each ball type, with Jy shifted to minimize overlap.A uniformly sampled x determines z1,y(x) from Iy and z2,y(x) from Jy; minimized overlap maximizes the chance of trying a different second bin.
- Guarantees: 0.702 is the competitive ratio guaranteed by Algorithm 2 for arbitrary graphs and arbitrary stochastic-node rates.The analysis handles dependencies introduced by adaptivity through first- and second-priority events and occupancy at distance two.
- Guarantees: 0.705 is the competitive ratio guaranteed when all stochastic-node sampling rates are integral.The stronger bound follows from an improved lower bound on the second-priority quantity qz under integral rates.
5 Upper Bounds for Online Algorithms
This section establishes upper bounds for non-adaptive and general online algorithms through instances with small, integral, and arbitrary arrival rates. The bounds range from 1−1/e for non-adaptive algorithms to 0.823 for all online algorithms.
- Small rates: 1−e^-1 is an upper bound for non-adaptive randomized algorithms when arrival rates are arbitrarily small.Proposition 5.1 gives an instance with rates r_y=o(1) where no non-adaptive randomized algorithm exceeds this ratio.
- Integral rates: 1−e^-2 ≃ 0.86 is an upper bound for every online algorithm when rates are integral.The construction combines a perfect matching between Y1 and Z with a complete bipartite graph between Y2 and Z.
- Integral rates: The integral-rate construction leaves an expected fraction of bins empty after matching Y1, while Y2 balls can use the remaining bins.With probability e^-1, a Y1 type does not arrive; the Y2 arrivals have expected number n/e and can match the corresponding empty bins offline.
- Arbitrary rates: The arbitrary-rate hardness construction uses matching thresholds from irregular cuckoo hashing to show that the offline optimum can match all balls with high probability.The analysis uses the threshold c*2.5 ≃ 0.81034 for a mixture of two- and three-choice types.
- Arbitrary rates: 0.823 is an upper bound on the competitive ratio of any deterministic or randomized online algorithm under arbitrary rates.The hard instance combines Y2, Y3, and Yn types, with Yn adjacent to every bin; numerical analysis gives E[|Ψ(n)|] ≤ 0.823n for n > 1000.
6 Discussion
The paper notes that competitive analysis is not necessarily the most suitable approach because the known input distribution permits optimal-policy computation by dynamic programming, but that approach is computationally expensive.
- Dynamic programming or future-event enumeration can derive the optimal allocation policy when the input distribution is known.The paper states that this approach takes exponential time and that computing the optimal allocation policy is NP-hard.
- It remains open whether a polynomial-time algorithm can achieve a guarantee better than the best possible competitive ratio or the paper’s ratio.