The sequential price of anarchy for atomic congestion games

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

96 Downloads (Pure)

Abstract

In situations without central coordination, the price of anarchy relates the quality of any Nash equilibrium to the quality of a global optimum. Instead of assuming that all players choose their actions simultaneously, we consider games where players choose their actions sequentially. The sequential price of anarchy, recently introduced by Paes Leme, Syrgkanis, and Tardos, relates the quality of any subgame perfect equilibrium to the quality of a global optimum. The effect of sequential decision making on the quality of equilibria, depends on the specific game under consideration. We analyze the sequential price of anarchy for atomic congestion games with affine cost functions. We derive several lower and upper bounds, showing that sequential decisions mitigate the worst case outcomes known for the classical price of anarchy. Next to tight bounds on the sequential price of anarchy, a methodological contribution of our work is, among other things, a “factor revealing‿ linear programming approach we use to solve the case of three players.
Original languageUndefined
Title of host publicationProceedings of the 10th Conference on Web and Internet Economics, WINE 2014
EditorsTie-Yan Liu, Qi Qi, Yinyu Ye
Place of PublicationBerlin
PublisherSpringer
Pages429-434
Number of pages6
ISBN (Print)978-3-319-13128-3
DOIs
Publication statusPublished - 14 Dec 2014
Event10th Conference on Web and Internet Economics, WINE 2014 - Beijing, China
Duration: 14 Dec 201417 Dec 2014
Conference number: 10

Publication series

NameLecture Notes In Computer Science
PublisherSpringer International Publishing Switzerland
Volume8877

Conference

Conference10th Conference on Web and Internet Economics, WINE 2014
Abbreviated titleWINE
CountryChina
CityBeijing
Period14/12/1417/12/14

Keywords

  • EWI-25269
  • Linear Programming
  • Equilibrium
  • Sequential Price of Anarchy
  • IR-93644
  • Congestion Game
  • Game Theory
  • METIS-309644

Cite this

de Jong, J., & Uetz, M. J. (2014). The sequential price of anarchy for atomic congestion games. In T-Y. Liu, Q. Qi, & Y. Ye (Eds.), Proceedings of the 10th Conference on Web and Internet Economics, WINE 2014 (pp. 429-434). (Lecture Notes In Computer Science; Vol. 8877). Berlin: Springer. https://doi.org/10.1007/978-3-319-13129-0_35