# No-Regret Learning for Fair Multi-Agent Social Welfare Optimization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 44 references that are in the map.
- First posted on arXiv 31 May 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [Bandit Convex Optimisation](https://mlsanity.com/paper/2402.06535/) (2024)
- [Fairness and Welfare Quantification for Regret in Multi-Armed Bandits](https://mlsanity.com/paper/2205.13930/) (2022)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [Finding Fair and Efficient Allocations](https://mlsanity.com/paper/1707.04731/) (2017)
- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings](https://mlsanity.com/paper/1912.12541/) (2019)
- [Estimating the Nash Social Welfare for coverage and other submodular valuations](https://mlsanity.com/paper/2101.02278/) (2021)

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

- [p-Mean Regret for Stochastic Bandits](https://mlsanity.com/paper/2412.10751/) (2024)
- [Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need](https://mlsanity.com/paper/2510.21312/) (2025)
- [Bandit Max-Min Fair Allocation](https://mlsanity.com/paper/2505.05169/) (2025)
- [Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization](https://mlsanity.com/paper/2605.06864/) (2026)
- [Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairness](https://mlsanity.com/paper/2502.15240/) (2025)
- [Procedural Fairness in Multi-Agent Bandits](https://mlsanity.com/paper/2601.10600/) (2026)
- [Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfare](https://mlsanity.com/paper/2605.01961/) (2026)
- [Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret](https://mlsanity.com/paper/2610.07737/) (2026)

## Abstract (arXiv)

We consider the problem of online multi-agent Nash social welfare (NSW) maximization. While previous works of Hossain et al. [2021], Jones et al. [2023] study similar problems in stochastic multi-agent multi-armed bandits and show that √T-regret is possible after T rounds, their fairness measure is the product of all agents' rewards, instead of their NSW (that is, their geometric mean). Given the fundamental role of NSW in the fairness literature, it is more than natural to ask whether no-regret fair learning with NSW as the objective is possible. In this work, we provide a complete answer to this question in various settings. Specifically, in stochastic N-agent K-armed bandits, we develop an algorithm with widetildeOleft(K^frac2NT^fracN-1Nright) regret and prove that the dependence on T is tight, making it a sharp contrast to the √T-regret bounds of Hossain et al. [2021], Jones et al. [2023]. We then consider a more challenging version of the problem with adversarial rewards. Somewhat surprisingly, despite NSW being a concave function, we prove that no algorithm can achieve sublinear regret. To circumvent such negative results, we further consider a setting with full-information feedback and design two algorithms with √T-regret: the first one has no dependence on N at all and is applicable to not just NSW but a broad class of welfare functions, while the second one has better dependence on K and is preferable when N is small. Finally, we also show that logarithmic regret is possible whenever there exists one agent who is indifferent about different arms.