If
, the security strategies are called a
*saddle point*, and
is called the *value* of the game. If this occurs, the order of the and
can be swapped without changing the value:

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
and
such that

for all and . Note that . When looking at a matrix game, a saddle point is found by finding the simple pattern shown in Figure 9.2.

By applying (9.52) (or using Figure 9.2), the saddle point is obtained when and . The result is that . In this case, neither player has regret after the game is finished. is satisfied because is the lowest cost it could have received, given that chose the third column. Likewise, is the highest cost that could have received, given that chose the bottom row.

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 tries to achieve one saddle point while 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.

Let denote the pair of choices for and , respectively. Both and are saddle points with value . What if chooses and chooses ? This is not a problem because is also a saddle point. Likewise, 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.

Steven M LaValle 2012-04-20