Skip to main content

Computing possible and necessary equilibrium actions (and bipartisan setwinners)

Publication ,  Conference
Brill, M; Freeman, R; Conitzer, V
Published in: 30th AAAI Conference on Artificial Intelligence, AAAI 2016
January 1, 2016

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 consider incompletely specified symmetric games in which all completions are required to be symmetric. Here, hardness holds even in weak tournament games (symmetric zero-sum games whose entries are all -1, 0, or 1) and in tournament games (symmetric zero-sum games whose non-diagonal entries are all -1 or 1). The latter result settles the complexity of the possible and necessary winner problems for a social-choice-Theoretic solution concept known as the bipartisan set. We finally give a mixed-integer linear programming formulation for weak tournament games and evaluate it experimentally.

Duke Scholars

Published In

30th AAAI Conference on Artificial Intelligence, AAAI 2016

ISBN

9781577357605

Publication Date

January 1, 2016

Start / End Page

418 / 424
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Brill, M., Freeman, R., & Conitzer, V. (2016). Computing possible and necessary equilibrium actions (and bipartisan setwinners). In 30th AAAI Conference on Artificial Intelligence, AAAI 2016 (pp. 418–424).
Brill, M., R. Freeman, and V. Conitzer. “Computing possible and necessary equilibrium actions (and bipartisan setwinners).” In 30th AAAI Conference on Artificial Intelligence, AAAI 2016, 418–24, 2016.
Brill M, Freeman R, Conitzer V. Computing possible and necessary equilibrium actions (and bipartisan setwinners). In: 30th AAAI Conference on Artificial Intelligence, AAAI 2016. 2016. p. 418–24.
Brill, M., et al. “Computing possible and necessary equilibrium actions (and bipartisan setwinners).” 30th AAAI Conference on Artificial Intelligence, AAAI 2016, 2016, pp. 418–24.
Brill M, Freeman R, Conitzer V. Computing possible and necessary equilibrium actions (and bipartisan setwinners). 30th AAAI Conference on Artificial Intelligence, AAAI 2016. 2016. p. 418–424.

Published In

30th AAAI Conference on Artificial Intelligence, AAAI 2016

ISBN

9781577357605

Publication Date

January 1, 2016

Start / End Page

418 / 424