Research Repository

The Inefficiency of Nash and Subgame Perfect Equilibria for Network Routing

Correa, Jose and de Jong, Jasper and De Keijzer, Bart and Uetz, Marc (2019) 'The Inefficiency of Nash and Subgame Perfect Equilibria for Network Routing.' Mathematics of Operations Research, 44 (4). ISSN 0364-765X

sequentiality-journal-final.pdf - Accepted Version

Download (450kB) | Preview


This paper provides new bounds on the quality of equilibria in finite congestion games with affine cost functions, specifically for atomic network routing games. It is well known that the price of anarchy equals exactly 5/2 in general. For symmetric network routing games, it is at most (5n−2)/(2n+ 1), where n is the number of players. The paper answers to two open questions for congestion games. First, we show that the price of anarchy bound (5n−2)/(2n+ 1) is tight for symmetric network routing games, thereby answering a decade-old open question. Secondly, we ask if sequential play and subgame perfection allows to evade worst-case Nash equilibria, and thereby reduces the price of anarchy. This is motivated by positive results for congestion games with a small number of players, as well as recent results for other resource allocation problems. Our main result is the perhaps surprising proof that subgame perfect equilibria of sequential symmetric network routing games with linear cost functions can have an unbounded price of anarchy. We complete the picture by analyzing the case with two players: We show that the sequential price of anarchy equals 7/5, and that computing the outcome of a subgame perfect equilibrium is NP-hard.

Item Type: Article
Uncontrolled Keywords: Nash and subgame perfect equilibrium, price of anarchy, congestion games, network routing
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 19 Dec 2018 13:48
Last Modified: 19 Jun 2020 17:15

Actions (login required)

View Item View Item