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

Speaker
Ilai Bistritz
Date
21/06/2016 - 12:30 - 11:00Add To Calendar 2016-06-21 11:00:00 2016-06-21 12:30:00 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 Economics building (No. 504), room 011 אוניברסיטת בר-אילן - Department of Economics Economics.Dept@mail.biu.ac.il Asia/Jerusalem public
Place
Economics building (No. 504), room 011
Affiliation
Bar-Ilan University
Abstract

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

Last Updated Date : 29/05/2016