Table of Contents

Solving Zero-Sum Games

\[\begin{bmatrix} 4 & 2 & 5 & 2\\ 2 & 1 & -1 & -20\\ 3 & 2 & 4 & 2\\ -16 & 0 & 16 & 1\\ \end{bmatrix}\]

Our row mins are

\[\begin{bmatrix} 2\\ -20\\ 2\\ -16\\ \end{bmatrix}\]

and our column maxes are

\[\begin{bmatrix} 4 & 2 & 16 & 2\\ \end{bmatrix}\]

So our saddle points are

\[\begin{pmatrix} \begin{pmatrix} 1\\0\\0\\0 \end{pmatrix}& \begin{pmatrix} 0\\1\\0\\0 \end{pmatrix}\\ \end{pmatrix}\]

which corresponds to \((e_1, e_2)\), and the others are \((e_3, e_4)\), \((e_3, e_2)\), and \((e_3, e_4)\).

Saddle points arise from optimal pure strategies, also called Pure Nash Equilibria.

Nash Equilibrium: Strategy pairs such that neither player can do better by unilaterally deviating from that strategy.

Example 2

Now take the example of

\[\begin{bmatrix} -2 & 5 & 1 & 0 & -4\\ 3 & -3 & -1 & 3 & 8\\ \end{bmatrix}\]

Taking \(\vec{p} = [p, 1-p]\) and \(A =\) our matrix, we get

\[\vec{p}^\top A = [3-5p, 8p-3, 2p-1, 3-3p, 8-12p]\]

Drawing our diagram, we can see that only columns 1 and 3 matter, so we set them equal to each other: \(3-5p = 2p-1\). Solving, we get \(p = 4/7\).

Similarly,