Note 12 - Zero-Sum Games
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,