Computing pure Nash and strong equilibria in bottleneck congestion games

Tobias Harks, Martin Hoefer, Max Klimm, Alexander Skopalik

    Research output: Contribution to journalArticleAcademicpeer-review

    13 Citations (Scopus)
    36 Downloads (Pure)

    Abstract

    Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria - a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g.; matroid or single-commodity bottleneck congestion games. In addition, we examine the more demanding goal to reach equilibria in polynomial time using natural improvement dynamics. Using unilateral improvement dynamics in matroid games pure Nash equilibria can be reached efficiently. In contrast, computing even a single coalitional improvement move in matroid and single-commodity games is strongly NP-hard. In addition, we establish a variety of hardness results and lower bounds regarding the duration of unilateral and coalitional improvement dynamics. They continue to hold even for convergence to approximate equilibria.

    Original languageEnglish
    Pages (from-to)193-215
    Number of pages23
    JournalMathematical programming
    Volume141
    Issue number1-2
    DOIs
    Publication statusPublished - 1 Oct 2013

    Fingerprint

    Congestion Games
    Matroid
    Computing
    Game
    Polynomials
    Network routing
    Nash Equilibrium
    Polynomial time
    Computational complexity
    Hardness
    Resilience
    Strengthening
    Computational Complexity
    Routing
    Continue
    Deviation
    NP-complete problem
    Lower bound

    Keywords

    • Bottleneck congestion games
    • Computation of strong equilibria
    • Improvement dynamics

    Cite this

    Harks, Tobias ; Hoefer, Martin ; Klimm, Max ; Skopalik, Alexander. / Computing pure Nash and strong equilibria in bottleneck congestion games. In: Mathematical programming. 2013 ; Vol. 141, No. 1-2. pp. 193-215.
    @article{4067cc211b714a03ac6df5687c55579c,
    title = "Computing pure Nash and strong equilibria in bottleneck congestion games",
    abstract = "Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria - a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g.; matroid or single-commodity bottleneck congestion games. In addition, we examine the more demanding goal to reach equilibria in polynomial time using natural improvement dynamics. Using unilateral improvement dynamics in matroid games pure Nash equilibria can be reached efficiently. In contrast, computing even a single coalitional improvement move in matroid and single-commodity games is strongly NP-hard. In addition, we establish a variety of hardness results and lower bounds regarding the duration of unilateral and coalitional improvement dynamics. They continue to hold even for convergence to approximate equilibria.",
    keywords = "Bottleneck congestion games, Computation of strong equilibria, Improvement dynamics",
    author = "Tobias Harks and Martin Hoefer and Max Klimm and Alexander Skopalik",
    year = "2013",
    month = "10",
    day = "1",
    doi = "10.1007/s10107-012-0521-3",
    language = "English",
    volume = "141",
    pages = "193--215",
    journal = "Mathematical programming",
    issn = "0025-5610",
    publisher = "Springer",
    number = "1-2",

    }

    Computing pure Nash and strong equilibria in bottleneck congestion games. / Harks, Tobias; Hoefer, Martin; Klimm, Max; Skopalik, Alexander.

    In: Mathematical programming, Vol. 141, No. 1-2, 01.10.2013, p. 193-215.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Computing pure Nash and strong equilibria in bottleneck congestion games

    AU - Harks, Tobias

    AU - Hoefer, Martin

    AU - Klimm, Max

    AU - Skopalik, Alexander

    PY - 2013/10/1

    Y1 - 2013/10/1

    N2 - Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria - a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g.; matroid or single-commodity bottleneck congestion games. In addition, we examine the more demanding goal to reach equilibria in polynomial time using natural improvement dynamics. Using unilateral improvement dynamics in matroid games pure Nash equilibria can be reached efficiently. In contrast, computing even a single coalitional improvement move in matroid and single-commodity games is strongly NP-hard. In addition, we establish a variety of hardness results and lower bounds regarding the duration of unilateral and coalitional improvement dynamics. They continue to hold even for convergence to approximate equilibria.

    AB - Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria - a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g.; matroid or single-commodity bottleneck congestion games. In addition, we examine the more demanding goal to reach equilibria in polynomial time using natural improvement dynamics. Using unilateral improvement dynamics in matroid games pure Nash equilibria can be reached efficiently. In contrast, computing even a single coalitional improvement move in matroid and single-commodity games is strongly NP-hard. In addition, we establish a variety of hardness results and lower bounds regarding the duration of unilateral and coalitional improvement dynamics. They continue to hold even for convergence to approximate equilibria.

    KW - Bottleneck congestion games

    KW - Computation of strong equilibria

    KW - Improvement dynamics

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

    U2 - 10.1007/s10107-012-0521-3

    DO - 10.1007/s10107-012-0521-3

    M3 - Article

    VL - 141

    SP - 193

    EP - 215

    JO - Mathematical programming

    JF - Mathematical programming

    SN - 0025-5610

    IS - 1-2

    ER -