{"id":"69437ffb-3c9b-487d-8ab8-0d4191ff2e8b","arxiv_id":"2504.16327","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A computationally efficient universal OCRS with preselected order achieves near-optimal (α,(1−ε)α) balance for all matroids and all α-uncontentious correlated priors, via LP duality and subsampling.","lead":"This paper designs online algorithms that choose the order in which items arrive before seeing which are active, and still guarantee every item is selected with probability proportional to its offline contention resolution guarantee, even for correlated active sets. It also gives an efficient LP-based reduction showing that any competitive matroid secretary algorithm yields a universal online contention resolution scheme in the same arrival model.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix E's approximate-LP proof misapplies normalization-requiring Lemmas 5.3/6.2 to vectors satisfying sum(x~_i mu_i)=1 rather than sum(x_i mu_i)=1; the bound is repairable via unnormalized forms, but as written Theorems 5.4/6.3 are not fully proved.","rationale":"The paper's main constructions and exact-LP arguments are convincing: the structural lemmas are correct, the LP duality argument in Section 5 is sound, and the Dughmi black box is not actually mysterious, since Lemma 6.1 follows immediately from c-competitiveness and Lemma 3.3. However, the computational-efficiency claims in Theorems 5.4 and 6.3 depend on the approximate-LP analysis in Appendix E, and that analysis contains a concrete normalization error. Lemmas 5.3 and 6.2 are stated only for vectors satisfying sum x_i mu_i = 1, but the approximate duals use sum x~_i mu_i = 1 with estimated coefficients. The cited lemmas are therefore not directly applicable. The error is repairable because the proofs of those lemmas yield unnormalized inequalities, and the corrected constants still support the claimed bounds. This makes the concern a proof gap rather than a refutation of the central theorems. A rigorous revision should supply the corrected derivations in E.1 and E.2. The reader's identified weakest assumption, the Dughmi Lemma 4.3 import, is not the actual soft spot; it is derivable from the secretary definition. Thus the verdict should be CONDITIONAL: accept the paper's core claims provided the approximate-LP proofs are fixed to use the unnormalized forms, with the constants checked.","tokens_in":36178,"tokens_out":45169,"duration_ms":417243,"concrete_test":"Re-prove Lemma E.2 without applying Lemma 5.3 to an unnormalized mu. Replace the line '>= alpha - sum_i epsilon alpha x_i mu_i (By Lemma 5.3)' with '>= alpha sum_i x_i mu_i - epsilon alpha sum_i x_i mu_i', then lower-bound sum_i x_i mu_i >= 1/(1+epsilon alpha) from sum_i x~_i mu_i = 1 and x~_i <= (1+epsilon alpha)x_i. Verify that alpha(1-epsilon)/(1+epsilon alpha) >= (1-2epsilon)alpha for epsilon in (0,1/6). Carry out the analogous repair for Lemma E.3 using the unnormalized form of Lemma 6.2. If either repaired bound fails to reach the claimed (1-2epsilon)alpha or (1-3epsilon)c alpha threshold, the approximation analysis in Appendix E collapses and Theorems 5.4 and 6.3 require rework.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In E.1, the approximate dual (31) enforces sum_i x~_i mu_i = 1. The proof of Lemma E.2 then invokes Lemma 5.3 to conclude sum_i q_{i,pi_mu} mu_i >= alpha. But Lemma 5.3 is stated for vectors satisfying sum_i x_i mu_i = 1; the vector mu in (31) need not satisfy this because x~_i only estimates x_i. The proof of Lemma 5.3 actually establishes the unnormalized inequality sum_i q_{i,pi_mu} mu_i >= alpha sum_i x_i mu_i for every mu >= 0. Feeding this into the rest of the argument gives sum_i x~_i mu_i = 1 and x~_i <= (1+epsilon alpha)x_i, hence sum_i x_i mu_i >= 1/(1+epsilon alpha), so the corrected bound is sum_i q~_{i,pi_mu} mu_i >= alpha(1-epsilon)/(1+epsilon alpha) >= (1-2epsilon)alpha. Thus the lemma's conclusion is correct but the written derivation is not. The same defect occurs in Lemma E.3, where Lemma 6.2 (stated for sum x_i mu_i = 1) is applied to a vector satisfying only sum x~_i mu_i = 1; the unnormalized form sum_i q_{i,mu'} mu_i >= c alpha (sum_i x_i mu_i - epsilon) repairs it. Because Theorems 5.4 and 6.3 rely on these approximate-LP lemmas, the submitted proof is incomplete as written. The structural lemmas (3.1, 4.1, 5.3) and the Dughmi import appear sound; Lemma 6.1 follows directly from c-competitiveness plus Lemma 3.3.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":36604,"tokens_out":10262,"duration_ms":98097,"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":[{"comment":"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.","section":"Appendix E.1, Lemma E.2"},{"comment":"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.","section":"Appendix E.2, Lemma E.3"}],"minor_comments":[{"comment":"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.","section":"Section 5, paragraph before Eq. (17)"},{"comment":"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.","section":"Algorithm 1, Line 4"},{"comment":"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.","section":"Theorem 1.3 and Theorem 6.3"},{"comment":"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.","section":"Section E.1 and E.2"}],"recommendation":"major_revision","confidential_remarks":"The normalization gap in Appendix E is localized and appears fully repairable, so I do not see a reason to doubt the central results. The only other outside dependency is Dughmi's Lemma 6.1, which the authors use as a black box; it may be worth asking them to state its exact hypotheses in the revision. If the repairs to Lemmas E.2 and E.3 are incorporated cleanly, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Junyao Zhao has written a strong theory paper. It gives the first computationally efficient universal OCRS in the preselected-order model, achieving (alpha, (1-eps)alpha) balance, and an LP-based reduction from universal OCRS to matroid secretary that works for any arrival model. Those are real contributions, and the answer to Dughmi's open question is a genuine advance.\n\nThe paper is also honest about its machinery. The independent and correlated subsampling OCRSs are new, with matching tightness examples in Section D. The LP-duality treatment of uncontentious distributions over permutations is clean, and the structural lemmas (3.1, 4.1, 5.3) are proven from matroid rank properties and Lemma 3.3, which is itself derived from the definition rather than assumed. I checked the main proofs of Theorems 3.4 and 4.4; the combinatorial parts hold up.\n\nThe one real problem is in Appendix E. The approximate LP analysis applies Lemmas 5.3 and 6.2 to vectors that only satisfy sum_i tilde{x}_i mu_i = 1, while the lemmas are stated for vectors with sum_i x_i mu_i = 1. The stress-test note is right: the written derivations of Lemmas E.2 and E.3 do not go through as printed. However, the unnormalized forms of both lemmas are true and follow from the same proofs, and plugging those in gives the same (1-O(eps)) factors with slightly adjusted constants. So the theorems are very likely correct; the submitted proof just has a local, repairable gap. This should be fixed before publication, but it is not a counterexample to the results.\n\nThe black-box import of Dughmi's Lemma 6.1 is fine; it is exactly the right kind of external theorem to cite, and the reduction inherits its conditions in a sound way.\n\nWho is this for? People working on contention resolution, matroid secretary, and online Bayesian selection. The paper will be cited and used. It deserves a serious referee. I would send it out and ask the author to clean up Appendix E.","headline":"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.","tokens_in":37117,"tokens_out":3255,"would_cite":true,"duration_ms":28228,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B35","68W27","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that preselected arrival orders admit universal online contention resolution with near-optimal balance for every matroid and correlated prior.","keywords":["online contention resolution schemes","universal OCRS","matroid secretary problem","preselected order","correlated distributions","linear programming","ellipsoid method","matroids"],"falsifier":"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$.","tokens_in":35965,"feed_emoji":"🎲","tokens_out":12943,"duration_ms":119129,"temperature":0.7,"pith_summary":"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.","feed_headline":"Fixed order gives near-optimal universal contention resolution","feed_subtitle":"An efficient scheme keeps every active element with probability (1-ε)α for any matroid and any correlated prior.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines universal OCRS and supplies Lemma 4.3, the imported black box saying a c-competitive matroid secretary algorithm yields an OCRS with factor c·α.","marker":"Dughmi (2020)"},{"why":"Introduced contention resolution schemes, ordered OCRSs for product distributions, and the LP-based approach extended here to correlated distributions.","marker":"Chekuri et al. (2014)"},{"why":"Defined ordered OCRS and the greedy selection framework that Algorithms 1 and 3 generalize.","marker":"Gupta and Nagarajan (2013)"},{"why":"Contributes the technique for efficiently solving OCRS LPs via the ellipsoid method with estimated coefficients.","marker":"Lee and Singla (2018)"},{"why":"Supplies the ellipsoid method used to find polynomial-size sets of dual constraints.","marker":"Grötschel et al. (2012)"},{"why":"Supplies matroid properties and the greedy optimality theorem used to show the decreasing-weight permutation realizes the weighted rank.","marker":"Welsh (2010)"},{"why":"Establishes the random-order equivalence between universal OCRS and matroid secretary, motivating the efficient reduction proved here.","marker":"Dughmi (2022)"},{"why":"Gives a constant-competitive free-order matroid secretary algorithm, the prior route to a non-efficient universal OCRS in that model.","marker":"Jaillet et al. (2013)"}],"fun_headline_variants":["Preselected order yields optimal universal OCRS","Optimal universal OCRS via LP on permutations","Preselecting order makes universal OCRS optimal","LP-chosen order gives optimal universal contention resolution"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Preselected order yields optimal universal OCRS","Optimal universal OCRS via LP on permutations","Preselecting order makes universal OCRS optimal","LP-chosen order gives optimal universal contention resolution"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000849,"raw_usage":{"total_tokens":3686,"prompt_tokens":931,"completion_tokens":2755,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":2708}},"tokens_in":547,"tokens_out":2755,"duration_ms":17696,"temperature":1.0,"reasoning_tokens":2708,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:07:16.432381+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[],"review_version":1}