# Bandit Max-Min Fair Allocation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 8 May 2025.

## Builds on (most cited first, 13 of 13)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Online Fair Division: A Survey](https://mlsanity.com/paper/1911.09488/) (2019)
- [Online Nash Social Welfare Maximization with Predictions](https://mlsanity.com/paper/2008.03564/) (2020)
- [Universal and Tight Online Algorithms for Generalized-Mean Welfare](https://mlsanity.com/paper/2109.00874/) (2021)
- [Repeated Fair Allocation of Indivisible Items](https://mlsanity.com/paper/2304.01644/) (2023)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [Online Algorithms for the Santa Claus Problem](https://mlsanity.com/paper/2210.07333/) (2022)
- [Online Max-min Fair Allocation](https://mlsanity.com/paper/2111.07235/) (2021)

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

- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)

## Abstract (arXiv)

In this paper, we study a new decision-making problem called the bandit max-min fair allocation (BMMFA) problem. The goal of this problem is to maximize the minimum utility among agents with additive valuations by repeatedly assigning indivisible goods to them. One key feature of this problem is that each agent's valuation for each item can only be observed through the semi-bandit feedback, while existing work supposes that the item values are provided at the beginning of each round. Another key feature is that the algorithm's reward function is not additive with respect to rounds, unlike most bandit-setting problems. Our first contribution is to propose an algorithm that has an asymptotic regret bound of O(m√Tln T/n + m√T ln(mnT)), where n is the number of agents, m is the number of items, and T is the time horizon. This is based on a novel combination of bandit techniques and a resource allocation algorithm studied in the literature on competitive analysis. Our second contribution is to provide the regret lower bound of Omega(m√T/n). When T is sufficiently larger than n, the gap between the upper and lower bounds is a logarithmic factor of T.