{"id":"bdd1791a-9a41-4678-9cc9-5c433d78b272","arxiv_id":"2502.09521","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Forward-backward random order improves contention-resolution guarantees to 0.622 for single-unit and 1/3 for knapsack, with the single-unit guarantee proven tight.","lead":"This paper designs contention resolution schemes for a new forward-backward arrival model, where agents arrive in a known order or its reverse with equal probability, and uses them to give fair rationing algorithms with per-agent service guarantees. The headline numbers: a tight 0.622 guarantee for single-unit constraints and a 1/3 guarantee for knapsack constraints, both improving on what is possible with a single adversarial order.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the central CRS theorems are sound; only minor, non-load-bearing issues remain.","rationale":"The reader identified the independence/known-order assumption as the weakest part of the paper, and I agree that this is the main modeling limitation: the reductions in Lemma 2.2 and the FKG-based service guarantees rely on independence of demands and on the forward-backward order being revealed to the algorithm. This is a scope restriction for the mobile food pantry application, not a correctness defect in the mathematical claims. My stress-test of the central proofs found no internal inconsistency. The single-unit tightness proof is a clean LP/duality argument: Lemma 3.3 constructs feasible primal solutions whose objective equals the claimed α0 for every input with total probability ρ, and Lemma 3.5 provides a dual certificate for the uniform instance whose value converges to α0. The knapsack construction is more involved, but the induction in Appendix C.1 is consistent with the feasible-probability conditions of Definition 5, and the resulting selection guarantee min_i (c_f(i)+c_b(i))/2 = 1/3 follows by the same averaging argument used in the single-unit case. The knapsack hardness reduction in Proposition 4.5 is valid because all sizes exceed 1/2, so at most one element can be accepted. The one concrete arithmetic slip is the additive constant in Lemma 3.5; it is localized to a finite-N bound and disappears in the limit, so it does not affect Theorems 1.3 or 1.5. The sampling caveats in Remarks 3 and 7 are standard in the CRS literature and concern computational implementation, not the existence of the schemes. For these reasons, the reader's ACCEPT verdict with high confidence should stand unchanged.","tokens_in":39489,"tokens_out":30545,"duration_ms":284888,"concrete_test":"Re-derive the objective bound in Lemma 3.5 symbolically: for N=2n+1 use (3.14)-(3.16) to compute Σ_{i=1}^N (y_f(i)+y_b(i))/N exactly for ρ=1 and N=3,5,7, and compare with α0+(ρ+2)/N and α0+(ρ+3)/N. If the true value is α0+(ρ+3)/N, restate Theorem 3.4 with an O(1/N) additive term; Theorems 1.3 and 1.5 remain valid because they only use the limit N→∞.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I could not identify a load-bearing concern with the central claims. The single-unit lower bound (Theorem 1.2) is supported by an explicit feasible solution to LP-SI built from the continuous certificate φ (Proposition 3.2, Lemma 3.3); the matching upper bound (Theorem 1.3) is certified by a feasible dual solution whose objective tends to the same constant (Lemma 3.5, Proposition 3.6). The knapsack 1/3 construction (Theorem 1.4) is grounded in the feasible selection probabilities of Definition 5 and the induction in Appendix C.1, and the 1/(2+e^{-1}) upper bound (Theorem 1.5) reduces correctly to the single-unit hardness result. The only concrete issue I found is minor: in Lemma 3.5, recomputing (3.21) through (3.22) appears to give an additive +3/N rather than the stated +2/N, an off-by-one constant that does not affect the N→∞ conclusion of Theorem 1.3. Two other soft spots are also non-load-bearing: the Type-III reduction in Lemma 2.2 uses an implicit 0/0 convention for demand atoms at zero, and Remarks 3 and 7 delegate sampling/discretization details without formal error bounds. These affect implementation and edge-case rigor in the reduction, not the existence of the CRS guarantees.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces forward-backward contention resolution schemes (FB-CRS), in which the arrival order is uniformly either the forward permutation or its reverse, and uses them for fair rationing of a single resource under three service definitions. The main theoretical results are: (i) for rank-1 (single-unit) constraints, an FB-CRS with selection guarantee exp(ρ/2)/(1+exp(ρ/2)ρ) for total active probability ρ, together with a matching upper bound; (ii) for knapsack constraints, a 1/3-selectable FB-CRS and an upper bound of 1/(2+e^{-1}); and (iii) a reduction from ex-ante fair rationing to CRS, with Type-II/III service handled by single-unit CRS and Type-I by knapsack CRS. The proofs are based on an LP characterization of single-unit FB-CRS, a closed-form continuous certificate φ, an explicit dual solution for tightness, and an invariant-based induction for the knapsack algorithm.","tokens_in":39761,"tokens_out":10278,"duration_ms":88803,"significance":"If the results are correct, they settle the exact power of the forward-backward arrival model for single-unit CRS, giving a tight guarantee strictly between the adversarial 1/2 and random-order 1-1/e, and they improve the state of the art for knapsack CRS even relative to offline and random-order settings. The paper also connects these CRS bounds to concrete fair-rationing algorithms. A notable strength is that the main constructions are explicit and parameter-free: the candidate functions φ and γ are given in closed form, the single-unit lower bound is verified through an explicit feasible LP solution, and the upper bound uses a fully specified dual solution. The knapsack hardness proof reuses the single-unit bound in a clean reduction. The write-up is largely self-contained, with the main inductive arguments included in the appendices.","major_comments":[],"minor_comments":[{"comment":"The 1-Lipschitz bound used to compare the right-endpoint and left-endpoint Riemann sums appears to give an additive constant of order (ρ+3)/N rather than the stated +2/N: the telescoping differences contribute an extra term beyond ρ/N, and the left-endpoint sum starts at ρ(n+1)/N rather than ρ/2. Since the conclusion of Theorem 1.3 only needs the additive error to tend to zero as N→∞, this does not affect the central tightness claim, but Theorem 3.4 should either be restated with the corrected constant or the inequality should be justified more carefully.","section":"Lemma 3.5, Eqs. (3.21)-(3.22)"},{"comment":"The FKG step divides by F_i^{-1}(q), which is zero on the interval corresponding to an atom of demand at zero. The paper's convention that 0/0 is treated as 1 for Type-III service does not by itself justify these divisions. This is a rigor gap in the reduction, but it is local and can likely be repaired with a truncation or limiting argument.","section":"Lemma 2.2, Type-III case, Eqs. (2.10)-(2.11)"},{"comment":"Algorithms 1 and 3 require exact computation of distributions of remaining supply or accumulated knapsack load (Rem and T_σ(i)), and the paper defers to sampling/discretization without formal error bounds. Since the theorems are about existence of CRS and the algorithms are conceptual, this is acceptable, but a precise implementation statement with convergence guarantees would make the algorithmic claims more complete.","section":"Remarks 3 and 7"},{"comment":"There are several typographical and formatting issues, including corrupted reference text (e.g., the author names in [AW18]) and inconsistent use of notation such as \"xσ(i)\" versus \"xf(i)\" in proofs. These should be cleaned up before publication.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The paper is strong and the central claims appear sound. I agree with the reader's positive assessment. My recommendation of minor_revision rather than immediate acceptance is driven by the small additive-constant error in Lemma 3.5 and the edge-case handling in the Type-III reduction; both are local and do not threaten the main theorems. The forward-backward model is a meaningful contribution, and the explicit LP/dual-based tightness proof is particularly valuable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main results are real. The single-unit FB-CRS guarantee exp(rho/2)/(1+exp(rho/2)rho) is proved from a concrete LP and matched by a dual certificate, so the tightness claim is not a guess. The constant 1/(1+e^{-1/2}) genuinely separates the two-order model from both adversarial (1/2) and random-order (1-1/e) settings. The knapsack 1/3 construction and the 1/(2+e^{-1}) upper bound are also new, and the upper bound correctly reuses the single-unit hardness with rho=2. I checked the logic that the worst single-unit input is the uniform one: the splitting argument in Appendix B.5 closes that gap properly, so the upper bound is not only for a contrived instance. This is a substantial paper in the online algorithms / prophet inequality subfield.\n\nThe paper also does something rare: the reduction from fair rationing to CRS is explicit enough that a reader can see exactly where each assumption is used. The FKG step in Lemma 2.2 is nontrivial and the extra case for qi > F_i(1) is handled, not swept aside. The knapsack induction in Appendix C is heavy but follows the JMZ22 template and the feasible-probability definition is coherent. I do not see a circular argument or a missing lemma that would collapse the main claims.\n\nSoft spots are minor. The stress-test note about Lemma 3.5 is right: the algebra around (3.21)-(3.22) appears to give an extra +1/N additive term, but this is absorbed in the limit and does not affect Theorem 1.3. The sampling-based implementation of Algorithm 1 and Algorithm 3 is delegated to Remarks 3 and 7 without formal error bounds, which is common in this literature but worth saying out loud. The food-bank motivation assumes independent demands and a known direction; correlated shocks or an adversarial direction would break the reduction. None of these touch the mathematical existence theorems.\n\nWho is this for? Researchers in contention resolution, prophet inequalities, and online resource allocation. It deserves a serious referee and, with the small constant fixed and the sampling remarks expanded, publication. I would cite it and would bring it to reading group.","headline":"The forward-backward CRS model yields a genuinely tight single-unit guarantee and a knapsack 1/3 that beats the offline state of the art; the proofs are LP-based and credible, with only minor implementation and edge-case gaps.","tokens_in":40278,"tokens_out":1258,"would_cite":true,"duration_ms":16252,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68W20","90C27","91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"A rationing system that serves agents in a forward order or its reverse, each equally likely, can guarantee each agent at least a 0.622 selection probability — and this bound is exactly what is achievable.","keywords":["contention resolution schemes","fair rationing","forward-backward arrival order","prophet inequalities","rank-1 matroid","knapsack constraints","online resource allocation","ex-ante fairness"],"falsifier":"Solve the LP-SI program by linear programming on arbitrary single-unit inputs with total probability $\\rho = 1$ and a few dozen elements; the paper's tightness claim asserts that the optimal value never exceeds $1/(1+e^{-1/2}) \\approx 0.622$, so the first instance whose LP optimum is larger refutes the central result. On the algorithmic side, sample Algorithm 3 on any knapsack instance with deterministic sizes summing to 1 and measure each element's conditional acceptance probability: a value below $1/3$ refutes the knapsack guarantee, while a single-unit instance with total probability 2 whose simulated acceptance probability exceeds $1/(2+e^{-1}) \\approx 0.422$ refutes the upper bound.","tokens_in":39317,"feed_emoji":"🚚","tokens_out":17655,"duration_ms":134489,"temperature":0.7,"pith_summary":"This paper establishes exactly how much fairness is gained when an online rationing system serves agents in a known forward order or its reverse, each equally likely — as when a mobile food pantry drives the same route in alternating directions. The main result is a single-unit contention resolution scheme with selection guarantee $\\exp(\\rho/2)/(1+\\exp(\\rho/2)\\rho)$ on instances of total arrival mass $\\rho$, which at $\\rho = 1$ gives $1/(1+e^{-1/2}) \\approx 0.622$ per agent, together with a matching proof that no scheme of this kind can do better. That number sits strictly between the $1/2$ that is best possible under a fixed order and the $1 - 1/e \\approx 0.632$ achievable under a fully random order, and it also improves the two-order prophet inequality from the golden-ratio constant $(\\sqrt{5}-1)/2 \\approx 0.618$. For the all-or-nothing Type-I service that requires knapsack constraints, the paper constructs a forward-backward scheme with guarantee $1/3$, improving on the $1/(3+e^{-2}) \\approx 0.319$ tight for a single order, and proves an upper bound of $1/(2+e^{-1}) \\approx 0.422$. A general reduction converts any such scheme into an online rationing policy that delivers the same per-agent service guarantee for Type-I, Type-II, or Type-III service, so the constants translate directly into fairness commitments.","feed_headline":"One route, two directions — a tight 0.622 rationing guarantee","feed_subtitle":"Reversible food-pantry routes beat the 0.5 fixed-order service bound at no extra driving cost.","key_machinery":"The engine is LP-SI, a linear program whose variables $c_f(i), c_b(i)$ are the probabilities of accepting element $i$ in the forward and backward orders conditional on it being active, with constraints $c_\\sigma(i) \\le 1 - \\sum_{j <_\\sigma i} x_j c_\\sigma(j)$ expressing that an accepted element blocks all earlier elements. The paper's solver is a continuous function $\\phi$ that satisfies $\\phi(z) + \\phi(\\rho - z) = 2\\alpha_0$ and $\\phi(z) \\le 1 - \\int_0^z \\phi(\\tau)\\,d\\tau$; element $i$ receives the average of $\\phi$ over its probability interval in the arrival order, which makes $\\phi$ a limiting feasible solution as element probabilities shrink and turns its two identities into a universal lower bound. On the dual side, $\\gamma(z)$ provides a feasible certificate whose value approaches the same number, with an engineered spike at the middle element handling the discontinuity between the continuous optimum and any finite instance. For knapsack, the same machinery runs with the linear $\\phi(z) = 4/9 - 2z/9$, and the algorithmic part is an induction maintaining an anti-concentration bound on the running accepted mass — the probability the mass lies in $(0, b]$ decays exponentially in the probability it lies beyond $b$ — which the '0-avoiding' acceptance rule preserves element by element. Completing the loop back to rationing, the reduction of Lemma 2.2 uses concavity of the expected-minimum function in the remaining supply, whose worst case is a bimodal distribution on $\\{0, 1\\}$, together with the FKG inequality, to convert expected allocation into expected service for Type-III targets.","core_discovery":"The paper's central discovery is a tight characterization of what the forward-backward arrival model can do for contention resolution. For single-unit selection, the best guarantee an instance can offer is captured by a small linear program that assigns each element separate acceptance probabilities under the forward and backward orders, subject to the constraint that accepting an element rules out every earlier arrival under the same order. The authors solve the continuous limit of this program with a piecewise exponential function $\\phi(z) = (2e^{\\rho/2} - e^z)/(1 + e^{\\rho/2}\\rho)$ on $[0, \\rho/2]$ and $\\phi(z) = e^{\\rho-z}/(1 + e^{\\rho/2}\\rho)$ on $(\\rho/2, \\rho]$, whose defining identities $\\phi(z) + \\phi(\\rho - z) = 2\\alpha_0$ and $\\phi(z) \\le 1 - \\int_0^z \\phi(\\tau)\\,d\\tau$ mirror the program's objective and constraints as element sizes vanish. They prove that averaging $\\phi$ over each element's interval in the arrival order yields feasible acceptance probabilities on every finite instance, and that the program's dual — built from the function $\\gamma(z) = \\rho e^{z-\\rho/2}/(2(1 + e^{\\rho/2}\\rho))$, augmented by a spike at the middle element to bridge finite-$n$ discreteness — matches the same value up to a vanishing error. The consequence is an exact frontier $\\exp(\\rho/2)/(1 + \\exp(\\rho/2)\\rho)$ for every total mass $\\rho$, and, for knapsack constraints, a linear $\\phi(z) = 4/9 - 2z/9$ fed into a '0-avoiding' algorithm that prefers filling already-open capacity, yielding the $1/3$ selection guarantee and the $1/(2+e^{-1})$ ceiling.","pith_inferences":["If the same LP-to-continuum method transfers to $k$-unit, matroid, or matching constraints, the forward-backward model would supply a full interpolation spectrum between the adversarial $1/2$ and the random-order $1-1/e$; the paper raises this question without claiming it.","The gap between the golden-ratio constant $(\\sqrt{5}-1)/2$ for static thresholds and $0.622$ for unrestricted schemes suggests adaptivity is worth roughly 0.4 percentage points in two-order models — a prediction one could test by computing the optimal threshold-policy constant on small instances and comparing it with the LP optimum.","The knapsack window between the $1/3$ lower bound and the $1/(2+e^{-1}) \\approx 0.422$ ceiling is the most direct open problem; the single-unit-style LP analysis is not yet available for knapsack feasibility, so the true worst-case constant is unknown.","A practical extension is to check the independence premise on real pantry demand data: if daily shocks across locations are approximately independent, the $0.622$ guarantee becomes an operational commitment, and if not, the FKG step of the reduction is the first place the proof would break."],"forward_implications":["For single-unit rationing under Type-II or Type-III service, the forward-backward model guarantees each agent at least $1/(1+e^{-1/2}) \\approx 0.622$ of its service target, improving the two-order prophet inequality from $(\\sqrt{5}-1)/2 \\approx 0.618$ to $0.622$.","The guarantee is exactly tight: no single-unit FB-CRS can beat $\\exp(\\rho/2)/(1+\\exp(\\rho/2)\\rho)$ for total arrival probability $\\rho$, so this exponential curve is the full power of the model.","For Type-I all-or-nothing service, which requires knapsack constraints, the forward-backward scheme achieves $1/3$, better than the $1/(3+e^{-2}) \\approx 0.319$ tight single-order bound and, to the authors' knowledge, the best guarantee known even in the offline setting.","No knapsack FB-CRS can exceed $1/(2+e^{-1}) \\approx 0.422$, so the two-order model is strictly weaker for knapsack than the random-order model, whose corresponding upper bound is $(1-e^{-2})/2 \\approx 0.432$.","Every result converts into an online rationing policy via the paper's reduction: an $\\alpha$-selectable CRS delivers per-agent expected service at least $\\alpha$ times any ex-ante feasible service vector, uniformly across Type-I, II, and III service."],"supporting_citations":[{"why":"Supplies the best-possible 1/2 single-order guarantee that forward-backward selection must beat, along with the LP-based analysis style for single-unit CRS.","marker":"[Ala14]"},{"why":"Gives the 1−1/e random-order guarantee and the ex-ante prophet inequality framework from which the paper's result is separated.","marker":"[LS18]"},{"why":"Introduces the two-order (forward-backward) prophet inequality with ratio (√5−1)/2 that the new CRS guarantee improves upon, and motivates the arrival model.","marker":"[ADK21]"},{"why":"Provides the tight 1/(3+e^{-2}) single-order knapsack guarantee, the hard instance reused for the upper bound, and the invariant-based induction underlying the knapsack algorithm.","marker":"[JMZ22]"},{"why":"Establishes the online CRS framework and the standard reduction from CRS guarantees to prophet inequalities that the applications rely on.","marker":"[FSZ21]"},{"why":"Defines the original offline contention resolution model that the knapsack results are compared against.","marker":"[CVZ14]"},{"why":"Characterizes offline service feasibility for Type-I/II/III rationing, the baseline that the forward-backward online reduction extends.","marker":"[JWZ23]"},{"why":"Introduces online rationing with Type-III service and the mobile food pantry application that motivates the forward-backward order.","marker":"[LIS14]"}],"fun_headline_variants":["Reversible order lifts rationing guarantee to tight 0.622","0.622 tight: two-order CRS beats one-order bound","Two-order fair rationing hits 0.622, knapsack gets 1/3","Forward-backward CRS: 0.622 tight, best for rank-1 matroids"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central guarantee rests on two premises: each agent's demand is drawn independently from a known distribution, and the forward-backward order is independent of the demands and known to the algorithm in advance; the reduction from rationing to contention resolution and the FKG-based service bound fail without them. A secondary premise the authors flag explicitly is that the algorithm can track or sample the distribution of remaining supply, which Remarks 3 and 7 delegate to sampling and discretization, so the delivered guarantee is only as strong as that approximation.","fun_headline_variants_meta":{"raw":{"variants":["Reversible order lifts rationing guarantee to tight 0.622","0.622 tight: two-order CRS beats one-order bound","Two-order fair rationing hits 0.622, knapsack gets 1/3","Forward-backward CRS: 0.622 tight, best for rank-1 matroids"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000246,"raw_usage":{"total_tokens":1752,"prompt_tokens":1373,"completion_tokens":379,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":989,"completion_tokens_details":{"reasoning_tokens":292}},"tokens_in":989,"tokens_out":379,"duration_ms":4537,"temperature":1.0,"reasoning_tokens":292,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T21:10:27.050404+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve the LP-SI program by linear programming on arbitrary single-unit inputs with total probability $\\rho = 1$ and a few dozen elements; the paper's tightness claim asserts that the optimal value never exceeds $1/(1+e^{-1/2}) \\approx 0.622$, so the first instance whose LP optimum is larger refutes the central result. On the algorithmic side, sample Algorithm 3 on any knapsack instance with deterministic sizes summing to 1 and measure each element's conditional acceptance probability: a value below $1/3$ refutes the knapsack guarantee, while a single-unit instance with total probability 2 whose simulated acceptance probability exceeds $1/(2+e^{-1}) \\approx 0.422$ refutes the upper bound.","supporting_citations":[],"review_version":1}