No-Regret Learning for Capacity-Constrained $\alpha$-Fair Multi-Agent Bandits

We study stochastic multi-agent bandits with finite arm capacities and a weighted $\alpha$-fair objective. The capacity-coupled matching action space and the non-Lipschitz objective near zero make standard upper confidence bound (UCB) analysis inapplicable. We propose a centralized two-phase cover-elimination-UCB algorithm that adaptively identifies a safe scale and uses a global elimination rule to remove certifiably poor base-arms while preserving optimal ones, thereby entering a Lipschitz regime. We derive a two-term regret upper bound, consisting of a capacity-coupled screening term for near-zero bad base-arms and a learning term in the safe Lipschitz regime, and establish a lower bound matching the $T$- and ${\mu }_{\min }^{\ast }$-dependence up to logarithmic factors. We then develop a low auction-call complexity decentralized algorithm based on geometric shrinking, utilizing dual prices from a decentralized auction to compute forced-insertion gaps through augmented alternating cycles. Experiments demonstrate the effectiveness of our algorithms.