Pith. sign in

REVIEW 2 major objections 4 minor 24 references

Universal Online Contention Resolution with Preselected Order

T0 review · 2 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that preselected arrival orders admit universal online contention resolution with near-optimal balance for every matroid and correlated prior.

desk verdict First efficient universal OCRS for preselected order, with a clean LP reduction to matroid secretary; one local gap in the approximate-LP proofs is easily repairable. read the letter →

arxiv 2504.16327 v1 pith:KOTAW5K5 submitted 2025-04-23 cs.DS cs.GT

Junyao Zhao This is my paper · ORCID
classification cs.DScs.GT MSC 05B3568W2790C05
keywords onlinecontentionresolutionschemesuniversalOCRSmatroidsecretaryproblempreselectedordercorrelateddistributionslinearprogrammingellipsoidmethodmatroids
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper aims to show that universal online contention resolution—the setting in which a matroid and an arbitrarily correlated prior distribution are known, and active elements arrive online—becomes tractable when the algorithm may preselect the arrival order. The main claim is that for every $\alpha,\varepsilon\in(0,1]$ there is a computationally efficient scheme that is $(\alpha,(1-\varepsilon)\alpha)$-universal, meaning every element is kept with probability at least $(1-\varepsilon)\alpha$ whenever it is active, for any matroid and any $\alpha$-uncontentious distribution. A second claim goes further: from any $c$-competitive matroid secretary algorithm, one can efficiently construct a universal OCRS with balance $(1-\varepsilon)c\alpha$ in the same arrival model, turning a previously information-theoretic reduction into an algorithmic one. If the arguments hold, universal contention resolution inherits the efficiency of matroid secretary algorithms, and the preselected-order model becomes the natural intermediate ground for correlated priors.

What carries the argument

The load-bearing object is a linear program over permutations $\pi$: each variable $\lambda_\pi$ is the probability of preselecting greedy order $\pi$, and each constraint asks that element $i$'s selection probability conditioned on activity reach $\beta$. The dual has one constraint per permutation, but the separation oracle only needs the permutation $\pi_\mu$ that orders elements by decreasing dual weight $\mu_i$; matroid greedy optimality makes that permutation dominate all others, and $\alpha$-uncontentiousness bounds the dual optimum below by $\alpha$. For the secretary reduction, the same LP is formed over a grid of discretized weight vectors, each giving rise to an OCRS that feeds those weights to the secretary algorithm and copies its selections; a discretization step and estimated coefficients account for the $(1-\varepsilon)$ loss.

What would settle it

On the two-element matroid with distribution $\Pr[A=\{1,2\}]=\Pr[A=\emptyset]=1/2$ and $\alpha=1/2$, solve the permutation LP (17): the paper's Lemma 5.3 predicts optimal value exactly $1/2$, and any computed optimum below that would refute the duality argument. For Theorem 6.3, exhibit any matroid, $\alpha$-uncontentious distribution, arrival model, and $c$-competitive secretary algorithm for which the constructed mixture selects some active element with probability below $(1-\varepsilon)c\alpha$.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that a universal OCRS can be computed offline by solving a linear program whose variables are permutations. For any matroid $M$ and any $\alpha$-uncontentious distribution $D_A$, the LP over distributions of greedy ordered OCRSs has optimum at least $\alpha$; the proof passes through the dual, where the only separating permutation that needs to be checked is the one sorted by decreasing dual weights, because the greedy matroid algorithm realizes the weighted rank. Solving this LP with the ellipsoid method and Monte-Carlo estimates yields an $(\alpha,(1-\varepsilon)\alpha)$-universal scheme with preselected order. The same LP idea, run over a discretized grid of weight vectors and using any $c$-competitive matroid secretary algorithm as a subroutine, produces an $(\alpha,(1-\varepsilon)c\alpha)$-universal OCRS in any arrival model.

Load-bearing premise

The load-bearing assumption is the imported lemma that a $c$-competitive matroid secretary algorithm, which learns weights one by one and must pick an independent set online, still guarantees expected selected weight at least $c\alpha$ times the total expected active weight when it is embedded into an OCRS by showing zero weights for inactive elements; if that lemma fails in some arrival model, the efficient secretary-to-OCRS reduction collapses.

Editorial extensions

If this is right

  • In the preselected-order model, universal OCRSs exist with balance $(1-\varepsilon)\alpha$ for every matroid and correlated prior; since no scheme can do better than balance $\alpha$, the guarantee is near-optimal up to the computational loss.
  • Any efficient $c$-competitive matroid secretary algorithm in any arrival model automatically gives an efficient $(\alpha,(1-\varepsilon)c\alpha)$-universal OCRS in that model, resolving the open algorithmic question about the secretary-to-OCRS conversion.
  • The schemes handle deliberately correlated priors, not only product distributions; the price for correlation is the assumption of $\alpha$-uncontentiousness and a running time that depends on $1/p_{\min}$, the smallest active probability.
  • The simpler subsampling algorithms give universal OCRSs with guarantees $\alpha^2/4$ and $\alpha^2/2$, and the paper proves these bounds are essentially tight for those algorithms, so they trade the optimal constant for transparency.
  • In the random-order model, where universal OCRS and matroid secretary are already known to be equivalent, the new reduction supplies the efficient direction: a constant-competitive secretary algorithm there would yield an efficient universal OCRS.
  • If the arguments hold, universal contention resolution becomes a linear-programming problem in the preselected-order model: choose a small mixture of greedy orders, then run it online without further adaptivity.
  • Because the secretary-to-OCRS conversion is black-box, any future constant-competitive matroid secretary algorithm, or any improvement in its running time, flows directly into universal OCRS; in the random-order model this also sharpens the known equivalence with the matroid secretary conjecture.
  • The running time dependence on $1/p_{\min}$ matches the paper's own example showing that algorithms with only sample access must pay that cost, suggesting the LP/ellipsoid scheme is near the sample-complexity limit rather than merely loose.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The permutation-LP view suggests a recipe for other online selection problems: precompute a small mixture of greedy policies through the dual, rather than adapting orders online; the matroid greedy optimality that makes the separation oracle single-permutation would need to be replaced by whatever dominance structure the new constraint system has.
  • Because the secretary-to-OCRS conversion is black-box, any future constant-competitive matroid secretary algorithm, or any improvement in its running time, flows directly into universal OCRS; in the random-order model this also sharpens the known equivalence with the matroid secretary conjecture.
  • The running time dependence on $1/p_{\min}$ matches the paper's own example showing that algorithms with only sample access must pay that cost, suggesting the LP/ellipsoid scheme is near the sample-complexity limit rather than merely loose.
  • A testable extension is to instantiate the reduction with the known constant-competitive free-order matroid secretary algorithm; this would yield the first computationally efficient universal OCRS for free-order arrivals, a model previously handled only by a non-efficient information-theoretic argument.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies universal online contention resolution schemes (OCRSs) for matroids in the preselected-order arrival model, where the algorithm non-adaptively chooses the order before observing the active set. It presents three constructions: an independent-subsampling greedy OCRS with (α, α²/4)-universality (Theorem 3.4), a correlated-subsampling OCRS with (α, α²/2)-universality (Theorem 4.4), and an LP-based OCRS achieving (α, (1−ε)α)-universality (Theorem 5.4). It also gives an efficient LP-duality reduction from universal OCRS to c-competitive matroid secretary algorithms, yielding (α, (1−ε)cα)-universal OCRSs for any arrival model (Theorem 6.3), answering a question from Dughmi (2020). The proofs rely on structural lemmas relating uncontentious distributions to matroid rank properties, LP duality, and Monte-Carlo estimation. Appendix D provides tightness examples showing the quadratic guarantees of Algorithms 1 and 3 cannot be improved beyond constants.

Significance. If the results hold, this is a significant advance: it gives the first computationally efficient universal OCRSs in the preselected-order model with near-optimal balance, and it provides an efficient secretary-to-OCRS reduction for arbitrary arrival models. The paper's strengths include detailed proofs of the structural lemmas, explicit tightness constructions in Appendix D, and a clear LP/ellipsoid framework with quantitative runtime bounds. The main caveat is a normalization gap in Appendix E that affects the proofs of Theorems 5.4 and 6.3 as written; this gap appears repairable using unnormalized forms of Lemmas 5.3 and 6.2. The paper also imports Dughmi's Lemma 6.1 as a black box, which is the only load-bearing external ingredient.

major comments (2)
  1. [Appendix E.1, Lemma E.2] The proof invokes Lemma 5.3 on a vector μ that satisfies ∑ᵢ x̃ᵢ μᵢ = 1, the normalization constraint of the approximate dual LP in Eq. (31). Lemma 5.3, however, is stated only for vectors satisfying ∑ᵢ xᵢ μᵢ = 1, and since x̃ᵢ merely estimates xᵢ, this normalization is not available. The gap is load-bearing because Lemma E.2 underpins the ellipsoid-based proof of Theorem 5.4. The defect is repairable: the proof of Lemma 5.3 actually establishes the unnormalized inequality ∑ᵢ qᵢ,π_μ μᵢ ≥ α ∑ᵢ xᵢ μᵢ for all μ ≥ 0, and inserting that into the rest of the argument yields ∑ᵢ q̃ᵢ,π_μ μᵢ ≥ α(1−ε)/(1+εα) ≥ (1−2ε)α. Thus the stated conclusion is correct, but the written derivation is not.
  2. [Appendix E.2, Lemma E.3] The proof applies Lemma 6.2 to a vector satisfying ∑ᵢ x̃ᵢ μᵢ = 1, the normalization constraint of (DP1') in Eq. (33), although Lemma 6.2 is stated for vectors with ∑ᵢ xᵢ μᵢ = 1. As in Lemma E.2, this is a genuine normalization error, and it affects the proof of Theorem 6.3. The repair is again to use the unnormalized form available from the proof of Lemma 6.2, namely ∑ᵢ qᵢ,μ′ μᵢ ≥ cα(∑ᵢ xᵢ μᵢ − ε), together with the event E bounds on x̃ᵢ. With this modification the claimed (1−3ε)cα bound can be recovered, but the current text does not supply that argument.
minor comments (4)
  1. [Section 5, paragraph before Eq. (17)] The phrase “super-exponentially many variables λπ” is inaccurate: the number of permutations is n!, which is super-polynomial but not super-exponential; “exponentially many” or “super-polynomially many” would be appropriate.
  2. [Algorithm 1, Line 4] The notation T_{α/2}(A′) inside the probability in Line 4 is used before the subsampling operator is explicitly applied to a random draw; the text should state that an independent draw of the subsampling operator is taken inside each probability evaluation.
  3. [Theorem 1.3 and Theorem 6.3] The statements say “for any c, ε > 0,” but c is a competitive ratio and should be restricted to (0,1]; otherwise the claimed (1−ε)cα bound is not meaningful for c > 1.
  4. [Section E.1 and E.2] The proofs generate estimates for all n! permutations (or all w ∈ W_εⁿ) only for the purpose of a union bound, while the algorithm computes estimates on demand during the ellipsoid run. This is a standard coupling argument, but it should be stated explicitly so that the reader does not confuse the proof device with an algorithmic enumeration.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all core lemmas are proved from the definition of alpha-uncontentiousness; the only imported ingredient is an external Dughmi lemma that is logically prior, not a self-citation.

full rationale

The paper's derivation chain is self-contained rather than circular. The central notion, alpha-uncontentiousness, is defined as the existence of an alpha-balanced CRS, and Lemma 3.3 derives the weighted-rank inequality directly from that definition; it is not assumed as the target result. Lemmas 3.1, 4.1, 5.2, and 5.3 are proved from matroid properties and Lemma 3.3, and the balance guarantees of Algorithms 1, 3, and 4 follow from these lemmas rather than from fitting any parameter to the desired conclusion. The LP-based construction solves an optimization problem whose objective is the balance factor, and the Monte-Carlo estimates of xi and qi,pi are inputs with explicit error bounds; the final guarantees are consequences, not renamed inputs. The only load-bearing imported result is Dughmi's Lemma 4.3, restated as Lemma 6.1, which is an external theorem asserting a property of the constructed OCRS D(ALG,w); it is logically prior to the paper's universality claims and does not assume the existence of an efficient universal OCRS, so it is not circular. There is no author-overlapping self-citation chain, no imported uniqueness theorem choosing the authors' model, and no ansatz smuggled in via citation. The Appendix E concern about applying Lemmas 5.3 and 6.2 to approximate vectors satisfying sum(x~_i mu_i)=1 rather than sum(x_i mu_i)=1 is a mathematical correctness issue in the written proof, repairable by the unnormalized forms of those lemmas; it is not a circularity because the lemmas do not presuppose the conclusions of Theorems 5.4 or 6.3. Accordingly, no circular step meeting the quoted-evidence standard can be identified.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard mathematics (matroid theory, LP duality, ellipsoid method) plus the paper's own lemmas. The only imported nontrivial result is Dughmi's Lemma 6.1, cited as a black box. No fitted parameters or invented entities.

assumptions (5)
  • standard math Standard matroid facts used throughout (rank submodularity, span properties, restriction equivalence) as in Lemma A.1.
    The main proofs (Lemmas 3.1, 4.1, 5.2) rely on these matroid properties, quoted from Welsh (2010).
  • standard math LP duality and the ellipsoid method with a separation oracle solve the exponentially large LPs.
    Used in Sections 5, 6 and E to compute and certify optimal mixtures of permutations; standard optimization toolbox.
  • domain assumption The prior DA is α-uncontentious for M, i.e., there exists an offline α-balanced CRS.
    This is the definitional premise of the whole paper; all universal guarantees are parameterized by α.
  • domain assumption Oracle access to a membership oracle for M and a sampling oracle for DA, with pmin>0.
    Stated in Section 2; the runtime bounds depend on t_M, t_DA, and 1/pmin.
  • domain assumption Dughmi (2020, Lemma 4.3) imported as a black box: a c-competitive matroid secretary algorithm ALG induces an OCRS D(ALG,w)_φ with E[Σ w_i 1(i∈φ(A))] ≥ c·α·E[Σ_{i∈A} w_i].
    Used as the key step in Theorem 6.3's reduction; not re-proved in this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Universal Online Contention Resolution with Preselected Order." pith.science (2026). https://pith.science/paper/KOTAW5K5

@misc{pith2026250416327,
  author       = {Pith},
  title        = {Pith review of: Universal Online Contention Resolution with Preselected Order},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KOTAW5K5}},
  note         = {Machine review of arXiv:2504.16327}
}
read the original abstract

Online contention resolution scheme (OCRS) is a powerful technique for online decision making, which--in the case of matroids--given a matroid and a prior distribution of active elements, selects a subset of active elements that satisfies the matroid constraint in an online fashion. OCRS has been studied mostly for product distributions in the literature. Recently, universal OCRS, that works even for correlated distributions, has gained interest, because it naturally generalizes the classic notion, and its existence in the random-order arrival model turns out to be equivalent to the matroid secretary conjecture. However, currently very little is known about how to design universal OCRSs for any arrival model. In this work, we consider a natural and relatively flexible arrival model, where the OCRS is allowed to preselect (i.e., non-adaptively select) the arrival order of the elements, and within this model, we design simple and optimal universal OCRSs that are computationally efficient. In the course of deriving our OCRSs, we also discover an efficient reduction from universal online contention resolution to the matroid secretary problem for any arrival model, answering a question from Dughmi (2020).

Figures

Figures reproduced from arXiv: 2504.16327 by the authors.

Figure 1
Figure 1. Illustration of Example D.1. DA is α-uncontentious for M We consider the following CRS: (1) Initialize X = {(u, u′ )}. (2) For each i ∈ [m], with probability 1 2 , add edge (vi , u) to X, and with probability 1 2 , add edge (vi , u′ ) to X. (3) Select an edge from {e1, . . . , en} uniformly at random and add it to X. Then, output X. We note that X is always feasible, because it does not contain multiple edges betwee… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Adamczyk and M

    M. Adamczyk and M. W odarczyk. Random order contention resolution schemes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 790--801. IEEE, 2018

    work page 2018

  2. [2]

    Agrawal, J

    S. Agrawal, J. Sethuraman, and X. Zhang. On optimal ordering in the optimal stopping problem. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 187--188, 2020

    work page 2020

  3. [3]

    Babaioff, N

    M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, secretary problems, and online mechanisms. In Symposium on Discrete Algorithms (SODA'07), pages 434--443, 2007

    work page 2007

  4. [4]

    Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms

    H. Beyhaghi, N. Golrezaei, R. P. Leme, M. Pal, and B. Sivan. Improved approximations for free-order prophets and second-price auctions. arXiv preprint arXiv:1807.03435, 2018

    work page Pith review arXiv 2018

  5. [5]

    Bubna and A

    A. Bubna and A. Chiplunkar. Prophet inequality: Order selection beats random order. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 302--336, 2023

    work page 2023

  6. [6]

    Chawla, J

    S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 311--320, 2010

    work page 2010

  7. [7]

    Chekuri, J

    C. Chekuri, J. Vondr\' a k, and R. Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43 0 (6): 0 1831--1879, 2014

    work page 2014

  8. [8]

    Chernoff

    H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, pages 493--507, 1952

    work page 1952

Show all 24 references
  1. [9]

    S. Dughmi. The outer limits of contention resolution on matroids and connections to the secretary problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2020

    2020

  2. [10]

    S. Dughmi. Matroid secretary is equivalent to contention resolution. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2022

    2022

  3. [11]

    Dughmi, Y

    S. Dughmi, Y. H. Kalayci, and N. Patel. Limitations of stochastic selection problems with pairwise independent priors. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, page 479–490, 2024

    2024

  4. [12]

    Feldman, O

    M. Feldman, O. Svensson, and R. Zenklusen. Online contention resolution schemes with applications to bayesian selection problems. SIAM Journal on Computing, 50 0 (2): 0 255--300, 2021

    2021

  5. [13]

    H. Fu, P. Lu, Z. G. Tang, H. Wu, J. Wu, and Q. Zhang. Sample-based matroid prophet inequalities. In Proceedings of the 25th ACM Conference on Economics and Computation, 2024

    2024

  6. [14]

    Gr \"o tschel, L

    M. Gr \"o tschel, L. Lov \'a sz, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012

    2012

  7. [15]

    Gupta and V

    A. Gupta and V. Nagarajan. A stochastic probing problem with applications. In Integer Programming and Combinatorial Optimization: 16th International Conference, IPCO 2013, Valpara \' so, Chile, March 18-20, 2013. Proceedings 16 , pages 205--216. Springer, 2013

    2013

  8. [16]

    Gupta, J

    A. Gupta, J. Hu, G. Kehne, and R. Levin. Pairwise-independent contention resolution. In International Conference on Integer Programming and Combinatorial Optimization, pages 196--209. Springer, 2024

    2024

  9. [17]

    M. T. Hajiaghayi, D. R. Kowalski, P. Krysta, and J. Olkowski. Optimal algorithms for free order multiple-choice secretary. arXiv preprint arXiv:2207.10703, 2022

    2022 arXiv

  10. [18]

    T. Hill. Prophet inequalities and order selection in optimal stopping problems. Proceedings of the American Mathematical Society, 88 0 (1): 0 131--137, 1983

    1983

  11. [19]

    Hoeffding

    W. Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pages 409--426. Springer, 1994

    1994

  12. [20]

    Jaillet, J

    P. Jaillet, J. A. Soto, and R. Zenklusen. Advances on matroid secretary problems: Free order model and laminar case. In International Conference on Integer Programming and Combinatorial Optimization, pages 254--265. Springer, 2013

    2013

  13. [21]

    Lee and S

    E. Lee and S. Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities. In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018

    2018

  14. [22]

    A. Liu, R. P. Leme, M. P \'a l, J. Schneider, and B. Sivan. Variable decomposition for prophet inequalities and optimal ordering. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 692--692, 2021

    2021

  15. [23]

    Peng and Z

    B. Peng and Z. G. Tang. Order selection prophet inequality: From threshold optimization to arrival time design. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 171--178. IEEE, 2022

    2022

  16. [24]

    D. J. Welsh. Matroid theory. Courier Corporation, 2010

    2010

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.