Simplifying Games with Dominated Strategies

What Makes a Strategy "Strictly Dominated"?

The foundation of this simplification process is the concept of strict dominance. A strategy is strictly dominated if there is another strategy available to the same player that yields a strictly higher payoff, regardless of what the other players do.

Formally, for player $i$, strategy $s_i^{\prime }\in S_i$ is strictly dominated by strategy $s_i\in S_i$ if for every possible combination of strategies of the other players, $s_{-i}\in S_{-i}$, the following is true:

where $u_i$ is the payoff function for player $i$, and $s_{-i}$ represents the strategies chosen by all players other than $i$.

A rational player, by definition, aims to maximize their payoff. Therefore, they would have no reason to ever choose the strictly dominated strategy $s_i^{\prime }$ when the superior strategy $s_i$ is available.

For a rigorous presentation of this idea, let's consult a formal text.

As you read, you will notice the definition for weak dominance, which uses a "greater than or equal to" condition ($\ge$) with a strict inequality for at least one case. While related, this concept is more problematic. The elimination of weakly dominated strategies can be ambiguous because the final result may depend on the order in which strategies are removed. We will return to this important distinction later. For now, we will focus exclusively on the robust and unambiguous case of strict dominance.

The Process: Iterated Elimination

The power of this concept emerges when we apply it iteratively. The assumption of common knowledge of rationality is key here. This means that every player is rational, every player knows that every other player is rational, every player knows that every player knows that every other player is rational, and so on, ad infinitum.

This allows for the following chain of reasoning:

1. I am rational, so I will eliminate my strictly dominated strategies.
2. I know you are rational, so I know you will eliminate yours.
3. Because I know you have eliminated your dominated strategies, the game is effectively smaller. In this reduced game, one of my remaining strategies might now become dominated. I can then eliminate it.
4. You know that I know that you are rational, so you can anticipate my reasoning in step 3 and perform a similar reduction.

This iterative process of removing strictly dominated strategies is called Iterated Elimination of Strictly Dominated Strategies (IESDS). Let's see it in action.

As you saw, the process unfolds in rounds:

• Round 1: Player 2's strategy 'X' is strictly dominated by 'Z'. Knowing this, both players can conceptually delete the 'X' column from the game.
• Round 2: In the newly reduced 2x2 game, Player 1's strategy 'A' is now strictly dominated by 'B'. The 'A' row is eliminated.
• Round 3: We are left with a 1x2 game where Player 1 is locked into playing 'B'. Player 2 simply chooses the better response, which is 'Z'.

The process concludes when no more strictly dominated strategies can be found for any player in the remaining game. The strategies that survive are called rationalizable strategies. If each player is left with a single strategy, the game is said to be "solvable by IESDS," and we have a strong prediction for the game's outcome.

Properties and Formal Guarantees

Your mathematical background will appreciate that this intuitive process rests on solid theoretical ground. IESDS has several crucial properties, particularly for finite games.

First, a key result is that for finite games, the order of elimination does not matter. Whether you eliminate all dominated strategies at once in each round, or go player by player, the final set of surviving strategies will always be the same. This is known as order independence.

Second, IESDS is tightly linked to the concept of Nash Equilibrium, which we will define in the next lesson.

The properties outlined in this text are significant. They guarantee that IESDS is a "safe" procedure for simplifying games—it won't cause us to lose the most important solutions.

The Weak Dominance Pitfall and Computational Complexity

To fully appreciate the robustness of IESDS, it's useful to contrast it with the iterated elimination of weakly dominated strategies (IEWDS). As mentioned, IEWDS lacks the order-independence property, which can lead to different outcomes depending on the path of elimination.

This ambiguity makes IEWDS a less reliable tool for prediction. From a computational standpoint, this difference is also stark. Given your background in algorithms, you'll find this interesting:

• For finite games, the problem of finding and removing all strictly dominated strategies is computationally efficient (solvable in polynomial time).
• In contrast, determining whether a strategy can be eliminated via some sequence of weak dominance eliminations is NP-complete, reflecting the combinatorial complexity of checking all possible elimination orders.

This difference in complexity and reliability is why IESDS is a foundational solution concept, while IEWDS is used more sparingly, often as a secondary "refinement" tool.

Let's consider a game where IESDS doesn't lead to a unique solution.

In the game shown above, take a moment to check for any strictly dominated strategies for either player.

• For Firm 1, compare its strategies. Is A, B, or C strictly worse than another option across all of Firm 2's choices?
• Do the same for Firm 2.

You will find that no pure strategy is strictly dominated. For example, for Firm 1, 'B' is better than 'A' if Firm 2 plays 'B' (1 > 0), but worse if Firm 2 plays 'A' (0 < 4). Since we cannot find a strategy that is always worse, no strategies can be eliminated. This game cannot be simplified by IESDS. This illustrates the limitation of this method and motivates the need for a more general solution concept, which we will cover next.

Conclusion

In this lesson, we have moved from representing games to analyzing them. We introduced the concept of strict dominance and the process of iterated elimination (IESDS) as a way to predict the behavior of rational players.

The key takeaways are:

• A strictly dominated strategy is one that yields a lower payoff than another strategy, no matter what opponents do.
• IESDS is a process of iteratively removing these strategies, justified by the assumption of common knowledge of rationality.
• For finite games, IESDS is order-independent, meaning the final outcome is unique regardless of the elimination sequence.
• The set of strategies that survive IESDS contains all Nash Equilibria of the game. If the process yields a single strategy profile, that is the unique Nash Equilibrium.
• Eliminating weakly dominated strategies does not share these robust properties and can lead to ambiguous outcomes.

We saw that IESDS is a powerful tool, but it doesn't solve every game. Many games, like the 3x3 example, have no strictly dominated strategies to eliminate. To analyze these, we need a more general concept of stability. In our next lesson, we will formally define the cornerstone of modern game theory: the Nash Equilibrium.