GuaranteeNash for Boolean games is NEXP-hard
Authors: Egor Ianovski and Luke Ong
Paper Information
| Title: | GuaranteeNash for Boolean games is NEXP-hard |
| Authors: | Egor Ianovski and Luke Ong |
| Proceedings: | KR 2014 Proceedings |
| Editors: | Chitta Baral, Laura Kovacs, Giuseppe De Giacomo and Thomas Eiter |
| Keywords: | Boolean games, Complexity theory, Game theory |
| Abstract: | ABSTRACT. We show that determining whether a Boolean game has an equilibrium that guarantees every player a given payoff is NEXP-hard. In the proof we encode a non-deterministic, exponential time Turing machine by having one player play a mixed strategy from which we can infer a computation history of the machine, and the other players verify that this history does in fact represent a valid, accepting run. |
| Pages: | 10 |
| Talk: | Jul 24 12:15 |
| Paper: |  |