The curse of ties in congestion games with limited lookahead
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.
|Congestion games, Greedy best-response, Limited backward induction, Subgame-perfect equilibrium|
|International Conference on Autonomous Agents and Multi-Agent Systems|
|Organisation||Networks and Optimization|
Groenland, C, & Schäfer, G. (2018). The curse of ties in congestion games with limited lookahead. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (pp. 1941–1943).