∃GUARANTEENASH for Boolean games is NEXP-Hard

Egor Ianovski, C.-h. Luke OngOxford 2014

TL;DR

This paper tackles the computational complexity of finding mixed strategy Nash equilibria in Boolean games, a powerful model for multiagent systems. The authors prove that determining if a Boolean game has a mixed strategy equilibrium where every player achieves a specific minimum payoff is NEXP-hard, making it a challenging problem for even the most powerful theoretical computers.

What Problem Does This Paper Address?

Boolean games are a flexible way to model strategic interactions among multiple agents. They represent games using propositional logic, where players control variables and have goals expressed as logical formulas. While much research has focused on pure strategy Nash equilibria (where each player chooses a single, fixed action), this is a limitation because many games, like the classic "matching pennies," don't have pure strategy equilibria. Mixed strategies, where players randomize their actions, are a more general concept that guarantees an equilibrium exists for any finite game. However, the computational complexity of finding these mixed strategy equilibria, especially with guaranteed payoffs, has remained largely unexplored for Boolean games. This paper addresses this gap by investigating the complexity of a specific decision problem: ∃GUARANTEENASH. This problem asks if there exists a mixed strategy Nash equilibrium where each player i achieves a utility of at least v[i], for a given payoff vector v.

Methods

The core of the paper is a reduction from a known NEXP-complete problem, NEXPTM (Non-deterministic Exponential Time Turing Machine acceptance), to the ∃GUARANTEENASH problem for Boolean games. This means they construct a Boolean game instance from any given instance of NEXPTM such that the Boolean game has a specific type of Nash equilibrium if and only if the Turing machine accepts its input within a certain number of steps.

The construction involves creating a complex Boolean game with six players. Each player is assigned specific propositional variables and goal formulas. The game is designed to simulate the computation of a non-deterministic Turing machine.

  • Player One is responsible for describing a potential computation history of the Turing machine, including tape contents, head position, and states at each step.
  • Player Two verifies the consistency of the head's movement across different cells and time steps.
  • Player Three checks if the transitions between computation steps are valid according to the Turing machine's rules.
  • Players Four, Five, and Six are essentially "matching pennies" players. They are used to force the other players to randomize their strategies, ensuring that the game explores a wide range of possible computation histories and that the desired equilibrium properties are met.

The proof carefully constructs the players' goal formulas (ψᵢ) and variable assignments (Φᵢ) to precisely mirror the acceptance condition of the Turing machine. The utilities are designed such that achieving a certain payoff in the Boolean game corresponds to the Turing machine accepting.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and constructs artificial game instances for its proofs.

Key Insights and Ideas

  • Mixed strategies are computationally hard for Boolean games: The paper establishes that even for a restricted class of games (Boolean games), finding mixed strategy Nash equilibria with guaranteed payoffs is computationally very difficult (NEXP-hard). This contrasts with the often more tractable pure strategy equilibria.
  • Boolean games can encode complex computations: The intricate construction of the six-player Boolean game demonstrates its power as a universal model for computation. The game effectively simulates a Turing machine's execution.
  • The role of "dummy" players: The use of players like Four, Five, and Six, who play simple matching pennies games, is crucial. They act as a mechanism to enforce randomization and ensure that the other players cannot trivially satisfy their goals without exploring all possibilities, which is essential for the reduction to work.
  • Connection to Boolean Circuit Games: The paper highlights that Boolean games are a specific case of Boolean circuit games. While prior work showed ∃GUARANTEENASH is NEXP-complete for Boolean circuit games, this paper's result for Boolean games is a direct proof of NEXP-hardness, not just a consequence of a more general result.
  • Dual problem (∀GUARANTEENASH) is coNEXP-hard: The paper also shows that the problem of determining if all Nash equilibria satisfy a payoff condition is coNEXP-hard, further underscoring the computational challenges in this area.

Key Results

  • The decision problem ∃GUARANTEENASH for Boolean games is NEXP-hard.
  • Consequently, ∃GUARANTEENASH for Boolean games is NEXP-complete.
  • The problem ∀GUARANTEENASH (whether all Nash equilibria guarantee a payoff) is coNEXP-hard.

The proof provides a constructive method to build a Boolean game instance from a NEXPTM instance, demonstrating the hardness. The specific payoffs achieved in the equilibrium are derived from the parameters of the Turing machine and the number of steps allowed.

Limitations and Future Work

  • Number of Players: The proof uses six players, which is quite complex. The authors suggest that the number of players can be reduced to three by collapsing players with similar roles. They also pose the question of whether it's possible to reduce it further to two players.
  • Membership Results: While hardness results are established, the paper notes that membership results for certain problems (like computing a mixed equilibrium) are still open and very challenging, potentially requiring new theoretical tools beyond current complexity classes like PPAD.
  • ε-equilibria: The paper briefly touches upon ε-equilibria as a way to handle games where rational equilibria might not exist or are hard to compute. It suggests that the problem of finding ε-equilibria for Boolean games might be NEXP-complete.
  • Generalization: The paper focuses on Boolean games. Extending these complexity results to other expressive game models could be a future direction.

Summary updated

Abstract

Boolean games are an expressive and natural formalism through which to investigate problems of strategic interaction in multiagent systems. Although they have been widely studied, almost all previous work on Nash equilibria in Boolean games has focused on the restricted setting of pure strategies. This is a shortcoming as finite games are guaranteed to have at least one equilibrium in mixed strategies, but many simple games fail to have pure strategy equilibria at all. We address this by showing that a natural decision problem about mixed equilibria: determining whether a Boolean game has a mixed strategy equilibrium that guarantees every player a given payoff, is NEXP-hard. Accordingly, the e variety of the problem is NEXP-complete. The proof can be adapted to show coNEXP-hardness of a similar question: whether all Nash equilibria of a Boolean game guarantee every player at least the given payoff.
BibTeX
@inproceedings{ianovski2014guaranteenash,
  author = {Egor Ianovski and C.-H. Luke Ong},
  title = {{∃GUARANTEENASH for Boolean games is NEXP-Hard}},
  booktitle = {Oxford},
  year = {2014},
}
Figure