Equilibria in Multiplayer Graph Games: An Algorithmic Study
For researchers in algorithmic game theory and verification, this work establishes the computational hardness of finding constrained equilibria in multiplayer games, though the results are incremental as they extend known techniques.
This paper studies the complexity of deciding whether multiplayer graph games contain equilibria (Nash and four alternatives) where each player's payoff lies in a given interval, providing complexity results for each equilibrium notion.
To verify the robustness of a program or protocol, it is common in the computer science community to rely on the theoretical framework of game theory. In particular, if one seeks to enforce a desired property, or specification, despite an unpredictable environment, a useful abstraction is to model the situation as a two-player zero-sum game. The goal is then to find a strategy for the system that guarantees the specification against any strategy of the environment. However, to model more complex situations, such as multiple systems with different objectives or an environment composed of various agents, the richer framework of multiplayer games must be considered. In this setting, a natural question is to identify equilibria, i.e., strategy profiles that are robust in the sense that no player has an incentive to deviate. The most well-known equilibrium concept is the Nash equilibrium, but several alternatives exist. We study five such notions and, for each of them, we provide complexity results for the constrained existence problem, which consists of deciding whether a given game contains an equilibrium that ensures each player a payoff within a specified interval.