The Complexity of Correlated Equilibria in Generalized Games

Correlated equilibria-and their generalizations known as Φ-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 in the negative, showing that this problem is PPAD-complete.