Engine · Chapter 0, Mathematical Foundations

The saddle point

Why does a two-by-two game have a value, and what does a mixed strategy guarantee?

The payoff matrix (A's payoff; B pays it)

rows columns

	y1	y2
x1
x2

Games from the book

Value of the game

- \frac{1}{3}

≈ -0.3333

In pure strategies A can guarantee $- 1$ (row 1) and B can hold A to $0$ (column 2); the gap closes only with randomisation.

D Chapter 6 certifies value $- \frac{1}{3}$ with $(\frac{1}{3}, \frac{2}{3})$ on both sides. Agreement, exactly.

The certificate

$p^{*} = (\frac{1}{3}, \frac{2}{3})$

$q^{*} = (\frac{1}{3}, \frac{2}{3})$

$L (p^{*}) = min_{y} (p^{* ⊤} G)_{y} = - \frac{1}{3}, U (q^{*}) = max_{x} (G q^{*})_{x} = - \frac{1}{3}$

Equal guarantees are a saddle point and a Nash pair (the bridge theorem); the pair is unexploitable.

A's payoff

p^{⊤} Gq

over A's mixture (left to right: P(x1) from 0 to 1) and B's (bottom to top: P(y1) from 0 to 1); dark is low, red is high. The ring is the saddle point. Drag the dot.

Your pair

$p = (\frac{1}{2}, \frac{1}{2}), q = (\frac{1}{2}, \frac{1}{2})$

A's guarantee $L (p)$	$- \frac{1}{2}$
Payoff $p^{⊤} Gq$	$- \frac{1}{4}$
B's ceiling $U (q)$	$0$
A's exploitability	$\frac{1}{4}$
B's exploitability	$\frac{1}{4}$
Gap $U (q) - L (p)$	$\frac{1}{2}$

The bracket $L (p) \leq p^{⊤} Gq \leq U (q)$ always holds; the gap is the pair's total exploitability, and a certificate is a proof that it is zero.