The Impact of Social Ignorance on Weighted Congestion Games
Theory of computing systems, Vol.50(3), pp.559-578
Apr 2012
We consider weighted linear congestion games, and investigate how social ignorance, namely lack of information about the presence of some players, affects the inefficiency of pure Nash equilibria (PNE) and the convergence rate of the ε-Nash dynamics. To this end, we adopt the model of graphical linear congestion games with weighted players, where the individual cost and the strategy selection of each player only depends on his neighboring players in the social graph. We show that such games admit a potential function, and thus a PNE. Next, we investigate the Price of Anarchy (PoA) and the Price of Stability (PoS) of graphical linear congestion games with respect to the players’ total actual cost. Our main result is that the impact of social ignorance on the PoA and on the PoS is naturally quantified by the independence number
α(G) of the social graph G. In particular, we show that the PoA grows roughly as α(G)(α(G)+2), which is essentially tight as long as α(G) does not exceed half the number of players, and that the PoS lies between α(G) and 2α(G). Moreover, we show that the ε-Nash dynamics reaches an α(G)(α(G)+2)-approximate configuration in polynomial time that does not directly depend on the social graph. For unweighted graphical linear games with symmetric strategies, we show that the ε-Nash dynamics reaches an ε-approximate PNE in polynomial time that exceeds the corresponding time for symmetric linear games by a factor at most as large as the number of players.
4
- The Impact of Social Ignorance on Weighted Congestion Games
- Dimitris Fotakis - School of Electrical and Computer Engineering National Technical University of Athens 15780 Athens GreeceVasilis Gkatzelis - Computer Science Department, Courant Institute New York University 251 Mercer Street New York NY 10012 USAAlexis Kaporis - Research Academic Computer Technology Institute N. Kazantzaki Str., University Campus 26500 Patras GreecePaul Spirakis - Research Academic Computer Technology Institute N. Kazantzaki Str., University Campus 26500 Patras Greece
- Theory of computing systems, Vol.50(3), pp.559-578
- Springer-Verlag; New York
- Journal article
- English
- Computer Science (Computing)
- 991014878155204721
research.portal.fulldisplay.sdgs.intro
research.portal.fulldisplay.incitesHighlights.intro
- esploro.research.conf.research.portal.label.prefix.inciteCollaboration
- research.portal.fulldisplay.incitesHighlights.institutionCollaboration
- research.portal.fulldisplay.incitesHighlights.internationalCollaboration
- esploro.research.conf.research.portal.label.prefix.inciteWOSResearchAreas
- Computer Science, Theory & Methods
- Mathematics