  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 $\epsilon$ 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.
