# Online Max-min Fair Allocation

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

## Key facts

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

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

- [Bandit Max-Min Fair Allocation](https://mlsanity.com/paper/2505.05169/) (2025)

## Abstract (arXiv)

We study an online version of the max-min fair allocation problem for indivisible items. In this problem, items arrive one by one, and each item must be allocated irrevocably on arrival to one of n agents, who have additive valuations for the items. Our goal is to make the least happy agent as happy as possible. In research on the topic of online allocation, this is a fundamental and natural problem. Our main result is to reveal the asymptotic competitive ratios of the problem for both the adversarial and i.i.d. input models. We design a polynomial-time deterministic algorithm that is asymptotically 1/n-competitive for the adversarial model, and we show that this guarantee is optimal. To this end, we present a randomized algorithm with the same competitive ratio first and then derandomize it. A natural derandomization fails to achieve the competitive ratio of 1/n. We instead build the algorithm by introducing a novel technique. When the items are drawn from an unknown identical and independent distribution, we construct a simple polynomial-time deterministic algorithm that outputs a nearly optimal allocation. We analyze the strict competitive ratio and show almost tight bounds for the solution. We further mention some implications of our results on variants of the problem.