Zero-Sum Polymatrix Games: A Generalization of Minmax
Author(s)
Cai, Yang; Candogan, Ozan; Papadimitriou, Christos; Daskalakis, Konstantinos
Downloadzerosum_final3.pdf (285.2Kb)
OPEN_ACCESS_POLICY
Open Access Policy
Creative Commons Attribution-Noncommercial-Share Alike
Terms of use
Metadata
Show full item recordAbstract
We show that in zero-sum polymatrix games, a multiplayer generalization of two-person zero-sum games, Nash equilibria can be found efficiently with linear programming. We also show that the set of coarse correlated equilibria collapses to the set of Nash equilibria. In contrast, other important properties of two-person zero-sum games are not preserved: Nash equilibrium payoffs need not be unique, and Nash equilibrium strategies need not be exchangeable or max-min.
Date issued
2016-01Department
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer ScienceJournal
Mathematics of Operations Research
Publisher
Institute for Operations Research and the Management Sciences (INFORMS)
Citation
Cai, Yang; Candogan, Ozan; Daskalakis, Constantinos, et al. “Zero-Sum Polymatrix Games: A Generalization of Minmax.” Mathematics of Operations Research 41, 2 (May 2016): 648–655. © 2016 Institute for Operations Research and the Management Sciences (INFORMS)
Version: Author's final manuscript
ISSN
0364-765X
1526-5471