The Inefficiency of Nash and Subgame Perfect Equilibria for Network Routing
- Submitting institution
-
King's College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 127952644
- Type
- D - Journal article
- DOI
-
10.1287/moor.2018.0968
- Title of journal
- MATHEMATICS OF OPERATIONS RESEARCH
- Article number
- C2
- First page
- 1286
- Volume
- 44
- Issue
- 4
- ISSN
- 0364-765X
- Open access status
- Technical exception
- Month of publication
- September
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper rigorously disproves a five-year-old conjecture about decision making in network games. The conjecture claimed that in strategic network routing, sequential decisions lead to better outcomes than simultaneous decisions. This paper closes the gap among upper-bound results and lower-bound results on these outcomes, as developed by Paes Leme et al. (ITCS2012) and De Jong et al. (WINE2014), respectively. This work was invited for presentation at the retrospective "Twenty Years of the Price of Anarchy" workshop. It has been an inspiration for multiple works on sequential decision making (see, e.g., https://doi.org/10.1007/978-3-030-64946-3_22, https://dl.acm.org/doi/10.5555/3237383.3238031) since the preliminary version was presented at WINE2015.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -