Conference proceeding
The Impact of Social Ignorance on Weighted Congestion Games
INTERNET AND NETWORK ECONOMICS, PROCEEDINGS, v 5929, pp 316-327
01 Jan 2009
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
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 epsilon-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. Our main result is that the impact of social ignorance on the Price of Anarchy (PoA) and the Price of Stability (PoS) is naturally quantified by the independence number alpha(G) of the social graph C. In particular, we show that the NA grows roughly as alpha(G)(alpha(G) + 2), which is essentially tight as long as alpha(G) does not exceed half the number of players, and that the PoS lies between alpha(G) and 2 alpha(G). Moreover, we show that the epsilon-Nash dynamics reaches an alpha(G)(alpha(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 epsilon-Nash dynamics reaches an epsilon-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.
Metrics
Details
- Title
- The Impact of Social Ignorance on Weighted Congestion Games
- Creators
- Dimitris Fotakis - National Technical University of AthensVasilis Gkatzelis - Courant Institute of Mathematical SciencesAlexis C. Kaporis - University of the AegeanPaul G. Spirakis - Computer Technology Institute and Press “DIOPHANTUS”
- Contributors
- S Leonardi (Editor)
- Publication Details
- INTERNET AND NETWORK ECONOMICS, PROCEEDINGS, v 5929, pp 316-327
- Series
- Lecture Notes in Computer Science
- Publisher
- Springer Nature
- Number of pages
- 3
- Grant note
- CCF0830516 / NSF; National Science Foundation (NSF) ICT-2008-215270(FRONTS) / EU; European Union (EU) Andreas Mentzelopoulos Scholarships
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000278097500029
- Scopus ID
- 2-s2.0-76649115660
- Other Identifier
- 991021868090604721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Theory & Methods