解决多智能体竞争抢资源时效率低下的问题，提出新机制实现高效协作。
Competitive Multi-armed Bandit Games for Resource Sharing
- 设计基于阈值的策略，分析自私与社会最优行为差异。
- 证明自私竞争导致无限效率损失（价格破产），且无法通过信息手段缓解。
- 提出信息+激励结合的新机制，实现最优效率和快速收敛，适合资源分配场景。
在现代资源共享系统中，多个智能体在未知随机条件下访问有限资源完成任务。当多个智能体同时访问同一资源（臂）时，会因竞争导致冲突和奖励下降。本文研究一种新型的N玩家K臂竞争型多臂赌博机（CMAB）游戏，其中非短视智能体随时间形成对未知臂的个性化估计。由于可能发生的碰撞及臂奖励的时间变化性，策略分析比已有针对短视智能体的研究更复杂。我们显式分析了社会最优与现有自私策略的阈值结构，发现后者收敛时间长达Ω(\frac{K}{η^2}\ln(\frac{KN}δ))，而社会最优策略通过协调通信可降至\mathcal{O}(\frac{K}{Nη^2}\ln(\frac{K}δ))。基于此，我们证明自私玩家对最优臂的竞争可能导致无限价格破产（PoA），即效率损失无界。进一步证明，任何非货币的信息机制（包括贝叶斯说服）都无法降低该无限PoA，因为非短视玩家的战略性谎报破坏了此类方法。为此，我们提出联合信息与侧支付（CISP）机制，根据玩家动态私有信念提供社会最优的臂推荐，并施加适当的信息与货币激励。该机制保持社会规划者事后预算平衡，确保玩家诚实上报，实现最小价格破产=1，且收敛速度与社会最优一致。
原文摘要 · Abstract (English)
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 $Ω(\frac{K}{η^2}\ln({\frac{KN}δ}))$, while socially optimal policy with coordinated communication reduces it to $\mathcal{O}(\frac{K}{Nη^2}\ln{(\frac{K}δ)})$. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。