Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6853005 | Artificial Intelligence | 2018 | 15 Pages |
Abstract
Boolean games allow us to succinctly represent strategic games with binary payoffs in the case where the players' preferences have a structure readily expressible in propositional logic. Since their introduction, the computational aspects of Boolean games have been of interest to the multiagent community, but so far the focus has been exclusively on pure strategy equilibria. In this paper we consider the complexity of problems involving mixed strategy equilibria, such as the existence of an equilibrium satisfying a given payoff constraint. The results are obtained by the observation that a mixed strategy can hold enough information to encode the computation history of an exponential time Turing machine.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Egor Ianovski, Luke Ong,