Best Response and Dominated Strategies

1. Best Response

In the previous lesson, we calculated player 1's expected payoff in Matching Pennies for playing "Head" or "Tail", given that player 2 plays "Head" with probability $q$. We found:

• $E[u_1(\text{Head},s_2)]=2q-1$
• $E[u_1(\text{Tail},s_2)]=1-2q$

A rational player, aiming to maximize their payoff, would simply compare these two values.

• If $2q-1>1-2q$ (which simplifies to $q>1/2$), Player 1 should play "Head".
• If $2q-1<1-2q$ (i.e., $q<1/2$), Player 1 should play "Tail".
• If $2q-1=1-2q$ (i.e., $q=1/2$), Player 1 is indifferent and gets the same payoff from "Head" or "Tail" (or any mix of them).

This simple comparison is the core idea of a best response.

Definition: Best Response
A strategy $s_i^{\ast }$ for player $i$ is a best response to an opponent strategy profile $s_{-i}$ if it maximizes player $i$'s payoff. That is, for any other strategy $s_i$ available to player $i$:
$u_i(s_i^{\ast },s_{-i})\ge u_i(s_i,s_{-i})$

The following video provides a detailed walkthrough of how to formalize this concept and derive a player's best response function, which specifies their best response for every possible strategy of the opponent.

Understanding how to find a player's best response to a given strategy is a fundamental skill. It is the building block for the central solution concept in game theory, Nash Equilibrium, which we will discuss in the next lesson.

2. Strictly Dominated Strategies

While "best response" identifies what to do in a specific situation, the concept of dominance helps us identify strategies that a player should never use, regardless of the situation.

Let's look at the classic Prisoner's Dilemma:

Consider Player 1's choices:

• If Player 2 Cooperates, Player 1 gets a payoff of 3 from Defecting vs. 2 from Cooperating. Defect is better.
• If Player 2 Defects, Player 1 gets a payoff of 1 from Defecting vs. 0 from Cooperating. Defect is better.

No matter what Player 2 does, Player 1 gets a strictly higher payoff by choosing Defect. In this case, we say that Player 1's strategy "Cooperate" is strictly dominated by "Defect". A rational player would never play a strictly dominated strategy.

Here is the formal definition.

Definition: Strictly Dominated Strategy
A strategy $s_i\in S_i$ is strictly dominated by another strategy $s_i^{\prime }\in S_i$ if for every possible combination of the other players' strategies $s_{-i}\in S_{-i}$, the payoff from playing $s_i^{\prime }$ is strictly greater than the payoff from playing $s_i$.
$u_i(s_i^{\prime },s_{-i})>u_i(s_i,s_{-i}),\forall s_{-i}\in S_{-i}$
Note that a pure strategy can also be dominated by a mixed strategy.

3. Iterated Elimination of Strictly Dominated Strategies (IESDS)

The power of dominance comes from applying it iteratively. The logic rests on the assumption of common knowledge of rationality:

1. All players are rational (so they won't play a strictly dominated strategy).
2. All players know that all other players are rational (so they know others won't play their dominated strategies).
3. All players know that all players know... and so on.

This allows us to perform Iterated Elimination of Strictly Dominated Strategies (IESDS):

1. Identify and remove all strictly dominated strategies for all players from the game.
2. In the new, smaller game, some strategies that were not dominated before might become dominated now.
3. Repeat this process—identifying and removing newly dominated strategies—until no more strategies can be eliminated.

The strategies that remain are the prediction of the game's outcome.

The following video provides an excellent walkthrough of this process.

A crucial connection exists between these two concepts: a strategy is strictly dominated if and only if it is never a best response. That is, for a strictly dominated strategy, there is no belief you could hold about your opponents' play that would make it the optimal choice. The proof for this theorem is a classic result in game theory, and it formally cements the intuition that dominated strategies are ones you should never play.

4. Practice with IESDS

Now it's your turn to apply the IESDS process. Consider the following game matrix.

Let's focus on Problem 1. Apply the IESDS algorithm to the game shown. For each step, identify which strategy is strictly dominated and by what.

Conclusion

In this lesson, we have developed our first set of tools for analyzing and solving games. By moving from simply calculating payoffs to comparing them, we can make concrete predictions about player behavior.

Key Takeaways:

• A best response is a strategy that yields the highest possible payoff, given what the other players are doing.
• A strategy is strictly dominated if there is another available strategy that always yields a strictly higher payoff, no matter what the opponents do. Rational players never play such strategies.
• Iterated Elimination of Strictly Dominated Strategies (IESDS) is a process that leverages common knowledge of rationality to simplify or solve a game by removing dominated strategies in rounds. For strict dominance, the order of removal does not matter.

Preview of the next lesson:
IESDS is a powerful tool, but in many games, no strategies are strictly dominated, or the process stops before reaching a unique outcome. We need a more general solution concept. In the next lesson, we will introduce Nash Equilibrium, a state where every player's strategy is a best response to the strategies of all other players. This concept is the cornerstone of modern game theory.