On Minmax Theorems for Multiplayer Games

22nd Annual ACM-SIAM Symposium on Discrete Algorithms

数学;计算机科学

Yang Cai

Others  :  http://www.siam.org/proceedings/soda/2011/SODA11_020_caiy.pdf
PID  :  32507

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

We prove a generalization of von Neumann's minmax theorem to the class of separable multiplayer zero- sum games, introduced in [Bregman and Fokin 1998]. These games are polymatrix|that is, graphical games in which every edge is a two-player game between its endpoints|in which every outcome has zero total sum of players' payos. Our generalization of the minmax theorem implies convexity of equilibria, polynomial- time tractability, and convergence of no-regret learning algorithms to Nash equilibria. Given that Nash equi- libria in 3-player zero-sum games are already PPAD- complete, this class of games, i.e. with pairwise sep- arable utility functions, denes essentially the broad- est class of multi-player constant-sum games to which we can hope to push tractability results. Our re- sult is obtained by establishing a certain game-class collapse, showing that separable constant-sum games are payo equivalent to pairwise constant-sum polyma- trix games|polymatrix games in which all edges are constant-sum games, and invoking a recent result of [Daskalakis, Papadimitriou 2009] for these games. We also explore generalizations to classes of non- constant-sum multi-player games. A natural candidate is polymatrix games with strictly competitive games on their edges. In the two player setting, such games are minmax solvable and recent work has shown that they are merely ane transformations of zero-sum games [Adler, Daskalakis, Papadimitriou 2009]. Surprisingly we show that a polymatrix game comprising of strictly competitive games on its edges is PPAD-complete to solve, proving a striking dierence in the complexity of networks of zero-sum and strictly competitive games. Finally, we look at the role of coordination in net- worked interactions, studying the complexity of poly- matrix games with a mixture of coordination and zero- sum games. We show that nding a pure Nash equi- librium in coordination-only polymatrix games is PLS- complete; hence, computing a mixed Nash equilibrium is in PLS \ PPAD, but it remains open whether the Supported by NSF CAREER Award CCF-0953960.