The curse of ties in congestion games with limited lookahead

Carla Groenland, Guido Schafer

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

Abstract

We introduce a novel framework to model limited lookahead in congestion games. Intuitively, the players enter the game sequentially and choose an optimal action under the assumption that the k - 1 subsequent players play subgame-perfectly. Our model naturally interpolates between outcomes of greedy best-response (k = 1) and subgame-perfect outcomes (k = n, the number of players). We study the impact of limited lookahead (parameterized by k) on the stability and inefficiency of the resulting outcomes. As our results reveal, increased lookahead does not necessarily lead to better outcomes; in fact, its effect crucially depends on the existence of ties and the type of game under consideration.

Original languageEnglish
Title of host publication17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1941-1943
Number of pages3
Volume3
ISBN (Print)9781510868083
Publication statusPublished - 2018
Event17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018 - Stockholm, Sweden
Duration: 10 Jul 201815 Jul 2018

Conference

Conference17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
CountrySweden
CityStockholm
Period10/07/1815/07/18

Bibliographical note

Main Track Extended Abstracts

Keywords

  • Congestion games
  • Greedy best-response
  • Limited backward induction
  • Subgame-perfect equilibrium

Cite this

Groenland, C., & Schafer, G. (2018). The curse of ties in congestion games with limited lookahead. In 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018 (Vol. 3, pp. 1941-1943). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).
Groenland, Carla ; Schafer, Guido. / The curse of ties in congestion games with limited lookahead. 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018. Vol. 3 International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2018. pp. 1941-1943
@inproceedings{770a5b6878884c408192f75440cf7e1b,
title = "The curse of ties in congestion games with limited lookahead",
abstract = "We introduce a novel framework to model limited lookahead in congestion games. Intuitively, the players enter the game sequentially and choose an optimal action under the assumption that the k - 1 subsequent players play subgame-perfectly. Our model naturally interpolates between outcomes of greedy best-response (k = 1) and subgame-perfect outcomes (k = n, the number of players). We study the impact of limited lookahead (parameterized by k) on the stability and inefficiency of the resulting outcomes. As our results reveal, increased lookahead does not necessarily lead to better outcomes; in fact, its effect crucially depends on the existence of ties and the type of game under consideration.",
keywords = "Congestion games, Greedy best-response, Limited backward induction, Subgame-perfect equilibrium",
author = "Carla Groenland and Guido Schafer",
note = "Main Track Extended Abstracts",
year = "2018",
language = "English",
isbn = "9781510868083",
volume = "3",
pages = "1941--1943",
booktitle = "17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018",
publisher = "International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)",

}

Groenland, C & Schafer, G 2018, The curse of ties in congestion games with limited lookahead. in 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018. vol. 3, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 1941-1943, 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018, Stockholm, Sweden, 10/07/18.

The curse of ties in congestion games with limited lookahead. / Groenland, Carla; Schafer, Guido.

17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018. Vol. 3 International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2018. p. 1941-1943.

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

TY - GEN

T1 - The curse of ties in congestion games with limited lookahead

AU - Groenland, Carla

AU - Schafer, Guido

N1 - Main Track Extended Abstracts

PY - 2018

Y1 - 2018

N2 - We introduce a novel framework to model limited lookahead in congestion games. Intuitively, the players enter the game sequentially and choose an optimal action under the assumption that the k - 1 subsequent players play subgame-perfectly. Our model naturally interpolates between outcomes of greedy best-response (k = 1) and subgame-perfect outcomes (k = n, the number of players). We study the impact of limited lookahead (parameterized by k) on the stability and inefficiency of the resulting outcomes. As our results reveal, increased lookahead does not necessarily lead to better outcomes; in fact, its effect crucially depends on the existence of ties and the type of game under consideration.

AB - We introduce a novel framework to model limited lookahead in congestion games. Intuitively, the players enter the game sequentially and choose an optimal action under the assumption that the k - 1 subsequent players play subgame-perfectly. Our model naturally interpolates between outcomes of greedy best-response (k = 1) and subgame-perfect outcomes (k = n, the number of players). We study the impact of limited lookahead (parameterized by k) on the stability and inefficiency of the resulting outcomes. As our results reveal, increased lookahead does not necessarily lead to better outcomes; in fact, its effect crucially depends on the existence of ties and the type of game under consideration.

KW - Congestion games

KW - Greedy best-response

KW - Limited backward induction

KW - Subgame-perfect equilibrium

UR - http://www.scopus.com/inward/record.url?scp=85054764572&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054764572&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9781510868083

VL - 3

SP - 1941

EP - 1943

BT - 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

ER -

Groenland C, Schafer G. The curse of ties in congestion games with limited lookahead. In 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018. Vol. 3. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). 2018. p. 1941-1943