# Sequential Fair Allocation of Limited Resources under Stochastic Demands

arXiv: https://arxiv.org/abs/2011.14382 · HTML: https://mlsanity.com/paper/2011.14382/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2020.

## Built on by (most cited first, 4 of 4)

- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Sequential Fair Resource Allocation under a Markov Decision Process Framework](https://mlsanity.com/paper/2301.03758/) (2023)
- [Time Fairness in Online Knapsack Problems](https://mlsanity.com/paper/2305.13293/) (2023)
- [Fair Resource Allocation for Demands with Sharp Lower Tail Inequalities](https://mlsanity.com/paper/2101.12403/) (2021)

## Abstract (arXiv)

We consider the problem of dividing limited resources between a set of agents arriving sequentially with unknown (stochastic) utilities. Our goal is to find a fair allocation - one that is simultaneously Pareto-efficient and envy-free. When all utilities are known upfront, the above desiderata are simultaneously achievable (and efficiently computable) for a large class of utility functions. In a sequential setting, however, no policy can guarantee these desiderata simultaneously for all possible utility realizations. A natural online fair allocation objective is to minimize the deviation of each agent's final allocation from their fair allocation in hindsight. This translates into simultaneous guarantees for both Pareto-efficiency and envy-freeness. However, the resulting dynamic program has state-space which is exponential in the number of agents. We propose a simple policy, HopeOnline, that instead aims to `match' the ex-post fair allocation vector using the current available resources and `predicted' histogram of future utilities. We demonstrate the effectiveness of our policy compared to other heurstics on a dataset inspired by mobile food-bank allocations.