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

#### 10.4.1.1 Eliminating Dominated Strategies

A strategy *s _{1}* for a agent

*A*

**dominates**strategy

*s*for

_{2}*A*if, for every action of the other agents, the utility of

*s*for agent

_{1}*A*is higher than the utility of

*s*for agent

_{2}*A*. Any pure strategy dominated by another strategy can be eliminated from consideration. The dominating strategy can be a randomized strategy. This can be done repeatedly.

**Example 10.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*. Agent 2 has possible actions

_{1},b_{1},c_{1}}*{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*: Agent 1 will never do

_{1}*c*if action

_{1}*a*is available to it. You can see that the payoff for Agent 1 is greater doing

_{1}*a*than doing

_{1}*c*, no matter what the other agent does.

_{1}Once action *c _{1}* is eliminated, action

*f*can be eliminated because it is dominated by the randomized strategy

_{2}*0.5×d*.

_{2}+0.5×e_{2}Once *c _{1}* and

*f*have been eliminated,

_{2}*b*is dominated by

_{1}*a*, and so Agent 1 will do action

_{1}*a*. Given that Agent 1 will do

_{1}*a*, Agent 2 will do

_{1}*d*. Thus, the payoff in this game will be 3 for Agent 1 and 5 for Agent 2.

_{2}Strategy *s _{1}*

**strictly dominates**strategy

*s*for Agent

_{2}*i*if, for all action profiles

*σ*of the other agents,

_{-i}utility(s_{1}σ_{-i},i) > utility(s_{2}σ_{-i},i).

It is clear that, if *s _{2}* is a pure strategy that is strictly
dominated by some strategy

*s*, then

_{1}*s*can never be in the support set of any Nash equilibrium. This holds even if

_{2}*s*is a stochastic strategy. Repeated elimination of strictly dominated strategies gives the same result, irrespective of the order in which the strictly dominated strategies are removed.

_{1}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 can be lost. Moreover, which equilibria are lost can depend on the order in which the dominated strategies are removed.