# Competitive Multi-armed Bandit Games for Resource Sharing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 26 Mar 2025.

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

- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [Information Directed Sampling for Stochastic Bandits with Graph Feedback](https://mlsanity.com/paper/1711.03198/) (2017)
- [Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1604.06377/) (2016)
- [Selfish Robustness and Equilibria in Multi-Player Bandits](https://mlsanity.com/paper/2002.01197/) (2020)
- [Multiplayer Bandit Learning, from Competition to Cooperation](https://mlsanity.com/paper/1908.01135/) (2019)
- [Exploration and Incentives in Reinforcement Learning](https://mlsanity.com/paper/2103.00360/) (2021)
- [Distributed Bandits with Heterogeneous Agents](https://mlsanity.com/paper/2201.09353/) (2022)
- [Decentralized Learning in Online Queuing Systems](https://mlsanity.com/paper/2106.04228/) (2021)
- [Optimizing Resource Allocation for Multi-modal Semantic Communication in Mobile AIGC Networks: A Diffusion-based Game Approach](https://mlsanity.com/paper/2409.17506/) (2024)
- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Learning an Unknown Network State in Routing Games](https://mlsanity.com/paper/1905.04433/) (2019)
- [When Congestion Games Meet Mobile Crowdsourcing: Selective Information Disclosure](https://mlsanity.com/paper/2211.14029/) (2022)
- [Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits](https://mlsanity.com/paper/2212.06279/) (2022)
- [Human-in-the-loop Learning for Dynamic Congestion Games](https://mlsanity.com/paper/2404.15599/) (2024)
- [Distributed Learning for Dynamic Congestion Games](https://mlsanity.com/paper/2405.03031/) (2024)
- [To Optimize Human-in-the-loop Learning in Repeated Routing Games](https://mlsanity.com/paper/2411.09867/) (2024)
- [Social Learning in Nonatomic Routing Games](https://mlsanity.com/paper/2009.11580/) (2020)
- [To Analyze and Regulate Human-in-the-loop Learning for Congestion Games](https://mlsanity.com/paper/2501.03055/) (2025)

## Abstract (arXiv)

In modern resource-sharing systems, multiple agents access limited resources with unknown stochastic conditions to perform tasks. When multiple agents access the same resource (arm) simultaneously, they compete for successful usage, leading to contention and reduced rewards. This motivates our study of competitive multi-armed bandit (CMAB) games. In this paper, we study a new N-player K-arm competitive MAB game, where non-myopic players (agents) compete with each other to form diverse private estimations of unknown arms over time. Their possible collisions on same arms and time-varying nature of arm rewards make the policy analysis more involved than existing studies for myopic players. We explicitly analyze the threshold-based structures of social optimum and existing selfish policy, showing that the latter causes prolonged convergence time Omega(fracKη2ln(fracKNδ)), while socially optimal policy with coordinated communication reduces it to O(fracKNη2ln(fracKδ)). Based on the comparison, we prove that the competition among selfish players for the best arm can result in an infinite price of anarchy (PoA), indicating an arbitrarily large efficiency loss compared to social optimum. We further prove that no informational (non-monetary) mechanism (including Bayesian persuasion) can reduce the infinite PoA, as the strategic misreporting by non-myopic players undermines such approaches. To address this, we propose a Combined Informational and Side-Payment (CISP) mechanism, which provides socially optimal arm recommendations with proper informational and monetary incentives to players according to their time-varying private beliefs. Our CISP mechanism keeps ex-post budget balanced for social planner and ensures truthful reporting from players, achieving the minimum PoA=1 and same convergence time as social optimum.