Source-linked AI summary
Online Stochastic Matching: Beating 1-1/e
Jon Feldman, Aranyak Mehta, Vahab Mirrokni, S. Muthukrishnan
TL;DR
The paper asks whether online stochastic bipartite matching can beat the 1−1/e bound. It uses two disjoint offline solutions to guide online assignments and shows that this approach beats 1−1/e, while the analysis is tight for a family of instances.
Problem
The paper asks whether online stochastic bipartite matching can beat the 1−1/e bound, motivated by display-ad allocation.
Method
The algorithm computes two disjoint offline solutions through boosted max flow and uses them in preference order for online assignments.
Results
The approach beats 1−1/e; the two suggested matchings analysis is tight on a family of instances.
Takeaways & Limitations
The paper adapts the power-of-two-choices idea to stochastic bipartite matching by combining offline guidance with online assignment.
Takeaways & Limitations
The two suggested matchings analysis is tight on a family of instances, and the display-ad model omits richer objectives such as maximizing contract value.
Abstract
from arXiv · showhide
We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of $1-1/e$. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the $1 - 1/e$ bound. Our main result is a 0.67-approximation online algorithm for stochastic bipartite matching, breaking this $1 - {1/e}$ barrier. Furthermore, we show that no online algorithm can produce a $1-ε$ approximation for an arbitrarily small $ε$ for this problem. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-)matchings. These two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution.
1 Introduction
The paper asks whether online stochastic bipartite matching can beat the 1−1/e guarantee, using display-ad allocation as motivation. It proposes two offline-guided solutions for online assignment and establishes both improved and limiting results.
- Problem setting: Advertisers are fixed and known, while impressions arrive online and must be assigned immediately without reusing endpoints.The model is an online bipartite matching problem motivated by allocating display advertisements.
- Prior guarantees: 1−1/e is optimal in the adversarial model, and greedy achieves the same ratio in the iid stochastic model, where no better guarantee was known.The iid model draws impressions repeatedly from a known distribution.
- Research question: The paper asks whether the 1−1/e bound can be beaten for online stochastic bipartite matching.This is stated as the main question addressed by the paper.
- Initial approach: The initial strategy computes a maximum matching in the expected graph and restricts online choices to it, but achieves exactly 1−1/e.The analysis is tight for this first offline-guided attempt.
- Main technique: The main algorithm computes two disjoint offline solutions, tries the first for each request, and uses the second if the first assignment fails.A boosted max-flow graph is decomposed into two edge-disjoint near-matchings, which also guide the optimum upper-bound analysis.
- Main technique: The two-solution idea adapts power of two choices from load balancing by replacing random choices with deterministic choices computed offline.The paper identifies this as a novel adaptation to stochastic bipartite matching.
2 Preliminaries
The preliminaries formalize iid arrivals, realized scenarios, approximation-factor notions, and concentration tools used for the stochastic matching analysis.
- Model: An instance consists of a bipartite graph, an impression distribution D, and n iid arrivals, with each advertiser assignable at most once.The distribution is defined by expected impression counts as Pr[i] = e_i/n.
- Model: Advertiser capacities can be generalized beyond one by replacing an advertiser with multiple copies.The paper states that all results extend to capacity c_a.
- Model: A realized scenario contains the arriving impression copies, and its realization graph connects each copy to the advertisers adjacent to its type.This graph is denoted by the realization graph.
- Approximation notions: The framework distinguishes high-probability, expectation-ratio, and expected-approximation-factor guarantees.A high-probability factor implies an expected approximation factor of at least α−o(1).
- Probabilistic tools: The analysis uses balls-in-bins expectations and Azuma’s inequality through appropriately defined Doob martingales for concentration.Two stated facts concern occupied bins and satisfied ordered bin sequences.
3 Hardness
The section shows that online stochastic matching has an approximation barrier strictly below 1, using a 6-cycle instance and an extension to growing instances.
- Hardness statement: Every randomized online algorithm has an expected approximation factor bounded strictly away from 1.
- Single-instance hardness: 26/27 is an upper bound on the expected approximation factor for every randomized algorithm on the specified 6-cycle instance.The limiting arrival pattern (x, y, y) occurs with probability 1/9 and yields approximation 2/3, while other scenarios contribute at most 1.
- Single-instance hardness: The 6-cycle uses three advertisers, three impression types, and six alternating advertiser–impression edges under a uniform arrival distribution.
- Asymptotic hardness: The hardness result is obtained by constructing instances containing many copies of the 6-cycle.
- Asymptotic hardness: A family of instances with n →∞ admits no online algorithm achieving a 1−o(1) expected approximation.
4 Offline Algorithms for Online Matching
The section develops offline-guided online matching algorithms for the iid model, first using one expected-instance matching and then two disjoint near-matchings. The two-matching approach beats the 1−1/e barrier, with its analysis shown tight on an instance family.
- Suggested Matching: The suggested algorithm computes a maximum matching in the expected arrival graph and restricts online assignments to its edges.Its performance analysis uses a max-flow formulation and a guided min-cut to bound the realized optimum.
- Suggested Matching: 1−1/e is the tight approximation factor for the single suggested-matching algorithm, even in expectation.A complete bipartite instance has optimum n while the algorithm matches each advertiser with probability at least 1−1/e.
- Two Suggested Matchings: The improved algorithm uses two disjoint near-matchings, trying the first assignment and then the second when the first fails.The matchings are obtained by boosting flow capacities and decomposing the resulting flow into disjoint solutions.
- Tightness: The analysis is tight: a family of instances gives the two suggested matchings algorithm expected approximation factor at most α + ǫ.The section also assumes e_i = 1 before extending to integer e_i by reduction.
5 Concluding Remarks
The paper discusses practical extensions of its two-matching approach, including broader objectives and k matchings, while identifying open problems for k=3 and fractional arrival rates.
- Applying the algorithm to display ads: The two-matching approach may help display-ad allocation because offline guiding solutions can be computed before rapid online assignment.The approach may also model objectives such as fairness when those objectives are tractable offline.
- Generalizing the algorithm: A k-matching algorithm would compute k edge-disjoint matchings and use them online in a prescribed order.If the expected graph admits k edge-disjoint perfect matchings, the paper states an approximation factor of 1 − 2
- Generalizing the algorithm: For k=3, the authors do not know how to generalize the result to general graphs, leaving the achieved constant c(k) open between .67 and .99.The passage reports ≃0.75 for k=2 and k=3 respectively, but the available text does not preserve the full displayed expression.
- Fractional version: For fractional arrival rates, the suggested-matching analysis generalizes, but the two-suggested-matchings analysis remains unresolved.The stated obstacle is the lack of an integral-style decomposition into two edge-disjoint large-value flows.
A Balls in Bins
This section develops concentration facts for balls-and-bins variables used in the paper, including occupied bins and satisfied bin sequences.
- Fact 1: Fact 1 bounds the number of bins in a chosen subset B that receive at least one ball when n balls are uniformly placed into n bins.The bound holds with probability at least 1 − 2e^−εn/2 for any ε > 0.
- Fact 2: Fact 2 defines a bin sequence as satisfied when an outside-R bin is occupied or an R-bin receives at least two balls.The sequences have size c, and each bin belongs to at most d sequences.
- Proof technique: The concentration arguments use bounded differences: moving one ball changes the occupied-bin or sequence-count variable by at most a bounded amount.The paper applies Azuma’s inequality to the associated Doob martingale.
B Details of the proof for Hardness Result
The hardness proof analyzes many independent 6-cycles under uniform stochastic arrivals and bounds the performance ratio by considering how many impressions each cycle receives.
- Hard instance: The hard instance consists of k copies of 6-cycles, with uniform arrivals over impressions and n=3k.The proof tracks the fractions of cycles receiving 1, 2, 3, or more than 3 impressions.
- Cycle cases: For cycles receiving 1 or 2 impressions, the analysis assumes ALG and OPT match 1 or 2 ads, respectively.For cycles receiving more than 3 impressions, both algorithms are assumed to achieve 3 matches to maximize their ratio contribution.
- Cycle cases: When exactly 3 impressions arrive, the case with two additional y impressions allows ALG at most two matches while OPT matches three.Other arrival patterns are treated as giving both algorithms three matches.
- Conclusion: The resulting high-probability bound establishes the stated hardness theorem.The section concludes by explicitly identifying the argument as a proof of Theorem 3.
C Non-integral Impression Arrival Rates
For non-integral impression arrival rates, the suggested-matching analysis extends through fractional flows, but the two-matching analysis does not yet extend because the needed decomposition is unavailable.
- Fractional version: The suggested-matching algorithm generalizes to rational arrival rates by computing a maximum flow and assigning each arriving impression probabilistically according to fractional flow values.The reported high-probability value is P_a∈A(1 − e^−F_a).
- Fractional version: The optimum is bounded by P_a∈A F_a with high probability, so the approximation factor is the ratio of these two expressions.The flow assigns total fraction F_a to advertiser a.
- Fractional analysis: The resulting mathematical program minimizes the ratio over values satisfying 0 ≤ F_a ≤ 1.The analysis orders the vector of F-values nonincreasingly and uses majorization.
- Fractional analysis: The fractional suggested-matching approximation factor is 1 − 1/e.The analysis identifies the minimum at the uniform vector and concludes this factor explicitly.
- Limitation: The TSM algorithm remains open for non-integer arrival rates because the required two-edge-disjoint-flow decomposition is unavailable in the non-integral case.The authors leave this generalization as an open question.
D Frequency Capping
The paper extends online stochastic matching to frequency-capped advertising, modeling impressions by advertiser–user pairs and incorporating per-user caps. The suggested matching algorithm retains its approximation guarantee, while generalizing TSM is more challenging.
- Model: Frequency caps limit how often an advertiser’s ad is shown to the same user, treating each impression as an advertiser–user pair.The model includes expected impression counts, advertiser impression totals, and a constant per-user cap.
- Suggested matching algorithm: The suggested matching algorithm adds advertiser–user nodes to the max-flow graph, with capacity c on advertiser-to-pair edges.The extension sets the advertiser-to-user-pair layer capacity to the per-user cap.
- Guarantee: The extended algorithm matches approximately F(1−1/e) impressions, while a min-cut argument bounds OPT by F with high probability.Here, F denotes the value of the flow.
- TSM extension: TSM does not generalize straightforwardly because capacities 2d_a and 2 can spread flow across more than d_a middle-layer nodes.This prevents the direct capacity-setting approach from working as desired.