Game Theory (Part 4)

Last time we talked about Nash equilibria for a 2-player normal form game. We saw that sometimes a Nash equilibrium doesn’t exist! Sometimes there’s more than one! But suppose there is at least one Nash equilibrium. How do we find one? Sometimes it’s hard.

Strict domination

But there’s a simple trick to rule out some possibilities. Sometimes player A will have a choice that gives them a bigger payoff than some choice no matter what choice player B makes. In this case we say choice strictly dominates choice And in this case, there’s no way that could be A’s choice in a Nash equilibrium, because player A can always improve their payoff by switching to choice

For example, look at this game:

	1	2
1	(0,0)	(-1,1)
2	(2,-1)	(0,0)
3	(-2,1)	(1,-1)
4	(0,1)	(2,0)

For player A, choice 4 strictly dominates choice 3. No matter what player B does, player A gets a bigger payoff if they make choice 4 than if they make choice 3. Stare at the black numbers in the table in rows 3 and 4 until you see this.

You can also see it using the payoff matrix for player A:

Each number in row 4 here is bigger than the number directly above it in row 3. In other words:

and

Puzzle. Are there any other examples of a choice for player A that strictly dominates another choice?

And of course the same sort of thing works for player B. If player B has a choice that gives them a better payoff than some choice no matter what player A does, then can’t show up as B’s choice in a Nash equilibrium.

We can make our remarks more precise:

Definition. A choice for player A strictly dominates a choice if

for all Similarly, a choice for player B strictly dominates a choice if

for all

Theorem 1. If a choice for player A strictly dominates a choice then no choice for player B gives a Nash equilibrium Similarly, if a choice for player B strictly dominates a choice then no choice for player A gives a Nash equilibrium

Proof. We’ll only prove the first statement since the second one works the exact same way. Suppose strictly dominates This means that

for all In this case, there is no way that the choice can be part of a Nash equilibrium. After all, if is a Nash equilibrium we have

for all . But this contradicts the previous inequality—just take █

Strict dominance

Definition. We say a choice is strictly dominant if it strictly dominates all other choices for that player.

Let me remind you again that a pure strategy is a way for one player to play a game where they always make the same choice. So, there is one pure strategy for each choice, and one choice for each pure strategy. This means we can be a bit relaxed about the difference between these words. So, what we’re calling strictly dominant choices, most people call strictly dominant pure strategies. You can read more about these ideas here:

• Strategic dominance, Wikipedia.

We’ve seen that if one choice strictly dominates another, that other choice can’t be part of a Nash equilibrium. So if one choices strictly dominates all others, that choice is the only one that can be part of a Nash equilibrium! In other words:

Theorem 2. If a choice for player A is strictly dominant, then any Nash equilibrium must have . Similarly, if a choice for player B is strictly dominant, then any Nash equilibrium must have .

Proof. We’ll only prove the first statement since the second one works the exact same way. Theorem 1 says that if a choice for player A strictly dominates a choice then no choice for player B gives a Nash equilibrium So, if strictly dominates all other choices for player A, it is impossible to have a Nash equilibrium unless █

We can go even further:

Theorem 3. If choice for player A is strictly dominant and choice for player B is strictly dominant, then is a Nash equilibrium, and there is no other Nash equilibrium.

Proof. Suppose choice for player A is strictly dominant and choice for player B is strictly dominant. Then by Theorem 2 any Nash equilibrium must have and . So, there is certainly no Nash equilibrium other than

But we still need to check that is a Nash equilibrium! This means we need to check that:

1) For all

2) For all

Part 1) is true because choice is strictly dominant. Part 2) is true because choice is strictly dominant. █

We can restate Theorem 3 is a less precise but rather pretty way:

Corollary. If both players have a strictly dominant pure strategy, there exists a unique Nash equilibrium.

Here I’m saying ‘pure strategy’ instead of ‘choice’ just to prepare you for people who talk that way!

Domination

I realize that the terminology here has a kind of S&M flavor to it, with all this talk of ‘strict domination’ and the like. But there’s nothing I can do about that—it’s standard!

Anyway, there’s also a less strict kind of dominance:

Definition. A choice for player A dominates a choice if

for all Similarly, a choice for player B dominates a choice if

for all

But there is less we can do with this definition. Why? Here’s why:

Puzzle. Find a normal-form two player game with 2 choices for each player, where is a Nash equilibrium even though is dominated by the other choice for player A and is dominated by the other choice for player B.