Conference proceeding
No-Regret Learning for Fair Multi-Agent Social Welfare Optimization
Advances in Neural Information Processing Systems 37 - 38th Conference on Neural Information Processing Systems, NeurIPS 2024, Vol.37
2024
Abstract
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 $\widetilde{\mathcal{O}}(K^{\frac{2}{N}}T^{\frac{N-1}{N}})$ 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.
Details
- Title: Subtitle
- No-Regret Learning for Fair Multi-Agent Social Welfare Optimization
- Creators
- Mengxiao Zhang - University of Iowa, United StatesRamiro Deo Campo Vuong - Cornell UniversityHaipeng Luo - University of Southern California
- Resource Type
- Conference proceeding
- Publication Details
- Advances in Neural Information Processing Systems 37 - 38th Conference on Neural Information Processing Systems, NeurIPS 2024, Vol.37
- ISSN
- 1049-5258
- Grant note
- IIS-1943607 / National Sleep Foundation (100003187) National Science Foundation (http://data.elsevier.com/vocabulary/SciValFunders/100000001) IIS-1943607 / National Science Foundation (http://data.elsevier.com/vocabulary/SciValFunders/100000001)
- Language
- English
- Date published
- 2024
- Academic Unit
- Business Analytics
- Record Identifier
- 9985033876702771
Metrics
9 Record Views