# Selfish Robustness and Equilibria in Multi-Player Bandits

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

## Key facts

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

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

- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Regret, stability & fairness in matching markets with bandit learners](https://mlsanity.com/paper/2102.06246/) (2021)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms: Learning Algorithms & Applications](https://mlsanity.com/paper/2204.13502/) (2022)
- [Decentralized Learning in Online Queuing Systems](https://mlsanity.com/paper/2106.04228/) (2021)
- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Multi-Player Bandits Robust to Adversarial Collisions](https://mlsanity.com/paper/2211.07817/) (2022)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [Constant or logarithmic regret in asynchronous multiplayer bandits](https://mlsanity.com/paper/2305.19691/) (2023)
- [Adversarial Attacks on Cooperative Multi-agent Bandits](https://mlsanity.com/paper/2311.01698/) (2023)
- [PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators](https://mlsanity.com/paper/2403.15524/) (2024)
- [Competitive Multi-armed Bandit Games for Resource Sharing](https://mlsanity.com/paper/2503.20975/) (2025)

## Abstract (arXiv)

Motivated by cognitive radios, stochastic multi-player multi-armed bandits gained a lot of interest recently. In this class of problems, several players simultaneously pull arms and encounter a collision - with 0 reward - if some of them pull the same arm at the same time. While the cooperative case where players maximize the collective reward (obediently following some fixed protocol) has been mostly considered, robustness to malicious players is a crucial and challenging concern. Existing approaches consider only the case of adversarial jammers whose objective is to blindly minimize the collective reward. We shall consider instead the more natural class of selfish players whose incentives are to maximize their individual rewards, potentially at the expense of the social welfare. We provide the first algorithm robust to selfish players (a.k.a. Nash equilibrium) with a logarithmic regret, when the arm performance is observed. When collisions are also observed, Grim Trigger type of strategies enable some implicit communication-based algorithms and we construct robust algorithms in two different settings: the homogeneous (with a regret comparable to the centralized optimal one) and heterogeneous cases (for an adapted and relevant notion of regret). We also provide impossibility results when only the reward is observed or when arm means vary arbitrarily among players.