Summary of No-regret Learning For Fair Multi-agent Social Welfare Optimization, by Mengxiao Zhang et al.
No-Regret Learning for Fair Multi-Agent Social Welfare Optimization
by Mengxiao Zhang, Ramiro Deo-Campo Vuong, Haipeng Luo
First submitted to arxiv on: 31 May 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Computer Science and Game Theory (cs.GT); Multiagent Systems (cs.MA); Machine Learning (stat.ML)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary The researchers investigate online multi-agent Nash social welfare (NSW) maximization in various settings, including stochastic N-agent K-armed bandits and adversarial rewards. They develop an algorithm with O(K(2/N)T(N-1)/N) regret in the stochastic setting and prove that this dependence on T is tight. In contrast, previous works achieved √T-regret bounds. The authors also consider a full-information feedback setting, designing two algorithms with √T-regret: one has no N-dependence and can be applied to a broader class of welfare functions, while the other has better K-dependence and is preferred when N is small. Additionally, they show that logarithmic regret is possible when one agent is indifferent about different arms. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary This paper studies how computers can make fair decisions online with many agents involved. The researchers want to know if it’s possible to make good choices while keeping everyone happy. They look at different situations and find new algorithms to achieve this goal. In some cases, they can do better than previous methods, but in others, there are limitations. This work is important because fairness matters in decision-making. |
