Rational Play in Extensive-Form Games

By inergency On Mar 26, 2024

[ad_1]

There are two types of epistemic/doxastic models used in the game-theoretic literature: the so-called “state-space” models and the “type-space” models. We will adopt the former (note that there is a straightforward way of translating one type of model into the other). In the standard state-space model of a given game, one takes as starting point a set of states (or possible worlds) and associates with every state a strategy for every player, thus providing an interpretation of a state in terms of players’ choices. If

ω

is a state and

s_{i}

is the strategy of player i at

ω

then the interpretation is that, at that state, player i plays

s_{i}

. If the game is simultaneous (so that there cannot be any unreached information sets), then there is no ambiguity in the expression “player i plays

s_{i}

”, but if the game is an extensive-form game then the expression is ambiguous. Consider, for example, the game of Figure 1 and a state

ω

where Players 1 and 2 play

a a

, so that Player 3’s information set is not reached; suppose also that the strategy of Player 3 associated with state

ω

is d. In what sense does Player 3 “play” d? Does it mean that, before the game starts, Player 3 has made a plan to play d if her information happens to be reached? Or does it mean (in a Stalnaker-Lewis interpretation of the counterfactual) that in the state most similar to

ω

where her information set is actually reached, Player 3 plays d? [This interpretation is adopted in [22] where it is pointed out that in this type of models “one possible culprit for the confusion in the literature regarding what is required to force the backward induction solution in games of perfect information is the notion of a strategy”.] Or is Player 3’s strategy d to be interpreted not as a statement about what Player 3 would do but as an expression of what the opponents think that Player 3 would do?

While most of the literature on the epistemic foundations of game theory makes use of strategy-based models, a few papers follow a behavioral approach by associating with each state a play (or outcome) of the game (the seminal contribution is [23], followed by [1,8,24,25]; the focus of this literature has been on games with perfect information). The challenge in this class of models is to capture the reasoning of a player who takes a particular action while considering what would happen if she took a different action. The most common approach is to postulate, for each player, a set of conditional beliefs, where the conditioning events are represented by possible histories in the game, including off-path histories ([23] uses extended information structures to model hypothetical knowledge, [8] use plausibility relations and [24] use conditional probability systems). Here we follow the simpler approach put forward in [1], which models the “pre-choice” beliefs of a player, while the previous literature considered the “after-choice” beliefs. The previous literature was based on the assumption that, if at a state a player takes action a, then she knows that she takes action a, that is, in all the states that she considers possible she takes action a. The pre-choice or deliberation stage approach, on the other hand, models the beliefs of the player at the time when she is contemplating the actions available to her and treats each of those actions as an “open possibility”. Thus, her beliefs take the following form: “if I take action a then the outcome will be x and if I take action b then the outcome will be y”, where the conditional “if p then q” is interpreted as a material conditional, that is, as equivalent to “either not p or q” (in [26] it is argued that, contrary to a common view, the material conditional is indeed sufficient to model deliberation; it is also shown how to convert pre-choice beliefs into after-choice beliefs, reflecting a later stage at which the agent has made up her mind on what to do). This analysis does not rely in any way on counterfactuals; furthermore, only the beliefs of the active players at the time of choice are modeled, so that no initial beliefs nor belief revision policies are postulated. The approach is described below and it makes use of the history-based definition of extensive-form game, which is reviewed in Appendix A.

3.1. Qualitative Beliefs

Let $Ω$ be a set, whose elements are called states (or possible worlds). We represent the beliefs of an agent by means of a binary relation $B \subseteq Ω \times Ω$ . The interpretation of $(ω, ω^{'}) \in B$ , also denoted by $ω B ω^{'}$ , is that at state $ω$ the agent considers state $ω^{'}$ possible; we also say that $ω^{'}$ is reachable from $ω$ by $B$ . For every $ω \in Ω$ we denote by $B (ω)$ the set of states that are reachable from $ω$ , that is, $B (ω) = {ω^{'} \in Ω : ω B ω^{'}}$ .

B

is transitive if

ω^{'} \in B (ω)

implies

B (ω^{'}) \subseteq B (ω)

and it is euclidean if

ω^{'} \in B (ω)

implies

B (ω) \subseteq B (ω^{'})

(it is well known that transitivity of

B

corresponds to positive introspection of beliefs: if the agent believes an event

E

then she believes that she believes

E

, and euclideanness corresponds to negative introspection: if the agent does not believe

E

then she believes that she does not believe

E

). We will assume throughout that the belief relations are transitive and euclidean so that

ω^{'} \in B (ω)

implies that

B (ω^{'}) = B (ω)

. Note that we do not assume reflexivity of

B

(that is, we do not assume that, for every state

ω

ω \in B (ω)

; reflexivity corresponds to the assumption that a player cannot have incorrect beliefs: an assumption that, as [27] points out, is conceptually problematic, especially in a multi-agent context). Hence, in general, the relation

B

does not induce a partition of the set of states.

Graphically, we represent a transitive and euclidean belief relation as shown in Figure 4, where

ω^{'} \in B (ω)

if and only if either there is an arrow from

ω

to the rounded rectangle containing

ω^{'}

, or

ω

and

ω^{'}

are enclosed in the same rounded rectangle (that is, if there is an arrow from state

ω

to a rounded rectangle, then, for every

ω^{'}

in that rectangle,

(ω, ω^{'}) \in B

and, for any two states

ω

and

ω^{'}

that are enclosed in a rounded rectangle,

{(ω, ω), (ω, ω^{'}), (ω^{'}, ω), (ω^{'}, ω^{'})} \subseteq B

The object of beliefs are propositions or events (i.e., sets of states; events are denoted by bold-type capital letters). We say that at state ω the agent believes event

E \subseteq Ω

if and only if

B (ω) \subseteq E

. For example, in the case illustrated in Figure 4, at state

α

the agent believes event

{β, γ}

. We say that, at state ω, event

E

is true if

ω \in E

. In the case illustrated in Figure 4, at state

α

the agent erroneously believes event

{β, γ}

, since event

{β, γ}

is not true at

α

(

α \notin B (α) = {β, γ}

). We say that at state ω the agent has correct beliefs if

ω \in B (ω)

(note that it is a consequence of euclideanness of the relation

B

that, even if the agent’s beliefs are objectively incorrect, she always believes that what she believes is true: if

ω^{'} \in B (ω)

then

ω^{'} \in B (ω^{'})

3.2. Models of Games

As a starting point in the definition of a model of a game, we take a set of states

Ω

and provide an interpretation of each state in terms of a particular play of the game, by means of a function

ζ : Ω \to Z

that associates, with every state

ω

, a play or terminal history

ζ (ω) \in Z

. Each state

ω

also provides a description of the beliefs of the active players by means of a binary relation

B_{h}

Ω

representing the beliefs of

ι (h)

, the player who moves at decision history h. It would be more precise to write

B_{ι (h)}

instead of

B_{h}

, but we have chosen the lighter notation since there is no ambiguity, because we assume (see Appendix A) that at every decision history there is a unique player who is active there. Note that beliefs are specified only at histories that are reached at a given state, in the sense that

B_{h} (ω) \neq ⌀

if and only if

h ≺ ζ (ω)

Definition 1.

A model of an extensive-form game is a tuple $〈Ω, ζ, {\{B_{h}\}}_{h \in D}〉$ where

Ω is a set of states.
$ζ : Ω \to Z$ is an assignment of a terminal history to each state.
For every $h \in D$ , $B_{h} \subseteq Ω \times Ω$ is a belief relation that satisfies the following properties:

1.

$B_{h} (ω) \neq ⌀$ if and only if $h ≺ ζ (ω)$ [beliefs are specified only at reached decision histories and are consistent: consistency means that there is no event $E$ such that both $E$ and its complement $\neg E$ are believed; it is well known that, at state ω, beliefs are consistent if and only if $B (ω) \neq ⌀$ ].

2.

If $ω^{'} \in B_{h} (ω)$ then $h^{'} ≺ ζ (ω^{'})$ for some $h^{'}$ such that $h^{'} \approx_{ι (h)} h$ [the active player at history h correctly believes that her information set that contains h has been reached; recall (see Appendix A) that $h^{'} \approx_{ι (h)} h$ (also written as $h^{'} \in [h]$ ) if and only if h and $h^{'}$ belong to the same information set of player $ι (h)$ (thus $ι (h) = ι (h^{'}))$ ].

3.

If $ω^{'} \in B_{h} (ω)$ then (1) $B_{h} (ω^{'}) = B_{h} (ω)$ and (2) if $h^{'} ≺ ζ (ω^{'})$ with $h^{'} \approx_{ι (h)} h$ then $B_{h^{'}} (ω^{'}) = B_{h} (ω)$ [by (1), beliefs satisfy positive and negative introspection and, by (2), beliefs are the same at any two histories in the same information set; thus one can unambiguously refer to a player’s beliefs at an information set, which is what we do in Figures 5–9].

4.

If $ω^{'} \in B_{h} (ω)$ and $h^{'} ≺ ζ (ω^{'})$ with $h^{'} \approx_{ι (h)} h$ , then, for every action $a \in A (h)$ (note that $A (h^{'}) = A (h)$ ), there is an $ω^{″} \in B_{h} (ω)$ such that $h^{'} a ≾ ζ (ω^{″})$ .

The last condition states that if, at state $ω$ and history h reached at $ω$ ( $h ≺ ζ (ω)$ ), player $ι (h)$ considers it possible that the play of the game has reached history $h^{'}$ , which belongs to her information set that contains h, then, for every action a available at that information set, there is a state $ω^{″}$ that she considers possible at h and $ω$ ( $ω^{″} \in B_{h} (ω)$ ) where she takes action a at history $h^{'}$ ( $h^{'} a ≾ ζ (ω^{″})$ ). This means that, for every available action, the active player at h considers it possible that she takes that action and thus has a belief about what will happen conditional on taking it. A further “natural” restriction on beliefs will be discussed later (Definition 6).

Figure 5 reproduces the game of Figure 1 and shows a model of it. For every reached decision history, under every state that the corresponding player considers possible we have shown the action actually taken by that player and the player’s payoff (at the terminal history associated with that state).

Suppose, for example, that the actual state is $γ$ . State $γ$ encodes the following facts and beliefs.

1.: As a matter of fact, Player 1 plays a, Player 2 plays b and Player 3 plays d.
2.: Player 1 (who chooses at the null history ⌀) believes that if she plays a then Player 2 will also play a (this belief is erroneous since at state $γ$ Player 2 actually plays b, after Player 1 plays a) and thus her utility will be 2, and she believes that if she plays b then Player 2 will play a and Player 3 will play d and thus her utility will be 1.
3.: Player 2 (who chooses at information set ${a, b}$ ) correctly believes that Player 1 played a and, furthermore, correctly believes that if he plays b then Player 3 will play d and thus his utility will be 1, and believes that if he plays a his utility will be 2.
4.: Player 3 (who chooses at information set ${a b, b a, b b}$ ) erroneously believes that both Player 1 and Player 2 played b; thus, she believes that if she plays c her utility will be 0 and if she plays d her utility will be 1.

On the other hand, if the actual state is $β$ , then the actual play is $a a$ and the beliefs of Players 1 and 2 are as detailed above (Points 2 and 3, respectively), while no beliefs are specified for Player 3, because Player 3 does not get to play (that is, Player 3 is not active at state $β$ since her information set is not reached).

3.4. Correct Beliefs

The notion of correct belief was first mentioned in Section 3.1 and was identified with local reflexivity (that is, reflexivity at a state, rather than global reflexivity). Since, at any state, only the beliefs of the active players are specified, we define the event that players have correct beliefs by restricting attention to those players who actually move. Thus, the event that the active players have correct beliefs, denoted by

T

(‘T’ stands for ‘true’), is defined as follows:

$ω \in T if and only if ω \in B_{h} (ω) for every h such that h ≺ ζ (ω) .$

(2)

For example, in the model of Figure 5, $T = {β}$ .

What does the expression “correct beliefs” mean? Consider state

β

in the model of Figure 5 where the active players (Players 1 and 2) have correct beliefs in the sense of (2) (

β \in B_{⌀} (β)

and

β \in B_{{a, b}} (β)

). Consider Player 1. There are two components to Player 1’s beliefs: (i) she believes that if she plays a then Player 2 will also play a, and (

i i

) she believes that if she plays b then Players 2 and 3 will play a and d, respectively. The first belief is correct at state

β

, where Player 1 plays a and Player 2 indeed follows with a. As for the second belief, whether it is correct or not depends on how we interpret it. If we interpret it as the material conditional “if b then

b a d

” (which is equivalent to “either not b or

b a d

”) then it is indeed true at state

β

, but trivially so, because the antecedent is false there (Player 1 does not play b). If we interpret it as a counterfactual conditional “if Player 1 were to play b then Players 2 and 3 would play a and d, respectively” then in order to decide whether the conditional is true or not one would need to enrich the model by adding a “similarity” or “closeness” relation on the set of states (in the spirit of [3,4]); one would then check if at the closest state(s) to

β

at which Player 1 plays b it is indeed the case that Players 2 and 3 play a and d, respectively. Note that there is no a priori reason to think that the closest state to

β

where Player 1 plays b is state

α

. This is because, as pointed out by Stalnaker ([30], p.48), there is no necessary connection between counterfactuals, which capture causal relations, and beliefs: for example, I may believe that, if I drop the vase that I am holding in my hands, it will break (because I believe it is made of glass) but my belief is wrong because—as a matter of fact—if I were to drop it, it would not break, since it is made of plastic.

Our models do not have the resources to answer the question: “at state $β$ , is it true —as Player 1 believes—that if Player 1 were to play b then Players 2 and 3 would play a and d, respectively?” One could, of course, enrich the models in order to answer the question, but is there a compelling reason to do so? In other words, is it important to be able to answer such questions? If we are merely interested in determining what rational players do, then what matters is what actions they actually take and what they believe when they act, whether or not those beliefs are correct in a stronger sense than is captured by the material conditional.

Is the material conditional interpretation of “if I play a then the outcome will be x” sufficient, though? Since the crucial assumption in the proposed framework is that the agent considers all of her available actions as possible (that is, for every available action there is a doxastically accessible state where she takes that action), material conditionals are indeed sufficient: the material conditional “if I take action a the outcome will be x” zooms in—through the lens of the agent’s beliefs— on those states where action a is indeed taken and verifies that at those states the outcome is indeed x, while the states where action a is not taken are not relevant for the truth of the conditional.

3.5. Self-Confirming Play

We have defined two events: the event

R

that all the active players are rational and the event

T

that all the active players have correct beliefs. In the model of Figure 5 we have that

R \cap T = {β}

and it so happens that

ζ (β) = a a

is a Nash equilibrium play, that is, there is a pure-strategy Nash equilibrium (namely,

(a, a, d)

) whose associated play is

a a

. However, as shown below, this is not always the case.

At a play associated with a state

ω \in R \cap T

, each active player’s chosen action is rationally justified by her beliefs at the time of choice (since

ω \in R

) and the beliefs concerning what will happen after that action turn out to be correct (since

ω \in T

), so that no player is faced with evidence that her beliefs were wrong. Does that mean that, once the final outcome

ζ (ω)

is revealed, no player regrets her actual choice? The answer is negative, because it is possible that a player, while not having any false beliefs, might not anticipate with precision the actions of the players who move after her. In the model shown in Figure 6 we have that

R \cap T = {α, β, γ}

, that is, at every state the active players are rational and have correct beliefs. Consider state

β

, where the play is

a d

. At state

β

Player 1 is rational because she believes that if she plays b her utility will be 1 and if she plays a her utility might be 0 but might also be 2 (she is uncertain about what Player 2 will do). Thus, she does not believe that action b is better than a and hence it is rational for her to play a (Definition 2). Player 2 is rational because she is indifferent between her two actions. However, ex post, when Player 1 learns that the actual outcome is

a d

, she regrets not taking action b instead of a. This example shows that, even though

β \in R \cap T

ζ (β) = a d

is not a Nash equilibrium play, that is, there is no Nash equilibrium whose associated play is

a d

Next we introduce another event which, in conjunction with

T

, guarantees that the active players’ beliefs about the opponents’ actual moves are exactly correct (note that a requirement built in the definition of a self-fulfilling equilibrium ([13], p.523) is that “each player’s beliefs about the opponents’ play are exactly correct”). Event

C

(’C’ for ’certainty’) defined below rules out uncertainty about the opponents’ past choices (Point 1) as well as uncertainty about the opponents’ future choices (Point 2). Note that Point 1 is automatically satisfied in games with perfect information and thus imposes restrictions on beliefs only in imperfect-information games.

Definition 3.

A state ω belongs to event $C$ if and only if, for every reached history h at ω (that is, for every $h ≺ ζ (ω))$ , and $\forall ω^{'}, ω^{″} \in B_{h} (ω)$ , $\forall h^{'}, h^{″} \in [h]$ (recall that $[h]$ is the information set that contains h),

1.: if $h^{'} ≺ ζ (ω^{'})$ and $h^{″} ≺ ζ (ω^{″})$ then $h^{'} = h^{″}$ ,
2.: $\forall a \in A (h)$ , if $h^{'} a ≺ ζ (ω^{'})$ and $h^{″} a ≺ ζ (ω^{″})$ then $ζ (ω^{'}) = ζ (ω^{″})$ .

Note that—concerning Point 1—a player may be erroneous in her certainty about the opponents’ past choices, that is, it may be that

ω \in C

, the actual reached history is

h ≺ ζ (ω)

and yet player

ι (h)

is certain that she is moving at history

h^{'} \in [h]

with

h^{'} \neq h

(for example, in the model of Figure 5, at state

γ

, which belongs to event

C

, and at reached history

a b

, Player 3 is certain that she is moving at history

b b

while, as a matter of fact, she is moving at history

a b

), and—concerning Point 2— a player may also be erroneous in her certainty about what will happen after her choice (for example, in the model of Figure 5, at state

γ

and history ⌀, Player 1 is certain that if she takes action a then Player 2 will also play a, but she is wrong about this, because, as a matter of fact, at state

γ

Player 2 follows with b rather than a).

In the model of Figure 5

C = Ω

, while in the model of Figure 6

C = ⌀

, because at the null history ⌀ Player 1 is uncertain about what will happen if she takes action a.

If state

ω

belongs to the intersection of events

C

and

T

then, at state

ω

, each active player’s beliefs about the opponents’ actual play are exactly correct. Note, however, that—as noted in Section 3.4—there is no way of telling whether or not a player is also correct about what would happen after her counterfactual choices, because the models that we are considering are not rich enough to address the issue of counterfactuals.

Definition 4.

Let G be a game and z a play (or terminal history) in G. We say that z is a self-confirming play if there exists a model of G and a state ω in that model such that (1) $ω \in R \cap T \cap C$ and (2) $z = ζ (ω)$ .

Definition 5.

Given a game G and a play z in G, call z a Nash play if there is a pure-strategy Nash equilibrium whose induced play is z.

It turns out that, in perfect-information games in which no player moves more than once along any play, the two notions of self-confirming play and Nash play are equivalent ([1], Proposition 1, p. 1012). For games with imperfect information, while it is still true that a Nash play is a self-confirming play, there may be self-confirming plays that are not Nash plays. The reason for this is that two players might have different beliefs about the potential choice of a third player. Figure 7 reproduces the game of Figure 3 together with a model of it.

In the model of Figure 7,

R = {γ}

T = {β, γ}

and

C = Ω

, so that

R \cap T \cap C = {γ}

. Thus, at state

γ

the active players (Players 1 and 2) are rational, have correct beliefs and have no uncertainty and yet

ζ (γ) = a A

which is not a Nash play (there is no Nash equilibrium that yields the play

a A

). Players 1 and 2 have different beliefs about what Player 3 would do at her information set: at state

γ

Player 1 believes that if she plays d then Player 3 will play L, while Player 2 believes that if he plays D then Player 3 will play R.

Next we introduce a new event, denoted by $A$ (‘A’ stands for ‘agreement’), that rules out such disagreement and use it to provide a doxastic characterization of Nash play in general games (with possibly imperfect information). First we need to add one more condition to the definition of a model of a game that is relevant only if the game has imperfect information.

The definition of model given in Section 3 (Definition 1) allows for “unreasonable” beliefs that express a causal link between a player’s action and her opponent’s reaction to it, when the latter does not observe the former’s choice. As an illustration of such beliefs, consider a game where Player 1 moves first, choosing between actions a and b, and Player 2 moves second choosing between actions c and d without being informed of Player 1’s choice, that is, histories a and b belong to the same information set of Player 2. Definition 1 allows Player 1 to have the following beliefs: “if I play a, then Player 2 will play c, while if I play b then Player 2 will play d”. Such beliefs ought to be rejected as “irrational” on the grounds that there cannot be a causal link between Player 1’s move and Player 2’s choice, since Player 2 does not get to observe Player 1’s move and thus cannot react differently to Player 1’s choice of a and Player 1’s choice of b. [It should be noted, however, that several authors have argued that such beliefs are not necessarily irrational: see, for example, [31,32,33,34,35,36]. A “causally correct” belief for Player 1 would require that the predicted choice(s) of Player 2 be the same, no matter what action Player 1 herself chooses.

Definition 6.

A causally restricted model of a game is a model (Definition 1) that satisfies the following additional restriction (a verbal interpretation follows; note that, for games with perfect information, there is no difference between a model and a restricted model, since (3) is vacuously satisfied).

5.: Let ω be a state, h a decision history reached at ω ( $h ≺ ζ (ω)$ ) and a and b two actions available at h ( $a, b \in A (h)$ ). Let $h_{1}$ and $h_{2}$ be two decision histories that belong to the same information set of player $j = ι (h_{1})$ ( $h_{1} \approx_{j} h_{2}$ ) and $c_{1}, c_{2}$ be two actions available at $h_{1}$ ( $c_{1}, c_{2} \in A (h_{1}) = A (h_{2})$ ). Then the following holds (recall that $[h]$ denotes the information set that contains decision history h, that is, $h^{'} \in [h]$ if and only if $h^{'} \approx_{ι (h)} h$ ):

$\begin{matrix} if h^{'}, h^{″} \in [h], ω_{1}, ω_{2} \in B_{h} (ω), h^{'} a ≺ h_{1} c_{1} ≾ ζ (ω_{1}) and \\ h^{″} b ≺ h_{2} c_{2} ≾ ζ (ω_{2}), then either c_{1} = c_{2} or there exist \\ ω_{1}^{'}, ω_{2}^{'} \in B_{h} (ω) such that h^{'} a ≺ h_{1} c_{2} ≾ ζ (ω_{1}^{'}) and \\ h^{″} b ≺ h_{2} c_{1} ≾ ζ (ω_{2}^{'}) . \end{matrix}$

(3)

In words: if, at state $ω$ and reached history h, player $i = ι (h)$ considers it possible that, if she takes action a, history $h_{1}$ is reached and player $j = ι (h_{1})$ takes action $c_{1}$ at $h_{1}$ and player i also considers it possible that, if she takes action b, then history $h_{2}$ is reached, which belongs to the same information set as $h_{1}$ , and player j takes action $c_{2}$ at $h_{2}$ , then either $c_{1} = c_{2}$ or at state $ω$ and history h player i must also consider it possible that (1) after taking action a, $h_{1}$ is reached and player j takes action $c_{2}$ at $h_{1}$ and (2) after taking action b, $h_{2}$ is reached and player j takes action $c_{1}$ at $h_{2}$ .

Figure 8 shows a game and four partial models of it, giving only the beliefs of Player 1 (at history ⌀): two of them violate Condition 5 of Definition 6 (the ones on the left that are labeled “not allowed”), while the other two satisfy it. Note that the models shown in Figure 5, Figure 6 and Figure 7 are all causally restricted models.

Now we turn to the notion of agreement, which is intended to rule out situations like the one shown in Figure 7 where Players 1 and 2 disagree about what action Player 3 would take at her information set

{d, a D}

Definition 7.

We say that at state ω active players i and j consider future information set $[h]$ of player $k = ι (h)$ if there exist

1.: two decision histories $h_{1}$ and $h_{2}$ that are reached at ω (that is, $h_{1} ≺ h_{2} ≺ ζ (ω)$ ) and belong to i and j, respectively, (that is, $i = ι (h_{1})$ and $j = ι (h_{2})$ ),
2.: states $ω_{1} \in B h_{1} (ω)$ and $ω_{2} \in B h_{2} (ω)$ ,
3.: decision histories $h^{'}, h^{″} \in [h]$ ,

such that, for some $h_{1}^{'} \approx_{i} h_{1}$ , $h_{1}^{'} ≺ h^{'} ≺ ζ (ω_{1})$ and, for some $h_{2}^{'} \approx_{j} h_{2}$ , $h_{2}^{'} ≺ h^{″} ≺ ζ (ω_{2})$ .

That is, player i at $h_{1}$ considers it possible that the play has reached history $h_{1}^{'} \in [h_{1}]$ and, after taking an action at $h_{1}^{'}$ , information set $[h]$ of player k is reached, and player j at $h_{2}$ considers it possible that the play has reached history $h_{2}^{'} \in [h_{2}]$ and, after taking an action at $h_{2}^{'}$ , that same information set $[h]$ of player k is reached.

Definition 8.

We say that at state ω active players i and j are in agreement if, for every future information set $[h]$ that they consider (Definition 7), they predict the same choices(s) of player $k = ι (h)$ at h, that is, if player i is active at reached history $h_{1}$ and player j is active at reached history $h_{2}$ , with $h_{1} ≺ h_{2} ≺ ζ (ω)$ , then

1.: if $ω_{1} \in B h_{1} (ω)$ and $h_{1}^{'} ≺ h^{'} a ≾ ζ (ω_{1})$ with $h_{1}^{'} \in [h_{1}]$ , $h^{'} \in [h]$ and $a \in A (h)$ , then there exists an $ω_{2} \in B h_{2} (ω)$ such that, for some $h^{″} \in [h]$ and $h_{2}^{'} \in [h_{2}]$ , $h_{2}^{'} ≺ h^{″} a ≾ ζ (ω_{2})$ , and
2.: if $ω_{2} \in B h_{2} (ω)$ with $h_{2}^{'} ≺ h^{″} b ≾ ζ (ω_{2})$ with $h_{2}^{'} \in [h_{2}]$ , $h^{″} \in [h]$ and $b \in A (h)$ then here exists an $ω_{1} \in B h_{1} (ω)$ such that, for some $h^{'} \in [h]$ and $h_{1}^{'} \in [h_{1}]$ , $h_{1}^{'} ≺ h^{'} b ≾ ζ (ω_{1})$ .

Finally we define the event, denoted by

A

, that any two active players are in agreement:

$ω \in A if and only if any two players active at ω are in agreement at ω .$

(4)

We can now state our characterization result, according to which a self-confirming play is a Nash play if and only if the beliefs of any two players are in agreement about the hypothetical choice(s) of a third player at a future information set that they both consider. As in [1] we restrict attention to games that satisfy the property that each player moves at most once along any play. Equivalently, one could consider the agent form of the game, where the same player at different information sets is regarded as different players, but with the same payoff function.

Proposition 1.

Consider a finite extensive-form game G where no player moves more than once along any play. Then,

(A): If z is a Nash play of G then there is a causally restricted model of G and a state $ω$ in that model such that (1) $ζ (ω) = z$ and (2) $ω \in R \cap T \cap C \cap A$ .
(B): For any causally restricted model of G and for every state $ω$ in that model, if $ω \in R \cap T \cap C \cap A$ then $ζ (ω)$ is a Nash play.

The proof of Proposition 1 is given in Appendix B.

Note that, in a perfect-information game,

T \cap C \subseteq A

. Hence Proposition 1 in [1] is a corollary of the above Proposition.

[ad_2]