Reproduce “Competitive Multi-armed Bandit Games for Resource Sharing” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Hongbo Li, Lingjie Duan
Competitive multi-armed bandit games are analyzed as dynamic resource-sharing problems in which players learn privately, compete for arms, and suffer collisions. The study shows that selfish learning can require substantially longer exploration and produce an unbounded price of anarchy, while the proposed Combined Informational and Side-Payment (CISP) mechanism is theoretically claimed to recover socially optimal performance with truthful participation and ex-post budget balance.
Key insights
- Non-myopic players may explore arms with lower current estimates because of their future information value, but decentralized exploration is slowed by collisions and conflicting private beliefs.
- Social coordination parallelizes arm sampling: the selfish convergence lower bound scales as Ω(Kη⁻² log(KN/δ)), whereas centralized learning achieves O(K(Nη²)⁻¹ log(K/δ)).
- Information control alone cannot guarantee efficiency when players can misreport observations; combining information with transfers is intended to align private and social incentives.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.