Suppose that the players apply security strategies, and . This results in a cost of . How do the players feel after the outcome? may feel satisfied because given that selected , it received the lowest cost possible. On the other hand, may regret its decision in light of the action chosen by . If it had known that would be chosen, then it could have picked to receive cost , which is better than . If the game were to be repeated, then would want to change its strategy in hopes of tricking to obtain a higher reward.

Is there a way to keep both players satisfied? Any time there is a gap between and , there is regret for one or both players. If and denote the amount of regret experienced by and , respectively, then the total regret is

Thus, the only way to satisfy both players is to obtain upper and lower values such that . These are properties of the game, however, and they are not up to the players to decide. For some games, the values are equal, but for many . Fortunately, by using randomized strategies, the upper and lower values always coincide; this is covered in Section 9.3.3.

Steven M LaValle 2020-08-14