Abstract
| Original language | Undefined |
|---|---|
| Title of host publication | 11th International Conference on Web and Internet Economics, WINE 2015 |
| Editors | Evangelos Markakis, Guido Schäfer |
| Place of Publication | Heidelberg |
| Publisher | Springer |
| Pages | 258-271 |
| Number of pages | 14 |
| ISBN (Print) | 978-3-662-48994-9 |
| DOIs | |
| Publication status | Published - Dec 2015 |
| Event | 11th International Conference on Web and Internet Economics, WINE 2015 - Amsterdam, Netherlands Duration: 9 Dec 2015 → 12 Dec 2015 Conference number: 11 https://event.cwi.nl/wine2015/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Verlag |
| Volume | 9470 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 11th International Conference on Web and Internet Economics, WINE 2015 |
|---|---|
| Abbreviated title | WINE |
| Country | Netherlands |
| City | Amsterdam |
| Period | 9/12/15 → 12/12/15 |
| Internet address |
Keywords
- CR-F.2
- EWI-26532
- MSC-65K05
- METIS-315076
- Network Routing Games
- Price of Anarchy
- IR-98689
- MSC-90C27
Cite this
}
The curse of sequentiality in routing games. / Correa, José; de Jong, Jasper; de Keijzer, Bart; Uetz, Marc Jochen.
11th International Conference on Web and Internet Economics, WINE 2015. ed. / Evangelos Markakis; Guido Schäfer. Heidelberg : Springer, 2015. p. 258-271 (Lecture Notes in Computer Science; Vol. 9470).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - The curse of sequentiality in routing games
AU - Correa, José
AU - de Jong, Jasper
AU - de Keijzer, Bart
AU - Uetz, Marc Jochen
N1 - 10.1007/978-3-662-48995-6_19
PY - 2015/12
Y1 - 2015/12
N2 - In the "The curse of simultaneity", Paes Leme at al. show that there are interesting classes of games for which sequential decision making and corresponding subgame perfect equilibria avoid worst case Nash equilibria, resulting in substantial improvements for the price of anarchy. This is called the sequential price of anarchy. A handful of papers have lately analysed it for various problems, yet one of the most interesting open problems was to pin down its value for network congestion games, where the price of anarchy equals 5/2. The main contribution of this paper is the surprising result that the sequential price of anarchy is unbounded even for linear symmetric routing games, thereby showing that sequentiality can be arbitrarily worse than simultaneity for this important class of games. Complementing this unboundedness result we solve an open problem in the area by establishing that the (regular) price of anarchy for linear symmetric routing games equals 5/2. Additionally, we prove that in these games, even with two players, computing the outcome of a subgame perfect equilibrium is NP-hard. The latter explains, to some extent, the difficulty of analyzing subgame perfect equilibria.
AB - In the "The curse of simultaneity", Paes Leme at al. show that there are interesting classes of games for which sequential decision making and corresponding subgame perfect equilibria avoid worst case Nash equilibria, resulting in substantial improvements for the price of anarchy. This is called the sequential price of anarchy. A handful of papers have lately analysed it for various problems, yet one of the most interesting open problems was to pin down its value for network congestion games, where the price of anarchy equals 5/2. The main contribution of this paper is the surprising result that the sequential price of anarchy is unbounded even for linear symmetric routing games, thereby showing that sequentiality can be arbitrarily worse than simultaneity for this important class of games. Complementing this unboundedness result we solve an open problem in the area by establishing that the (regular) price of anarchy for linear symmetric routing games equals 5/2. Additionally, we prove that in these games, even with two players, computing the outcome of a subgame perfect equilibrium is NP-hard. The latter explains, to some extent, the difficulty of analyzing subgame perfect equilibria.
KW - CR-F.2
KW - EWI-26532
KW - MSC-65K05
KW - METIS-315076
KW - Network Routing Games
KW - Price of Anarchy
KW - IR-98689
KW - MSC-90C27
U2 - 10.1007/978-3-662-48995-6_19
DO - 10.1007/978-3-662-48995-6_19
M3 - Conference contribution
SN - 978-3-662-48994-9
T3 - Lecture Notes in Computer Science
SP - 258
EP - 271
BT - 11th International Conference on Web and Internet Economics, WINE 2015
A2 - Markakis, Evangelos
A2 - Schäfer, Guido
PB - Springer
CY - Heidelberg
ER -