Simulating cardinal preferences in Boolean games: A proof technique

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.