Skip to Content

Graphical Congestion Games

Efficient resource sharing is essential in a wide range of systems in economics, engineering, biology, and sociology. The problem of understanding how individuals share resources in a distributed fashion is therefore scientifically important. The problem is also important in many practical situations, such as the design of communication networks, or the making business decisions like market entry. Interestingly, a wide range of distributed resource sharing scenarios can be modeled by congestion games. The idea is to treat individuals as players in a game, and they select which resources to use. The payoff that a player receives from using a resource is given by some decreasing function of that resource’s congestion level (i.e., the total number of players using it).

Although the original congestion game (e.g., Rosenthal (1973)) is rather general, it includes no notion of space. This makes the game model unsuitable for modeling situations like spectrum allocation in wireless networks, or market entry in spatially distributed businesses. We have studied a more general class of graphical congestion games. The players are represented by vertices within an undirected graph. A player’s congestion level is now the number of his neighbors who are using the same resource (i.e., only linked players can congest one another). We have looked at various types of graphical congestion games, including those with general utility functions on weighted and directed graphs. We also looked at the applications of graphical congestion games in wireless communications, including those models that capture special characteristics of random access games, physical interference model based power control games, and QoS satisfaction games for inelastic applications such as video streaming. 

Project Team

NCEL Members: Xu Chen, Jianwei Huang, Richard Southwell
Collaborators: Yanjiao Chen (Hong Kong University of Science and Technology), Biying Shou (The City University of Hong Kong), Qian Zhang (Hong Kong University of Science and Technology)

Chen, Xu, and Jianwei Huang. "Spatial Spectrum Access Game." IEEE Transactions on Mobile Computing. 14.3 (2015): 646-659. Download: SpatialGame-TMC.pdf (1.09 MB)
Southwell, Richard, Xu Chen, and Jianwei Huang. "Quality of Service Games for Spectrum Sharing." IEEE Journal on Selected Areas in Communications (2014). Download: jsac0314southwell.pdf (2.81 MB)
Chen, Xu, and Jianwei Huang. "Distributed Spectrum Access with Spatial Reuse." IEEE Journal on Selected Areas in Communications. 31.3 (2013): 593-603. Download: jsac0313chen-final.pdf (753.72 KB)
Southwell, Richard, Xu Chen, and Jianwei Huang Quality of Service Satisfaction Games for Spectrum Sharing. IEEE INFOCOM - Mini Conference. Turin, Italy, 2013. Download: 1569647131.pdf (437.92 KB)
Southwell, Richard, Jianwei Huang, and Biying Shou Physical Interference Model Based Spectrum Sharing with Generalized Spatial Congestion Games. IEEE International Conference on Communication Systems (ICCS). Singapore, 2012. Download: ICCS2012.pdf (378.45 KB)
Southwell, Richard, et al. Convergence Dynamics of Graphical Congestion Games. International Conference on Game Theory for Networks (GameNets)., 2012. Download: gamenets12.pdf (642.97 KB)
Chen, Xu, and Jianwei Huang Spatial Spectrum Access Game: Nash Equilibria and Distributed Learning. ACM Mobihoc. Hilton Head Island, South Carolina, 2012. Download: Mobihoc12.pdf (437.44 KB)
Tekin, Cem, et al. "Atomic Congestion Games on Graphs and Their Applications in Networking." IEEE Transactions on Networking. 20.5 (2012): 1541-1552. Download: 06138321.pdf (2.14 MB)
Southwell, Richard, and Jianwei Huang Convergence Dynamics of Resource-Homogeneous Congestion Games. International Conference on Game Theory for Networks (GameNets). Shanghai, China, 2011. Download: congestionGamenets2011.pdf (1.35 MB)






story | by Dr. Radut