Zero-Sum Polymatrix Games: A Generalization of Minmax

Yang Cai, Ozan Candogan, Constantinos Daskalakis, Christos Papadimitriou

Mathematics of Operations Research · 2016 · 51 citations · 5 references

DOIFull text

Open access

Concepts

Abstract

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.

References

5