Since a game under Formulation 9.7 can be nicely expressed as a matrix, it is tempting to use linear algebra to conveniently express expected costs. Let and . As in Section 9.1.3, a randomized strategy for can be represented as an -dimensional vector,

(9.55) |

The probability axioms of Section 9.1.2 must be satisfied: 1) for all , and 2) . If is considered as a point in , then the two constraints imply that it must lie on an -dimensional simplex (recall Section 6.3.1). If , this means that lies in a triangular subset of . Similarly, let represent a randomized strategy for as an -dimensional vector,

that also satisfies the probability axioms. In (9.56), denotes

Let denote the expected cost that will be received if plays and plays . This can be computed as

Note that the cost, , makes use of the assumption in Formulation 9.7 that the actions are consecutive integers. The expected cost can be alternatively expressed using the cost matrix, . In this case

in which the product yields a scalar value that is precisely (9.57). To see this, first consider the product . This yields an -dimensional vector in which the th element is the expected cost that would receive if it tries . Thus, it appears that views as a nature player under the probabilistic model. Once and are multiplied, a scalar value is obtained, which averages the costs in the vector according the probabilities of .

Let and denote the set of all randomized strategies for
and
, respectively. These spaces include strategies that are
equivalent to the deterministic strategies considered in Section
9.3.2 by assigning probability one to a single action.
Thus, and can be considered as expansions of the set of
possible strategies in comparison to what was available in the
deterministic setting. Using and , *randomized security
strategies* for
and
are defined as

and

respectively. These should be compared to (9.44) and (9.46). The differences are that the space of strategies has been expanded, and expected cost is now used.

The *randomized upper value* is defined as

and the

Since and include the deterministic security strategies, and . These inequalities imply that the randomized security strategies may have some hope in closing the gap between the two values in general.

The most fundamental result in zero-sum game theory was shown by von
Neumann [956,957], and it states that
for any game in Formulation 9.7. This yields
the *randomized value*
for the game. This means that there
will never be expected regret if the players stay with their security
strategies. If the players apply their randomized security
strategies, then a *randomized saddle point* is obtained. This
saddle point cannot be seen as a simple pattern in the matrix
because it instead exists over and .

The guaranteed existence of a randomized saddle point is an important result because it demonstrates the value of randomization when making decisions against an intelligent opponent. In Example 9.7, it was intuitively argued that randomization seems to help when playing against an intelligent adversary. When playing the game repeatedly with a deterministic strategy, the other player could learn the strategy and win every time. Once a randomized strategy is used, the players will not experience regret.

Steven M LaValle 2012-04-20