On spectrum sharing games

作     者：Halldorsson, Magnus M. Halpern, Joseph Y. Li, Li Erran Mirrokni, Vahab S. 

作者机构：Reykjavik Univ Sch Comp Sci IS-101 Reykjavik Iceland Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Bell Labs Alcatel Lucent Ctr Networking Res Murray Hill NJ 07974 USA Google Res Theory Grp New York NY USA 

出 版 物：《DISTRIBUTED COMPUTING》 (分布式计算)

年 卷 期：2010年第22卷第4期

页      面：235-248页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：DoD Multidisciplinary University, (N00014-01-1-0795) National Science Foundation, NSF, (CTC-0208535) Office of Naval Research, ONR, (N00014-00-1-03-41, N00014-01-10-511) Air Force Office of Scientific Research, AFOSR, (ANI-0335244, F49620-02-1-0101) 

主　　题：Game theory Nash equilibrium Price of anarchy Graph coloring Approximation algorithm Unit disk graph 

摘      要：Efficient spectrum-sharing mechanisms are crucial to alleviate the bandwidth limitation in wireless networks. In this paper, we consider the following question: can free spectrum be shared efficiently? We study this problem in the context of 802.11 or WiFi networks. Each access point (AP) in a WiFi network must be assigned a channel for it to service users. There are only finitely many possible channels that can be assigned. Moreover, neighboring access points must use different channels so as to avoid interference. Currently these channels are assigned by administrators who carefully consider channel conflicts and network loads. Channel conflicts among APs operated by different entities are currently resolved in an ad hoc manner (i.e., not in a coordinated way) or not resolved at all. We view the channel assignment problem as a game, where the players are the service providers and APs are acquired sequentially. We consider the price of anarchy of this game, which is the ratio between the total coverage of the APs in the worst Nash equilibrium of the game and what the total coverage of the APs would be if the channel assignment were done optimally by a central authority. We provide bounds on the price of anarchy depending on assumptions on the underlying network and the type of bargaining allowed between service providers. The key tool in the analysis is the identification of the Nash equilibria with the solutions to a maximal coloring problem in an appropriate graph. We relate the price of anarchy of these games to the approximation factor of local optimization algorithms for the maximum k-colorable subgraph problem. We also study the speed of convergence in these games.