Asymptotically Optimal Distributed Channel Allocation: a Competitive Game-Theoretic Approach

Abstract: In this work we consider the problem of distributed channel allocation in large networks under the frequency-selective interference channel. Performance is measured by the weighted sum of achievable rates. We present a natural non-cooperative game theoretic formulation for this problem. It is shown that with high probability, when interference is sufficiently strong, this game has a pure price of anarchy approaching infinity and there is an asymptotically large number of equilibria with the worst performance. We propose a novel non-cooperative M Frequency-Selective Interference Channel Game (M-FSIG) where players limit their utility. We prove for the M-FSIG that asymptotically there is a large number of permutation equilibria, and all other equilibria are almost a permutation. Then we analyze the order statistics of the fading channels and show that for a broad class of fading distributions, the M best channels of each player are asymptotically optimal, even if M is asymptotically increasing. Consequently, the pure price of anarchy converges to one in probability for any interference regime. Furthermore, the permutation equilibria achieve asymptotically max-min fairness between the players. In order to exploit these results algorithmically we propose a modified Fictitious Play algorithm that can be implemented distributedly. We carry out simulations that show its fast convergence to the proven pure Nash equilibria.

Paper