display | more...

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 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 .

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.

Log in or register to write something here or to contact authors.