Well-Founded Extensive Games with Perfect Information

Research on strategic games assumes that players have to their disposal infinitely many strategies. This allows one to view strategic games with mixed strategies as customary strategic games with infinitely many strategies. This assumption is also used in a study of various standard examples, such as Cournot or Bertrand competition, in which the players have to set the production level or the price of a product.

In contrast, the exposition of the standard results for the extensive games with perfect information (from now, just ‘extensive games’) is usually limited to finite games. This restriction rules out a study of various natural examples, for example infinite variants of the ultimatum game or some bargaining games, see, e.g., [17]. In the first case the game has just two stages but the first player may have infinitely many actions to choose from, while in the second case the game has an arbitrary, though finite, number of stages. Such games are then analyzed separately, without taking into account general results.

The aim of this paper is to provide a systematic account of extensive games with perfect information in a setting that only requires that the underlying game tree is well-founded (i.e., has no infinite paths). We call such games well-founded¹¹1Such games are sometimes called games with finite horizon (see, e.g., [16]). We decided to use instead the qualification ‘well-founded’ because ‘finite horizon’ is sometimes used to indicate that the game tree is of bounded depth, i.e, has a finite rank (a concept introduced in the next section)..

The standard tool to analyze finite extensive games is the concept of a subgame perfect equilibrium. Their existence is established by means of the backward induction algorithm. In infinite well-founded extensive games subgame perfect equilibria may fail to exist. Also one cannot resort to any version of this algorithm since it will not terminate. In principle this could be taken care of by defining a joint strategy as an eventual outcome of an infinite computation. However, for arbitrary well-founded games one would have then to proceed by means of a transfinite induction, which raises a legitimate question whether such a process can be called a computation.

Therefore, instead of trying to define such generalized computations we dispense with the backward induction altogether and simply proceed by transfinite induction. This results in mathematical proofs of existence that are not supported by any algorithm, but still, as illustrated by examples, the obtained results can be used to compute the sets of subgame perfect equilibria in specific well-founded games and to deduce their existence in special cases. Informally, transfinite induction analyzes the game tree ‘top down’, while the backward induction proceeds ’bottom up’ and consequently cannot be naturally applied to infinite game trees.

Most results, though not all, are natural generalizations of the corresponding results for the case of finite extensive games. Some of these results fail to hold for infinite games and some of the traditional proofs for finite games, notably the ones involving the backward induction, have to be suitably modified. In what follows we focus both on arbitrary well-founded games and on two-player zero-sum games with, respectively, two and three outcomes.

In the literature we found only one paper in which well-founded games appear, namely [6]. The authors provide using higher-order computability theory a formula that defines the set of subgame perfect equilibria under an assumption that implies their existence, and apply it to determine a subgame perfect equilibrium in an infinite three stage game. In several books various examples of infinite extensive games are studied and various extensions of finite extensive games, for example games with chance moves, see, e.g., [17], simultaneous moves, see, e.g., [16], or repeated extensive games, see [14], are introduced (not to mention games with imperfect information). Also subgame perfect equilibria in games allowing infinite plays have been studied, see, e.g., [9] and a more recent [11]. In [2] a maximally general definition of an extensive form game is proposed that among others covers repeated games, differential games, and stochastic games. In the proposed framework even immediate predecessors of an action may not exist (like in continuous time interactive decisions examples). In our opinion the class of games considered here merits attention as a first natural generalization to study.

In the next section we introduce the relevant concepts and provide natural examples of well-founded extensive games. In Section 3 we establish existence of subgame perfect equilibria for some natural classes of well-founded games and show how to apply a characterization result to compute the set of subgame perfect equilibria for specific example games. Then, in Section 4 we consider two classes of two-player well-founded games: win or lose games and chess-like games. As a stepping stone towards characterizations of the sets of subgame perfect equilibria in these games we show that the well-known result attributed to Zermelo [24] (see also [20]) about existence of winning strategies continues to hold for well-founded games.

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. In drawings the edges will be directed downwards.

An extensive game with perfect information (in short, just an extensive game) for $n\geq 1$ players consists of:

• •

  a set of players $\{1,\mbox{$\ldots$},n\}$,

• •

  a game tree, which is a tree $T:=(V,E)$ with a turn function $turn:V\setminus Z\to\{1,\mbox{$\ldots$},n\}$, where $Z$ is the set of leaves of $T$,

• •

  the payoff functions $p_{\_}i:Z\mbox{$\>\rightarrow\>$}\mathbb{R}$, for each player $i$.

We denote it by $(T,turn,p_{\_}1,\mbox{$\ldots$},p_{\_}n)$.

The function $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 $turn(v)$ at $v$. For a node $u$ in $T$ let $T^{u}$ denote the subtree of $T$ rooted at $u$.

We say that an extensive game is finite, finite depth, infinite, or well-founded if, respectively, its game tree is finite, finite depth, infinite, or well-founded. Recall that a tree is called well-founded if it has no infinite paths (see, e.g., [22, page 224]).

Further, following [3], we say that an extensive game is without relevant ties if for all non-leaf nodes $u$ in $T$ the function $p_{\_}i$, where $\mathit{turn}(u)=i$, is injective on the leaves of $T^{u}$. This is more general than saying that a game is generic, which means that each $p_{\_}i$ is an injective function.

We shall often rely on the concept of a rank of a well-founded tree $T$. Recall that it is defined inductively as follows, where $v$ is the root of $T$:

where $sup(X)$ denotes the least ordinal larger than all ordinals in the set $X$. Transfinite induction will be needed only to deal with games on the trees with rank $>\omega$.

In the figures below we identify the actions with the labels we put on the edges and thus identify each action with the corresponding move. For convenience we do not assume the labels to be unique, but it will not lead to confusion. Further, we annotate the non-leaf nodes with the identity of the player whose turn it is to move and the name of the node. Finally, we annotate each leaf node with the corresponding sequence of the values of the $p_{\_}i$ functions.

Below, given a two-player extensive game we denote the opponent of player $i$ by $-i$ instead of $3-i$.

The class of endogenous games studied in [10] form another example of well-founded extensive games. These games are played in two stages. In the first stage the players are involved in pre-play negotiations that essentially fix the payoff functions and in the second stage they choose their strategies. The resulting game is infinite due to the pre-play negotiations, while the rank of the game tree is 2.

Note that by König’s lemma [12] every finitely branching well-founded extensive games is finite. Consequently, interesting well-founded extensive games necessarily have infinite branching.

For an extensive game $G:=(T,turn,p_{\_}1,\mbox{$\ldots$},p_{\_}n)$ let $V_{\_}i:=\{v\in V\setminus Z\mid 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$. We call each element $s\in S$ a joint strategy, denote the $i$th element of $s$ 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 $i$’s strategy is $s^{\prime}_{\_}i$ and for all $j\neq i$, player $j$’s strategy is $s_{\_}j$. Occasionally we write $(s_{\_}i,s_{\_}{-i})$ instead of $s$. Finally, we abbreviate the Cartesian product $\times_{\_}{j\neq i}S_{\_}j$ to $S_{\_}{-i}$. So 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 of these functions. Each joint strategy assigns a unique descendant to every node in $V\setminus Z$. In fact, we can identify joint strategies with such assignments.

From now on the above notation will be used in the context of any considered extensive game $G$. In particular $S_{\_}i$ will always denote the set of strategies of player $i$.

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$,

• •

  if $v_{\_}{k}\not\in Z$, then $v_{\_}{k+1}:=s_{\_}i(v_{\_}k)$, where $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.

Suppose now that the extensive game is well-founded. Then for each joint strategy $s$ the rooted path $\mathit{play}(s)$ is finite. Denote by $\mathit{leaf}(s)$ the last element of $\mathit{play}(s)$. We call $(p_{\_}1(leaf(s)),\mbox{$\ldots$},p_{\_}n(leaf(s)))$ the outcome of the game $G$ when each player $i$ pursues his strategy $s_{\_}i$ and abbreviate it as $p(leaf(s))$. We call two joint strategies $s$ and $t$ payoff equivalent if $p(leaf(s))=p(leaf(t))$.

We say that a strategy $s_{\_}i$ of player $i$ a best response to a joint strategy $s_{\_}{-i}$ of his opponents if for all $s^{\prime}_{\_}i\in S_{\_}i$, $p_{\_}i(leaf(s))\geq p_{\_}i(leaf(s^{\prime}_{\_}i,s_{\_}{-i}))$. Next, we call a joint strategy $s$ a Nash equilibrium if each $s_{\_}i$ is a best response to $s_{\_}{-i}$, that is, if

Finally, we recall the notion of a subgame perfect equilibrium due to Selten [21](see also section 6.2 in [16]), though now defined for the larger class of well-founded games.

The subgame of $G$ rooted at the node $w$, denoted by $G^{w}$, is defined as follows:

• •

  its set of players is $\{1,\mbox{$\ldots$},n\}$,

• •

  its tree is $T^{w}$,

• •

  its turn and payoff functions are the restrictions of the corresponding functions of $G$ to the nodes of $T^{w}$.

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.

Suppose now the extensive game $G$ is well-founded. Then the notion of a Nash equilibrium is well-defined. 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 $G^{w}$. Informally $s$ is subgame perfect equilibrium in $G$ if it induces a Nash equilibrium in every subgame of $G$.

An analysis of the subgame perfect equilibria in the games from Examples 2.2 and 2.3 is more involved and will be provided in the next section using a characterization of the set of subgame perfect equilibria of a well-founded extensive game.

In general subgame perfect equilibria may not exist in well-founded games. As an example take the modification of the Ultimatum game from Example 2.1 in which instead of $[0,100]$ one considers the open interval $(0,100)$. In this section we establish existence of subgame perfect equilibria in some natural classes of well-founded games. This will directly follow from a characterization of the sets of subgame perfect equilibria in such games.

We begin by stating a preparatory lemma, called the ‘one deviation property’ in [16]. To keep the paper self-contained we include in the Appendix the proof. It is more detailed than the one given in [16].

Intuitively, the first condition states that among the subgames rooted at the children of the root $v$, the one determined by the first move in the game $G$ yields the maximal outcome for the player who moved. Recall that for a function $f:X\to Y$ (with $X$ non-empty), $\mathrm{argmax}_{\_}{x\in X}f(x):=\{y\in X\mid f(y)=\max_{\_}{x\in X}f(x)\}$. Using this notation this condition can be reformulated as: $s_{\_}i(v)\in\mathrm{argmax}_{\_}{u\in C(v)}p_{\_}i(\mathit{leaf}(s^{u}))$, where $i=\mathit{turn}(v)$.

The above corollary allows us to characterize inductively the set of subgame perfect equilibria in each well-founded extensive game.

Consider a well-founded extensive game $G$ with the root $v$ and suppose $C(v)\neq\emptyset$. Consider the subgames $G^{w}$, where $w\in C(v)$, and a function $f$ that assigns to each sequence $t$ of joint strategies in these subgames a child of $v$. Then each pair of $t$ and $f$ determines a joint strategy in $G$ that we denote by $(f,t)$.

Recall that by $S^{w}$ we denote the set of joint strategies in the subgame $G^{w}$. Given subsets $U^{w}$ of $S^{w}$ for $w\in C(v)$ and a set of functions $F$ from $\times_{\_}{w\in C(v)}U^{w}$ to $C(v)$, we denote by $[F,\times_{\_}{w\in C(v)}U^{w}]$ the set of joint strategies in $G$ defined by

In the first case $(\mbox{$\emptyset$},\mbox{$\ldots$},\mbox{$\emptyset$})$ stands for the joint strategy that consists of the $n$-tuple of the empty strategies. Note that when $C(v)\neq\emptyset$ if any of the sets $U^{w}$ or $F$ is empty, then so is $[F,\times_{\_}{w\in C(v)}U^{w}]$. Further, we denote the set of subgame perfect equilibria in $G$ by $\mathit{SPE}(G)$.

In particular, if the set $\mathrm{argmax}_{\_}{w\in C(v)}p_{\_}i(\mathit{leaf}(t^{w}))$ is empty, then $F=\mbox{$\emptyset$}$ and hence $\mathit{SPE}(G)=\mbox{$\emptyset$}$. Intuitively, each function $f\in F$, given a sequence of subgame perfect equilibria in the subgames rooted at the children of the root $v$, selects a root of the subgame in which the outcome in the equilibrium is maximal for the player who moves at $v$.

If $C(v)\neq\emptyset$, then by Corollary 3.7 every subgame perfect equilibrium in the game $G$ is of the form $(f,t)$, where for all $w\in C(v)$, $t^{w}$ is a subgame perfect equilibrium in $G^{w}$ and for some $w\in C(v)$ we have $f(t)=w$ and $p_{\_}i(\mathit{leaf}(s^{w}))\geq p_{\_}i(\mathit{leaf}(s^{u}))$ for all $u\in C(v)$. $\Box$

The above result can be generalized to some games with infinitely many outcomes. An example is a game in which for each player the set of outcomes is either finite or equals the set of negative integers. More generally, consider a well-founded extensive game in which for each player the set of outcomes is a reverse well-ordered set, i.e., every subset of this set has a greatest element. Then Theorem 3.9 implies that the game has a subgame perfect equilibrium.

In particular, every generic well-founded extensive game with finitely many outcomes has a unique subgame perfect equilibrium. We now show how Theorem 3.9 can be used to reason about subgame perfect equilibria in specific extensive games.

Next, we establish a result showing that for a class of well-founded extensive games all subgame perfect equilibria are payoff equivalent. The following condition was introduced in [18]:

This condition is in particular satisfied by the two-player well-founded extensive games that are strictly competitive, which means that

(To see it transpose $i$ and $-i$ and conjoin both equivalences.)

For finite extensive games this result was stated in [16, page 100] as Exercise 100.2. The most natural proof makes use of the backward induction. For infinite games a different proof is needed.

We say that a well-founded extensive game $(T,turn,p_{\_}1,\mbox{$\ldots$},p_{\_}n)$ satisfies the transference of decisionmaker indifference (TDI) condition if: $\mbox{$\forall$}i\in\{1,\ldots,n\}\>\mbox{$\forall$}r_{\_}i,t_{\_}i\in S_{\_}i\>\mbox{$\forall$}s_{\_}{-i}\in S_{\_}{-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.

Clearly, condition (1) implies the TDI condition. The TDI condition was introduced in [15], the results of which imply that in every finite extensive game with perfect information that satisfies the TDI condition all subgame perfect equilibria are payoff equivalent. We conjecture that this result extends to well-founded extensive games.

In this section we characterize subgame perfect equilibria of two-player zero-sum well-founded extensive games with, respectively, two and three outcomes. By Corollary 3.10 each of these games has a subgame perfect equilibrium. Below we consider the outcomes $(1,-1)$, $(0,0)$, and $(-1,1)$, but the obtained results hold with the same proofs for arbitrary outcomes as long as the game remains zero-sum.

A two-player extensive game is called a win or lose game if the only possible outcomes are $(1,-1)$ and $(-1,1)$, with 1 associated with winning and 0 with losing. Given a well-founded win or lose game $G$ we call a strategy $s_{\_}i$ of player $i$ a winning strategy if $\mbox{$\forall$}s_{\_}{-i}\in S_{\_}{-i}\ p_{\_}i(\mathit{leaf}(s_{\_}i,s_{\_}{-i}))=1$. Below we denote the (possibly empty) set of winning strategies of player $i$ in $G$ by $\mathit{win}_{\_}i(G)$.

A classic result, attributed to Zermelo [24], implies that in finite win or lose games one of the players has a winning strategy. This result also holds for arbitrary well-founded games.

From Corollary 3.10 we know that every well-founded win or lose game has a subgame perfect equilibrium, thus in particular a Nash equilibrium. The following result clarifies the relation between Nash equilibria and winning strategies. We denote the set of Nash equilibria in an extensive game $G$ by $\mathit{NE}(G)$.