11.4.1 Computing Nash Equilibria

To compute a Nash equilibrium for a game in normal form, there are three steps:

1.

Eliminate dominated strategies.
2.

Determine support set, the set of actions which have non-zero probabilities.
3.

Determine the probability for the actions in the support set.

It turns out that the second of these is the most difficult.

Eliminating Dominated Strategies

A strategy $s_{1}$ for a agent $A$ dominates strategy $s_{2}$ for $A$ if, for every action of the other agents, the utility of $s_{1}$ for agent $A$ is higher than the utility of $s_{2}$ for agent $A$ . This is formalized below. Any pure strategy dominated by another strategy can be eliminated from consideration. The dominating strategy could be a randomized strategy. Removing dominated strategies can be done repeatedly.

Example 11.15.

Consider the following payoff matrix, where the first agent chooses the row and the second agent chooses the column. In each cell is a pair of payoffs: the payoff for Agent 1 and the payoff for Agent 2. Agent 1 has actions $\{a_{1},b_{1},c_{1}\}$ . Agent 2 has actions $\{d_{2},e_{2},f_{2}\}$ .

		Agent 2
		$d_{2}$	$e_{2}$	$f_{2}$
	$a_{1}$	$3,5$	$5,1$	$1,2$
Agent 1	$b_{1}$	$1,1$	$2,9$	$6,4$
	$c_{1}$	$2,6$	$4,7$	$0,8$

(Before looking at the solution try to work out what each agent should do.)

Action $c_{1}$ can be removed because it is dominated by action $a_{1}$ : Agent 1 will never do $c_{1}$ if action $a_{1}$ is available to it. Notice how the payoff for Agent 1 is greater doing $a_{1}$ than doing $c_{1}$ , no matter what the other agent does.

Once action $c_{1}$ is eliminated, action $f_{2}$ can be eliminated because it is dominated for Agent 2 by the randomized strategy $0.5*d_{2}+0.5*e_{2}$ .

Once $c_{1}$ and $f_{2}$ have been eliminated, $b_{1}$ is dominated by $a_{1}$ , and so Agent 1 will do action $a_{1}$ . Given that Agent 1 will do $a_{1}$ , Agent 2 will do $d_{2}$ . Thus, the payoff in this game will be 3 for Agent 1 and 5 for Agent 2.

Strategy $s_{1}$ strictly dominates strategy $s_{2}$ for Agent $i$ if, for all action profiles $\sigma_{-i}$ of the other agents,

utility(s_{1}\sigma_{-i},i)>utility(s_{2}\sigma_{-i},i)

in which case $s_{2}$ is strictly dominated by $s_{1}$ . If $s_{2}$ is a pure strategy that is strictly dominated by some strategy $s_{1}$ , then $s_{2}$ can never be in the support set of any Nash equilibrium. This holds even if $s_{1}$ is a stochastic strategy. Repeated elimination of strictly dominated strategies gives the same result, regardless of the order in which the strictly dominated strategies are removed.

There are also weaker notions of domination, where the greater than symbol in the preceding formula is replaced by greater than or equal. If the weaker notion of domination is used, there is always a Nash equilibrium with support of the non-dominated strategies. However, some Nash equilibria may be lost. Moreover, which equilibria are lost can depend on the order in which the dominated strategies are removed.

Computing Randomized Strategies

An agent will only randomize between actions if the actions all have the same utility to the agent, given the strategies of the other agents. This idea leads to a set of constraints that can be solved to compute 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, an agent 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. This is not feasible unless there are only a 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, an agent can search from smaller support sets to larger sets.

Suppose agent $i$ is randomizing between actions $a_{i}^{1},\dots,a_{i}^{k_{i}}$ in a Nash equilibrium. Let $p_{i}^{j}$ be the probability that agent $i$ does action $a_{i}^{j}$ . Let $\sigma_{-i}$ be the strategies for the other agents, which is a function of their probabilities. The fact that this is a Nash equilibrium gives the following constraints: $p_{i}^{j}>0$ , $\sum_{j=1}^{k_{i}}p_{i}^{j}=1$ , and, for all $j,j^{\prime}$

utility(a_{i}^{j}\sigma_{-i},i)=utility(a_{i}^{j^{\prime}}\sigma_{-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^{\prime}\notin\{a_{i}^{1},\dots,a_{i}^{k_{i}}\}$ ,

utility(a_{i}^{j}\sigma_{-i},i)\geq utility(a^{\prime}\sigma_{-i},i).

Example 11.16.

In Example 11.9, suppose the goalkeeper jumps right with probability $p_{g}$ and the kicker kicks right with probability $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_{k}=0.4$ .

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

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

Solving for $p_{g}$ gives $p_{g}=0.3$ .

Thus, the only Nash equilibrium has $p_{k}=0.4$ and $p_{g}=0.3$ .

Artificial Intelligence 2E

11.4.1 Computing Nash Equilibria

Eliminating Dominated Strategies

Example 11.15.

Computing Randomized Strategies

Example 11.16.

Artificial
Intelligence 2E