Linear Systems Equivalent to Two-Person Zero Sum Games

Abstract

We provide two characterizations of the set of equilibria of a two-person zero-sum “matrix” (TPZS) game. The first is a lemma, which says that a strategy profile (pair of randomizations over pure strategies) is an equilibrium if an only if along with another real number, it satisfies a specific system of linear inequalities. The second is a proposition, which says that a strategy profile is an equilibrium if an only if along with two real numbers it solves a certain linear programming problem. The proposition is a special case of the “Equivalence Theorem” in Mangasarian and Stone (1964) and for this special case, the proof appeals to the existence result about equilibrium for a TPZS game. It is well-known that the proof of this equilibrium existence result- which is not a complete characterization by itself- requires using a linear programming problem and its dual. To the best of our knowledge, the proposition we prove, is not available anywhere that is accessible to us.

A strategy profile is said to be completely mixed if it assigns positive probabilities to all pure strategies for both players and a TPZS game is said to be completely mixed if all equilibria of the game are completely mixed. We show that a completely mixed TPZS game has a unique equilibrium strategy.