Saddle points

If $\underline{L}^*= \overline{L}^*$, the security strategies are called a saddle point, and $L^*= \underline{L}^*= \overline{L}^*$ is called the value of the game. If this occurs, the order of the $\max$ and $\min$ can be swapped without changing the value:

$$L^*= \min_{u \in U} \Big\{ \max_{v \in V} \Big\{ L(u,v) \Big\} \Big\} = \max_{v \in V} \Big\{ \min_{u \in U} \Big\{ L(u,v) \Big\} \Big\} .$$ (9.51)

A saddle point is sometimes referred to as an equilibrium because the players have no incentive to change their choices (because there is no regret). A saddle point is defined as any $u^{*} \in U$ and $v^{*} \in V$ such that

$$L(u^{*},v) \leq L(u^{*},v^{*}) \leq L(u,v^{*})$$ (9.52)

for all $u \in U$ and $v \in V$. Note that $L^*= L(u^{*},v^{*})$. When looking at a matrix game, a saddle point is found by finding the simple pattern shown in Figure 9.2.

Figure 9.2: A saddle point can be detected in a matrix by finding a value $L^*$ that is lowest among all elements in its column and greatest among all elements in its row.

Example 9..14 (A Deterministic Saddle Point)   Here is a matrix game that has a saddle point:

$$\begin{tabular}{cc} & $V$ $U$ & \begin{tabular}{\vert c\vert... ... \hline 1 & -1 & 7 \hline 0 & -2 & 4 \hline \end{tabular} \end{tabular} .$$ (9.53)

By applying (9.52) (or using Figure 9.2), the saddle point is obtained when $u = 3$ and $v = 3$. The result is that $L^*= 4$. In this case, neither player has regret after the game is finished. ${{\rm P}_1}$ is satisfied because $4$ is the lowest cost it could have received, given that ${{\rm P}_2}$ chose the third column. Likewise, $4$ is the highest cost that ${{\rm P}_2}$ could have received, given that ${{\rm P}_1}$ chose the bottom row. $\blacksquare$

What if there are multiple saddle points in the same game? This may appear to be a problem because the players have no way to coordinate their decisions. What if ${{\rm P}_1}$ tries to achieve one saddle point while ${{\rm P}_2}$ tries to achieve another? It turns out that if there is more than one saddle point, then there must at least be four, as shown in Figure 9.3. As soon as we try to make two ``+'' patterns like the one shown in Figure 9.2, they intersect, and four saddle points are created. Similar behavior occurs as more saddle points are added.

Figure 9.3: A matrix could have more than one saddle point, which may seem to lead to a coordination problem between the players. Fortunately, there is no problem, because the same value will be received regardless of which saddle point is selected by each player.

Example 9..15 (Multiple Saddle Points)   This game has multiple saddle points and follows the pattern in Figure 9.3:

$$\begin{tabular}{cc} & $V$ $U$ & \begin{tabular}{\vert c\vert... ...1 & 0 & -2 \hline 3 & 2 & -7 & 3 & 8 \hline \end{tabular} \end{tabular} .$$ (9.54)

Let $(i,j)$ denote the pair of choices for ${{\rm P}_1}$ and ${{\rm P}_2}$, respectively. Both $(2,2)$ and $(4,4)$ are saddle points with value $V = 0$. What if ${{\rm P}_1}$ chooses $u=2$ and ${{\rm P}_2}$ chooses $v = 4$? This is not a problem because $(2,4)$ is also a saddle point. Likewise, $(4,2)$ is another saddle point. In general, no problems are caused by the existence of multiple saddle points because the resulting cost is independent of which saddle point is attempted by each player. $\blacksquare$