Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

10.4.1.1 Eliminating Dominated Strategies

A strategy s1 for a agent A dominates strategy s2 for A if, for every action of the other agents, the utility of s1 for agent A is higher than the utility of s2 for agent 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 {a1,b1,c1}. Agent 2 has possible actions {d2,e2,f2}.
Agent 2
d2e2f2
a13,55,11,2
Agent 1b11,12,96,4
c12,64,70,8

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

Action c1 can be removed because it is dominated by action a1: Agent 1 will never do c1 if action a1 is available to it. You can see that the payoff for Agent 1 is greater doing a1 than doing c1, no matter what the other agent does.

Once action c1 is eliminated, action f2 can be eliminated because it is dominated by the randomized strategy 0.5×d2+0.5×e2.

Once c1 and f2 have been eliminated, b1 is dominated by a1, and so Agent 1 will do action a1. Given that Agent 1 will do a1, Agent 2 will do d2. Thus, the payoff in this game will be 3 for Agent 1 and 5 for Agent 2.

Strategy s1 strictly dominates strategy s2 for Agent i if, for all action profiles σ-i of the other agents,

utility(s1 σ-i,i) > utility(s2σ-i,i).

It is clear that, if s2 is a pure strategy that is strictly dominated by some strategy s1, then s2 can never be in the support set of any Nash equilibrium. This holds even if s1 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.

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.