1 of 32

Dominated Strategies and IEDS

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

2 of 32

Outline�

Review
Dominated strategies
Iterated elimination of strictly dominated strategies (IEDS)

3 of 32

Review�

A set of players (at least two players)
For each player i, a set of strategies S_i
The payoffs received by each player for the combinations of the strategies

{Player 1, Player 2, ... Player n}
S₁, S₂, ..., S_n
u_i(s₁, s₂, ...s_n), for all s₁∈S₁, s₂∈S₂, ... s_n∈S_n

DEFINITION: A strategic static game consists of

The timing of the game:

Each player i chooses his/her strategy s_i without knowledge of others’ choices
Then each player i receives his/her payoff u_i(s₁, s₂, ..., s_n)
The game ends

4 of 32

Prisoners’ Dilemma: Normal-form representation�

Set of players: {Prisoner 1, Prisoner 2}
Sets of strategies: S₁= S₂= {NC, C}
Payoff functions: u₁(NC, NC)=-1, u₁(NC, C)=-9, u₁(C, NC)=0, u₁(C, C)=-6,� u₂(NC, NC)=-1, u₂(NC, C)=0, u₂(C, NC)=-9, u₂(C, C)=-6

-1 , -1	-9 , 0
0 , -9	-6 , -6

Prisoner 1

Prisoner 2

Players

Strategies

Payoffs

5 of 32

Solving Prisoners’ Dilemma�

Dominated strategy:

There exists another strategy which always does better regardless of other players’ choices
Not confess (NC) is always dominated by confess (C) disregarding what the other player chooses

-1 , -1	-9 , 0
0 , -9	-6 , -6

Prisoner 1

Prisoner 2

6 of 32

Strictly dominated strategy�

DEFINITION: Strictly dominated strategy

In the normal-form game {S₁, S₂,..., S_n, u₁, u₂,..., u_n}, let s_i', s_i" ∈ S_i be feasible strategies for player i
Strategy s_i“ strictly dominates strategy s_i' if u_i(s₁,s₂,...,s_i-₁,s_i',s_i+₁,...,s_n) < u_i(s₁,s₂,...,s_i-₁,s_i",s_i+₁,...,s_n) for all s₁∈ S₁, s₂∈ S₂, ..., s_i-₁∈S_i-₁, s_i+₁∈ S_i+₁, ..., s_n∈ S_n

We say that s_i' is strictly dominated strategy

s_i" is strictly better than s_i'

regardless of other players’ choices

7 of 32

Weakly dominated strategy�

DEFINITION: Weakly dominated strategy

In the normal-form game {S₁, S₂,..., S_n, u₁, u₂,..., u_n}, let s_i', s_i" ∈ S_i be feasible strategies for player i
Strategy s_i“ weakly dominates strategy s_i' if u_i(s₁,s₂,...,s_i-₁,s_i',s_i+₁,...,s_n) ≤ u_i(s₁,s₂,...,s_i-₁,s_i",s_i+₁,...,s_n) for all s₁∈ S₁, s₂∈ S₂, ..., s_i-₁∈S_i-₁, s_i+₁∈ S_i+₁, ..., s_n∈ S_n

We say that s_i' is weakly dominated strategy

s_i" is at least as good as s_i'

regardless of other players’ choices

8 of 32

Example 1�

Is there a strictly dominated strategy for player 2?

Strategy L is better than R if player 1 selects U
Strategy R is better than L if player 1 selects D
L and R are not dominated strategies for player 2

Is there a strictly dominated strategy for player 1?

Strategy D is strictly dominated by U
D should never be played by a rational player 1

		Player 2
		L	R
Player 1	U	2, 3	5, 0
Player 1	D	1, 0	4, 3

9 of 32

Example 2: Matching Pennies�

Any dominated strategy for player 1?

Any dominated strategy for player 2?

		Player 2
		H	T
Player 1	H	1, -1	-1, 1
Player 1	T	-1, 1	1, -1

10 of 32

Iterated elimination of strictly dominated strategies�

A rational player never chooses a strictly dominated strategy (but may choose a weakly dominated strategy)

Hence, any strictly dominated strategy can be eliminated

We can use a concept of strictly dominated strategies to solve different games:

If a strategy is strictly dominated, eliminate it
The size and complexity of the game is reduced
Then eliminate any strictly dominated strategies from the reduced game
Continue doing so successively

11 of 32

Example 3�

Any strictly dominated strategies for player 1?

Any strictly dominated strategies for player 2?

When every player has a dominant strategy, the game has a strictly dominant strategy solution

		Player 2
		L	R
Player 1	U	8, 4	5, 3
Player 1	D	7, 0	3, -1

12 of 32

Example 4�

Any strictly dominated strategy for player 1?

D is strictly dominated by M

Any strictly dominated strategy for player 2?

		Player 2
		L	R
Player 1	U	1, 1	0,-1
	M	0, 2	1, 0
	D	-1,-1	0, 0

13 of 32

Example 4:�Iterated elimination of strictly dominated strategies (IEDS)

Analyzing player 1’s strategies:

D is a strictly dominated strategy
Player 1 should never play D
That is, we should eliminate D from player 1’s strategy set

		Player 2
		L	R
Player 1	U	1, 1	0,-1
	M	0, 2	1, 0
	D	-1,-1	0, 0

14 of 32

Example 4:�Iterated elimination of strictly dominated strategies (IEDS)

Analyzing player 2’s strategies:

After eliminating player 1’s strictly dominated strategy, the payoff matrix becomes smaller
Knowing that player 1 will never play his strictly dominated strategy, R becomes player 2’s strictly dominated strategy
Therefore, eliminate R

		Player 2
		L	R
Player 1	U	1, 1	0,-1
	M	0, 2	1, 0

15 of 32

Example 4: �Iterated elimination of strictly dominated strategies (IEDS)

Analyzing player 1’s strategies:

Knowing that player 2 will never play R, M becomes a strictly dominated strategy for player 1
Eliminate M

		Player 2
		L
Player 1	U	1, 1
	M	0, 2

16 of 32

Example 4:�Iterated elimination of strictly dominated strategies (IEDS)

To recap:

The eliminating process is called iterated elimination of dominated strategy (IEDS)
The strategy choice (U, L) is said to be an equilibrium reached by IEDS

		Player 2
		L	R
Player 1	U	1, 1	0,-1
	M	0, 2	1, 0
	D	-1,-1	0, 0

17 of 32

Experiment #1: Guessing game�

Decisions:

Each person is asked to choose a number between (and including) 0 and 100 simultaneously. Communication is not allowed in this game

Earnings:

The person whose number is closest to, but not exceeding, 2/3 of the average (called the target number) earns $10, while the rest of the class earns $0

18 of 32

Guessing game�

Guessing game = “Beauty contest” game

Beauty contest: a newspaper contest in which people guess what faces others will guess are most beautiful

Keynes (General Theory of Employment, Interest, and Money, 1936, p. 156):

“It is not a case of choosing those which, to the best of one’s judgment, are really the prettiest, nor even those which average opinion genuinely thinks the prettiest. We have reached the third degree, where we devote our intelligences to anticipating what average opinion expects the average opinion to be. And there are some, I believe, who practice the fourth, fifth, and higher degrees.”

19 of 32

Guessing game�

The guessing game can be used to distinguish whether people “practice the 4^th, 5^th, and higher degrees” of reasoning as Keynes wondered

Level 0: bid = 50; target = 50 * 2/3 = 33
Level 1: bid = 33; target = 33 * 2/3 = 22
Level 2: bid = 22; target = 22 * 2/3 = 15
Level 3: bid = 15; target = 15 * 2/3 = 10
Level 4: …
In game theory, players do not stop this iterated reasoning until they reach a point from which they do not want to deviate
(Nash) equilibrium = 0; target = 0 * 2/3 = 0

Guessing game provides a rough measure of the number of steps of strategic thinking that people do

20 of 32

Guessing game: IEDS equilibrium�

Choosing any number above 66 is a dominated strategy

Because the highest possible target number is 100 * 2/3 = 66, you can always do better by choosing a number lower than 66

Choosing any number between 44 and 66 is a dominated strategy

Because the highest possible target number is 66 * 2/3 = 44

Deleting dominated strategies iteratively leads you to 0 (Nash equilibrium)

21 of 32

Experiment #1: Guessing game�Results (CWRU 2021)

Level 0

Level 1

Level 2

Level 3

Nash

22 of 32

Experiment #1: Guessing game �Results (Selten and Nagel 1998)

23 of 32

Experiment #1: Guessing game�Results (Camerer 2003)

24 of 32

Case vs Caltech�

25 of 32

What can we conclude?�

The game-theoretic equilibrium of 0 is a poor prediction of individual choices

Behavioral game theory uses a concept of level-k reasoning as a better predictor
Level-k is used to explain different behaviors, including over-bidding in auctions and stock market bubbles

Typical distribution of levels in experiments:

Level 0: about 10%
Level 1: about 40%
Level 2: about 30%
Level 3: about 10%
Other: about 10%

26 of 32

Limited iterated reasoning�

Princess Bride – Battle of Wits

http://www.youtube.com/watch?v=U_eZmEiyTo0

27 of 32

Pros and Cons of IEDS�

The advantage of IEDS (iterated elimination of dominated strategy) is that:

It is based on the appealing idea that rational players do not play dominated strategies

The disadvantages of IEDS is that:

(1) Rationality: it assumes that all players are completely rational and it is common knowledge
(2) Existence: not all games are dominance solvable

28 of 32

Pros and Cons of IEDS: Rationality�

What’s the IEDS outcome?

The outcome of the IEDS is (M, C) with payoffs (3, 6)

Player 2 can guarantee a payoff of 5 by playing L, while by using IEDS, player 2 runs the risk of getting 0 should player 1 not be as rational as he thinks she is

		Player 2
		L	C	R
Player 1	U	4, 5	1, 6	5, 4
	M	3, 5	3, 6	5, 4
	D	2, 5	2, 0	7,-1

29 of 32

Pros and Cons of IEDS: Existence�

What’s the IEDS outcome?

Delete player 1’s D and player 2’s R
No further dominated strategies can be eliminated
Matching pennies game

Some games are not dominance solvable

		Player 2
		L	C	R
Player 1	U	1, -1	-1, 1	0, -2
	M	-1, 1	1, -1	0, -2
	D	-2, 0	-2, 0	-2, -2

30 of 32

We need an alternative solution�

Next Time!

31 of 32

Thank you!

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

32 of 32

References�

Watson, J. (2013). Strategy: An Introduction to Game Theory (3rd Edition). Publisher: W. W. Norton & Company. (Chapters 6 & 7)
Selten, R., & Nagel, R. (1998). Das Zahlenwahlspiel-Hintergründe und Ergebnisse. Spektrum der Wissenschaft, February, 16-22.
Camerer, C.F. (2003). Behavioural studies of strategic thinking in games. Trends in Cognitive Sciences, 7(5), 225-231.