Asymptotically optimal distributed channel allocation: A competitive game-theoretic approach
Authors:
- 1 September 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1272-1279
Abstract
In this paper 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. First we present a natural non-cooperative game theoretic formulation for this problem. It is shown that, when interference is sufficiently strong, this game has a pure price of anarchy approaching infinity with high probability, and there is an asymptotically increasing number of equilibria with the worst performance. Then we propose a novel non-cooperative M Frequency-Selective Interference Game (M-FSIG), where users limit their utility such that it is greater than zero only for their M best channels, and equal for them. We show that the M-FSIG exhibits, with high probability, an increasing number of optimal pure Nash equilibria and no bad equilibria. Consequently, the pure price of anarchy converges to one in probability in any interference regime. 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.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Fully Distributed Optimal Channel Assignment for Open Spectrum AccessIEEE Transactions on Signal Processing, 2013
- Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tablesRandom Structures & Algorithms, 2012
- Smart carrier sensing for distributed computation of the generalized nash bargaining solution2011
- Cooperative Game Theory and the Gaussian Interference ChannelIEEE Journal on Selected Areas in Communications, 2008
- Adaptive channel allocation spectrum etiquette for cognitive radio networks2005
- Distributed coordination of spectrum and the prisoner~s dilemma2005
- Fair multiuser channel allocation for OFDMA networks using Nash bargaining solutions and coalitionsIEEE Transactions on Communications, 2005
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963
- Non-Cooperative GamesAnnals of Mathematics, 1951
- Distinct representatives of subsetsBulletin of the American Mathematical Society, 1948