{"ID":2876836,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.21753","arxiv_id":"2508.21753","title":"Sequential Fair Allocation With Replenishments: A Little Envy Goes An Exponentially Long Way","abstract":"We study the trade-off between envy and inefficiency in repeated resource allocation settings with stochastic replenishments, motivated by real-world systems such as food banks and medical supply chains. Specifically, we consider a model in which a decision-maker faced with stochastic demand and resource donations must trade off between an equitable and efficient allocation of resources over an infinite horizon. The decision-maker has access to storage with fixed capacity $M$, and incurs efficiency losses when storage is empty (stockouts) or full (overflows). We provide a nearly tight (up to constant factors) characterization of achievable envy-inefficiency pairs. Namely, we introduce a class of Bang-Bang control policies whose inefficiency exhibits a sharp phase transition, dropping from $Θ(1/M)$ when $Δ= 0$ to $e^{-Ω(ΔM)}$ when $Δ\u003e 0$, where $Δ$ is used to denote the target envy of the policy. We complement this with matching lower bounds, demonstrating that the trade-off is driven by supply, as opposed to demand uncertainty. Our results demonstrate that envy-inefficiency trade-offs not only persist in settings with dynamic replenishment, but are shaped by the decision-maker's available capacity, and are therefore qualitatively different compared to previously studied settings with fixed supply.","short_abstract":"We study the trade-off between envy and inefficiency in repeated resource allocation settings with stochastic replenishments, motivated by real-world systems such as food banks and medical supply chains. Specifically, we consider a model in which a decision-maker faced with stochastic demand and resource donations must...","url_abs":"https://arxiv.org/abs/2508.21753","url_pdf":"https://arxiv.org/pdf/2508.21753v1","authors":"[\"Chido Onyeze\",\"Sean R. Sinclair\",\"Chamsi Hssaine\",\"Siddhartha Banerjee\"]","published":"2025-08-29T16:28:09Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.GT\",\"math.PR\"]","methods":"[]","has_code":false}