Online Contention Resolution Schemes

1 Introduction

• OCRSs overcome the ordering limits of earlier rounding approaches, handle adversarially presented information, and yield a matroid constrained oblivious posted-pricing mechanism and an O(1)-competitive algorithm for weighted probing with deadlines.The paper also states that its approach gives optimal guarantees up to moderate constant factors for a class of online submodular maximization problems.Source: §1 · p. 2

1.1 Online contention resolution schemes

• Greedy OCRSs use c-selectability to ensure an element remains selectable with probability at least c regardless of prior selections, giving guarantees even against an almighty adversary.The paper reports that Ω(1)-selectable greedy OCRSs exist for many natural constraints.Source: §1.1 · p. 4

1.2 Our results

• The results provide constant-selectability greedy OCRSs for matroid, matching, and knapsack relaxations, and combine schemes for intersections with selectability c1 · c2.The matroid scheme is deterministic, while the matching and knapsack schemes are randomized; the paper rules out deterministic greedy OCRSs for its natural knapsack relaxation at any constant parameters.Source: §1.2 · p. 5
• For x ∈ bP, a (b, c)-selectable greedy OCRS obtains expected value at least c · F(x) for monotone submodular objectives and c/4 · F(x) for non-monotone objectives.For the stated class of OCRSs formed by combining Theorem 1.8 schemes, an OCRS achieves c · F(x) against an online adversary for nonnegative submodular objectives, but it is not efficient as stated.Source: §1.2 · p. 6

1.3 Applications

• The paper reduces three previously studied online applications to finding appropriate OCRSs, using a common framework to clarify their connections.The introduction identifies posted pricing, prophet inequalities, and probing models among the settings motivating the framework.Source: §1 · p. 2, §1.3 · p. 6

Prophet inequalities for Bayesian online selection problems

• A c-selectable greedy OCRS yields a Bayesian online selection algorithm for a down-closed feasible family against an almighty adversary.The theorem states that the algorithm returns a feasible set; the supplied passage cuts off before specifying its guarantee.Source: Prophet inequalities for Bayesian… · p. 7
• Θ(1)-factor prophet inequalities hold against an almighty adversary when constraints intersect a constant number of matroid, knapsack, and matching constraints.The results also give an e(p+1)-factor inequality for the intersection of p matroids and a better constant than Kleinberg and Weinberg’s for p ≥ 4, even against a stronger adversary.Source: Prophet inequalities for Bayesian… · pp. 7–8

Oblivious posted pricing mechanisms

• A c-selectable greedy OCRS for a relaxation of a down-closed feasibility family yields a COPM at most a factor c worse than the optimal truthful mechanism, even against an almighty adversary.This resolves the open question of constant-gap COPMs for general matroids and extends constant-gap results to more general constraint families.Source: Oblivious posted pricing mechanisms · pp. 8–9
• A posted price mechanism for BMUMD has constant optimality gap when feasibility is the intersection of a constant number of matroid, knapsack, and matching constraints.The result follows using the reduction from multi-parameter to single-parameter settings.Source: Oblivious posted pricing mechanisms · p. 9

Stochastic probing

• A (b · cin · cout)-approximation for weighted stochastic probing is achievable when an almighty adversary chooses the probing order and both inner and outer constraints have the stated greedy OCRSs.If the OCRSs are efficient and their relaxations have separation oracles, the algorithm runs in polynomial time.Source: Stochastic probing · p. 9
• A (b(1 −b) · cin · cout)-approximation for weighted stochastic probing with deadlines is achievable for down-closed inner and outer constraints.This addresses the open question of weighted probing with deadlines; polynomial time follows when the OCRSs are efficient and the relaxations have separation oracles.Source: Stochastic probing · pp. 9–10
• A ((1 −e−b −o(1)) · cin · cout)-approximation for submodular stochastic probing holds under an almighty adversary’s probing order and down-closed inner and outer constraints.The result extends to substantially more general settings than the cited matroid-intersection guarantee; polynomial time follows under the stated OCRS efficiency and separation-oracle conditions.Source: Stochastic probing · p. 10

2.1 OCRS for matroids

• For b ∈ [0,1], there exists a (b, 1−b)-selectable deterministic greedy OCRS for any matroid polytope; for k matroid polytopes on a common ground set, there exists a (b, (1−b)k)-selectable deterministic greedy OCRS for their intersection.Source: §2.1 · p. 10

2.1.1 Proof of termination of chain construction

• The matroid chain construction terminates because its first refined set is a strict subset of every nonempty ground set.The proof bounds the weighted probability of being spanned by b · (x(N) + (1 − b) rank(S)), strictly when S is nonempty.Source: §2.1.1 · p. 12

Efficient implementation

• Monte Carlo estimates yield a randomized matroid-chain construction that, with probability at least 1 − |N|^-α, gives a (b, 1 − b − ε)-selectable greedy OCRS.Its running time is O(α · ε^-2 · poly(|N|) · T), where T is the time for one matroid independence-oracle call.Source: Efficient implementation · p. 13

2.2 OCRSs for matchings in general graphs

• For matching relaxations in general graphs, a randomized greedy OCRS is (b, e^-2b)-selectable; setting its potential-edge set to all edges gives a deterministic (b, (1 − b)^2)-selectable OCRS.The relaxation is weaker than the matching polytope, so the result also applies to the matching polytope.Source: §2.2 · pp. 14–15

2.3 OCRSs for knapsack constraint

• For every n, some knapsack constraint rules out deterministic greedy OCRSs with selectability c > (1 − b)^(n−1), while the section presents a randomized greedy OCRS for any single-knapsack polytope.The randomized construction separates elements larger than 1/2 from smaller elements and chooses which group to accept greedily.Source: §2.3 · pp. 15–16

2.4 Combining constraints

• Greedy OCRSs for different polytopes can be combined to form a greedy OCRS for their intersection.The section identifies this as Theorem 1.9 and states it is proved in Section 2.4.Source: §2 · p. 10, §2.4 · p. 16
• For each input x, the combined OCRS uses the intersection of the two schemes’ down-closed families.The combined family is Fπ,x = Fπ1,x ∩ Fπ2,x.Source: §2.4 · p. 16
• Combining (b, c1)- and (b, c2)-selectable greedy OCRSs yields a (b, c1 · c2)-selectable greedy OCRS.This is Lemma 2.11.Source: §2.4 · p. 16
• The proof obtains the product bound by applying the FKG inequality to the two monotone events for the intersected families.The argument uses each scheme’s selectability bound and monotonicity of the events.Source: §2.4 · p. 17

3 From Selectability to Approximation

• A (b, c)-selectable greedy OCRS on x ∈ bP yields E[f(S)] ≥ c·F(x) for monotone f, and E[f(S(1/2))] ≥ (c/4)·F(x) for non-monotone f.For the non-monotone guarantee, the random decisions used to calculate S(1/2) are part of the algorithm and known to the almighty adversary.Source: §3 · pp. 17, 19
• The characteristic CRS retains elements feasible alongside every feasible subset of A, and is a monotone (b, c)-balanced CRS whose output is contained in the greedy OCRS output.Source: §3 · pp. 17–18
• For non-negative submodular f, an element-monotone (b, c)-selectable OCRS yields an OCRS guaranteeing E[f(S)] ≥ c·F(x) for every online adversary and x ∈ bP.The paper states that greedy OCRSs for specific polytopes can be converted to element-monotone OCRSs with the same selectability guarantee; the matroid greedy OCRS already has this property.Source: §3 · pp. 19–20
• For reducible x, there exists a non-reducible x′ ≤ x with F(x′) ≥ F(x).The paper notes that sampling can find a non-reducible vector in polynomial time with value at least F(x) − |N|^-d · max{f({e}) | x_e > 0}, for every constant d > 0.Source: §3 · p. 20
• The online-adversary construction tests each active element using earlier revealed active elements and an independent sample for unrevealed elements, and always returns a feasible set.It accepts e when the resulting set belongs to e’s down-closed family F_e.Source: §3 · p. 20

• Selectability gives Pr[R(x) \ {e} ∈ F_e] ≥ c for every element, and non-reducibility ensures relevant marginal values are nonnegative.Source: §3 · p. 23
• Submodularity and Lemma 3.14 bound each element’s contribution using the probability that the other active elements belong to F_e.Source: §3 · p. 23
• c·F(x) + (1 − c)f(∅) ≥ c·F(x) is the lower bound established in the proof.Source: §3 · p. 23

Proof of Theorem 1.12

• For Bayesian online selection, a relaxation based on each element’s highest xe-fraction of values upper-bounds the prophet, and a c-selectable OCRS achieves at least c times its value.The OCRS uses only whether an element is active, not its precise value, preserving the conditional value of selected elements.Source: Proof of Theorem 1.12 · pp. 24–25

Proof of Theorem 1.15

• A c-selectable OCRS yields a COPM with expected revenue at least c times the relaxed revenue, using independent two-price offers with acceptance probabilities xe.If the relaxation is only α-approximate, the COPM is at most a factor α · c worse than Myerson’s mechanism.Source: Proof of Theorem 1.15 · pp. 25–26

Extension to other objectives

• The posted-price argument extends unchanged to decomposable agentwise objectives, including revenue, welfare, and surplus, with a c-factor guarantee.These objectives use ge(Ze, pe) equal to pe, Ze, and Ze − pe, respectively; Yan [24] highlighted the relaxation’s broader applicability.Source: Extension to other objectives · p. 26

4.3 Stochastic probing

• For weighted stochastic probing, relaxation (R1) upper-bounds optimal expected weight, and the proof’s algorithm targets b(cin * cout) times the relaxation optimum using inner and outer OCRSs.The resulting CRS is monotone and (p ◦ (bx*), cin · cout)-balanced; Algorithm 1’s selected set is contained in the intersection of the inner and outer CRSs and the algorithm is legal.Source: §4.3 · pp. 26–28
• E[w(S)] ≥ b(cin · cout) · w(p ◦ x*) for the weighted stochastic probing output.The bound follows because the rounded set is contained in the feasible output set and weights are non-negative.Source: §4.3 · pp. 28–29
• b(1−b)·cin·cout is the approximation ratio for probing with deadlines, compared with the best algorithm subject to the same deadlines.The guarantee holds regardless of the order in which the algorithm can probe; probing in increasing deadline order ensures deadline feasibility.Source: §4.3 · p. 29
• The optimal value of relaxation (R2), using f+, upper-bounds the optimal algorithm’s expected performance for submodular stochastic probing.The f+ extension captures distributions with element marginals at most x, accommodating dependencies caused by adaptive probing.Source: §4.3 · p. 30
• E[f(S)] ≥ (cin · cout) · F(p ◦ x̃) for the output of modified Algorithm 1.The algorithm replaces bx* with x̃, and its analysis applies the CRS guarantees to the resulting rounded set.Source: §4.3 · p. 30

A Definitions of Matroidal Concepts

• A matroid has a finite ground set and a nonempty family of independent sets satisfying the augmentation property.If independent sets I and J have |I| > |J|, some element of I \ J can be added to J while preserving independence.Source: A Definitions of Matroidal Concepts · p. 32
• The rank of a set is the size of its largest independent subset; a base is independent and has size equal to the matroid's rank.An independent set's rank equals its size.Source: A Definitions of Matroidal Concepts · p. 32
• An element is spanned by a set when adding it does not increase the set's rank; the span collects all such elements.Source: A Definitions of Matroidal Concepts · p. 32
• Restriction keeps only a subset of the ground set, while contraction removes it and tests independence by adding a base of that subset.The contraction definition is independent of which base is chosen.Source: A Definitions of Matroidal Concepts · pp. 32–33