{"id":"948a1bf1-44b5-4031-8346-50b297b42492","arxiv_id":"2411.11741","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"For k-fold matroid unions, there is a prophet inequality with competitive ratio 1-O(sqrt(log k/k)), proved via a new bicriterion concentration inequality for monotone 1-Lipschitz functions.","lead":"The paper shows that large girth alone does not guarantee good prophet inequalities, but k-fold matroid unions do, achieving a competitive ratio that approaches 1. It introduces a new bicriterion concentration inequality for monotone 1-Lipschitz functions that may be of independent interest.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly identifies Theorem 3 as the load-bearing premise; if it failed, the OCRS selectability and hence Theorem 2 would collapse. I checked the proof of Theorem 3 in detail. Lemma 22's derivative identity is correct (the partial derivative calculation and the factor q_i cancel as claimed), Lemma 24 and Facts 25–26 are valid, and the combination with the modified log-Sobolev inequality (Lemma 21) yields exactly the differential inequality needed. The subsequent comparison argument and Markov step are sound. The application in Section 4.3.3 works: with b=1−sqrt(log k/k), s=1−b, t=sqrt(k log k), st=log k, so the bad event Pr[f(X')=k] is bounded by 1/k. The only genuine errors found are presentation-level: the displayed lower bound in Section 4.3.3 omits the e^{-(1-b)} thinning factor (though the final formula includes it); Theorem 1's 'girth k' should read 'girth at least 2k'; and Theorem 2's 'for every k' should be read asymptotically, as the bound is only meaningful for large k. Lemma 18 has a compressed step, but the missing justification is valid because rank-increasing elements form a basis of each protection set. Thus the central claim withstands scrutiny, and the reader's conditional-accept verdict needs no change.","tokens_in":20676,"tokens_out":47698,"duration_ms":423173,"concrete_test":"Exhaustively verify Theorem 3 by exact enumeration over all monotone 1-Lipschitz functions on {0,1}^4, a grid of p∈[0,1]^4, s∈(0,1], and t>0, computing Pr[f(X^(s)) ≥ E[f(X)] + t] exactly and comparing with e^{-st}; a violation would pinpoint a flaw in the entropy argument, while success would further corroborate the central claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After close review, I cannot identify a load-bearing flaw in the central argument. The key premise is Theorem 3, and its proof via Lemma 22 combined with Lemma 21 is internally consistent: the differential inequality λF'(λ) ≤ F(λ) log F(λ) follows from the two lemmas, the comparison with G0(λ)=λE[Z(0)] is valid, and Markov's inequality yields the stated tail bound. The application of Theorem 3 to the OCRS in Section 4.3.3 is also sound once the displayed selectability lower bound is corrected to include the e^{-(1-b)} thinning factor, which the final selectability formula already contains. Lemma 18's proof omits a justification that non-rank-increasing additions to S do not change ω_e(R∪S); this follows because {e_1,...,e_{i-1}}×[k] spans S0_before×[k]. The remaining issues (girth at least 2k versus 'girth k'; k=1 versus the asymptotic statement) are presentation-level and do not affect the asymptotic theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies prophet inequalities for k-fold matroid unions. It first shows that large girth alone is not sufficient: for every k there is a graphic matroid of girth at least k whose optimal competitive ratio is at most 1/2+epsilon (Theorem 1). It then proves a near-optimal prophet inequality with competitive ratio 1-O(sqrt(log k/k)) for every k-fold matroid union (Theorem 2), obtained from a (1-O(sqrt(log k/k)))-selectable online contention resolution scheme (Theorem 9). The key technical ingredient is a new bicriterion concentration inequality (Theorem 3): for any monotone 1-Lipschitz function f over independent Bernoulli variables X and any s in (0,1], Pr[f(X^(s)) >= E[f(X)] + t] <= e^{-st}, where X^(s) has probabilities scaled by e^{-s}. The proof combines an entropy-method differential inequality with Massart's modified logarithmic Sobolev inequality. I verified the main logical chain: Theorem 3 follows from Lemmas 21-24, the OCRS analysis in Section 4.3.3 applies the concentration bound to a carefully defined occupancy function, Lemma 18 establishes the required chain decomposition, and Section 3 gives an explicit hardness construction.","tokens_in":20777,"tokens_out":25784,"duration_ms":240450,"significance":"If the results hold, Theorems 2 and 9 give a substantial generalization of the known near-optimal prophet inequalities for k-uniform matroids to all k-fold matroid unions, and the OCRS is directly useful. The concentration inequality (Theorem 3) is novel and dimension-free in a bicriterion sense; it applies to all monotone 1-Lipschitz functions, a class for which ordinary dimension-free upper-tail bounds are impossible, so it may well be of independent interest. The paper contains fully written proofs of the central lemmas, including the entropy-method derivation and the explicit high-girth construction, and it does not rely on fitted parameters or circular reasoning. The main weakness is a small number of local proof-completeness issues that should be fixed, but they do not affect the validity of the asymptotic results.","major_comments":[],"minor_comments":[{"comment":"The displayed chain 'Pr[(e,i) is accepted | (e,i) is active] >= 1 - Pr[f(X') >= k]' omits the e^{-(1-b)} factor coming from the initial rejection step in Algorithm 4. The correct inequality is Pr[(e,i) accepted | (e,i) active] >= e^{-(1-b)} * (1 - Pr[f(X') >= k]). The final selectability formula already contains this factor, so the issue is local, but the displayed chain should be corrected.","section":"Section 4.3.3, final paragraph"},{"comment":"The proof needs one additional justification: when bounding the stopping condition for e_i, one must replace S0_before x [k] by {e_1,...,e_{i-1}} x [k]. This is valid because {e_1,...,e_{i-1}} is a basis of S0_before in M, so {e_1,...,e_{i-1}} x [k] spans S0_before x [k] in the extended k-fold union. As written, the equalities involving span are false (span is not equal to S0 unless S0 is closed), and the transfer of the condition E[omega_e_i(R cup S)] > bk to the smaller set is asserted without proof.","section":"Appendix B, proof of Lemma 18"},{"comment":"The theorem states that the constructed matroid has girth exactly k, but the proof only establishes girth at least 2k (after the edge-splitting construction). The abstract uses 'girth >= k', which is what the proof supports. To match the theorem statement, either weaken it to 'girth at least k' or explicitly add a disjoint k-cycle to the construction.","section":"Theorem 1 statement vs. Section 3 proof"},{"comment":"The theorem is stated for every k >= 1, but the claimed bound 1 - O(sqrt(log k/k)) is false for k = 1: any matroid is the 1-fold union of itself, and not every matroid admits a 1-competitive prophet inequality. The proof itself shows the selectability is (1-1/k)*b*e^{-(1-b)}, which is 0 for k = 1. The statement should be restricted to sufficiently large k or handled separately.","section":"Theorem 2 statement"},{"comment":"In the sentence 'we prove Theorem 9 by showing the existence of an OCRS for all k-fold union M^k and x* in P_{M^k}', the symbol x* is used both for the extended ground set and the original ground set. Please distinguish the original vector x from the extended vector x* to avoid confusion.","section":"Section 4.3.3, notation after Fact 10"}],"recommendation":"minor_revision","confidential_remarks":"The paper is well within the scope of the journal and the central claims appear correct. The issues listed in the minor comments are local and fixable; in particular, the stress-test concern about Theorem 3 does not land, since the differential inequality proof is internally consistent. I would be happy to see a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know first: this paper has a new, real result — a dimension-free bicriterion tail bound for arbitrary monotone 1-Lipschitz functions (Theorem 3) — and it actually powers a (1 − O(sqrt(log k/k)))-selectable OCRS for k-fold matroid unions, which gives the same competitive ratio for prophet inequalities. I checked the main proof steps and they hold up. The entropy-method argument for Theorem 3 is legitimate: Lemma 22 together with Massart's modified log-Sobolev inequality gives the differential inequality λF'(λ) ≤ F(λ) log F(λ), and the comparison with λ E[Z(0)] yields the tail bound. I could not find a hidden circularity or a fitted parameter.\n\nThe paper also does something useful in the negative direction: it shows large girth alone does not give you better than 1/2, via a dense high-girth graph construction. That is a clean counterexample to a natural conjecture.\n\nNow the soft spots, in proportion. Three things need fixing in a revision, but none of them undermine the final theorems. First, the displayed selectability lower bound in Section 4.3.3 omits the e^{-(1-b)} thinning factor; as written that display is false, though the final selectability computation two lines later already includes it. Second, Theorem 1 states 'girth k' but the construction actually gives girth at least 2k; the statement is true in the direction needed, but the wording is off. Third, Theorem 2 and the abstract say 'every k-fold matroid union,' but the bound is asymptotic in k; for k=1 the ratio would be 1, which is impossible. These are presentation-level, not load-bearing.\n\nThe citation pattern looks fine; the novel claims are new, and the self-citations are to the OCRS framework they build on.\n\nWho benefits: anyone working on online contention resolution, prophet inequalities, or dimension-free concentration for set functions. The paper deserves a serious referee from a theory venue, and I would engage with it.","headline":"Novel bicriterion concentration inequality that is proved correctly and powers a strong OCRS/prophet inequality for k-fold matroid unions; only presentation-level issues need fixing.","tokens_in":21406,"tokens_out":2114,"would_cite":true,"duration_ms":19813,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60E15","05B35","68W27","90C27","60G40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves every k-fold matroid union admits a prophet inequality with competitive ratio approaching 1, while large girth alone cannot beat 1/2.","keywords":["Prophet inequalities","Online contention resolution schemes","k-fold matroid unions","Bicriterion concentration inequality","Matroid girth","Self-bounding functions","Entropy method","Dimension-free tail bounds"],"falsifier":"A direct test: for a small k-fold matroid union, take the occupancy function from Definition 14, choose probabilities $p$ so that $\\mathbb{E}[f(X)]\\approx k$, set $s=\\sqrt{\\log k/k}$ and $t=\\sqrt{k\\log k}$, and numerically evaluate $\\Pr[f(X^{(s)})\\ge \\mathbb{E}[f(X)]+t]$. Theorem 3 requires this tail to be at most $e^{-st}\\approx 1/k$; a single violation for a monotone 1-Lipschitz $f$ would refute the central technical claim. A simpler surrogate is $f(x)=\\min(m,\\sum_i x_i)$ with $m\\gg k$, where the exponent $-st$ is known to be sharp up to a constant, so checking whether the bound holds there tests the inequality's tightness.","tokens_in":20409,"feed_emoji":"🎰","tokens_out":13369,"duration_ms":111140,"temperature":0.7,"pith_summary":"This paper asks which feasibility families admit prophet inequalities with competitive ratio approaching 1, in the way that k-uniform matroids do. It proves two answers: large girth alone is not enough, because there are graphic matroids of girth at least k on which no algorithm beats 1/2; but k-fold matroid unions are enough, because every such union admits a $1-O(\\sqrt{\\log k/k})$-competitive prophet inequality. The positive result is built from an online contention resolution scheme whose selectability rests on a new bicriterion concentration inequality: after scaling every item's activation probability down by $e^{-s}$, any monotone 1-Lipschitz function over independent Bernoulli items has a dimension-free exponential tail of size $e^{-st}$. This inequality supplies the 'Chernoff-strength' concentration that the matroid-union setting needs, even though the occupancy functions involved are not self-bounding.","feed_headline":"k-fold matroid unions admit near-1 prophet inequalities","feed_subtitle":"A new concentration inequality yields a near-1 competitive prophet inequality for every k-fold union.","key_machinery":"The key machinery is the bicriterion concentration inequality of Theorem 3: for every monotone 1-Lipschitz $f$ and every $s\\in(0,1]$, $t>0$, $\\Pr[f(X^{(s)})\\ge \\mathbb{E}[f(X)]+t]\\le e^{-st}$, where $X^{(s)}$ has probabilities $e^{-s}p$. The proof studies $F(\\lambda)=\\mathbb{E}[e^{\\lambda f(X^{(\\lambda)})}]$, in which $\\lambda$ acts simultaneously as the tail parameter and the scaling factor; a derivative estimate combined with a modified logarithmic Sobolev inequality yields the differential inequality $\\lambda F'(\\lambda)\\le F(\\lambda)\\log F(\\lambda)$, and Markov's inequality converts the resulting bound on $F$ into the tail bound. This inequality is what makes the chain-decomposition OCRS work: it turns the expected-occupancy bound $\\mathbb{E}[\\omega_e(R(x^*)\\cup N_1)]\\le bk$ into a high-probability guarantee that $\\omega_e$ stays below $k$ after the extra scaling by $e^{-(1-b)}$.","core_discovery":"The central claim is that a k-fold matroid union supports a $1-O(\\sqrt{\\log k/k})$-selectable online contention resolution scheme, and therefore a prophet inequality with the same competitive ratio for arbitrary value distributions. The proof defines an occupancy function $\\omega_e(S)=k-\\mathrm{rank}(S\\cup(\\{e\\}\\times[k]))+\\mathrm{rank}(S)$ on the extended k-fold union, which is monotone, 1-Lipschitz, and detects when an element is spanned; a chain decomposition protects elements whose expected occupancy is close to k. Selectability reduces to a tail bound on the monotone 1-Lipschitz function $f(S)=\\omega_e(S\\cup N_1)$, and the paper proves the bicriterion inequality $\\Pr[f(X^{(s)})\\ge \\mathbb{E}[f(X)]+t]\\le e^{-st}$ for the scaled Bernoulli vector $X^{(s)}\\sim\\mathrm{Ber}(e^{-s}p)$. The concentration inequality is the technical heart: it gives dimension-free exponential concentration for functions that need not be self-bounding, at the price of comparing $f(X^{(s)})$ with $\\mathbb{E}[f(X)]$ rather than $f(X)$.","pith_inferences":["The bicriterion inequality likely transfers to other online selection problems with feasibility defined by a matroid union or packing constraint: scale down arrival probabilities, prove occupancy concentration, then recover selectability.","The negative result for large girth suggests that the right combinatorial property for near-1 prophet inequalities is not cycle-freeness but union-of-matroids structure; one could test whether other matroid operations (truncation, direct sums, transversal matroids) preserve the guarantee.","The theorem leaves a natural quantitative question: whether the $e^{-s}$ scaling in the concentration inequality is necessary, or whether a milder scaling such as $p\\to(1-c\\sqrt{\\log k/k})p$ would suffice for the specific occupancy functions used.","A numerical search over small matroids could calibrate the constant in the $e^{-st}$ exponent and check whether the bound is tight for the exact class of occupancy functions, not just for linear $f$."],"forward_implications":["Every k-fold matroid union admits a $1-O(\\sqrt{\\log k/k})$-competitive prophet inequality, matching the k-uniform matroid guarantee up to a logarithmic factor.","The implied online contention resolution scheme is $1-O(\\sqrt{\\log k/k})$-selectable, so each element is accepted with almost its marginal probability even under an adversary that sees all past realizations.","Large girth does not yield near-1 prophet inequalities: for every k, there exist graphic matroids of girth k whose optimal competitive ratio is $1/2$, so the k-fold union property is doing the real work.","The bicriterion concentration inequality is a standalone tool: for any monotone 1-Lipschitz function over independent items, an exponential scaling of probabilities forces a dimension-free $e^{-st}$ upper tail.","Whether the $O(\\sqrt{\\log k/k})$ rate can be sharpened to $O(1/\\sqrt{k})$ for k-fold unions remains open."],"supporting_citations":[{"why":"Supplies the OCRS-to-prophet reduction, the protection-set procedure, and the chain-decomposition method on which Algorithm 4 is built.","marker":"[12]"},{"why":"Provides the modified logarithmic Sobolev inequality (Lemma 21) that converts the derivative bound on $F(\\lambda)$ into the differential inequality used to prove Theorem 3.","marker":"[20]"},{"why":"Establishes the entropy method for self-bounding functions that the proof of the bicriterion concentration inequality adapts.","marker":"[5]"},{"why":"Shows dimension-free concentration fails for general monotone subadditive functions, motivating the scaled bicriterion comparison in Theorem 3.","marker":"[27]"},{"why":"Supplies the dense graphs of large girth used in the construction proving that large girth does not suffice (Theorem 1).","marker":"[18]"},{"why":"Gives the 1 - O(1/sqrt(k)) prophet inequality for k-uniform matroids that the paper's k-fold union result extends and nearly matches.","marker":"[1]"}],"fun_headline_variants":["Near-1 prophet inequalities for all k-fold matroid unions","Chernoff-strength concentration without self-bounding","Bicriterion concentration yields near-optimal prophet inequalities","k-fold unions: prophet inequalities tend to 1","New concentration inequality powers prophet inequalities"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the new bicriterion concentration inequality (Theorem 3) for monotone 1-Lipschitz functions; if it fails for some occupancy function, the selectability estimate in Subsection 4.3.3, and with it the near-1 prophet inequality for k-fold matroid unions, collapses.","fun_headline_variants_meta":{"raw":{"variants":["Near-1 prophet inequalities for all k-fold matroid unions","Chernoff-strength concentration without self-bounding","Bicriterion concentration yields near-optimal prophet inequalities","k-fold unions: prophet inequalities tend to 1","New concentration inequality powers prophet inequalities"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000248,"raw_usage":{"total_tokens":1559,"prompt_tokens":972,"completion_tokens":587,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":588,"completion_tokens_details":{"reasoning_tokens":513}},"tokens_in":588,"tokens_out":587,"duration_ms":6014,"temperature":1.0,"reasoning_tokens":513,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:15:23.030937+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct test: for a small k-fold matroid union, take the occupancy function from Definition 14, choose probabilities $p$ so that $\\mathbb{E}[f(X)]\\approx k$, set $s=\\sqrt{\\log k/k}$ and $t=\\sqrt{k\\log k}$, and numerically evaluate $\\Pr[f(X^{(s)})\\ge \\mathbb{E}[f(X)]+t]$. Theorem 3 requires this tail to be at most $e^{-st}\\approx 1/k$; a single violation for a monotone 1-Lipschitz $f$ would refute the central technical claim. A simpler surrogate is $f(x)=\\min(m,\\sum_i x_i)$ with $m\\gg k$, where the exponent $-st$ is known to be sharp up to a constant, so checking whether the bound holds there tests the inequality's tightness.","supporting_citations":[{"cited_title":"About the constants in talagrand's concentration inequalities for empirical processes","cited_arxiv_id":null,"evidence_quote":"Provides the modified logarithmic Sobolev inequality (Lemma 21) that converts the derivative bound on $F(\\lambda)$ into the differential inequality used to prove Theorem 3."},{"cited_title":"A sharp concentration inequality with applications","cited_arxiv_id":null,"evidence_quote":"Establishes the entropy method for self-bounding functions that the proof of the bicriterion concentration inequality adapts."},{"cited_title":"A new series of dense graphs of high girth","cited_arxiv_id":null,"evidence_quote":"Supplies the dense graphs of large girth used in the construction proving that large girth does not suffice (Theorem 1)."}],"review_version":1}