Competitive Multi-Armed Bandit Games for Resource Sharing

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 theoretical study of competitive multi-armed bandit (CMAB) games. In this paper, we study a new <inline-formula><tex-math notation="LaTeX">$N$</tex-math></inline-formula>-player <inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula>-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 the same arms and the time-varying nature of arm rewards make the policy analysis here more involved than the existing studies for myopic players. We explicitly analyze the threshold-based structures of the social optimum and the existing selfish policy, showing that the latter causes prolonged convergence times <inline-formula><tex-math notation="LaTeX">$\Omega (\frac{K}{\eta ^{2}}\ln ({\frac{KN}{\delta }}))$</tex-math></inline-formula>, while the socially optimal policy with coordinated communication reduces it to <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(\frac{K}{N\eta ^{2}}\ln {(\frac{K}{\delta })})$</tex-math></inline-formula>. Based on the policy 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 the social optimum. We further prove that no informational (non-monetary) mechanism (including Bayesian persuasion) can reduce the infinite PoA, as 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 diverse and time-varying private beliefs. Our CISP mechanism keeps ex-post budget balanced for the social planner and ensures truthful reporting from players, thereby achieving the minimum <inline-formula><tex-math notation="LaTeX">$\text{PoA}=1$</tex-math></inline-formula> and the same convergence time as the social optimum.