The Inefficiency of Nash and Subgame Perfect Equilibria for Network Routing

José Correa, Jasper de Jong, Bart de Keijzer, Marc Uetz*

*Corresponding author for this work

    Research output: Contribution to journalArticleAcademicpeer-review

    17 Downloads (Pure)

    Abstract

    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. This 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. Second, we ask whether 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.
    Original languageEnglish
    Pages (from-to)1286-1303
    Number of pages18
    JournalMathematics of operations research
    Volume44
    Issue number4
    Early online date10 Sep 2019
    DOIs
    Publication statusPublished - Nov 2019

    Fingerprint Dive into the research topics of 'The Inefficiency of Nash and Subgame Perfect Equilibria for Network Routing'. Together they form a unique fingerprint.

  • Cite this