A Distributed Algorithm For Spatial Spectrum Access Games

Consider a wireless network in which selfish users compete with each other for usage of spectrum. We view this competition as a spatial spectrum access game. There are two fundamental questions regarding this game:how to converge to the optimal Nash equilibrium, and how to converge fast. To answer these two questions, we ap-ply a technique called Belief Propagation to design algorithms for users in this game, which can guarantee fast convergence to an optimal or nearly optimal pure strategy Nash equilibrium. Specifically, when the interference graph is an undirected tree or a directed acyclic graph, our algorithms can find the optimal Nash equilibrium in linear time. For general undirected interference graph, our algorithm converges fast as long as the game is potential (which is the case for many typical scenarios). For some other typical spatial spectrum access games, our algorithms can provide a good approxima-tion to the optimal Nash equilibrium.