Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2605.03436 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918483005014016 |
|---|---|
| author | Averbakh, Igor Jiang, Hongyi Samaranayake, Samitha Wang, Akang Wu, Jianghua |
| author_facet | Averbakh, Igor Jiang, Hongyi Samaranayake, Samitha Wang, Akang Wu, Jianghua |
| contents | Allocating scarce, indivisible resources to diverse groups under uncertainty is a central challenge in operations research, where efficiency-focused methods often underserve marginalized populations. We study the Fair Online Resource Allocation with Indivisible Units (FORA-IU) problem, in which an unpredictable sequence of demands must be served from a strictly fixed inventory, and ask what fairness guarantees are achievable under different distributional and structural assumptions.
We adopt a fairness criterion based on the expected filling ratio (FE-FR-beta), which balances each group's expected allocation against its expected demand and priority weight. We design online policies that calibrate acceptance probabilities to the remaining budget, analyze both arbitrary time-varying and stationary arrivals, introduce the Random Cyclic Blocks (RCB) algorithm tailored to the stationary case, and study the effect of restricting policies to all-or-nothing allocations.
For arbitrary time-varying arrivals, our policy achieves the optimal universal fairness guarantee of 1/(1+R_beta), where R_beta denotes the priority-weighted system load. For time-invariant arrivals, RCB achieves the exact finite-horizon guarantee [1-(1-R_beta/T)^T]/R_beta, which is at least (1-e^{-R_beta})/R_beta and is also tight. We further show that all-or-nothing allocation policies cannot match these guarantees.
These findings demonstrate that distributional stationarity strictly improves the fairness frontier, and that partial fulfillment is a necessary condition for attaining optimal fairness in online indivisible resource allocation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03436 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Promoting Fair Online Resource Allocation with Indivisible Units Averbakh, Igor Jiang, Hongyi Samaranayake, Samitha Wang, Akang Wu, Jianghua Optimization and Control 68W27, 91B32 Allocating scarce, indivisible resources to diverse groups under uncertainty is a central challenge in operations research, where efficiency-focused methods often underserve marginalized populations. We study the Fair Online Resource Allocation with Indivisible Units (FORA-IU) problem, in which an unpredictable sequence of demands must be served from a strictly fixed inventory, and ask what fairness guarantees are achievable under different distributional and structural assumptions. We adopt a fairness criterion based on the expected filling ratio (FE-FR-beta), which balances each group's expected allocation against its expected demand and priority weight. We design online policies that calibrate acceptance probabilities to the remaining budget, analyze both arbitrary time-varying and stationary arrivals, introduce the Random Cyclic Blocks (RCB) algorithm tailored to the stationary case, and study the effect of restricting policies to all-or-nothing allocations. For arbitrary time-varying arrivals, our policy achieves the optimal universal fairness guarantee of 1/(1+R_beta), where R_beta denotes the priority-weighted system load. For time-invariant arrivals, RCB achieves the exact finite-horizon guarantee [1-(1-R_beta/T)^T]/R_beta, which is at least (1-e^{-R_beta})/R_beta and is also tight. We further show that all-or-nothing allocation policies cannot match these guarantees. These findings demonstrate that distributional stationarity strictly improves the fairness frontier, and that partial fulfillment is a necessary condition for attaining optimal fairness in online indivisible resource allocation. |
| title | Promoting Fair Online Resource Allocation with Indivisible Units |
| topic | Optimization and Control 68W27, 91B32 |
| url | https://arxiv.org/abs/2605.03436 |