| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6873762 | Information and Computation | 2018 | 31 Pages |
Abstract
Boolean games are a succinct representation of strategic games with a logical flavour. While they have proved to be a popular formalism in the multiagent community, a commonly cited shortcoming is their inability to express richer utilities than success or failure. In addition to being a modelling limitation, this parsimony of preference has made proving complexity bounds difficult. We address the second of these issues by demonstrating how cardinal utilities can be simulated via expected utility. This allows us to prove that RationalNash and IrrationalNash are NEXP-hard, and to translate hardness results for IsNash and DValue into the Boolean games framework.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Egor Ianovski, Luke Ong,