saddle point

In the context of undergraduate multivariate calculus courses, a saddle point is a point on a two-dimensional surface in three dimensions that is a local minimum in one direction and a local maximum in another. More generally, it's a point on a differential manifold where the Gauss curvature is negative. Without going into the mathematical details, one can think of it as a point where the surface is both concave and convex, like a saddle: you can sit in it and on it at the same time.

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 a_ij 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 a_ij be a saddle point for a game in strategic form given by X,Y,A. Then the game has value a_ij , achieved when Player 1 plays the pure strategy x_i and Player 2 the pure strategy y_j .

Proof:
Player 1 is guaranteed a payoff of at least a_ij by using strategy x_i since for any strategy choice y_j' by Player 2, A(x_i, y_j') = a_ij' ≥ a_ij since a_ij is the minimum of row i. Thus V ≥ a_ij .

Player 2 is guaranteed a payoff of at least -a_ij by using strategy y_j since for any strategy choice x_i' by Player 1, the payoff to Player 2 is -A(x_i' , y_j) = -a_i'j ≥ -a_ij as a_ij ≥ a_i'j by virtue of being the maximum of column j. Thus -V ≥ -a_ij and so V ≤ a_ij .

Hence V = a_ij and the pure strategies are x_i, y_j .

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.