Many results in game theory are linked to topological notions; a saddle point is an example. This writeup applies to a game in two player, zero-sum strategic form X,Y,A.
An element aij of a matrix A is described as a Saddle point if it equals both the
minimum of row i and the maximum of column j.
A payoff matrix needn't have a saddle point, but if it does, then the usually technical minimax theorem is easily shown to hold true:
(Minimax Theorem for a game with a Saddle point)
Let aij be a saddle point for
a game in strategic form given by X,Y,A. Then the game has value aij , achieved when Player
1 plays the pure strategy xi and Player 2 the pure strategy yj .
Proof:
Player 1 is guaranteed a payoff of at least aij by using strategy xi since for any strategy
choice yj' by Player 2, A(xi, yj') = aij' ≥ aij since aij is the minimum of row i. Thus V ≥ aij .
Player 2 is guaranteed a payoff of at least -aij by using strategy yj since for any strategy choice xi'
by Player 1, the payoff to Player 2 is -A(xi' , yj) = -ai'j ≥ -aij as aij ≥ ai'j by virtue of being the maximum of column j. Thus -V ≥ -aij and so V ≤ aij .
Hence V = aij and the pure strategies are xi, yj .
2 × 2 Games
Any game described by a 2 × 2 payoff matrix can be dealt with by the preceeding theorem. It is
easy to check such a small matrix for a Saddle point, and furthermore in the absence of such an
element, the minimax theorem can be proven by direct calculation of mixed strategies for each player that yield the
same value:
(Minimax Theorem for a 2×2 game without a Saddle point)
If the strategic form
of a game is given by
a b
c d
with none of {a, b, c, d} a Saddle point, then the game has value V = (ad - bc) / (a - b + d - c)
Player 1 has a mixed strategy which ensures an average gain of V, regardless of Player 2’s strategy.
Player 2 has a mixed strategy which ensures an average loss of V, regardless of Player 1’s strategy.
The proof is a matter of routine algebra after identifying appropriate cases a<b and a>b ; the appropriate calculations can be found in section 2.4.2 of the print version of this entry (see homenode).
Games with more than two options per player may reduce to the 2×2 case as a result of dominated strategies, at which point the above analysis ensures the minimax theorem easily holds for them too. The argument used in the proof implicitly demonstrates that two players using strategies that yield the value of a zero-sum game are in Nash equilibrium.
Part of A survey of game theory- see project homenode for details and links to the print version.