# Iterated Elimination of Weakly Dominated Strategies in Well-Founded Games

Krzysztof R. Apt Centrum Wiskunde & Informatica
Amsterdam, The NetherlandsUniversity of Warsaw
Warsaw, Poland<EMAIL_ADDRESS>Department of CSE,
IIT Kanpur, Kanpur, India Sunil Simon Department of CSE,
IIT Kanpur, Kanpur, India<EMAIL_ADDRESS>
###### Abstract

Recently, in [4], we studied well-founded games, a natural extension of finite
extensive games with perfect information in which all plays are finite. We
extend here, to this class of games, two results concerned with iterated
elimination of weakly dominated strategies, originally established for finite
extensive games.

The first one states that every finite extensive game with perfect information
and injective payoff functions can be reduced by a specific iterated
elimination of weakly dominated strategies to a trivial game containing the
unique subgame perfect equilibrium. Our extension of this result to well-
founded games admits transfinite iterated elimination of strategies. It
applies to an infinite version of the centipede game. It also generalizes the
original result to a class of finite games that may have several subgame
perfect equilibria.

The second one states that finite zero-sum games with $n$ outcomes can be
solved by the maximal iterated elimination of weakly dominated strategies in
$n-1$ steps. We generalize this result to a natural class of well-founded
strictly competitive games.

##  1 Introduction

This paper is concerned with the iterated elimination of weakly dominated
strategies (IEWDS) in the context of natural class of infinite extensive games
with perfect information. While simple examples show that the deletion of
weakly dominated strategies may result in removal of a unique Nash
equilibrium, IEWDS has some merit if it results in solving a game. It is for
instance used to show that the so-called “beauty contest” game has exactly one
Nash equilibrium (see, e.g., [8, Chapter 5]). Other games can be solved this
way, see, e.g., [12, pages 63, 110-114].

This procedure was also studied in the realm of finite extensive games with
perfect information. In [9] the correspondence between the outcomes given by
the iterated elimination of weakly dominated strategies and backward induction
was investigated in the context of binary voting agendas with sequential
voting. More recently, this procedure was studied in [17] in the context of
supermodular games.

For arbitrary games two important results were established. The first one
states, see [12], that in such games with injective payoff functions (such
games are sometimes called _generic_) a specific iterated elimination of
weakly dominated strategies (that mimics the backward induction) yields a
trivial game which contains the unique subgame perfect equilibrium. It was
noticed in [5] that this result holds for a slightly more general class of
games _without relevant ties_.111All mentioned concepts are explained in
Sections 2, 4, and 5. We did not find any precise proofs in the literature.
The proof is briefly sketched in [12, pages 108-109] and summarized in [5,
pages 48-49] as follows: “if backward induction deletes action $a$ at node
$x$, delete all the strategies reaching $x$ and choosing $a$”. We provided in
[3] a detailed proof of the stronger result of [5] in which we clarified how
the backward induction algorithm needs to be modified to achieve the desired
outcome.

The second result, due to [7], is concerned with finite extensive zero-sum
games. It states that such games can be reduced to a trivial game by the
‘maximal’ iterated elimination of weakly dominated strategies in $n-1$ steps,
where $n$ is the number of outcomes.222An alternative proof given in [18]
shows that the result holds for the larger class of strictly competitive
games. In [3] we clarified that the original proof also holds for this class
of games.

In [4] we studied a natural extension of finite extensive games with perfect
information in which one assumes that all plays are finite. We called these
games well-founded games.333In the economic literature such games are
sometimes called ‘games with finite horizon’. The subject of this paper is to
extend the above two results to well-founded games. In both cases some non-
trivial difficulties arise.

12$(0,0)$$L$$(2,0)$$R$$A$1$(2,0)$$C$$(0,0)$$D$$B$

Figure 1: An extensive game $G$ and the corresponding strategic game
$\Gamma(G)$

| $L$ | $R$
---|---|---
AC | $(0,0)$ | $(2,0)$
AD | $(0,0)$ | $(2,0)$
BC | $(2,0)$ | $(2,0)$
BD | $(0,0)$ | $(0,0)$

######  Example 1.1.

Consider the extensive game $G$ and the corresponding strategic game
$\Gamma(G)$ given in Figures 1. $G$ has three subgame perfect equilibria which
are all payoff equivalent:
$\\{(\mathit{AC},R),(\mathit{BC},L),(\mathit{BC},R)\\}$. We can observe that
in $\Gamma(G)$ no sequence of iterated elimination of weakly dominated
strategies results in a trivial game that contains all the subgame perfect
equilibria in $G$. To see this, first note that the strategies $L$ and $R$ of
player 2 are never weakly dominated irrespective of the elimination done with
respect to the strategies of player 1. Also, note that the strategy
$\mathit{BD}$ of player 1 is strictly dominated by $\mathit{BC}$ in
$\Gamma(G)$. Thus the only possibility of reducing $\Gamma(G)$ to a trivial
game is to eliminate all strategies of player 1 except $\mathit{BC}$. But this
results in the elimination of $(\mathit{AC},R)$ which is a subgame perfect
equilibrium in $G$. $\Box$

This might suggest that one should limit oneself to extensive games with a
unique subgame perfect equilibrium. Unfortunately, this restriction does not
work either as shown in Example 1.2. Additional complication arises when the
game has no subgame perfect equilibrium as shown in 1.3.

1$(0,100)$$0$$(x,100-x)$$x$2$(100,0)$$L$$(0,0)$$R$$100$$\cdots$$\cdots$ Figure
2: A game $G$ with a unique SPE
1$(0,0)$$A$$(0,1)$$B$$2$$(0,0)$$(0,1)$$(0,2)$$\ldots$$\cdots$$C$ Figure 3: A
game $G$ with no SPE

######  Example 1.2.

Consider a ‘trimmed version’ of the ultimatum game from [4] given in Figure 2,
in which for each $x\in[0,100]$ the root has a direct descendant $x$. This
game has a unique subgame perfect equilibrium, namely $(100,L)$. Consider an
iterated elimination of weakly dominated strategies. For each strategy of
player 1 the strategies $L$ and $R$ of player 2 yield the same payoff. So
these two strategies are never eliminated. Further, strategy 100 of player 1
is never eliminated either, since for any strategy $x<100$ we have
$p_{\\_}1(x,L)=x<100=p_{\\_}1(100,L)$ and $p_{\\_}1(x,R)=x>0=p_{\\_}1(100,R)$.
So the joint strategies $(100,L)$ and $(100,R)$ are never eliminated and they
are not payoff equivalent. (In fact, each iterated elimination of weakly
dominated strategies yields the game with the sets of strategies $\\{100\\}$
and $\\{L,R\\}$.) $\Box$

######  Example 1.3.

Consider the well-founded game $G$ given in Figure 3. Clearly $G$ has no
subgame perfect equilibrium. Further, strategies $A$ and $B$ of player 1 yield
the same outcome for him, so cannot be eliminated by any iterated elimination
of weakly dominated strategies. Thus any result of such an elimination
contains at least two outcomes, $(0,0)$ and $(0,1)$. So $G$ cannot be reduced
to a trivial game. $\Box$

To address these issues, we introduce the concept of an _SPE-invariant_ well-
founded game. These are games in which subgame perfect equilibria exist and
moreover in each subgame such equilibria are payoff equivalent. Then we show
that the first result can be extended to such games. In view of the above
examples it looks like the strongest possible generalization of the original
result. In particular, it applies to an infinite version of the well-known
centipede game of [16].

This result calls for a careful extension of the iterated elimination of
weakly dominated strategies to infinite games: its stages have to be indexed
by ordinals and one has to take into account that the outcome can be the empty
game.

When limited to finite games, our theorem extends the original result. In
particular it applies to the class of extensive games that satisfy the
_transference of decisionmaker indifference (TDI)_ condition due to [11], a
class that includes strictly competitive games. We also show that the well-
founded games with finitely many outcomes that satisfy the TDI condition are
SPE-invariant. Also when extending the second result, about strictly
competitive games, to well-founded games one has to be careful. The original
proof crucially relies on the fact that finite extensive zero-sum games have a
value. Fortunately, as we showed in [4], well-founded games with finitely many
outcomes have a subgame perfect equilibrium, so a fortiori a Nash equilibrium,
which suffices to justify the relevant argument (Lemma 5.28 in Section 5).

By carefully checking of the crucial steps of the original proof we extend the
original result to a class of well-founded strictly competitive games that
includes _almost constant_ games, in which for all but finitely many leaves
the outcome is the same. It remains an open problem whether this result holds
for all strictly competitive games with finitely many outcomes.

IEWDS is one of the early approaches applied to analyze strategies and
extensive games. It does not take into account epistemic reasoning of players
in the presence of assumptions such as common knowledge of rationality. The
vast literature on this subject, starting with [6] and [13], led to
identification of several more informative ways of analyzing finite extensive
games with imperfect information. We just mention here two representative
references. In [5] Pearce’s notion of _extensive form rationalizability_ (EFR)
was studied and it was shown that for extensive games without relevant ties it
coincides with the IEWDS. A more general notion of common belief in future
rationality was studied in [14] that led to identification of a new iterative
elimination procedure called _backward dominance_.

In our paper IEWDS is defined as a transfinite elimination procedure. A number
of papers, starting with [10], analyzed when such a transfinite elimination of
strategies cannot be reduced to an iteration over $\omega$ steps. In our
framework it is a simple consequence of the fact that the ranks of the
admitted game trees can be arbitrary ordinals. In particular, an infinite
version of the centipede game considered in Example 4.18 requires more than
$\omega$ elimination rounds.

##  2 Preliminaries

###  2.1 Strategic games

A _strategic game_
$H=(H_{\\_}1,\mbox{$\ldots$},H_{\\_}n,p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$
consists of a set of players $\\{1,\mbox{$\ldots$},n\\}$, where $n\geq 1$, and
for each player $i$, a set $H_{\\_}i$ of _strategies_ along with a _payoff
function_ $p_{\\_}i:H_{\\_}1\times\cdots\times
H_{\\_}n\mbox{$\>\rightarrow\>$}\mathbb{R}$.

We call each element of $H_{\\_}1\times\cdots\times H_{\\_}n$ a _joint
strategy_ of players $1,\mbox{$\ldots$},n$, denote the $i$th element of $s\in
H_{\\_}1\times\cdots\times H_{\\_}n$ by $s_{\\_}i$, and abbreviate the
sequence $(s_{\\_}{j})_{\\_}{j\neq i}$ to $s_{\\_}{-i}$. We write
$(s^{\prime}_{\\_}i,s_{\\_}{-i})$ to denote the joint strategy in which
player’s $i$ strategy is $s^{\prime}_{\\_}i$ and each other player’s $j$
strategy is $s_{\\_}j$. Occasionally we write $(s_{\\_}i,s_{\\_}{-i})$ instead
of $s$. Finally, we abbreviate the Cartesian product $\times_{\\_}{j\neq
i}H_{\\_}j$ to $H_{\\_}{-i}$.

Given a joint strategy $s$, we denote the sequence
$(p_{\\_}1(s),\mbox{$\ldots$},p_{\\_}n(s))$ by $p(s)$ and call it an _outcome_
of the game. We say that $H$ _has $k$ outcomes_ if $|\\{p(s)\mid s\in
H_{\\_}1\times\cdots\times H_{\\_}n\\}|=k$ and call a game _trivial_ if it has
one outcome. If one of the sets $H_{\\_}i$ is empty, we call the game _empty_
and _non-empty_ otherwise. Unless explicitly stated, all used strategic games
are assumed to be non-empty. We say that two joint strategies $s$ and $t$ are
_payoff equivalent_ if $p(s)=p(t)$.

We call a joint strategy $s$ a _Nash equilibrium_ if
$\mbox{$\forall$}i\in\\{1,\ldots,n\\}\mbox{$\forall$}s^{\prime}_{\\_}i\in
H_{\\_}i:p_{\\_}i(s_{\\_}i,s_{\\_}{-i})\geq
p_{\\_}i(s^{\prime}_{\\_}i,s_{\\_}{-i})$. When the number of players and their
payoff functions are known we can identify the game $H$ with the set of
strategies in it.

By a _subgame_ of a strategic game $H$ we mean a game obtained from $H$ by
removing some strategies. Given a set $\cal J$ of subgames of a strategic game
$H$ we define $\bigcap{\cal J}$ as the subgame of $H$ in which for each player
$i$ his set of strategies is $\bigcap_{\\_}{J\in{\cal J}}J_{\\_}i$. Also,
given two subgames $H^{\prime}$ and $H^{\prime\prime}$ of a strategic game $H$
we write $H^{\prime}\mbox{$\>\subseteq\>$}H^{\prime\prime}$ if for each player
$i$, $H^{\prime}_{\\_}i\mbox{$\>\subseteq\>$}H^{\prime\prime}_{\\_}i$.

Consider two strategies $s_{\\_}i$ and $s^{\prime}_{\\_}i$ of player $i$ in a
strategic game $H$. We say that $s_{\\_}i$ _weakly dominates
$s^{\prime}_{\\_}i$_ (or equivalently, that $s^{\prime}_{\\_}i$ is _weakly
dominated by $s_{\\_}i$_) in $H$ if $\mbox{$\forall$}s_{\\_}{-i}\in
H_{\\_}{-i}:p_{\\_}i(s_{\\_}i,s_{\\_}{-i})\geq
p_{\\_}i(s^{\prime}_{\\_}i,s_{\\_}{-i})$ and $\mbox{$\exists$}s_{\\_}{-i}\in
H_{\\_}{-i}:p_{\\_}i(s_{\\_}i,s_{\\_}{-i})>p_{\\_}i(s^{\prime}_{\\_}i,s_{\\_}{-i})$.

In what follows, given a strategic game we consider, possibly transfinite,
sequences of sets of strategies. They are written as
$(\rho_{\\_}{\alpha},\alpha<\gamma)$, where $\alpha$ ranges over all ordinals
smaller than some ordinal $\gamma$. Given two such sequences
$\rho:=(\rho_{\\_}{\alpha},\alpha<\gamma)$ and
$\rho^{\prime}:=(\rho^{\prime}_{\\_}{\alpha^{\prime}},\alpha^{\prime}<\gamma^{\prime})$,
we denote by $(\rho,\rho^{\prime})$ their concatenation (which is indexed by
$\gamma+\gamma^{\prime}$), by $\rho^{\beta}$ the subsequence
$(\rho_{\\_}{\alpha},\alpha<\beta)$ of $\rho$, and for $\alpha<\beta$ by
$\rho^{\beta-\alpha}$ the subsequence such that
$(\rho^{\alpha},\rho^{\beta-\alpha})=\rho^{\beta}$. Further, we write
$H\to^{\rho}H^{\prime}$ to denote the fact that the game $H^{\prime}$ is the
outcome of the iterated elimination from the non-empty game $H$ of the sets of
strategies that form $\rho$. In each step all eliminated strategies are weakly
dominated in the current game. As a result $H^{\prime}$ may be empty. The
relation $\to^{\rho}$ is defined as follows.

If $\rho=(\rho_{\\_}0)$, that is, if $\gamma=1$, then $H\to^{\rho}H^{\prime}$
holds if each strategy in the set $\rho_{\\_}0$ is weakly dominated in $H$ and
$H^{\prime}$ is the outcome of removing from $H$ all strategies from
$\rho_{\\_}0$. If $\gamma$ is a successor ordinal $>1$, say $\gamma=\delta+1$,
and $H\to^{\rho^{\prime}}H^{\prime}$,
$H^{\prime}\to^{(\rho_{\\_}{\delta})}H^{\prime\prime}$, where $H^{\prime}$ is
non-empty, and $\rho^{\prime}:=(\rho_{\\_}{\alpha},\alpha<\delta)$, then
$H\to^{\rho}H^{\prime\prime}$. Finally, if $\gamma$ is a limit ordinal and for
all $\beta<\gamma$, $H\to^{\rho^{\beta}}H^{\beta}$, then
$H\to^{\rho}\bigcap_{\\_}{\beta<\gamma}H^{\beta}$. In general, the strategic
game $H$ from which we eliminate strategies will be a subgame of a game
$\Gamma(G)$, where $G$ is an extensive game (to be defined shortly). It will
be then convenient to allow in $\rho$ strategies from $\Gamma(G)$. In the
definition of $H\to^{\rho}H^{\prime}$ we then disregard the strategies from
$\rho$ that are not from $H$. In the proofs below we rely on the following
observations about the $\to^{\rho}$ relation, the proofs of which we omit.

######  Note 2.4.

  1. (i)

Suppose $H\to^{\rho}H^{\prime}$ and
$H^{\prime}\to^{\rho^{\prime}}H^{\prime\prime}$, where $H^{\prime}$ is non-
empty. Then $H\to^{(\rho,\rho^{\prime})}H^{\prime\prime}$.

  2. (ii)

Suppose $H\to^{\rho}H^{\prime}$, where
$\rho=(\rho_{\\_}{\alpha},\alpha<\gamma)$ and $\gamma$ is a limit ordinal.
Suppose further that for a sequence of ordinals
$(\alpha_{\\_}{\delta})_{\\_}{\delta<\epsilon}$ converging to $\gamma$ we have
$H\to^{\rho^{\alpha_{\\_}{\delta}}}H^{\alpha_{\\_}{\delta}}$ for all
$\delta<\epsilon$. Then
$H^{\prime}=\bigcap_{\\_}{\delta<\epsilon}H^{\alpha_{\\_}{\delta}}$.

###  2.2 Well-founded games

We recall from [4] the definition of a well-founded game. A _tree_ is an
acyclic directed connected graph, written as $(V,E)$, where $V$ is a non-empty
set of nodes and $E$ is a possibly empty set of edges. An _extensive game with
perfect information_ $(T,\mathit{turn},p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$
consists of a set of players $\\{1,\mbox{$\ldots$},n\\}$, where $n\geq 1$
along with the following. A _game tree_ , which is a tree $T:=(V,E)$ with a
_turn function_ $\mathit{turn}:V\setminus Z\to\\{1,\mbox{$\ldots$},n\\}$,
where $Z$ is the set of leaves of $T$. For each player $i$ a _payoff function_
$p_{\\_}i:Z\mbox{$\>\rightarrow\>$}\mathbb{R}$, for each player $i$. The
function $\mathit{turn}$ determines at each non-leaf node which player should
move. The edges of $T$ represent possible _moves_ in the considered game,
while for a node $v\in V\setminus Z$ the set of its children
$C(v):=\\{w\mid(v,w)\in E\\}$ represents possible _actions_ of player
$\mathit{turn}(v)$ at $v$.

We say that an extensive game with perfect information is _finite_ ,
_infinite_ , or _well-founded_ if, respectively, its game tree is finite,
infinite, or well-founded. Recall that a tree is called _well-founded_ if it
has no infinite paths. _From now on by an _extensive game_ we mean a well-
founded extensive game with perfect information._

For a node $u$ in $T$ we denote the subtree of $T$ rooted at $u$ by $T^{u}$.
In the proofs we shall often rely on the concept of a _rank_ of a well-founded
tree $T$, defined inductively as follows, where $v$ is the root of $T$:

$\mathit{rank}(T):=\begin{cases}0&\text{ if $T$ has one node}\\\
\mathit{sup}\\{\mathit{rank}(T^{u})+1\mid u\in C(v)\\}&\text{
otherwise,}\end{cases}$

where $sup(X)$ denotes the least ordinal larger than all ordinals in the set
$X$.

For an extensive game $G:=(T,\mathit{turn},p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$
let $V_{\\_}i:=\\{v\in V\setminus Z\mid\mathit{turn}(v)=i\\}$. So $V_{\\_}i$
is the set of nodes at which player $i$ moves. A _strategy_ for player $i$ is
a function $s_{\\_}i:V_{\\_}i\to V$, such that $(v,s_{\\_}i(v))\in E$ for all
$v\in V_{\\_}i$. We denote the set of strategies of player $i$ by $S_{\\_}i$.
Let $S=S_{\\_}1\times\cdots\times S_{\\_}n$. As in the case of the strategic
games we use the ‘$-i$’ notation, when referring to sequences of strategies or
sets of strategies.

Each joint strategy $s=(s_{\\_}1,\mbox{$\ldots$},s_{\\_}n)$ determines a
rooted path $\mathit{play}(s):=(v_{\\_}1,\mbox{$\ldots$},v_{\\_}m)$ in $T$
defined inductively as follows. $v_{\\_}1$ is the root of $T$ and if
$v_{\\_}{k}\not\in Z$, then $v_{\\_}{k+1}:=s_{\\_}i(v_{\\_}k)$, where
$\mathit{turn}(v_{\\_}k)=i$. So when the game tree consists of just one node,
$v$, we have $\mathit{play}(s)=v$. Informally, given a joint strategy $s$, we
can view $\mathit{play}(s)$ as the resulting _play_ of the game. For each
joint strategy $s$ the rooted path $\mathit{play}(s)$ is finite since the game
tree is assumed to be well-founded. Denote by $\mathit{leaf}(s)$ the last
element of $\mathit{play}(s)$. To simplify the notation we just write
everywhere $p_{\\_}i(s)$ instead of $p_{\\_}i(\mathit{leaf}(s))$.

With each extensive game
$G:=(T,\mathit{turn},p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$ we associate a
strategic game $\Gamma(G)$ defined as follows.
$\Gamma(G):=(S_{\\_}1,\mbox{$\ldots$},S_{\\_}n,p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$,
where each $S_{\\_}i$ is the set of strategies of player $i$ in $G$. In the
degenerate situation when the game tree consists of just one node, each
strategy is the empty function, denoted by $\emptyset$, and there is only one
joint strategy, namely the $n$-tuple
$(\mbox{$\emptyset$},\mbox{$\ldots$},\mbox{$\emptyset$})$ of these functions.
In that case we just stipulate that
$p_{\\_}i(\mbox{$\emptyset$},\mbox{$\ldots$},\mbox{$\emptyset$})=0$ for all
players $i$. All notions introduced in the context of strategic games can now
be reused in the context of an extensive game $G$ simply by referring to the
corresponding strategic form $\Gamma(G)$. In particular, the notion of a Nash
equilibrium is well-defined.

The _subgame_ of an extensive game
$G:=(T,\mathit{turn},p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$, rooted at the node
$w$ and denoted by $G^{w}$, is defined as follows. The set of players is
$\\{1,\mbox{$\ldots$},n\\}$, the game tree is $T^{w}$. The $\mathit{turn}$ and
payoff functions are the restrictions of the corresponding functions of $G$ to
the nodes of $T^{w}$. We call $G^{w}$ a _direct subgame_ of $G$ if $w$ is a
child of the root $v$.

Note that some players may ‘drop out’ in $G^{w}$, in the sense that at no node
of $T^{w}$ it is their turn to move. Still, to keep the notation simple, it is
convenient to admit in $G^{w}$ all original players in $G$.

Each strategy $s_{\\_}i$ of player $i$ in $G$ uniquely determines his strategy
$s^{w}_{\\_}i$ in $G^{w}$. Given a joint strategy
$s=(s_{\\_}1,\mbox{$\ldots$},s_{\\_}n)$ of $G$ we denote by $s^{w}$ the joint
strategy $(s^{w}_{\\_}1,\mbox{$\ldots$},s^{w}_{\\_}n)$ in $G^{w}$. Further, we
denote by $S_{\\_}i^{w}$ the set of strategies of player $i$ in the subgame
$G^{w}$ and by $S^{w}$ the set of joint strategies in this subgame.

Finally, a joint strategy $s$ of $G$ is called a _subgame perfect equilibrium_
in $G$ if for each node $w$ of $T$, the joint strategy $s^{w}$ of $G^{w}$ is a
Nash equilibrium in the subgame $G^{w}$. We denote by $\mathit{SPE}(G)$ the
set of subgame perfect equilibria in $G$. Finally, we say that a game is _SPE-
invariant_ if it has a subgame perfect equilibrium and in each subgame of it
all subgame perfect equilibria are payoff equivalent.

We shall often use the following result.

######  Theorem 2.5 ([4]).

Every extensive game with finitely many outcomes has a subgame perfect
equilibrium.

##  3 Preliminary lemmas

In this section we present a sequence of lemmas needed to prove our first main
result. In the proofs we often switch between a game and its direct subgames.

Consider an extensive game
$G:=(T,\mathit{turn},p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$ with the root $v$ and
a child $w$ of $v$. For each player $j$ to each of his strategy $t_{\\_}j$ in
a direct subgame $G^{w}$ there corresponds a natural set $[t_{\\_}j]$ of his
strategies in the game $G$ defined by $[t_{\\_}j]:=\\{s_{\\_}j\mid
t_{\\_}j=s^{w}_{\\_}j\text{\ and\ }s_{\\_}j(v)=w\text{\ if\
}j=\mathit{turn}(v)\\}$. So for a player $j$, $[t_{\\_}j]$ is the set of his
strategies in $G$ the restriction of which to $G^{w}$ is $t_{\\_}j$, with the
additional proviso that if $j=\mathit{turn}(v)$, then each strategy in
$[t_{\\_}j]$ selects $w$ at the root $v$. We call $[t_{\\_}j]$ the _lifting_
of $t_{\\_}j$ to the game $G$. The following lemma clarifies the relevance of
lifting.

######  Lemma 3.6.

Consider a direct subgame $G^{w}$ of $G$. Suppose that the strategy $t_{\\_}j$
is weakly dominated in $G^{w}$. Then each strategy in $[t_{\\_}j]$ is weakly
dominated in $G$.

######  Proof 3.7.

Suppose that $t_{\\_}j$ is weakly dominated in $G^{w}$ by some strategy
$u_{\\_}j$. Take a strategy $v_{\\_}j$ in $[t_{\\_}j]$. We show that
$v_{\\_}j$ is weakly dominated in $G$ by the strategy $w_{\\_}j$ in
$[u_{\\_}j]$ that coincides with $v_{\\_}j$ on all the nodes that do not
belong to $G^{w}$. So $w_{\\_}j$ is obtained from $v_{\\_}j$ by replacing in
it $v^{w}_{\\_}j$, i.e., $t_{\\_}j$, by $u_{\\_}j$. Below $s_{\\_}{-j}$
denotes a sequence of strategies in $G$ of the opponents of player $j$.

_Case 1._ $j=\mathit{turn}(v)$.

By the choice of $u_{\\_}j$ for all $s_{\\_}{-j}$
$p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})\leq p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$
and for some $s_{\\_}{-j}$
$p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})<p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$.
Further, by the definition of $[\cdot]$ we have $v_{\\_}j(v)=w$, so for all
$s_{\\_}{-j}$ we have
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})=p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})$ and
$p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})=p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$, so the
claim follows.

_Case 2._ $j\neq\mathit{turn}(v)$.

Let $i=\mathit{turn}(v)$. Take some $s_{\\_}{-j}$. If $s_{\\_}i(v)=w$, then
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})=p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})$ and
$p_{\\_}j(w_{\\_}j,s_{\\_}{-j})=p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$. Thus
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})\leq p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$ by the
choice of $u_{\\_}j$ and $w_{\\_}j$. Further, if $s_{\\_}i(v)\neq w$, then
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})=p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$ by the choice
of $w_{\\_}j$.

Choose an arbitrary $s_{\\_}{-j}$ such that $s_{\\_}i(v)=w$ and
$p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})<p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$. By
the choice of $s_{\\_}i$ we have
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})=p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})$ and
$p_{\\_}j(w_{\\_}j,s_{\\_}{-j})=p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$, so
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})<p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$. Thus the
claim follows.

We now extend the notation $[\cdot]$ to sets of strategies and sequences of
sets strategies. First, given a set of strategies $A$ in a direct subgame
$G^{w}$ of $G$ we define $[A]:=\bigcup_{\\_}{s_{\\_}j\in A}[s_{\\_}j]$. Next,
given a sequence $\rho$ of sets of strategies of players, each set taken from
a direct subgame of $G$, we denote by $[\rho]$ the corresponding sequence of
sets of strategies of players in $G$ obtained by replacing each element $A$ in
$\rho$ by $[A]$.

Given a set $A$ of strategies of players in a direct subgame $G^{w}$ we define
the corresponding set of strategies in the game $G$ by putting $\langle
A\rangle=\\{s_{\\_}j\mid s^{w}_{\\_}j\in A\\}$. Thus for a set $A$ of
strategies in a direct subgame $G^{w}$, the set $\langle A\rangle$ differs
from $[A]$ in that we do include in the former set strategies $s_{\\_}j$ for
which $s_{\\_}j(v)\neq w$. Given a set $A$ of strategies of player $j$ in the
subgame $G^{w}$, we call $\langle A\rangle$ an _extension_ of $A$ to the game
$G$. Further, given a subgame $H$ of $\Gamma(G^{w})$, we define $\langle
H\rangle$ as the subgame of $\Gamma(G)$ in which for each player $j$ we have
$\langle H\rangle_{\\_}j=\langle H_{\\_}j\rangle$.

In what follows we need a substantially strengthened version of Lemma 3.6 that
relies on the following concept. Given an extensive game $G$ with a root $v$,
we say that a non-empty subgame $J$ of $\Gamma(G)$ _does not depend on_ a
direct subgame $G^{w}$ if for any strategy $s_{\\_}j$ from $J$ any
modification of it on the non-leaf nodes of $G^{w}$ or on $v$ if
$\mathit{turn}(v)=j$ is also in $J$. Note that in particular $\Gamma(G)$ does
not depend on any of its direct subgame and that for any non-empty subgame $H$
of a direct subgame $G^{w}$ of $G$ the subgame $\langle H\rangle$ does not
depend on any other direct subgame of $G$.

######  Lemma 3.8.

Consider a direct subgame $G^{w}$ of $G$, subgames $H$ and $H^{\prime}$ of
$\Gamma(G^{w})$ and a set $A$ of strategies in $H$. Suppose that
$H\to^{A}H^{\prime}$ and that the subgame $J$ of $\Gamma(G)$ does not depend
on $G^{w}$. Then $J\cap\langle H\rangle\to^{[A]}J\cap\langle
H^{\prime}\rangle$.

######  Proof 3.9.

Take a strategy $v_{\\_}j$ in $[A]$. For some strategy $t_{\\_}j$ from $A$
that is weakly dominated in $H$ by some strategy $u_{\\_}j$ we have
$v_{\\_}j\in[t_{\\_}j]\cap J_{\\_}j$. Select a strategy $w_{\\_}j$ in
$[u_{\\_}j]$ that coincides with $v_{\\_}j$ on the nodes that do not belong to
$G^{w}$. So $w_{\\_}j$ is a modification of $v_{\\_}j$ on the non-leaf nodes
of $G^{w}$ and consequently, by the assumption about $J$, it is in $J_{\\_}j$.
Further, $w_{\\_}j$ is in $\langle H\rangle$, since $u_{\\_}j$ is from $H$.

We claim that $v_{\\_}j$ is weakly dominated in $J\cap\langle H\rangle$ by
$w_{\\_}j$. Below $s_{\\_}{-j}$ denotes a sequence of strategies of the
opponents of player $j$ in the original game $G$.

_Case 1._ $j=\mathit{turn}(v)$.

By the choice of $u_{\\_}j$ for all $s_{\\_}{-j}$ such that
$s^{w}_{\\_}{-j}\in H_{\\_}{-j}$ $p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})\leq
p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$ and for some $s_{\\_}{-j}$ such that
$s^{w}_{\\_}{-j}\in H_{\\_}{-j}$
$p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})<p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$. By
the definition of ‘does not depend on’ and the fact that $j=\mathit{turn}(v)$
we can also assume that the latter $s_{\\_}{-j}$ is from $J_{\\_}{-j}$ by
stipulating that $s_{\\_}{-j}=t_{\\_}{-j}$ for an arbitrary joint strategy $t$
from $J$.

Further, by the definition of $[\cdot]$ we have $v_{\\_}j(v)=w$, so for all
$s_{\\_}{-j}$ such that $s^{w}_{\\_}{-j}\in H_{\\_}{-j}$ we have
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})=p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})$ and
$p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})=p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$. Hence for
all $s_{\\_}{-j}$ $p_{\\_}j(v_{\\_}j,s_{\\_}{-j})\leq
p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$ and for some $s_{\\_}{-j}$ such that
$s_{\\_}{-j}\in J_{\\_}{-j}$ and $s^{w}_{\\_}{-j}\in H_{\\_}{-j}$ (i.e., for
some $s_{\\_}{-j}\in(J\cap\langle H\rangle)_{\\_}{-j}$)
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})<p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$. This
establishes the claim.

_Case 2._ $j\neq\mathit{turn}(v)$.

Let $i=\mathit{turn}(v)$. Take some $s_{\\_}{-j}$. If $s_{\\_}i(v)=w$, then
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})=p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})$ and
$p_{\\_}j(w_{\\_}j,s_{\\_}{-j})=p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$. Thus
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})\leq p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$ by the
choice of $u_{\\_}j$ and $w_{\\_}j$. Further, if $s_{\\_}i(v)\neq w$, then
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})=p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$ by the choice
of $w_{\\_}j$. So for all $s_{\\_}{-j}$ we have
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})\leq p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$.

Choose an arbitrary $s_{\\_}{-j}$ such that $s_{\\_}i(v)=w$,
$s^{w}_{\\_}{-j}\in H_{\\_}{-j}$, and
$p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})<p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$.
Additionally, we can claim that $s_{\\_}{-j}\in J_{\\_}{-j}$ by stipulating
that $s_{\\_}{-j}=t_{\\_}{-j}$ for an arbitrary joint strategy $t$ from $J$.
Then $s_{\\_}{-j}\in(J\cap\langle H\rangle)_{\\_}{-j}$.

By the choice of $s_{\\_}i$ we have
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})=p_{\\_}j(t_{\\_}j,s^{w}_{\\_}{-j})$ and
$p_{\\_}j(w_{\\_}j,s_{\\_}{-j})=p_{\\_}j(u_{\\_}j,s^{w}_{\\_}{-j})$, so
$p_{\\_}j(v_{\\_}j,s_{\\_}{-j})<p_{\\_}j(w_{\\_}j,s_{\\_}{-j})$. This
establishes the claim for this case.

We continue with some lemmas concerned with the relation $\to^{\rho}$.

######  Lemma 3.10.

Consider a direct subgame $G^{w}$ of $G$. Suppose that for some sequence
$\rho$ of sets of strategies of players in $G^{w}$ and a subgame $H$ of
$\Gamma(G^{w})$, $\Gamma(G^{w})\to^{\rho}H$. Suppose further that the subgame
$J$ of $\Gamma(G)$ does not depend on $G^{w}$. Then $J\to^{[\rho]}J\cap\langle
H\rangle$.

######  Proof 3.11.

We proceed by transfinite induction on the length $\gamma$ of
$\rho=(\rho_{\\_}{\alpha},\alpha<\gamma)$.

_Case 1._ $\gamma=1$.

By Lemma 3.8 $J\cap\langle\Gamma(G^{w})\rangle\to^{[\rho_{\\_}0]}J\cap\langle
H\rangle$, so the claim holds since $\langle\Gamma(G^{w})\rangle=\Gamma(G)$
and $J\cap\Gamma(G)=J$.

_Case 2._ $\gamma$ is a successor ordinal $>1$.

Suppose $\gamma=\delta+1$. Then $\rho=(\rho^{\prime},\rho_{\\_}{\delta})$,
where $\rho^{\prime}:=(\rho_{\\_}{\alpha},\alpha<\delta)$. By definition for
some $H^{\prime}$ we have $\Gamma(G^{w})\to^{\rho^{\prime}}H^{\prime}$ and
$H^{\prime}\to^{\rho_{\\_}{\delta}}H$. By the induction hypothesis
$J\to^{[\rho^{\prime}]}J\cap\langle H^{\prime}\rangle$ and by Lemma 3.8
$J\cap\langle H^{\prime}\rangle\to^{[\rho_{\\_}{\delta}]}J\cap\langle
H\rangle$, so the claim follows by Note 2.4$(i)$, since
$[\rho]=([\rho^{\prime}],[\rho_{\\_}{\delta}])$.

_Case 3._ $\gamma$ is a limit ordinal.

By definition for some games $H^{\beta}$, where $\beta<\gamma$, we have
$\Gamma(G^{w})\to^{\rho^{\beta}}H^{\beta}$ and
$H=\bigcap_{\\_}{\beta<\gamma}H^{\beta}$,
where—recall—$\rho^{\beta}=(\rho_{\\_}{\alpha},\alpha<\beta)$. By the
induction hypothesis for all $\beta<\gamma$, we have
$J\to^{[\rho^{\beta}]}J\cap\langle H^{\beta}\rangle$. So by definition
$J\to^{[\rho]}J\cap\langle H\rangle$, since $J\cap\langle
H\rangle=\bigcap_{\\_}{\beta<\gamma}\langle J\cap H^{\beta}\rangle$ as
$\langle H\rangle=\bigcap_{\\_}{\beta<\gamma}\langle H^{\beta}\rangle$.

######  Lemma 3.12.

Consider an extensive game $G$ with the root $v$. Suppose that
$(w_{\\_}{\alpha},\alpha<\gamma)$ is a sequence of children of $v$ and that
for all $\alpha<\gamma$, $\rho_{\\_}{\alpha}$ is a sequence of sets of
strategies in the direct subgame $G^{w_{\\_}{\alpha}}$. Suppose further that
for each $\alpha<\gamma$
$\Gamma(G^{w_{\\_}{\alpha}})\to^{\rho_{\\_}{\alpha}}H^{w_{\\_}{\alpha}}$,
where each game $H^{w_{\\_}{\alpha}}$ is non-empty. Let $\rho$ be the
concatenation of the sequences $(\rho_{\\_}{\alpha},\alpha<\gamma)$. Then
$\Gamma(G)\to^{[\rho]}\bigcap_{\\_}{\alpha<\gamma}\langle
H^{w_{\\_}{\alpha}}\rangle$.

By assumption each $H^{w_{\\_}{\alpha}}$ is a non-empty subgame of
$\Gamma(G^{w_{\\_}{\alpha}})$, so each $\langle H^{w_{\\_}{\alpha}}\rangle$ is
a non-empty subgame of $\Gamma(G)$, and consequently
$\bigcap_{\\_}{\alpha<\gamma}\langle H^{w_{\\_}{\alpha}}\rangle$ is also a
non-empty subgame of $\Gamma(G)$.

Informally, suppose that for each direct subgame $G^{w_{\\_}{\alpha}}$ of $G$
we can reduce the corresponding strategic game $\Gamma(G^{w_{\\_}{\alpha}})$
to a non-empty game $H^{w_{\\_}{\alpha}}$. Then the strategic game $\Gamma(G)$
can be reduced to a strategic game the strategies of which are obtained by
intersecting for each player the extensions of his strategy sets in all games
$H^{w_{\\_}{\alpha}}$. To establish this lemma we do not assume that
$(w_{\\_}{\alpha},\alpha<\gamma)$ contains all children of $v$, which makes it
possible to proceed by induction.

######  Proof 3.13.

We proceed by transfinite induction on the length $\gamma$ of $\rho$.

_Case 1._ $\gamma=1$. Follows from Lemma 3.10 with $J=\Gamma(G)$.

_Case 2._ $\gamma$ is a successor ordinal $>1$.

Suppose $\gamma=\delta+1$. By the induction hypothesis
$\Gamma(G)\to^{[\rho^{\delta}]}\bigcap_{\\_}{\alpha<\delta}\langle
H^{w_{\\_}{\alpha}}\rangle$, where $\rho^{\delta}$ is the concatenation of the
sequences $(\rho_{\\_}{\alpha},\alpha<\delta)$. We also have by assumption
$\Gamma(G^{w_{\\_}{\delta}})\to^{\rho_{\\_}{\delta}}H^{w_{\\_}{\delta}}$.

Note that the subgame $\bigcap_{\\_}{\alpha<\delta}\langle
H^{w_{\\_}{\alpha}}\rangle$ of $\Gamma(G)$ does not depend on
$G^{w_{\\_}{\delta}}$, so by Lemma 3.10 we have that
$\bigcap_{\\_}{\alpha<\delta}\langle
H^{w_{\\_}{\alpha}}\rangle\to^{[\rho_{\\_}{\delta}]}\bigcap_{\\_}{\alpha<\delta}\langle
H^{w_{\\_}{\alpha}}\rangle\cap\langle H^{w_{\\_}{\delta}}\rangle$. By Note
2.4$(i)$ the claim follows.

_Case 3._ $\gamma$ is a limit ordinal.

By the induction hypothesis for all $\beta<\gamma$
$\Gamma(G)\to^{[\rho^{\beta}]}\bigcap_{\\_}{\alpha<\beta}\langle
H^{w_{\\_}{\alpha}}\rangle$, where $\rho^{\beta}$ is the concatenation of the
sequences $(\rho_{\\_}{\alpha},\alpha<\beta)$. Then by Note 2.4$(ii)$ and by
definition
$\Gamma(G)\to^{[\rho]}\bigcap_{\\_}{\beta<\gamma}\bigcap_{\\_}{\alpha<\beta}\langle
H^{w_{\\_}{\alpha}}\rangle$. But
$\bigcap_{\\_}{\beta<\gamma}\bigcap_{\\_}{\alpha<\beta}\langle
H^{w_{\\_}{\alpha}}\rangle=\bigcap_{\\_}{\alpha<\gamma}\langle
H^{w_{\\_}{\alpha}}\rangle$, so the claim follows.

The next lemma shows that when each subgame $H^{w_{\\_}{\alpha}}$ of
$\Gamma(G^{w_{\\_}{\alpha}})$ is trivial, under some natural assumptions the
subgame $\bigcap_{\\_}{\alpha<\gamma}\langle H^{w_{\\_}{\alpha}}\rangle$ of
$\Gamma(G)$ can then be reduced in one step to a trivial game.

######  Lemma 3.14.

Consider an extensive game $G$ with the root $v$. Suppose that

  1. (a)

$G$ has a subgame perfect equilibrium and all subgame perfect equilibria of
$G$ are payoff equivalent,

  2. (b)

for all $w\in C(v)$, $\mathit{SPE}(G^{w})\mbox{$\>\subseteq\>$}H^{w}$, where
$H^{w}$ is a trivial subgame of $\Gamma(G^{w})$.

Then for some set of strategies $A$ we have $\bigcap_{\\_}{w\in C(v)}\langle
H^{w}\rangle\to^{A}H^{\prime}$, where $H^{\prime}$ a trivial game and
$\mathit{SPE}(G)\mbox{$\>\subseteq\>$}H^{\prime}$.

######  Proof 3.15.

Let $H:=\bigcap_{\\_}{w\in C(v)}\langle H^{w}\rangle$. Note that $H$ is a non-
empty subgame of $\Gamma(G)$.

Denote the unique outcome in the game $H^{w}$ by $val^{w}$, i.e., for all
joint strategies $s$ in $H^{w}$ we have $p(s)=val^{w}$. Then the possible
outcomes in $H$ are $val^{w}$, where $w\in C(v)$. More precisely, suppose that
$i=\mathit{turn}(v)$. Then if $s$ is a joint strategy in $H$, then
$p(s)=val^{w}$, where $s_{\\_}i(v)=w$.

Take two strategies $t^{\prime}_{\\_}i$ and $t^{\prime\prime}_{\\_}i$ of
player $i$ in $H$ with $t^{\prime}_{\\_}i(v)=w_{\\_}1$ and
$t^{\prime\prime}_{\\_}i(v)=w_{\\_}2$ such that
$val_{\\_}i^{w_{\\_}1}<val_{\\_}i^{w_{\\_}2}$. This means that for any joint
strategies $s_{\\_}{-i}$ from $H_{\\_}{-i}$ we have
$p_{\\_}i(t^{\prime}_{\\_}i,s_{\\_}{-i}<p_{\\_}i(t^{\prime\prime}_{\\_}i,s_{\\_}{-i}$,
so $t^{\prime}_{\\_}i$ is weakly dominated in $H$ by $t^{\prime\prime}_{\\_}i$
(actually, even strictly dominated).

By assumption _(a)_ $G$ has a subgame perfect equilibrium, so by Corollary 7
of [4] $\max\\{val_{\\_}i^{w}\mid w\in C(v)\\}$ exists. Denote it by
$val_{\\_}i$ and let $W:=\\{w\in C(v)\mid val_{\\_}i^{w}=val_{\\_}i\\}$. So
$W$ is the set of children $w$ of $v$ for which the corresponding value
$val_{\\_}{i}^{w}$ is maximal. Finally, let $A$ be the set of strategies
$t_{\\_}i$ of player $i$ in $H$ such that $t_{\\_}i(v)\not\in W$.

By the above observation about $t^{\prime}_{\\_}i$ and
$t^{\prime\prime}_{\\_}i$ all strategies in $A$ are weakly dominated in $H$.
By removing them from $H$ we get a game $H^{\prime}$ with the unique payoff
$val_{\\_}i$ for player $i$. To prove that $H^{\prime}$ is trivial consider
two joint strategies $s$ and $t$ in $H^{\prime}$. Suppose that
$s_{\\_}i(v)=w_{\\_}1$ and $t_{\\_}i(v)=w_{\\_}2$. Then $w_{\\_}1,w_{\\_}2\in
W$, $s^{w_{\\_}1}\in H^{w_{\\_}1}$, $t^{w_{\\_}2}\in H^{w_{\\_}2}$,
$p(s)=p(s^{w_{\\_}1})$, and $p(t)=p(t^{w_{\\_}2})$.

By Theorem 8 of [4] subgame perfect equilibria $u^{\prime}$ and
$u^{\prime\prime}$ in $G$ exist such that $u^{\prime}_{\\_}i(v)=w_{\\_}1$,
$(u^{\prime})^{w_{\\_}1}$ is a subgame perfect equilibrium in $G^{w_{\\_}1}$,
$u^{\prime\prime}_{\\_}i(v)=w_{\\_}2$, and $(u^{\prime\prime})^{w_{\\_}2}$ is
a subgame perfect equilibrium in $G^{w_{\\_}2}$. Then
$p(u^{\prime})=p((u^{\prime})^{w_{\\_}1})$ and
$p(u^{\prime\prime})=p((u^{\prime\prime})^{w_{\\_}2})$, so
$p((u^{\prime})^{w_{\\_}1})=p((u^{\prime\prime})^{w_{\\_}2})$ by assumption
_(a)_. Further, by assumption _(b)_ both $(u^{\prime})^{w_{\\_}1}\in
H^{w_{\\_}1}$ and $(u^{\prime\prime})^{w_{\\_}2}\in H^{w_{\\_}2}$, so since
both subgames are trivial, $p(s^{w_{\\_}1})=p((u^{\prime})^{w_{\\_}1})$ and
$p(t^{w_{\\_}2})=p((u^{\prime})^{w_{\\_}2})$. Consequently $p(s)=p(t)$, which
proves that $H^{\prime}$ is trivial.

To prove that $\mathit{SPE}(G)\mbox{$\>\subseteq\>$}H^{\prime}$ consider a
subgame perfect equilibrium $s$ in $G$. Take some $u\in C(v)$. By assumption
_(b)_ , $s^{u}\in H^{u}$, so $p_{\\_}i(s^{u})=val_{\\_}i^{u}$ and, by the
definition of $\langle\cdot\rangle$, $s\in H$. Suppose that $s_{\\_}i(v)=w$.
By Corollary 7 of [4] $val_{\\_}i^{w}=val_{\\_}i$, i.e., $s_{\\_}i(v)\in W$.
This means that $s_{\\_}i\not\in A$ and thus $s\in H^{\prime}$.

##  4 SPE-invariant games

We can now prove the desired result.

######  Theorem 4.16.

Consider an SPE-invariant extensive game $G$. There exists a sequence $\rho$
of strategies of players in $G$ and a subgame $H$ of $\Gamma(G)$ such that
$\Gamma(G)\to^{\rho}H$, $H$ is trivial and $\mathit{SPE}(G)\subseteq H$.

######  Proof 4.17.

We proceed by induction on the rank of the game tree of $G$. For game trees of
rank 0 all strategies are empty functions, so $\Gamma(G)$ is a trivial game
with the unique joint strategy
$(\mbox{$\emptyset$},\mbox{$\ldots$},\mbox{$\emptyset$})$ and
$\mathit{SPE}(G)=\\{(\mbox{$\emptyset$},\mbox{$\ldots$},\mbox{$\emptyset$})\\}$,
so the claim holds. Suppose that the rank of the game tree of $G$ is
$\alpha>0$ and assume that claim holds for all extensive games with the game
trees of rank smaller than $\alpha$.

Let $v$ be the root of $G$. Each direct subgame of $G$ is SPE-invariant, so by
the induction hypothesis for all $w\in C(v)$ there exists a sequence
$\rho^{w}$ of strategies of players in $G^{w}$ and a subgame $H^{w}$ of
$\Gamma(G^{w})$ such that $\Gamma(G^{w})\to^{\rho^{w}}H^{w}$, $H^{w}$ is
trivial and $\mathit{SPE}(G^{w})\mbox{$\>\subseteq\>$}H^{w}$. The claim now
follows by Lemmas 3.12 and 3.14.

The following example illustrates the use of this theorem. An extensive game
is called _generic_ if each payoff function is an injective.

$v(1)$$S_{\\_}1:(1,0)$$S$$C_{\\_}1(2)$$S_{\\_}2:(0,2)$$S$$C_{\\_}2:(2,1)$$C$$C$
Figure 4: Centipede game with 2 periods
$C_{\\_}{2t}(1)$$S_{\\_}{2t+1}:(x+1,y)$$S$$C_{\\_}{2t+1}(2)$$S_{\\_}{2t+2}:(x,y+3)$$S$$C_{\\_}{2t+2}:(x+2,y+2)$$C$$C$
Figure 5: From $t$ to $t+2$ periods

######  Example 4.18.

Recall that the centipede game, introduced in [16] (see also [12, pages
106-108]), is a two-players extensive game played for an even number of
periods. We define it inductively as follows. The game with 2 periods is
depicted in Figure 4. Here and below the argument of each non-leaf is the
player whose turn is to move, and the leaves are followed by players’ payoffs.
The moves are denoted by the letters $C$ and $S$. The game with $2t+2$ periods
is obtained from the game with $2t$ periods by replacing the leaf
$C_{\\_}{2t}$ by the tree depicted in Figure 5.

By the the result of [12, pages 108-109]) each centipede game can be reduced
by an iterated elimination of weakly dominated strategies to a trivial game
which contains the unique subgame perfect equilibrium, with the outcome
$(1,0)$. We now show that the same holds for an infinite version of the
centipede game $G$ in which player 2 begins the game by selecting an even
number $2t>0$. Subsequently, the centipede version with $2t$ periods is
played.

Note that $G$ is SPE-invariant. Indeed, $G$ has infinitely many subgame
perfect equilibria (one for each first move of player 2), but each of them
yields the outcome $(1,0)$. Moreover, each subgame of $G$ is either a
centipede game with $2t$ periods for some $t>0$, or a subgame of such a game.
So each subgame of $G$ is a finite generic game and thus has a unique subgame
perfect equilibrium.

By Theorem 4.16 we can reduce $G$ by an infinite iterated elimination of
weakly dominated strategies to a trivial game which contains all its subgame
perfect equilibria. Note that the strategy elimination sequence constructed in
the proof of this theorem consists of for more than $\omega$ steps. $\Box$

For finite extensive games, Theorem 4.16 extends the original result reported
in [12, pages 108-109]. Namely, the authors prove the corresponding result for
finite extensive games that are generic. In such games a unique subgame
perfect equilibrium exists, while we only claim that the game is SPE-
invariant.

To clarify the relevance of this relaxation let us mention two classes of
well-founded extensive games that are SPE-invariant and that were studied for
finite extensive games. Following [5] we say that an extensive game
$(T,\mathit{turn},p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$ is _without relevant
ties_ if for all non-leaf nodes $u$ in $T$ the payoff function $p_{\\_}i$,
where $\mathit{turn}(u)=i$, is injective on the leaves of $T^{u}$. This is a
more general property than being generic. The relevant property for finite
extensive games is that a game without relevant ties has a unique subgame
perfect equilibrium, see [3] for a straightforward proof. In the case of well-
founded games a direct modification of this proof, that we omit, shows that
every extensive game without relevant ties has at most one subgame perfect
equilibrium. Further, if a game is without relevant ties, then so is every
subgame of it, so we conclude that well-founded games without relevant ties
are SPE-invariant.

Next, following [11] we say that an extensive game
$(T,turn,p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$ satisfies the _transference of
decisionmaker indifference (TDI)_ condition if:

$\begin{array}[]{l}\mbox{$\mbox{$\forall$}i\in\\{1,\ldots,n\\}\>\mbox{$\forall$}r_{\\_}i,t_{\\_}i\in
S_{\\_}i\>\mbox{$\forall$}s_{\\_}{-i}\in S_{\\_}{-i}$}\\\
\mbox{[$p_{\\_}{i}(\mathit{leaf}(r_{\\_}i,s_{\\_}{-i}))=p_{\\_}{i}(\mathit{leaf}(t_{\\_}i,s_{\\_}{-i}))\to
p(\mathit{leaf}(r_{\\_}i,s_{\\_}{-i}))=p(\mathit{leaf}(t_{\\_}i,s_{\\_}{-i}))$].}\end{array}$

where $S_{\\_}i$ is the set of strategies of player $i$. Informally, this
condition states that whenever for some player $i$, two of his strategies
$r_{\\_}i$ and $t_{\\_}i$ are indifferent w.r.t. some joint strategy
$s_{\\_}{-i}$ of the other players then this indifference extends to all
players.

Strategic games that satisfy the TDI condition are of interest because of the
main result of [11] which states that in finite games that satisfy this
condition iterated elimination of weakly dominated strategies is order
independent.444Alternative proofs of this result were given in [2] and [18].
The authors also give examples of natural games that satisfy this condition.
Also strictly competitive games studied in the next section satisfy this
condition.

The following result extends an implicit result of [11] to well-founded games.

######  Theorem 4.19.

Consider an extensive game $G$. Suppose that $G$ has finitely many outcomes
and $G$ satisfies the TDI condition. Then $G$ is SPE-invariant.

######  Proof 4.20.

We reduce the game $G$ to a finite game $H$ as follows. First, consider the
set of all leaves of the game tree $T$ of $G$ that are the ends of the plays
corresponding with a subgame perfect equilibrium. Next, for each outcome
associated with a subgame perfect equilibrium retain in this set just one leaf
with this outcome. By assumption the resulting set $L$ is finite.

Next, order the leaves arbitrarily. Following this ordering remove all leaves
with an outcome already associated with an earlier leaf, but ensuring that the
leaves from $L$ are retained. Let $M$ be the resulting set of leaves. Finally,
remove all nodes of $T$ from which no leaf in $M$ can be reached.

The resulting tree corresponds to a finite extensive game $H$ in which all the
outcomes possible in $G$ are present. Further, all the leaves of $H$ are also
leaves of $G$, so $H$ satisfies the TDI condition since $G$ does. So by
Theorem 12 of [3] (that is implicit in [11]) all subgame perfect equilibria of
$H$ are payoff equivalent.

Further, by Theorem 2.5 $G$ has a subgame perfect equilibrium. Consider two
subgame perfect equilibria $s$ and $t$ in $G$ with the outcomes $p(s)$ and
$p(t)$. By construction two subgame perfect equilibria $s^{\prime}$ and
$t^{\prime}$ in $H$ exist such that $p(s)=p(s^{\prime})$ and
$p(t)=p(t^{\prime})$. We conclude that all subgame perfect equilibria of $G$
are payoff equivalent.

To complete the proof it suffice to note that if an extensive game $G$
satisfies the TDI condition, then so does every subgame of it. Indeed,
consider a subgame $G^{w}$ of $G$. Let $i=\mathit{turn}(w)$ and take
$r^{w}_{\\_}i,t^{w}_{\\_}i\in S^{w}_{\\_}i$ and $s^{w}_{\\_}{-i}\in
S^{w}_{\\_}{-i}$. Extend these strategies to the strategies
$r_{\\_}i,t_{\\_}i$ and $s_{\\_}{-i}$ in the game $G$ in such a way that $w$
lies both on $\mathit{play}(r_{\\_}i,s_{\\_}{-i})$ and on
$\mathit{play}(t_{\\_}i,s_{\\_}{-i})$. Then
$p(r^{w}_{\\_}i,s^{w}_{\\_}{-i})=p(r_{\\_}i,s_{\\_}{-i})$ and
$p(t^{w}_{\\_}i,s^{w}_{\\_}{-i})=p(t_{\\_}i,s_{\\_}{-i})$, so the claim
follows.

######  Corollary 4.21.

The claim of Theorem 4.16 holds for extensive games with finitely many
outcomes that satisfy the TDI condition.

Conjecture Every extensive game that satisfies the TDI-condition is SPE-
invariant.

If the conjecture is true, Theorem 4.16 holds for all extensive games that
satisfy the TDI condition. An example of a game with infinitely many outcomes
that satisfies the TDI condition is the infinite version of the centipede game
from Example 4.18.

##  5 Strictly competitive extensive games

In some games, for instance, the infinite version of the centipede game from
Example 4.18, infinite rounds of elimination of weakly dominated strategies
are needed to solve the game. In this section, we focus on maximal elimination
of weakly dominated strategies and identify a subclass of extensive games for
which we can provide a finite bound on the number of elimination steps
required to solve the game. The outcome is our second main result which is a
generalization of the following result due to [7] to a class of well-founded
games.

Theorem Every finite extensive zero-sum game with $n$ outcomes can be reduced
to a trivial game by the maximal iterated elimination of weakly dominated
strategies in $n-1$ steps.

We first present some auxiliary results. Their proofs follow our detailed
exposition in [3] of the proofs in [7] generalized to strictly competitive
games, now appropriately modified to infinite games.

###  5.1 Preliminary results

We denote by $H^{1}$ the subgame of $H$ obtained by the elimination of all
strategies that are weakly dominated in $H$, and put $H^{0}:=H$ and
$H^{k+1}:=(H^{k})^{1}$, where $k\geq 1$. Abbreviate the phrase ‘iterated
elimination of weakly dominated strategies’ to IEWDS. If for some $k$, $H^{k}$
is a trivial game we say that $H$ _can be solved by the IEWDS_.

In infinite strategic games with finitely many outcomes it is possible that
all strategies of a player are weakly dominated as shown in the Example 5.22.
Then by definition, $H^{1}$ is an empty game. We define a class of games,
called WD-admissible games in which this does not happen.

######  Example 5.22.

Consider the following infinite zero-sum strategic game with two outcomes:

${{\begin{array}[c]{@{}r|*{5}{c|}}\hfil\hbox{}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\ignorespaces$A$
}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\ignorespaces$B$
}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\ignorespaces$C$
}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\ignorespaces$D$
}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\cr{\vskip-0.4pt}{\cline{2-}}{}{}{}\hfil\hbox{\ignorespaces$A$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}{}\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\cr{\vskip-0.4pt}{\cline{2-}}{}{}{}\hfil\hbox{\ignorespaces$B$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}{}\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$1,-1$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\cr{\vskip-0.4pt}{\cline{2-}}{}{}{}\hfil\hbox{\ignorespaces$C$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}{}\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$1,-1$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$1,-1$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\cr{\vskip-0.4pt}{\cline{2-}}{}{}{}\hfil\hbox{\ignorespaces$D$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}{}\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$0,0$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$1,-1$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$1,-1$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$1,-1$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\cr{\vskip-0.4pt}{\cline{2-}}{}{}{}\hfil\hbox{\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}{}\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\hfil\hbox{\ignorespaces\ignorespaces$\dots$
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}}\hfil\hbox{\vrule
height=9.41666pt,depth=2.58334pt,width=0.0pt}\cr{\vskip-0.4pt}{\cline{2-}}\hskip
6.0pt\hbox to21.66664pt{\hfil}\hskip 6.0pt\hskip 6.0pt\hbox
to21.66664pt{\hfil}\hskip 6.0pt\hskip 6.0pt\hbox to21.66664pt{\hfil}\hskip
6.0pt\hskip 6.0pt\hbox to21.66664pt{\hfil}\hskip 6.0pt\hskip 6.0pt\hbox
to21.66664pt{\hfil}\hskip 6.0pt\crcr}}\end{array}$

This game has a Nash equilibrium, namely $(A,A)$, but each strategy of the row
player is weakly dominated. So after one round of elimination the empty game
is reached. $\Box$

Consider a strategic game $H$. We say that a strategy is _undominated_ if no
strategy weakly dominates it. Next, we say that $H$ is _WD-admissible_ if for
all subgames $H^{\prime}$ of it the following holds: each strategy is
undominated or is weakly dominated by an undominated strategy. Intuitively, a
strategic game $H$ is WD-admissible if in every subgame $H^{\prime}$ of it,
for every strategy $s_{\\_}i$ in $H^{\prime}$ the relation ‘is weakly
dominated’ in $H^{\prime}$ has a maximal element above $s_{\\_}i$. The crucial
property of WD-admissible games is formalised in the following lemma whose
proof follows directly by induction.

######  Lemma 5.23.

Let $H:=(H_{\\_}1,\mbox{$\ldots$},H_{\\_}n,p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$
be a WD-admissible strategic game and for $k\geq 1$, let
$H^{k}:=(H^{k}_{\\_}1,\mbox{$\ldots$},H^{k}_{\\_}n,p_{\\_}1,\mbox{$\ldots$},p_{\\_}n)$.
Then $\mbox{$\forall$}i\in\\{1,\mbox{$\ldots$},n\\}\
\mbox{$\forall$}s_{\\_}i\in H_{\\_}i\ \mbox{$\exists$}t_{\\_}i\in
H^{k}_{\\_}i\ \mbox{$\forall$}s_{\\_}{-i}\in
H^{k}_{\\_}{-i}:p_{\\_}i(t_{\\_}i,s_{\\_}{-i})\geq
p_{\\_}i(s_{\\_}i,s_{\\_}{-i})$.

A two player strategic game $H=(H_{\\_}1,H_{\\_}2,p_{\\_}1,p_{\\_}2)$ is
called _strictly competitive_ if $\mbox{$\forall$}i\in\\{1,2\\}\
\mbox{$\forall$}s,s^{\prime}\in S:p_{\\_}i(s)\geq p_{\\_}i(s^{\prime})\text{
iff }p_{\\_}{-i}(s)\leq p_{\\_}{-i}(s^{\prime})$. For $i\in\\{1,2\\}$ we
define $maxmin_{\\_}{i}(H):=\max_{\\_}{s_{\\_}{i}\in
H_{\\_}i}\min_{\\_}{s_{\\_}{-i}\in
H_{\\_}{-i}}p_{\\_}i(s_{\\_}i,s_{\\_}{-i})$. We allow $-\infty$ and $\infty$
as minima and maxima, so $maxmin_{\\_}{i}(H)$ always exists. When
$maxmin_{\\_}{i}(H)$ is finite we call any strategy $s^{*}_{\\_}i$ such that
$\min_{\\_}{s_{\\_}{-i}\in
H_{\\_}{-i}}p_{\\_}i(s^{*}_{\\_}i,s_{\\_}{-i})=maxmin_{\\_}{i}(H)$ a _security
strategy_ for player $i$ in $H$.

We shall reuse the following auxiliary results from [3].

######  Note 5.24.

Let $H=(H_{\\_}1,H_{\\_}2,p_{\\_}1,p_{\\_}2)$ be a strictly competitive
strategic game. Then

$\mbox{$\forall$}i\in\\{1,2\\}\ \mbox{$\forall$}s,s^{\prime}\in
S:p_{\\_}i(s)=p_{\\_}i(s^{\prime})\text{ iff
}p_{\\_}{-i}(s)=p_{\\_}{-i}(s^{\prime}).$

This simply means that every strictly competitive strategic game satisfies the
TDI condition.

######  Lemma 5.25.

Consider a strictly competitive strategic game $H$ with a Nash equilibrium
$s$. Suppose that for some $i\in\\{1,2\\}$, $t_{\\_}i$ weakly dominates
$s_{\\_}i$. Then $(t_{\\_}i,s_{\\_}{-i})$ is also a Nash equilibrium.

######  Lemma 5.26.

Consider a strictly competitive strategic game $H$ with two outcomes that has
a Nash equilibrium. Then $H^{1}$ is a trivial game.

The following result is standard (for the used formulation see, e.g., [15,
Theorem 5.11, page 235]).

######  Theorem 5.27.

Consider a strictly competitive strategic game $H$.

  1. (i)

All Nash equilibria of $H$ yield the same payoff for player $i$, namely
$maxmin_{\\_}{i}(H)$.

  2. (ii)

All Nash equilibria of $H$ are of the form $(s^{*}_{\\_}1,s^{*}_{\\_}2)$ where
each $s^{*}_{\\_}i$ is a security strategy for player $i$.

By modifying the proof of Corollary 5 from [3] appropriately, we have the
following.

######  Lemma 5.28.

Consider a WD-admissible strictly competitive strategic game $H$ that has a
Nash equilibrium. Then $H^{1}$ has a Nash equilibrium, as well, and for all
$i\in\\{1,2\\}$, $maxmin_{\\_}{i}(H)=maxmin_{\\_}{i}(H^{1})$.

###  5.2 A bound on IEWDS

We now move on to a discussion of extensive games. We say that an extensive
game $G$ is _WD-admissible_ (respectively, _strictly competitive_) if
$\Gamma(G)$ is WD-admissible (respectively, strictly competitive). We write
$\Gamma^{k}(G)$ instead of $(\Gamma(G))^{k}$, $\Gamma_{\\_}i(G)$ instead of
$(\Gamma(G))_{\\_}i$, and $\Gamma^{k}_{\\_}i(G)$ instead of
$(\Gamma^{k}(G))_{\\_}i$. So $\Gamma^{0}(G)=\Gamma(G)$. Further, for a
strictly competitive game $H=(H_{\\_}1,H_{\\_}2,p_{\\_}1,p_{\\_}2)$ with
finitely many outcomes for each player $i$ we define the following three sets:
$p_{\\_}i^{\mathit{max}}(H):=\max_{\\_}{s\in S}p_{\\_}i(s)$,
$\mathit{win}_{\\_}i(H):=\\{s_{\\_}i\in
H_{\\_}i\mid\mbox{$\forall$}s_{\\_}{-i}\in
H_{\\_}{-i}\>p_{\\_}i(s_{\\_}i,s_{\\_}{-i})=p_{\\_}i^{\mathit{max}}(H)\\}$ and
$\mathit{lose}_{\\_}{-i}(H)=\\{s_{\\_}{-i}\in H_{\\_}{-i}\mid\exists
s_{\\_}{i}\in
H_{\\_}{i}\>p_{\\_}{i}(s_{\\_}{i},s_{\\_}{-i})=p^{\mathit{max}}_{\\_}{i}(H)\\}$.
By the assumption about $H$, $p_{\\_}i^{\mathit{max}}(H)$ is finite.

We can then prove the following generalization of the crucial Lemma 1 and
Theorem 1 from [7], where the proofs are analogous to that of Lemma 18 and
Theorem 19 in [3].

######  Lemma 5.29.

Let $G$ be a WD-admissible strictly competitive extensive game with finitely
many outcomes. For all $i\in\\{1,2\\}$ and for all $k\geq 0$, if
$\mathit{win}_{\\_}i(\Gamma^{k}(G))=\emptyset$ then
$\mathit{lose}_{\\_}{-i}(\Gamma^{k}(G))\cap\Gamma^{k+2}_{\\_}{-i}(G)=\mbox{$\emptyset$}$.

Lemma 5.29 implies that if for all $i\in\\{1,2\\}$,
$\mathit{win}_{\\_}i(\Gamma^{k}(G))=\emptyset$ then two further rounds of
eliminations of weakly dominated strategies remove from $\Gamma^{k}(G)$ at
least two outcomes.

This allows us to establish the following result. The proof is almost the same
as the one given in [3, Theorem 19] for the finite extensive games. We
reproduce it here for the convenience of the reader.

######  Theorem 5.30.

Let $G$ be a WD-admissible strictly competitive extensive game with at most
$m$ outcomes. Then $\Gamma^{m-1}(G)$ is a trivial game.

######  Proof 5.31.

We prove a stronger claim, namely that for all $m\geq 1$ and $k\geq 0$ if
$\Gamma^{k}(G)$ has at most $m$ outcomes, then $\Gamma^{k+m-1}(G)$ is a
trivial game.

We proceed by induction on $m$. For $m=1$ the claim is trivial. For $m=2$ we
first note that by Theorem 2.5 and Lemma 5.28 each game $\Gamma^{k}(G)$ has a
Nash equilibrium. So the claim follows by Lemma 5.26. For $m>2$ two cases
arise.

_Case 1._ For some $i\in\\{1,2\\}$,
$\mathit{win}_{\\_}i(\Gamma^{k}(G))\neq\emptyset$.

For player $i$ every strategy $s_{\\_}i\in\mathit{win}_{\\_}i(\Gamma^{k}(G))$
weakly dominates all strategies
$s_{\\_}i^{\prime}\notin\mathit{win}_{\\_}i(\Gamma^{k}(G))$ and no strategy in
$\mathit{win}_{\\_}i(\Gamma^{k}(G))$ is weakly dominated. So the set of
strategies of player $i$ in $\Gamma^{k+1}(G)$ equals
$\mathit{win}_{\\_}i(\Gamma^{k}(G))$ and consequently
$p_{\\_}i^{\mathit{max}}(\Gamma^{k}(G))$ is his unique payoff in this game. By
Note 5.24 $\Gamma^{k+1}(G)$, and hence also $\Gamma^{k+m-1}(G)$, is a trivial
game.

_Case 2._ For all $i\in\\{1,2\\}$,
$\mathit{win}_{\\_}i(\Gamma^{k}(G))=\emptyset$.

Take joint strategies $s$ and $t$ such that
$p_{\\_}1(s)=p_{\\_}1^{\max}(\Gamma^{k}(G))$ and
$p_{\\_}2(t)=p_{\\_}2^{\max}(\Gamma^{k}(G))$. By Note 5.24 the outcomes
$(p_{\\_}1(s),p_{\\_}2(s))$ and $(p_{\\_}1(t),p_{\\_}2(t))$ are different
since $m>1$.

We have $s_{\\_}2\in\mathit{lose}_{\\_}{2}(\Gamma^{k}(G))$ and
$t_{\\_}1\in\mathit{lose}_{\\_}{1}(\Gamma^{k}(G))$. Hence by Lemma 5.29 for no
joint strategy $s^{\prime}$ in $\Gamma^{k+2}(G)$ we have
$p_{\\_}1(s^{\prime})=p_{\\_}1^{\max}(\Gamma^{k}(G))$ or
$p_{\\_}2(s^{\prime})=p_{\\_}2^{\max}(\Gamma^{k}(G))$.

So $\Gamma(G^{k+2})$ has at most $m-2$ outcomes. By the induction hypothesis
$\Gamma(G^{k+m-1})$ is a trivial game.

We now show that Theorem 5.30 holds for a large class of natural games. Call
an extensive game _almost constant_ if for all but finitely many leaves the
outcome is the same. Note that every almost constant game has finitely many
outcomes, but the converse does not hold. Indeed, it suffices to take a game
with two outcomes, each associated with infinitely many leaves. The following
general result holds.

######  Theorem 5.32.

Every almost constant extensive game is WD-admissible.

######  Proof 5.33.

We begin with two unrelated observations. Call a function $p:A\to B$ _almost
constant_ if for some $b$ we have $p(a)=b$ for all but finitely many $a\in A$.

_Observation 1._ Consider two sequences of some elements
$(v_{\\_}0,v_{\\_}1,\mbox{$\ldots$})$ and
$(w_{\\_}0,w_{\\_}1,\mbox{$\ldots$})$ such that $v_{\\_}j\neq v_{\\_}k$,
$v_{\\_}j\neq w_{\\_}k$, and $w_{\\_}j\neq w_{\\_}k$ for all $j\geq 0$ and
$k>j$, and a function
$p:\\{v_{\\_}0,v_{\\_}1,\mbox{$\ldots$}\\}\cup\\{w_{\\_}0,w_{\\_}1,\mbox{$\ldots$}\\}\to
B$ such that $p(v_{\\_}j)\neq p(w_{\\_}j)$ for all $j\geq 0$. Then $p$ is not
almost constant.

Indeed, otherwise for some $k\geq 0$ the function
$p:\\{v_{\\_}{k},v_{\\_}{k+1},\mbox{$\ldots$}\\}\cup\\{w_{\\_}{k},w_{\\_}{k+1},\mbox{$\ldots$}\\}\to
B$ would be constant.

_Observation 2._ Take an extensive game. For some player $i$, consider two
joint strategies $(s_{\\_}i,s_{\\_}{-i})$ and
$(s_{\\_}i^{\prime},s^{\prime}_{\\_}{-i})$. If
$\mathit{leaf}(s_{\\_}i,s_{\\_}{-i})=\mathit{leaf}(s^{\prime}_{\\_}i,s^{\prime}_{\\_}{-i})$
then
$\mathit{leaf}(s_{\\_}i,s_{\\_}{-i})=\mathit{leaf}(s^{\prime}_{\\_}i,s_{\\_}{-i})$.

Indeed, consider any node $w$ in $\mathit{play}(s_{\\_}i,s_{\\_}{-i})$ such
that $\mathit{turn}(w)=i$. Then by assumption
$s_{\\_}i(w)=s^{\prime}_{\\_}i(w)$. This implies that
$\mathit{play}(s_{\\_}i,s_{\\_}{-i})=\mathit{play}(s^{\prime}_{\\_}i,s_{\\_}{-i})$,
which yields the claim.

Now consider an almost constant extensive game $G$. Take an arbitrary subgame
$H$ of $\Gamma(G)$. Suppose by contradiction that for some player $i$ there
exists an infinite sequence of strategies
$s_{\\_}i^{0},s_{\\_}i^{1},s_{\\_}i^{2},\ldots$ such that for all $j\geq 0$,
$s_{\\_}i^{j+1}$ weakly dominates $s_{\\_}i^{j}$ in $H$. By definition of weak
dominance, for all $j\geq 0$ there exists $s^{j}_{\\_}{-i}\in H_{\\_}{-i}$
such that
$p_{\\_}i(s_{\\_}i^{j},s_{\\_}{-i}^{j})<p_{\\_}i(s_{\\_}i^{j+1},s_{\\_}{-i}^{j})$.
Let for $j\geq 0$, $v_{\\_}j=\mathit{leaf}(s_{\\_}i^{j},s_{\\_}{-i}^{j})$ and
$w_{\\_}j=\mathit{leaf}(s_{\\_}i^{j+1},s_{\\_}{-i}^{j})$. By the above
inequalities $p_{\\_}i(v_{\\_}j)\neq p_{\\_}i(w_{\\_}j)$ for all $j\geq 0$.

We now argue that $v_{\\_}j\neq v_{\\_}k$, $v_{\\_}j\neq w_{\\_}k$, and
$w_{\\_}j\neq w_{\\_}k$ for all $j\geq 0$ and $k>j$. First, note that by the
transitivity of the ‘weakly dominates’ relation we have the following.

  * •

$p_{\\_}i(s_{\\_}i^{j},s_{\\_}{-i}^{j})<p_{\\_}i(s_{\\_}i^{j+1},s_{\\_}{-i}^{j})\leq
p_{\\_}i(s_{\\_}i^{k},s_{\\_}{-i}^{j})$,

  * •

$p_{\\_}i(s_{\\_}i^{j},s_{\\_}{-i}^{j})<p_{\\_}i(s_{\\_}i^{j+1},s_{\\_}{-i}^{j})\leq
p_{\\_}i(s_{\\_}i^{k+1},s_{\\_}{-i}^{j})$,

  * •

$p_{\\_}i(s_{\\_}i^{j+1},s_{\\_}{-i}^{k})\leq
p_{\\_}i(s_{\\_}i^{k},s_{\\_}{-i}^{k})<p_{\\_}i(s_{\\_}i^{k+1},s_{\\_}{-i}^{k})$.

This implies in turn,
$\mathit{leaf}(s_{\\_}i^{j},s_{\\_}{-i}^{j})\neq\mathit{leaf}(s_{\\_}i^{k},s_{\\_}{-i}^{j})$,
$\mathit{leaf}(s_{\\_}i^{j},s_{\\_}{-i}^{j})\neq\mathit{leaf}(s_{\\_}i^{k+1},s_{\\_}{-i}^{j})$,
and
$\mathit{leaf}(s_{\\_}i^{j+1},s_{\\_}{-i}^{k})\neq\mathit{leaf}(s_{\\_}i^{k+1},s_{\\_}{-i}^{k})$.
So by Observation 2 we have the following.

  * •

$v_{\\_}j=\mathit{leaf}(s_{\\_}i^{j},s_{\\_}{-i}^{j})\neq\mathit{leaf}(s_{\\_}i^{k},s_{\\_}{-i}^{k})=v_{\\_}k$,

  * •

$v_{\\_}j=\mathit{leaf}(s_{\\_}i^{j},s_{\\_}{-i}^{j})\neq\mathit{leaf}(s_{\\_}i^{k+1},s_{\\_}{-i}^{k})=w_{\\_}k$,

  * •

$w_{\\_}j=\mathit{leaf}(s_{\\_}i^{j+1},s_{\\_}{-i}^{j})\neq\mathit{leaf}(s_{\\_}i^{k+1},s_{\\_}{-i}^{k})=w_{\\_}k$.

By Observation 1, $p_{\\_}i$ is not almost constant, which contradicts the
assumption that $G$ is almost constant. By the transitivity of the ‘weakly
dominates’ relation we conclude that $G$ is WD-admissible.

######  Corollary 5.34.

Let $G$ be an almost constant strictly competitive extensive game with at most
$m$ outcomes. Then $\Gamma^{m-1}(G)$ is a trivial game.

### Acknowledgments

We thank the reviewers for their helpful comments. The second author was
partially supported by the grant CRG/2022/006140.

## References

  * [1]
  * [2] K.R. Apt (2004): _Uniform Proofs of Order Independence for Various Strategy Elimination Procedures_.  The B.E. Journal of Theoretical Economics 4(1), 10.2202/1534-5971.1141.  Available at https://arxiv.org/abs/cs/0403024.  Article 5, 48 pages.
  * [3] K.R. Apt & S. Simon (2021): _A tutorial for computer scientists on finite extensive games with perfect information_.  Bulletin of the EATCS 135\.  Available at https://arxiv.org/abs/2204.08740.  40 pages.
  * [4] K.R. Apt & S. Simon (2021): _Well-founded extensive games with perfect information_.  In: Proceedings 18th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2021, 335, Electronic Proceedings in Theoretical Computer Science (EPTCS), pp. 7–21, 10.4204/EPTCS.335.2.
  * [5] P. Battigalli (1997): _On rationalizability in extensive games_.  Journal of Economic Theory 74, pp. 40–61, 10.1006/jeth.1996.2252.
  * [6] B.D. Bernheim (1984): _Rationalizable Strategic Behavior_.  Econometrica 52(4), pp. 1007–1028, 10.2307/1911196.
  * [7] C. Ewerhart (2002): _Iterated Weak Dominance in Strictly Competitive Games of Perfect Information_.  Journal of Economic Theory 107(2), pp. 474–482, 10.1006/jeth.2001.2958.
  * [8] A. Heifetz (2012): _Game Theory: Interactive Strategies in Economics and Management_.  Cambridge University Press, 10.1017/CBO9781139049344.
  * [9] P. Hummel (2008): _Iterative elimination of weakly dominated strategies in binary voting agendas with sequential voting_.  Social Choice and Welfare 31(2), pp. 257–269, 10.1007/s00355-007-0278-4.
  * [10] B. L. Lipman (1994): _A Note on the Implications of Common Knowledge of Rationality_.  Games and Economic Behavior 6, pp. 114–129, 10.1006/game.1994.1006.
  * [11] L.M. Marx & J.M. Swinkels (1997): _Order Independence for Iterated Weak Dominance_.  Games and Economic Behaviour 18, pp. 219–245, 10.1006/game.1997.0525.
  * [12] M.J. Osborne & A. Rubinstein (1994): _A Course in Game Theory_.  The MIT Press.
  * [13] D.G. Pearce (1984): _Rationalizable Strategic Behavior and the Problem of Perfection_.  Econometrica 52(4), pp. 1029–1050, 10.2307/1911197.
  * [14] A. Perea (2014): _Belief in the opponents’ future rationality_.  Games and Economic Behaviour 83, pp. 231–254, 10.1016/j.geb.2013.11.008.
  * [15] K. Ritzberger (2001): _Foundations of Non-cooperative Game Theory_.  Oxford University Press, Oxford, UK.
  * [16] R. Rosenthal (1981): _Games of perfect information, predatory pricing and the chain-store paradox_.  Journal of Economic Theory 25(1), pp. 92–100, 10.1016/0022-0531(81)90018-1.
  * [17] J. Sobel (2019): _Iterated weak dominance and interval-dominance supermodular games_.  Theoretical Economics 14(1), pp. 71–102, 10.3982/TE2904.
  * [18] L.P. Østerdal (2005): _Iterated weak dominance and subgame dominance_.  Journal of Mathematical Economics 41(6), pp. 637–645, 10.1016/j.jmateco.2003.11.013.