Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

#### 10.4.1.2 Computing Randomized Strategies

We can use the fact that an agent will only randomize between
actions if the actions all have the same utility to the agent (given the
strategies of the other agent). This forms a set of constraints that
can be solved to give a Nash equilibrium. If these constraints can be
solved with numbers in the range *(0,1)*, and the mixed strategies
computed for each agent are not dominated by another strategy for the agent, then this
strategy profile
is a Nash equilibrium.

Recall that a support set is a set of pure strategies that each have non-zero probability in a Nash equilibrium.

Once dominated strategies have been eliminated, we can search over
support sets to determine whether the support sets form a Nash
equilibrium. Note that, if there are *n* actions available to an agent,
there are *2 ^{n}-1* non-empty subsets, and we have to search over combinations of
support sets for the various agents. So this is not very feasible
unless there are few non-dominated actions or there are Nash
equilibria with small support sets. To find simple (in terms of the
number of actions in the support set)
equilibria, we can search from smaller support sets to larger sets.

Suppose agent *i* is randomizing between actions
*a _{i}^{1},...,a_{i}^{ki}* in a Nash equilibrium. Let

*p*be the probability that agent

_{i}^{j}*i*does action

*a*. Let

_{i}^{j}*σ*be the strategies for the other agents as a function of their probabilities. The fact that this is a Nash equilibrium gives the following constraints:

_{-i}(p_{-i})*p*,

_{i}^{j}>0*∑*, and, for all

_{j=1}^{ki}p_{i}^{j}=1*j, j'*

utility(a_{i}^{j}σ_{-i}(p_{-i}),i) = utility(a_{i}^{j'}σ_{-i}(p_{-i}),i).

We also require that the utility of doing *a _{i}^{j}* is not less than
the utility of doing an action outside of the support set. Thus, for all

*a' ∉{a*,

_{i}^{1},...,a_{i}^{ki}}utility(a_{i}^{j}σ_{-i}(p_{-i}),i) ≥ utility(a'σ_{-i}(p_{-i}),i).

**Example 10.16:**In Example 10.9, suppose the goalkeeper jumps right with probability

*p*and the kicker kicks right with probability

_{j}*p*.

_{k}If the goalkeeper jumps right, the probability of a goal is

0.9p_{k}+0.2(1-p_{k}).

If the goalkeeper jumps left, the probability of a goal is

0.3p_{k}+0.6(1-p_{k}).

The only time the goalkeeper would randomize is if these are equal; that is, if

0.9p_{k}+0.2(1-p_{k})=0.3p_{k}+0.6(1-p_{k}).

Solving for *p _{k}* gives

*p*. Similarly, for the kicker to randomize, the probability of a goal must be the same whether the kicker kicks left or right:

_{k}=0.40.2p_{j}+ 0.6(1-p_{j}) = 0.9p_{j}+0.3(1-p_{j}).

Solving for *p _{j}* gives

*p*. Thus, the only Nash equilibrium is where

_{j}= 0.3*p*and

_{k}=0.4*p*.

_{j}= 0.3