Journal article
The complexity of decision problems about equilibria in two-player Boolean games
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 513.4KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.artint.2018.04.006
Authors
+ Oxford-Man Institute of Quantitative Finance
More from this funder
- Funding agency for:
- Ianovski, E
- Publisher:
- Elsevier
- Journal:
- Artificial Intelligence More from this journal
- Volume:
- 261
- Pages:
- 1-15
- Publication date:
- 2018-05-29
- Acceptance date:
- 2018-04-26
- DOI:
- EISSN:
-
1872-7921
- ISSN:
-
0004-3702
- Keywords:
- Pubs id:
-
pubs:844713
- UUID:
-
uuid:55d54673-1ded-4092-8a69-ec2c3a6b3b2f
- Local pid:
-
pubs:844713
- Source identifiers:
-
844713
- Deposit date:
-
2018-04-28
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier
- Copyright date:
- 2018
- Notes:
- © 2018 Elsevier B.V. All rights reserved. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: https://doi.org/10.1016/j.artint.2018.04.006
If you are the owner of this record, you can report an update to it here: Report update to this record