2012/06/03 by Richard Southwell, Southwell, Richard, Jianwei Huang +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Networking and Internet Architecture (cs.NI) #cs.GT #cs.NI
paper · pdf · doi:10.48550/arxiv.1206.0430
arxiv created 2012/06/03 · openalex publication_date 2012/06/03 · arxiv updated 2012/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
With the advance of complex large-scale networks, it is becoming increasingly important to understand how selfish and spatially distributed individuals will share network resources without centralized coordinations. In this paper, we introduce the graphical congestion game with weighted edges (GCGWE) as a general theoretical model to study this problem. In GCGWE, we view the players as vertices in a weighted graph. The amount of negative impact (e.g. congestion) caused by two close-by players to each other is determined by the weight of the edge linking them. The GCGWE unifies and significantly generalizes several simpler models considered in the previous literature, and is well suited for modeling a wide range of networking scenarios. One good example is to use the GCGWE to model spectrum sharing in wireless networks, where we can properly define the edge weights and payoff functions to capture the rather complicated interference relationship between wireless nodes. By identifying which GCGWEs possess pure Nash equilibria and the very desirable finite improvement property, we gain insight into when spatially distributed wireless nodes will be able to self-organize into a mutually acceptable resource allocation. We also consider the efficiency of the pure Nash equilibria, and the computational complexity of finding them.