The curse of sequentiality in routing games

José Correa, Jasper de Jong, Bart de Keijzer, Marc Jochen Uetz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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.
Original languageUndefined
Title of host publication11th International Conference on Web and Internet Economics, WINE 2015
EditorsEvangelos Markakis, Guido Schäfer
Place of PublicationHeidelberg
PublisherSpringer
Pages258-271
Number of pages14
ISBN (Print)978-3-662-48994-9
DOIs
Publication statusPublished - Dec 2015
Event11th International Conference on Web and Internet Economics, WINE 2015 - Amsterdam, Netherlands
Duration: 9 Dec 201512 Dec 2015
Conference number: 11
https://event.cwi.nl/wine2015/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume9470
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Web and Internet Economics, WINE 2015
Abbreviated titleWINE
CountryNetherlands
CityAmsterdam
Period9/12/1512/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

Correa, J., de Jong, J., de Keijzer, B., & Uetz, M. J. (2015). The curse of sequentiality in routing games. In E. Markakis, & G. Schäfer (Eds.), 11th International Conference on Web and Internet Economics, WINE 2015 (pp. 258-271). (Lecture Notes in Computer Science; Vol. 9470). Heidelberg: Springer. https://doi.org/10.1007/978-3-662-48995-6_19
Correa, José ; de Jong, Jasper ; de Keijzer, Bart ; Uetz, Marc Jochen. / The curse of sequentiality in routing games. 11th International Conference on Web and Internet Economics, WINE 2015. editor / Evangelos Markakis ; Guido Schäfer. Heidelberg : Springer, 2015. pp. 258-271 (Lecture Notes in Computer Science).
@inproceedings{6ff6cb2d19ff497da1bba82d9fd33fb3,
title = "The curse of sequentiality in routing games",
abstract = "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.",
keywords = "CR-F.2, EWI-26532, MSC-65K05, METIS-315076, Network Routing Games, Price of Anarchy, IR-98689, MSC-90C27",
author = "Jos{\'e} Correa and {de Jong}, Jasper and {de Keijzer}, Bart and Uetz, {Marc Jochen}",
note = "10.1007/978-3-662-48995-6_19",
year = "2015",
month = "12",
doi = "10.1007/978-3-662-48995-6_19",
language = "Undefined",
isbn = "978-3-662-48994-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "258--271",
editor = "Evangelos Markakis and Guido Sch{\"a}fer",
booktitle = "11th International Conference on Web and Internet Economics, WINE 2015",

}

Correa, J, de Jong, J, de Keijzer, B & Uetz, MJ 2015, The curse of sequentiality in routing games. in E Markakis & G Schäfer (eds), 11th International Conference on Web and Internet Economics, WINE 2015. Lecture Notes in Computer Science, vol. 9470, Springer, Heidelberg, pp. 258-271, 11th International Conference on Web and Internet Economics, WINE 2015, Amsterdam, Netherlands, 9/12/15. https://doi.org/10.1007/978-3-662-48995-6_19

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 proceedingConference contributionAcademicpeer-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 -

Correa J, de Jong J, de Keijzer B, Uetz MJ. The curse of sequentiality in routing games. In Markakis E, Schäfer G, editors, 11th International Conference on Web and Internet Economics, WINE 2015. Heidelberg: Springer. 2015. p. 258-271. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-662-48995-6_19