Journal article

Simulating cardinal preferences in Boolean games: A proof technique

Abstract:: Boolean games are a succinct representation of strategic games with a logical ﬂavour. 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 diﬃcult. We address the second of these issues by demonstrating how cardinal utilities can be simulated via expected utility. This allows us to prove thatRationalNash and IrrationalNash are NEXP-hard, and to translate hardness results forIsNash and DValue into the Boolean games framework.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Ianovski, E., & Ong, C. (2018). Simulating cardinal preferences in Boolean games: A proof technique. Information and Computation, 261(3), 488–518.

MLA Style

Ianovski, E, and C Ong. “Simulating Cardinal Preferences in Boolean Games: A Proof Technique.” Information and Computation, vol. 261, no. 3, 2018, pp. 488–518.

Chicago Style

Ianovski, E, and C Ong. 2018. “Simulating Cardinal Preferences in Boolean Games: A Proof Technique.” Information and Computation 261 (3): 488–518.
Print

Access Document

Files:: main.pdf

(Preview, Accepted manuscript, pdf, 693.6KB, Terms of use)

Publisher copy:: 10.1016/j.ic.2017.09.008

Authors

+ Ianovski, E More by this author

Institution:: University of Oxford
Division:: MPLS Division
Department:: Computer Science
Role:: Author

+ Ong, C More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Oxford college:: Merton College
Role:: Author

+ Oxford-Man Institute of Quantitative Finance More from this funder

Funding agency for:: Ianovski, E

Publisher:: Elsevier
Journal:: Information and Computation More from this journal
Volume:: 261
Issue:: 3
Pages:: 488-518
Publication date:: 2018-04-02
Acceptance date:: 2017-11-01
DOI:: 10.1016/j.ic.2017.09.008
EISSN:: 1090-2651
ISSN:: 0890-5401

Pubs id:: pubs:747125
UUID:: uuid:48f08657-4077-4cd9-b6af-8b86ab6ab771
Local pid:: pubs:747125
Source identifiers:: 747125
Deposit date:: 2017-11-21
ARK identifier:: ark:/29072/ora_48f0865740774cd9b6af8b86ab6ab771

Terms of use

Copyright holder:: Elsevier Ltd
Copyright date:: 2018
Notes:: Copyright © 2018 Elsevier Ltd. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: https://doi.org/10.1016/j.ic.2017.09.008

Licence:: CC Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND)

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP