# Stochastic Bandits for Egalitarian Assignment

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 37 references that are in the map.
- First posted on arXiv 8 Oct 2024.

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

- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [Concurrent bandits and cognitive radio networks](https://mlsanity.com/paper/1404.5421/) (2014)
- [Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing](https://mlsanity.com/paper/1801.10242/) (2018)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Presentation of a Recommender System with Ensemble Learning and Graph Embedding: A Case on MovieLens](https://mlsanity.com/paper/2008.01192/) (2020)
- [Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms](https://mlsanity.com/paper/2206.08776/) (2022)

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

- [PAK-UCB Contextual Bandit: An Online Learning Approach to Prompt-Aware Selection of Generative Models and LLMs](https://mlsanity.com/paper/2410.13287/) (2024)
- [Fairness in Repeated Matching: A Maximin Perspective](https://mlsanity.com/paper/2510.04624/) (2025)
- [Online Social Welfare Function-based Resource Allocation](https://mlsanity.com/paper/2602.01400/) (2026)
- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)

## Abstract (arXiv)

We study EgalMAB, an egalitarian assignment problem in the context of stochastic multi-armed bandits. In EgalMAB, an agent is tasked with assigning a set of users to arms. At each time step, the agent must assign exactly one arm to each user such that no two users are assigned to the same arm. Subsequently, each user obtains a reward drawn from the unknown reward distribution associated with its assigned arm. The agent's objective is to maximize the minimum expected cumulative reward among all users over a fixed horizon. This problem has applications in areas such as fairness in job and resource allocations, among others. We design and analyze a UCB-based policy EgalUCB and establish upper bounds on the cumulative regret. In complement, we establish an almost-matching policy-independent impossibility result.