Forward-backward Contention Resolution Schemes for Fair Rationing

Calum MacRury; Cliff Stein; Will Ma

Forward-backward Contention Resolution Schemes for Fair Rationing

T0 review · 0 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2502.09521 v1 pith:QZN6FFDJ submitted 2025-02-13 cs.DS cs.DM

Will Ma , Calum MacRury , Cliff Stein This is my paper · ORCID

classification cs.DScs.DM MSC 68W2768W2090C2791B32

keywords contentionresolutionschemesfairrationingforward-backwardarrivalorderprophetinequalitiesrank-1matroidknapsackconstraintsonlineresourceallocationex-antefairness

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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

The 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.

Soft 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.

Who 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.

Referee Report

0 major / 4 minor

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.

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.

minor comments (4)

[Lemma 3.5, Eqs. (3.21)-(3.22)] 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.
[Lemma 2.2, Type-III case, Eqs. (2.10)-(2.11)] 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.
[Remarks 3 and 7] 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.
[Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the CRS guarantees are proved from explicit feasible primal/dual solutions, with no fitted parameter renamed as a prediction.

full rationale

The paper's central claims are self-contained. Theorem 1.2 is established by explicitly constructing an LP-SI feasible solution (3.7) from the continuous certificate φ (3.4), verifying feasibility via (3.9)-(3.10) and the integral identity (3.5); the guarantee is then realized by Algorithm 2 whose acceptance probability is shown to equal the LP solution (Lemma 3.1, Appendix B.1). Theorem 1.3 is proven by weak duality on the same LP: the dual solution (3.16) is certified feasible in Lemma 3.5 using only properties of γ (Proposition 3.6) and the α0 identity (3.19). Theorem 1.4 uses the same constructive pattern: feasible selection probabilities (4.18) are built from φ (4.14) and certified against Definition 5 in Lemma 4.4, then implemented by Algorithm 3 with the induction deferred to Appendix C.1. The induction is adapted from [JMZ22], but the proof is reproduced rather than merely cited, so the self-citation is not load-bearing. Theorem 1.5 reduces the knapsack upper bound to the single-unit bound on the same instance as [JMZ22]; this is a benchmark input, not an assumption that entails the conclusion. The reduction of Section 2 is also non-circular: τi is calibrated to reproduce cσ(i)xi by the mean value theorem (2.8), and the service guarantee is derived from FKG and rearrangement inequalities rather than imposed. Minor issues, such as a possible +3/N versus +2/N in Lemma 3.5, sampling details in Remarks 3 and 7, and the 0/0 convention for Type-III service at zero demand, affect implementation and edge-case rigor but do not make any equation equal its own conclusion.

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

The central results are derived from a small set of modeling assumptions and standard inequalities; no free parameters are fitted to data, and the paper does not introduce new unobserved entities.

assumptions (3)

domain assumption Agent demands Di are independent and drawn from known distributions Fi.
Definition 1 and the CRS reduction rely on independent activeness and sizes; the FKG inequality applications in Lemma 2.2 and the selection-probability calculations require independence.
domain assumption The arrival order Λ is independent of demands and uniformly distributed over the forward permutation f and its reverse b, and is revealed to the algorithm before arrivals.
Section 1.2 defines FB-CRS on this model; all guarantees are conditional on this exact order distribution, and results would change under adversarial or independent-random-order models.
standard math Standard inequalities (FKG, rearrangement, LP duality, mean value theorem) are valid.
Used in proofs of Lemma 2.2, Lemma 3.3, and Theorem 3.4; no unproved custom lemmas beyond standard tools.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Forward-backward Contention Resolution Schemes for Fair Rationing." pith.science (2026). https://pith.science/paper/QZN6FFDJ

@misc{pith2026250209521,
  author       = {Pith},
  title        = {Pith review of: Forward-backward Contention Resolution Schemes for Fair Rationing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QZN6FFDJ}},
  note         = {Machine review of arXiv:2502.09521}
}

abstract

We use contention resolution schemes (CRS) to derive algorithms for the fair rationing of a single resource when agents have stochastic demands. We aim to provide ex-ante guarantees on the level of service provided to each agent, who may measure service in different ways (Type-I, II, or III), calling for CRS under different feasibility constraints (rank-1 matroid or knapsack). We are particularly interested in two-order CRS where the agents are equally likely to arrive in a known forward order or its reverse, which is motivated by online rationing at food banks. In particular, we derive a two-order CRS for rank-1 matroids with guarantee $1/(1+e^{-1/2})\approx 0.622$, which we prove is tight. This improves upon the $1/2$ guarantee that is best-possible under a single order (Alaei, SIAM J. Comput. 2014), while achieving separation with the $1-1/e\approx 0.632$ guarantee that is possible for random-order CRS (Lee and Singla, ESA 2018). Because CRS guarantees imply prophet inequalities, this also beats the two-order prophet inequality with ratio $(\sqrt{5}-1)/2\approx 0.618$ from (Arsenis, SODA 2021), which was tight for single-threshold policies. Rank-1 matroids suffice to provide guarantees under Type-II or III service, but Type-I service requires knapsack. Accordingly, we derive a two-order CRS for knapsack with guarantee $1/3$, improving upon the $1/(3+e^{-2})\approx 0.319$ guarantee that is best-possible under a single order (Jiang et al., SODA 2022). To our knowledge, $1/3$ provides the best-known guarantee for knapsack CRS even in the offline setting. Finally, we provide an upper bound of $1/(2+e^{-1})\approx 0.422$ for two-order knapsack CRS, strictly smaller than the upper bound of $(1-e^{-2})/2\approx0.432$ for random-order knapsack CRS.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 15 canonical work pages

[1]

[ACK18] Yossi Azar, Ashish Chiplunkar, and Haim Kaplan, Prophet secretary: Surpassing the 1-1/e barrier , Proceedings of the 2018 ACM Conference on Economics and Com pu- tation (New York, NY, USA), EC ’18, Association for Computin g Machinery, 2018, p. 303–318. [ADK21] Makis Arsenis, Odysseas Drosis, and Robert Kleinbe rg, Constrained-order prophet inequa...

work page 2018
[10]

27 [GN13] Anupam Gupta and Viswanath Nagarajan, A stochastic probing problem with appli- cations, Integer Programming and Combinatorial Optimization - 16t h International Conference, IPCO 2013, Valpara´ ıso, Chile, March 18-20,

work page 2013
[15]

[PT22] Bo Peng and Zhihao Gavin Tang, Order selection prophet inequality: From threshold optimization to arrival time design , 2022 IEEE 63rd Annual Symposium on Founda- tions of Computer Science (FOCS) (2022), 171–178. [PW24] Neel Patel and David Wajc, Combinatorial stationary prophet inequalities, Proceedings of the 2024 ACM-SIAM Symposium on Discrete A...

work page 2022
[16]

[SC84] Ester Samuel-Cahn, Comparison of threshold stop rules and maximum for independe nt nonnegative random variables , the Annals of Probability (1984), 1213–1216. [SJBY23] Sean R Sinclair, Gauri Jain, Siddhartha Banerjee, and Christina Lee Yu, Sequen- tial fair allocation: Achieving the optimal envy-eﬃciency trade-oﬀ curve , Operations Research 71 (202...

work page 1984
[17]

4, 1555–1573

[ZZCT18] Yuanguang Zhong, Zhichao Zheng, Mabel C Chou, and C hung-Piaw Teo, Resource pooling and allocation policies to deliver diﬀerentiated s ervice, Management Science 64 (2018), no. 4, 1555–1573. 30 A Additions to Section 2 A.1 Proof of Lemma 2.1 Let βi = E[si(Yi, Di)] for all i. We set qi to the smallest value in [0,1] that makes (2.2) hold. To see t...

work page 2018
[245]

Mechanism Design via the Interim Relaxation

[Ala14] Saeed Alaei, Bayesian combinatorial auctions: Expanding single buyer m echanisms to many buyers , SIAM Journal on Computing 43 (2014), no. 2, 930–972. [AW18] Marek Adamczyk and Micha/suppress l W/suppress lodarczyk,Random order contention resolution schemes, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2018, pp....

work page Pith review arXiv 2014
[695]

[MXX20] Will Ma, Pan Xu, and Yifan Xu, Group-level fairness maximization in online bipartite matching, arXiv preprint arXiv:2011.13908 (2020). [NSW25] Joseph (Seﬃ) Naor, Aravind Srinivasan, and David Wa jc, Online dependent rounding schemes for bipartite matchings, with , Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025,...

arXiv 2020
[781]

2, 255–300

[FSZ21] Moran Feldman, Ola Svensson, and Rico Zenklusen, Online contention resolution schemes with applications to bayesian selection problems , SIAM Journal on Computing 50 (2021), no. 2, 255–300. [FTW+21] Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qian fan Zhang, Random order vertex arrival contention resolution schemes for mat ching, with ap...

work page 2021

Show all 17 references

[2007]

1946–1961,

[CSZ19] Jose Correa, Raimundo Saona, and Bruno Ziliotto, Prophet secretary through blind strategies, pp. 1946–1961,

1946
[2013]

Goemans and Jos´ e Correa, eds.), Lecture Notes in Computer S cience, vol

Proceedings (Michel X. Goemans and Jos´ e Correa, eds.), Lecture Notes in Computer S cience, vol. 7801, Springer, 2013, pp. 205–216. [Har13] Jason D Hartline, Mechanism design and approximation , Book draft. October 122 (2013), no

2013
[2018]

3, 789–812

[Ma18] Will Ma, Improvements and generalizations of stochastic knapsack an d markovian bandits approximation algorithms , Mathematics of Operations Research 43 (2018), no. 3, 789–812. [MM24] Calum MacRury and Will Ma, Random-order contention resolution via continuous induction...

2018 arXiv
[2019]

6, 1831–1879

[CVZ14] Chandra Chekuri, Jan Vondr´ ak, and Rico Zenklusen, Submodular function maximiza- tion via the multilinear relaxation and contention resolut ion schemes , SIAM Journal on Computing 43 (2014), no. 6, 1831–1879. [DKP24] Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel...

2014
[2020]

215, Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2022, pp

26 [Dug22] Shaddin Dughmi, Matroid secretary is equivalent to contention resolution, 13th Innova- tions in Theoretical Computer Science Conference, ITCS 202 2, January 31 - February 3, 2022, Berkeley, CA, USA (Mark Braverman, ed.), LIPIcs, vol. 215, Schloss Dagstuhl - Leibniz-...

2022
[2021]

[GHKL24] Anupam Gupta, Jinqiao Hu, Gregory Kehne, and Roie L evin, Pairwise-independent contention resolution, International Conference on Integer Programming and Comb i- natorial Optimization, Springer, 2024, pp. 196–209. [GMTS24] Giordano Giambartolomei, Frederik Mallmann-Tr...

2024
[2022]

1221–1246

[JMZ22] Jiashuo Jiang, Will Ma, and Jiawei Zhang, Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack , Proceedings of the 2022 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, p p. 1221–1246. [JWZ23] Jiashuo Jiang, Shixin W...

2023
[2024]

who is next in line?

[EFGT22] Tomer Ezra, Michal Feldman, Nick Gravin, and Zhiha o Gavin Tang, Prophet matching with general arrivals , Mathematics of Operations Research 47 (2022), no. 2, 878–898. [EFGT23] , “who is next in line?” on the signiﬁcance of knowing the arriv al order in bayesian onlin...

2022
[2025]

8, 1091–

[CL99] G´ erard P Cachon and Martin A Lariviere, Capacity choice and allocation: Strategic behavior and supply chain performance , Management science 45 (1999), no. 8, 1091–

1999

Pith tools

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

[1] [1]

[ACK18] Yossi Azar, Ashish Chiplunkar, and Haim Kaplan, Prophet secretary: Surpassing the 1-1/e barrier , Proceedings of the 2018 ACM Conference on Economics and Com pu- tation (New York, NY, USA), EC ’18, Association for Computin g Machinery, 2018, p. 303–318. [ADK21] Makis Arsenis, Odysseas Drosis, and Robert Kleinbe rg, Constrained-order prophet inequa...

work page 2018

[2] [10]

27 [GN13] Anupam Gupta and Viswanath Nagarajan, A stochastic probing problem with appli- cations, Integer Programming and Combinatorial Optimization - 16t h International Conference, IPCO 2013, Valpara´ ıso, Chile, March 18-20,

work page 2013

[3] [15]

[PT22] Bo Peng and Zhihao Gavin Tang, Order selection prophet inequality: From threshold optimization to arrival time design , 2022 IEEE 63rd Annual Symposium on Founda- tions of Computer Science (FOCS) (2022), 171–178. [PW24] Neel Patel and David Wajc, Combinatorial stationary prophet inequalities, Proceedings of the 2024 ACM-SIAM Symposium on Discrete A...

work page 2022

[4] [16]

[SC84] Ester Samuel-Cahn, Comparison of threshold stop rules and maximum for independe nt nonnegative random variables , the Annals of Probability (1984), 1213–1216. [SJBY23] Sean R Sinclair, Gauri Jain, Siddhartha Banerjee, and Christina Lee Yu, Sequen- tial fair allocation: Achieving the optimal envy-eﬃciency trade-oﬀ curve , Operations Research 71 (202...

work page 1984

[5] [17]

4, 1555–1573

[ZZCT18] Yuanguang Zhong, Zhichao Zheng, Mabel C Chou, and C hung-Piaw Teo, Resource pooling and allocation policies to deliver diﬀerentiated s ervice, Management Science 64 (2018), no. 4, 1555–1573. 30 A Additions to Section 2 A.1 Proof of Lemma 2.1 Let βi = E[si(Yi, Di)] for all i. We set qi to the smallest value in [0,1] that makes (2.2) hold. To see t...

work page 2018

[6] [245]

Mechanism Design via the Interim Relaxation

[Ala14] Saeed Alaei, Bayesian combinatorial auctions: Expanding single buyer m echanisms to many buyers , SIAM Journal on Computing 43 (2014), no. 2, 930–972. [AW18] Marek Adamczyk and Micha/suppress l W/suppress lodarczyk,Random order contention resolution schemes, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2018, pp....

work page Pith review arXiv 2014

[7] [695]

[MXX20] Will Ma, Pan Xu, and Yifan Xu, Group-level fairness maximization in online bipartite matching, arXiv preprint arXiv:2011.13908 (2020). [NSW25] Joseph (Seﬃ) Naor, Aravind Srinivasan, and David Wa jc, Online dependent rounding schemes for bipartite matchings, with , Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025,...

arXiv 2020

[8] [781]

2, 255–300

[FSZ21] Moran Feldman, Ola Svensson, and Rico Zenklusen, Online contention resolution schemes with applications to bayesian selection problems , SIAM Journal on Computing 50 (2021), no. 2, 255–300. [FTW+21] Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qian fan Zhang, Random order vertex arrival contention resolution schemes for mat ching, with ap...

work page 2021