On the Complexity of Pareto-Optimal Nash and Strong Equilibria

Martin Hoefer, Alexander Skopalik

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)

    Abstract

    We consider the computational complexity of coalitional solution concepts in scenarios related to load balancing such as anonymous and congestion games. In congestion games, Pareto-optimal Nash and strong equilibria, which are resilient to coalitional deviations, have recently been shown to yield significantly smaller inefficiency. Unfortunately, we show that several problems regarding existence, recognition, and computation of these concepts are hard, even in seemingly special classes of games. In anonymous games with constant number of strategies, we can efficiently recognize a state as Pareto-optimal Nash or strong equilibrium, but deciding existence for a game remains hard. In the case of player-specific singleton congestion games, we show that recognition and computation of both concepts can be done efficiently. In addition, in these games there are always short sequences of coalitional improvement moves to Pareto-optimal Nash and strong equilibria that can be computed efficiently.
    Original languageEnglish
    Pages (from-to)441-453
    Number of pages13
    JournalTheory of computing systems
    DOIs
    Publication statusPublished - Dec 2013

    Keywords

    • Anonymous games
    • Congestion games
    • Convergence
    • Equilibrium computation
    • Load balancing
    • Nash equilibrium
    • Strong equilibrium

    Fingerprint Dive into the research topics of 'On the Complexity of Pareto-Optimal Nash and Strong Equilibria'. Together they form a unique fingerprint.

    Cite this