Root Dominance - Job Market Paper
Abstract
Root dominance is an intermediate dominance relation between weak and
strict dominances. In addition to weak dominance, root dominance requires
strict dominance on all profiles where an opponent plays a best response to the
dominating strategy. The iterated elimination of root dominated strategies
(IERDS) outcome refines the iterated elimination of strictly dominated
strategies (IESDS) outcome, and IERDS is an order independent procedure in
finite games, contrary to the iterated elimination of weakly dominated strategies
(IEWDS). In addition, IERDS does not face the inconsistency that we call
mutability. That is, IERDS does not alter the dominance relation between two
strategies like IEWDS does. Finally, we introduce a rationality concept which
corresponds to root undominated strategies. This rationality concept is induced
by perturbations of the game such that a player believes the strategies he is
considering might be observable by his opponent. We discuss the links between
our concept and other concepts established in various literatures such as the
conjectural variations theory.
Keywords: Dominance relations; Iterated elimination procedures; Rationality
1 Introduction
1.1 Motivating example
Assume two agents who have coordination incentives but also have strong egocentric
biases. That is, each agent is indifferent between, on the one hand, coordinating on
his least preferred action with the other agent and, on the other hand,
miscoordinating but choosing his preferred action. This situation can be represented
in the following game which can be seen as a modified version of the battle of the
sexes (BoS) where best responses payoffs are underlined 12:
j’s Strategy
1 Remark that utility functions can be denoted: Ui(Ai) = 2 + 1Aj −1Oj, Ui(Bi) = 1 + 1Bj −1Oj, Ui(Oi) = 0+1Oj;
and in a symmetric way for player j: Uj(Bj) = 2+1Bi −1Oi, Uj(Aj) =
2 + 1Ai −1Oi, Uj(Oj) = 0 + 1Oi.
1
, i’s
Strategy Aj Bj Oj
Ai (3,2) (2,2) (1,0)
Bi (1,1) (2,3) (0,0)
Oi (0,0) (0,1) (1,1)
Figure 1: Modified Version of the Battle of the Sexes
Remark first that no strategy is strictly dominated. Thus, the iterated elimination
of strictly dominated strategies (IESDS) does not eliminate any strategy. In contrast,
both outside options Oi and Oj are weakly dominated (respectively by Ai and Bj).
As well, Bi and Aj are weakly dominated3. However, as noted by Samuelson (1992):
It is well known that the order in which dominated strategies are
eliminated can affect the outcome of the [iterated elimination of weakly
dominated strategies (IEWDS)].
In other words, IEWDS is order dependent (see also Marx and Swinkels (1997);
Hillas and Samet (2020)). Here, it is the case since IEWDS always eliminates outside
options Oi and Oj but only sometimes Aj and/or Bi. It is striking that no iterated
elimination procedure based on a dominance relation 3 can both provide a unique
outcome when applied to this game and still eliminate some strategies. Particularly, it
is remarkable that even the Nash equilibrium (Oi,Oj) cannot be ruled out while we
could intuitively think that players “should” try to coordinate on better outcomes. In
this paper, we introduce a new dominance relation named root dominance and an
associated order independent iterated elimination procedure the iterated elimination
of root dominated strategies (IERDS) such that IERDS eliminates both Oi and Oj and
stops there. Root dominance requires weak dominance and strict dominance on all
the profiles where the opponent best responds to the dominating strategy. In our
version of the Battle of the Sexes, j best responds to Ai by playing Aj or Bj. At these two
profiles, Ai strictly payoff dominates Oi. Therefore, Ai root dominates Oi. On the
contrary, playing Ai does not yield a strictly higher payoff than playing Bi when j plays
Bj. Thus, Ai does not root dominate Bi and Bi is never eliminated by IERDS.
3 In addition to the ouside options, this is the main difference with the standard BoS. 3See
Definition 1 for the precise definition.
2
,1.2 Elimination procedures based on dominance relations
Iterated elimination of strictly dominated strategies (IESDS) is one of the most basic
tools of game theory. It is among the least vulnerable solution concepts when
analysts eliminate strategies to predict the outcome of a situation. Notably, it is
equivalent to the concept of rationalizability in two-player games (see Bernheim
(1984); Pearce (1984)) and when a game is dominance solvable 4, it reinforces the use
of the Nash equilibrium as a solution concept, like in the Cournot duopoly.
Remarkably, for instance, IESDS is essential to understand why there is a unique
equilibrium in global games (see Carlsson and van Damme (1993)). However, the
conceptual robustness of IESDS necessarily reduces its use when precise predictions
are required. Instead, iterated elimination of weakly dominated strategies (IEWDS)
outcome is a refinement of IESDS outcome. IEWDS has been largely applied in
different strands of the economic literature such that the voting literature (see
Moulin (1979)). Additionally, a certain order of IEWDS is equivalent to the backward
induction solution5 (see Moulin (1986, p.84)). Though, IEWDS may go sometimes “too
far” in the selection. As an example, it may eliminate the only Nash equilibrium in
certain games such that the Bertrand duopoly. Furthermore, inconsistencies of
IEWDS refrain its use as a solution concept. In particular, order dependence 6 of
IEWDS (and therefore the multiplicity of final outcomes) prevents firm forecasts.
However, attempts to justify the use of IEWDS have been made. Among this
literature, Marx and Swinkels (1997) shows that IEWDS is payoffs order independent
in games with transference of decisionmaker indifference (TDI) 7, and define in
association, the nice weak domination8. Nevertheless, the order independence result
is limited to payoffs (and does not apply to strategies) 9, while in the context of
decision theory, Kahneman and Tversky (1979) show that payoffs may not determine
4 Dominance solvability means that IESDS outcome is a unique profile.
5 It is true in games where, if a player is indifferent between two terminal nodes, it implies that all
players are indifferent at these same terminal nodes. Moulin (1986)) calls this assumption the one-to-
one assumption.
6 It means that different applications of the procedure may lead to different final outcomes. See
Section 2 for definitions. The problem of order independence of procedures has given a rich literature
(see for instance Gilboa et al. (1990); Apt (2005, 2011); Luo et al. (2020); Hillas and Samet (2020)).
7 A game exhibits TDI when, if one agent is indifferent between two strategies at a given
opponents’ profile, every player is indifferent between the two profiles formed by either one or the
other strategy of the first player, and the given opponents’ profile.
8 A strategy si′ of player i is said nicely weakly dominated by strategy si′′ if, in addition to weak
dominance, everywhere where i is indifferent between si′ and si′′, i’s opponents are also indifferent
between i playing si′ and si′′.
9 See Appendix D to distinguish our notion of order independence and the Marx and Swinkels
(1997)’s one.
3
, entirely the preferences. Then, from both theoretical and practical points of view,
payoffs independence might not be considered as strong a result as strategies order
independence. Alternatively, we propose in this paper a dominance relation and an
associated procedure whose outcome refines the IESDS outcome and is (payoff and
strategies) order independent in every finite game.
1.3 Outline
We introduce in this paper a new kind of iterated elimination procedure based on a
new dominance relation called root dominance. Root dominance is a stronger relation
than weak dominance and weaker than strict dominance. That is, root dominance
requires weak dominance and the strict payoff dominance on a specific profile set:
the best reply set to the dominating strategy. Note that this last property depends
essentially on the dominating strategy, which is, to the best of our knowledge, a
novelty. We introduce also a new iterated elimination procedure, whose order
independence property is not limited to payoffs, but concerns strategies as well.
In the next section, we establish a simplified framework with only pure strategies.
In Section 3, we define the notion of root dominance and our iterated elimination
procedure IERDS. Additionally, we illustrate them with some examples. In Section 4,
we show the technical lemmas and the order independence result. We make a
succinct literature review about iterated elimination procedures in Section 5. Then, in
Section 6, we present the mutability issue, notably faced by IEWDS, and show that
IERDS is immutable. In Section 7, we extend our concepts to a framework with mixed
strategies and show that our results hold true. We introduce our rationality concepts
in Section 8 and we compare them specifically to the concepts in conjectural variation
theory concepts. Finally, we conclude in Section 9.
2 Framework with pure strategies
We denote Γ = {I,S,U} a finite game with I the set of players, S = ΠSi, Si being the
i∈I
finite strategy set of player i ∈ I (we consider only pure strategies), and U the vector
of utility functions of each player i where Ui : S → R. We denote S−i = Π Sj the
j∈I\{i}
strategy profiles set of i’s opponents. Finally, we denote s ∈ S a strategy profile, and
s−i ∈ S−i the strategy profile of the opponents of i ∈ I such that when i plays si, s =
(si,s−i).
Here, we define the main notion that motivates this paper, namely order
independence. Before, we define a process associated with any dominance relation: A
4
Abstract
Root dominance is an intermediate dominance relation between weak and
strict dominances. In addition to weak dominance, root dominance requires
strict dominance on all profiles where an opponent plays a best response to the
dominating strategy. The iterated elimination of root dominated strategies
(IERDS) outcome refines the iterated elimination of strictly dominated
strategies (IESDS) outcome, and IERDS is an order independent procedure in
finite games, contrary to the iterated elimination of weakly dominated strategies
(IEWDS). In addition, IERDS does not face the inconsistency that we call
mutability. That is, IERDS does not alter the dominance relation between two
strategies like IEWDS does. Finally, we introduce a rationality concept which
corresponds to root undominated strategies. This rationality concept is induced
by perturbations of the game such that a player believes the strategies he is
considering might be observable by his opponent. We discuss the links between
our concept and other concepts established in various literatures such as the
conjectural variations theory.
Keywords: Dominance relations; Iterated elimination procedures; Rationality
1 Introduction
1.1 Motivating example
Assume two agents who have coordination incentives but also have strong egocentric
biases. That is, each agent is indifferent between, on the one hand, coordinating on
his least preferred action with the other agent and, on the other hand,
miscoordinating but choosing his preferred action. This situation can be represented
in the following game which can be seen as a modified version of the battle of the
sexes (BoS) where best responses payoffs are underlined 12:
j’s Strategy
1 Remark that utility functions can be denoted: Ui(Ai) = 2 + 1Aj −1Oj, Ui(Bi) = 1 + 1Bj −1Oj, Ui(Oi) = 0+1Oj;
and in a symmetric way for player j: Uj(Bj) = 2+1Bi −1Oi, Uj(Aj) =
2 + 1Ai −1Oi, Uj(Oj) = 0 + 1Oi.
1
, i’s
Strategy Aj Bj Oj
Ai (3,2) (2,2) (1,0)
Bi (1,1) (2,3) (0,0)
Oi (0,0) (0,1) (1,1)
Figure 1: Modified Version of the Battle of the Sexes
Remark first that no strategy is strictly dominated. Thus, the iterated elimination
of strictly dominated strategies (IESDS) does not eliminate any strategy. In contrast,
both outside options Oi and Oj are weakly dominated (respectively by Ai and Bj).
As well, Bi and Aj are weakly dominated3. However, as noted by Samuelson (1992):
It is well known that the order in which dominated strategies are
eliminated can affect the outcome of the [iterated elimination of weakly
dominated strategies (IEWDS)].
In other words, IEWDS is order dependent (see also Marx and Swinkels (1997);
Hillas and Samet (2020)). Here, it is the case since IEWDS always eliminates outside
options Oi and Oj but only sometimes Aj and/or Bi. It is striking that no iterated
elimination procedure based on a dominance relation 3 can both provide a unique
outcome when applied to this game and still eliminate some strategies. Particularly, it
is remarkable that even the Nash equilibrium (Oi,Oj) cannot be ruled out while we
could intuitively think that players “should” try to coordinate on better outcomes. In
this paper, we introduce a new dominance relation named root dominance and an
associated order independent iterated elimination procedure the iterated elimination
of root dominated strategies (IERDS) such that IERDS eliminates both Oi and Oj and
stops there. Root dominance requires weak dominance and strict dominance on all
the profiles where the opponent best responds to the dominating strategy. In our
version of the Battle of the Sexes, j best responds to Ai by playing Aj or Bj. At these two
profiles, Ai strictly payoff dominates Oi. Therefore, Ai root dominates Oi. On the
contrary, playing Ai does not yield a strictly higher payoff than playing Bi when j plays
Bj. Thus, Ai does not root dominate Bi and Bi is never eliminated by IERDS.
3 In addition to the ouside options, this is the main difference with the standard BoS. 3See
Definition 1 for the precise definition.
2
,1.2 Elimination procedures based on dominance relations
Iterated elimination of strictly dominated strategies (IESDS) is one of the most basic
tools of game theory. It is among the least vulnerable solution concepts when
analysts eliminate strategies to predict the outcome of a situation. Notably, it is
equivalent to the concept of rationalizability in two-player games (see Bernheim
(1984); Pearce (1984)) and when a game is dominance solvable 4, it reinforces the use
of the Nash equilibrium as a solution concept, like in the Cournot duopoly.
Remarkably, for instance, IESDS is essential to understand why there is a unique
equilibrium in global games (see Carlsson and van Damme (1993)). However, the
conceptual robustness of IESDS necessarily reduces its use when precise predictions
are required. Instead, iterated elimination of weakly dominated strategies (IEWDS)
outcome is a refinement of IESDS outcome. IEWDS has been largely applied in
different strands of the economic literature such that the voting literature (see
Moulin (1979)). Additionally, a certain order of IEWDS is equivalent to the backward
induction solution5 (see Moulin (1986, p.84)). Though, IEWDS may go sometimes “too
far” in the selection. As an example, it may eliminate the only Nash equilibrium in
certain games such that the Bertrand duopoly. Furthermore, inconsistencies of
IEWDS refrain its use as a solution concept. In particular, order dependence 6 of
IEWDS (and therefore the multiplicity of final outcomes) prevents firm forecasts.
However, attempts to justify the use of IEWDS have been made. Among this
literature, Marx and Swinkels (1997) shows that IEWDS is payoffs order independent
in games with transference of decisionmaker indifference (TDI) 7, and define in
association, the nice weak domination8. Nevertheless, the order independence result
is limited to payoffs (and does not apply to strategies) 9, while in the context of
decision theory, Kahneman and Tversky (1979) show that payoffs may not determine
4 Dominance solvability means that IESDS outcome is a unique profile.
5 It is true in games where, if a player is indifferent between two terminal nodes, it implies that all
players are indifferent at these same terminal nodes. Moulin (1986)) calls this assumption the one-to-
one assumption.
6 It means that different applications of the procedure may lead to different final outcomes. See
Section 2 for definitions. The problem of order independence of procedures has given a rich literature
(see for instance Gilboa et al. (1990); Apt (2005, 2011); Luo et al. (2020); Hillas and Samet (2020)).
7 A game exhibits TDI when, if one agent is indifferent between two strategies at a given
opponents’ profile, every player is indifferent between the two profiles formed by either one or the
other strategy of the first player, and the given opponents’ profile.
8 A strategy si′ of player i is said nicely weakly dominated by strategy si′′ if, in addition to weak
dominance, everywhere where i is indifferent between si′ and si′′, i’s opponents are also indifferent
between i playing si′ and si′′.
9 See Appendix D to distinguish our notion of order independence and the Marx and Swinkels
(1997)’s one.
3
, entirely the preferences. Then, from both theoretical and practical points of view,
payoffs independence might not be considered as strong a result as strategies order
independence. Alternatively, we propose in this paper a dominance relation and an
associated procedure whose outcome refines the IESDS outcome and is (payoff and
strategies) order independent in every finite game.
1.3 Outline
We introduce in this paper a new kind of iterated elimination procedure based on a
new dominance relation called root dominance. Root dominance is a stronger relation
than weak dominance and weaker than strict dominance. That is, root dominance
requires weak dominance and the strict payoff dominance on a specific profile set:
the best reply set to the dominating strategy. Note that this last property depends
essentially on the dominating strategy, which is, to the best of our knowledge, a
novelty. We introduce also a new iterated elimination procedure, whose order
independence property is not limited to payoffs, but concerns strategies as well.
In the next section, we establish a simplified framework with only pure strategies.
In Section 3, we define the notion of root dominance and our iterated elimination
procedure IERDS. Additionally, we illustrate them with some examples. In Section 4,
we show the technical lemmas and the order independence result. We make a
succinct literature review about iterated elimination procedures in Section 5. Then, in
Section 6, we present the mutability issue, notably faced by IEWDS, and show that
IERDS is immutable. In Section 7, we extend our concepts to a framework with mixed
strategies and show that our results hold true. We introduce our rationality concepts
in Section 8 and we compare them specifically to the concepts in conjectural variation
theory concepts. Finally, we conclude in Section 9.
2 Framework with pure strategies
We denote Γ = {I,S,U} a finite game with I the set of players, S = ΠSi, Si being the
i∈I
finite strategy set of player i ∈ I (we consider only pure strategies), and U the vector
of utility functions of each player i where Ui : S → R. We denote S−i = Π Sj the
j∈I\{i}
strategy profiles set of i’s opponents. Finally, we denote s ∈ S a strategy profile, and
s−i ∈ S−i the strategy profile of the opponents of i ∈ I such that when i plays si, s =
(si,s−i).
Here, we define the main notion that motivates this paper, namely order
independence. Before, we define a process associated with any dominance relation: A
4
