• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Simulating cardinal preferences in Boolean games: A proof technique

Information and Computation. 2018. No. 261. P. 488-518.
Ianovski E., Ong L.

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 IrrationalNashare NEXP-hard, and to translate hardness results for IsNash and DValue into the Boolean games framework.