Conference item icon

Conference item

Computing possible and necessary equilibrium actions (and bipartisan set winners)

Abstract:

In many multiagent environments, a designer has some, but limited control over the game being played. In this paper, we formalize this by considering incompletely specified games, in which some entries of the payoff matrices can be chosen from a specified set. We show that it is NP-hard for the designer to make this choices optimally, even in zero-sum games. In fact, it is already intractable to decide whether a given action is (potentially or necessarily) played in equilibrium. We also consi...

Expand abstract
Publication status:
Accepted
Peer review status:
Peer reviewed

Actions


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Grant:
IIS- 1527434, IIS-0953756, CCF-1101659, CCF-1337215
More from this funder
Grant:
W911NF-12-1-0550, W911NF-11-1-0332, W911NF-11-1-0332
Guggenheim Fellowship More from this funder
Alexander von Humboldt Foundation More from this funder
Publisher:
Association for the Advancement of Artificial Intelligence Publisher's website
Host title:
Thirtieth AAAI Conference on Artificial Intelligence
Publication date:
2016-01-01
ISSN:
2159-5399
Source identifiers:
579634
Pubs id:
pubs:579634
UUID:
uuid:8f6e30dd-dd64-422e-88e1-f208ea71649b
Local pid:
pubs:579634
Deposit date:
2015-12-10

Terms of use


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