The Complexity of Correlated Equilibria in Generalized Games
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914108077506560 |
|---|---|
| author | Bernasconi, Martino Castiglioni, Matteo Celli, Andrea Farina, Gabriele |
| author_facet | Bernasconi, Martino Castiglioni, Matteo Celli, Andrea Farina, Gabriele |
| contents | Correlated equilibria -- and their generalization $Φ$-equilibria -- are a fundamental object of study in game theory, offering a more tractable alternative to Nash equilibria in multi-player settings. While computational aspects of equilibrium computation are well-understood in some settings, fundamental questions are still open in generalized games, that is, games in which the set of strategies allowed to each player depends on the other players' strategies. These classes of games model fundamental settings in economics and have been a cornerstone of economics research since the seminal paper of Arrow and Debreu [1954]. Recently, there has been growing interest, both in economics and in computer science, in studying correlated equilibria in generalized games. It is known that finding a social welfare maximizing correlated equilibrium in generalized games is NP-hard. However, the existence of efficient algorithms to find any equilibrium remains an important open question. In this paper, we answer this question negatively, showing that this problem is PPAD-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01899 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Complexity of Correlated Equilibria in Generalized Games Bernasconi, Martino Castiglioni, Matteo Celli, Andrea Farina, Gabriele Computer Science and Game Theory Correlated equilibria -- and their generalization $Φ$-equilibria -- are a fundamental object of study in game theory, offering a more tractable alternative to Nash equilibria in multi-player settings. While computational aspects of equilibrium computation are well-understood in some settings, fundamental questions are still open in generalized games, that is, games in which the set of strategies allowed to each player depends on the other players' strategies. These classes of games model fundamental settings in economics and have been a cornerstone of economics research since the seminal paper of Arrow and Debreu [1954]. Recently, there has been growing interest, both in economics and in computer science, in studying correlated equilibria in generalized games. It is known that finding a social welfare maximizing correlated equilibrium in generalized games is NP-hard. However, the existence of efficient algorithms to find any equilibrium remains an important open question. In this paper, we answer this question negatively, showing that this problem is PPAD-complete. |
| title | The Complexity of Correlated Equilibria in Generalized Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2506.01899 |