# EGuaranteeNash for Boolean Games is NEXP-Hard

arXiv: https://arxiv.org/abs/1312.4114 · HTML: https://mlsanity.com/paper/1312.4114/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2013.

## Built on by (most cited first, 1 of 1)

- [Boolean Observation Games](https://mlsanity.com/paper/2202.03637/) (2022)

## Abstract (arXiv)

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 ε 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.