mlsanityData to 7 Oct 2026

Fair Algorithms for Multi-Agent Multi-Armed Bandits

arXiv 2007.06699 ↗First posted 13 Jul 2020cs.GT cs.AIcited by 41

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 7; 2023: 8; 2024: 13; 2025: 7; 2026: 5.

41 papers.

Sort:

By area:

  1. 2022Multi-agent Dynamic Algorithm Configurationcited by 36
  2. 2022Fairness and Welfare Quantification for Regret in Multi-Armed Banditscited by 17
  3. 2023Runtime Monitoring of Dynamic Fairness Propertiescited by 17
  4. 2022Socially Fair Reinforcement Learningcited by 13
  5. 2022An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regretcited by 10
  6. 2022Online Approval Committee Electionscited by 9
  7. 2023Nash Regret Guarantees for Linear Banditscited by 9
  8. 2022Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Banditscited by 8
  9. 2023Learning with Exposure Constraints in Recommendation Systemscited by 8
  10. 2023Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learningcited by 8
  11. 2024No-Regret Learning for Fair Multi-Agent Social Welfare Optimizationcited by 7
  12. 2023On-Demand Communication for Asynchronous Multi-Agent Banditscited by 6
29 more
  1. 2023BanditQ: Fair Bandits with Guaranteed Rewardscited by 6
  2. 2024p-Mean Regret for Stochastic Banditscited by 6
  3. 2021Decentralized Task Offloading in Edge Computing: A Multi-User Multi-Armed Bandit Approachcited by 5
  4. 2024Fair Online Bilateral Tradecited by 4
  5. 2024Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copiescited by 4
  6. 2024Stochastic Bandits for Egalitarian Assignmentcited by 4
  7. 2022Ranked Prioritization of Groups in Combinatorial Bandit Allocationcited by 3
  8. 2024Federated Linear Contextual Bandits with Heterogeneous Clientscited by 3
  9. 2024Fair Best Arm Identification with Fixed Confidencecited by 3
  10. 2025Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Needcited by 3
  11. 2023Bandit Learning to Rank with Position-Based Click Models: Personalized and Equal Treatmentscited by 2
  12. 2025Beyond Predictions: A Participatory Framework for Multi-Stakeholder Decision-Makingcited by 2
  13. 2024Fairness and Privacy Guarantees in Federated Contextual Banditscited by 1
  14. 2024Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Banditscited by 1
  15. 2024A Note on Bias to Completecited by 1
  16. 2024Intuitions of Compromise: Utilitarianism vs. Contractualismcited by 1
  17. 2024QuACK: A Multipurpose Queuing Algorithm for Cooperative k-Armed Banditscited by 1
  18. 2024Fairness in Reinforcement Learning with Bisimulation Metricscited by 1
  19. 2025Bandit Max-Min Fair Allocationcited by 1
  20. 2025Fair Algorithms with Probing for Multi-Agent Multi-Armed Banditscited by 1
  21. 2025Your Recourse, My Loss? Algorithmic Recourse under Shared Constraintscited by 1
  22. 2026Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimizationcited by 1
  23. 2023Disincentivizing Polarization in Social Networkscited by 0
  24. 2025Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairnesscited by 0
  25. 2025Fairness in the Multi-Secretary Problemcited by 0
  26. 2026Procedural Fairness in Multi-Agent Banditscited by 0
  27. 2026Envy-Free Allocation of Indivisible Goods via Noisy Queriescited by 0
  28. 2026Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfarecited by 0
  29. 2026The Optimization Trilemma: Efficiency, Comfort and Fairness in Decentralized Multi-agent Coordinationcited by 0