Sequential Fair Allocation With Replenishments: A Little Envy Goes An Exponentially Long Way
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914014027579392 |
|---|---|
| author | Onyeze, Chido Sinclair, Sean R. Hssaine, Chamsi Banerjee, Siddhartha |
| author_facet | Onyeze, Chido Sinclair, Sean R. Hssaine, Chamsi Banerjee, Siddhartha |
| contents | 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, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21753 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sequential Fair Allocation With Replenishments: A Little Envy Goes An Exponentially Long Way Onyeze, Chido Sinclair, Sean R. Hssaine, Chamsi Banerjee, Siddhartha Optimization and Control Computer Science and Game Theory Probability 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, 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. |
| title | Sequential Fair Allocation With Replenishments: A Little Envy Goes An Exponentially Long Way |
| topic | Optimization and Control Computer Science and Game Theory Probability |
| url | https://arxiv.org/abs/2508.21753 |