# Fair Algorithms for Multi-Agent Multi-Armed Bandits

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2020.

## Built on by (most cited first, 30 of 41)

- [Multi-agent Dynamic Algorithm Configuration](https://mlsanity.com/paper/2210.06835/) (2022)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [Runtime Monitoring of Dynamic Fairness Properties](https://mlsanity.com/paper/2305.04699/) (2023)
- [Socially Fair Reinforcement Learning](https://mlsanity.com/paper/2208.12584/) (2022)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [Online Approval Committee Elections](https://mlsanity.com/paper/2202.06830/) (2022)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learning](https://mlsanity.com/paper/2306.00324/) (2023)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [On-Demand Communication for Asynchronous Multi-Agent Bandits](https://mlsanity.com/paper/2302.07446/) (2023)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [p-Mean Regret for Stochastic Bandits](https://mlsanity.com/paper/2412.10751/) (2024)
- [Decentralized Task Offloading in Edge Computing: A Multi-User Multi-Armed Bandit Approach](https://mlsanity.com/paper/2112.11818/) (2021)
- [Federated Linear Contextual Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2403.00116/) (2024)
- [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (2024)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Stochastic Bandits for Egalitarian Assignment](https://mlsanity.com/paper/2410.05856/) (2024)
- [Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need](https://mlsanity.com/paper/2510.21312/) (2025)
- [Ranked Prioritization of Groups in Combinatorial Bandit Allocation](https://mlsanity.com/paper/2205.05659/) (2022)
- [Fair Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2408.17313/) (2024)
- [Bandit Learning to Rank with Position-Based Click Models: Personalized and Equal Treatments](https://mlsanity.com/paper/2311.04528/) (2023)
- [Beyond Predictions: A Participatory Framework for Multi-Stakeholder Decision-Making](https://mlsanity.com/paper/2502.08542/) (2025)
- [Fairness and Privacy Guarantees in Federated Contextual Bandits](https://mlsanity.com/paper/2402.03531/) (2024)
- [Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits](https://mlsanity.com/paper/2402.05575/) (2024)
- [A Note on Bias to Complete](https://mlsanity.com/paper/2402.11710/) (2024)
- [Intuitions of Compromise: Utilitarianism vs. Contractualism](https://mlsanity.com/paper/2410.05496/) (2024)
- [QuACK: A Multipurpose Queuing Algorithm for Cooperative k-Armed Bandits](https://mlsanity.com/paper/2410.23867/) (2024)
- [Fairness in Reinforcement Learning with Bisimulation Metrics](https://mlsanity.com/paper/2412.17123/) (2024)

## Abstract (arXiv)

We propose a multi-agent variant of the classical multi-armed bandit problem, in which there are N agents and K arms, and pulling an arm generates a (possibly different) stochastic reward for each agent. Unlike the classical multi-armed bandit problem, the goal is not to learn the "best arm"; indeed, each agent may perceive a different arm to be the best for her personally. Instead, we seek to learn a fair distribution over the arms. Drawing on a long line of research in economics and computer science, we use the Nash social welfare as our notion of fairness. We design multi-agent variants of three classic multi-armed bandit algorithms and show that they achieve sublinear regret, which is now measured in terms of the lost Nash social welfare.