Sequential Fair Allocation With Replenishments: A Little Envy Goes An Exponentially Long Way
ACM SIGMETRICS Performance Evaluation Review · 20.07.2026 · 54 (1) · 79-81
DOI: 10.1145/3820171.3806858 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 27.07.2026. Verfasst von Chido Onyeze und 3 weiteren Autor:innen. Die Arbeit nennt 11 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF (National Science Foundation), Cornell Engineering.
Abstract (Originalsprache)
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 Δ > 0, where Δ is used to denote the target envy of the policy. We complement this with matching lower bounds. 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.
Förderung
- NSF (National Science Foundation)
- Cornell Engineering
Zitieren
APA
Onyeze, C., Sinclair, S. R., Hssaine, C., & Banerjee, S. (2026). Sequential Fair Allocation With Replenishments: A Little Envy Goes An Exponentially Long Way. ACM SIGMETRICS Performance Evaluation Review, 54(1), 79-81. https://doi.org/10.1145/3820171.3806858
Vancouver
Onyeze C, Sinclair SR, Hssaine C, Banerjee S. Sequential Fair Allocation With Replenishments: A Little Envy Goes An Exponentially Long Way. ACM SIGMETRICS Performance Evaluation Review. 2026;54(1):79-81. doi:10.1145/3820171.3806858
BibTeX
@article{Onyeze2026,
author = {Onyeze, Chido and Sinclair, Sean R. and Hssaine, Chamsi and Banerjee, Siddhartha},
title = {Sequential Fair Allocation With Replenishments: A Little Envy Goes An Exponentially Long Way},
journal = {ACM SIGMETRICS Performance Evaluation Review},
year = {2026},
volume = {54},
number = {1},
pages = {79--81},
doi = {10.1145/3820171.3806858}
}
EUVIMED