Discussion Paper No.343
Discovery Process in Normal-Form Games with
Unawareness: Cognitive Stability and Closedness
under Rational Behavior
Yoshihiko Tada
Chuo University
Economic Reserch Institute,
Associate Researcher
February 2021

INSTITUTE OF ECONOMIC RESEARCH
Chuo University
Tokyo, Japan

Discovery Process in Normal-Form Games with
Unawareness: Cognitive Stability and Closedness
under Rational Behavior ∗Yoshihiko Tada†‡
February 6, 2021

Abstract
This study examines how each player chooses her/his optimal action in“normal-form games with unawareness” by applying a “discovery process”
to them. We show that if each player implements a best response to
the opponents’ immediately preceding plays, then any discovery process
converges to a set closed under rational behavior (CURB) on the realizableaction set. Moreover, in the objective game in any initial normal-form
game with unawareness, when every CURB set on the realizable action
set is mutually known, every discovery process converges to a discovered
game possessing a cognitively stable generalized Nash equilibrium. It is
not necessary that each player must be aware of the opponents’ utilities
in our results.
JEL classification: C72; D83
Keywords: Game Theory; Unawareness; Discovery; Generalized Nash
Equilibrium; Cognitive Stability; Closed under Rational Behavior

1

Introduction

This study analyzes a discovery process named the discovery process with Markov
best responses and convergence. Games with unawareness assume that someplayer may be unaware of certain actions and their opponents’ actual subjective
games.1 In games with unawareness, some players’ beliefs about their opponents’ play may be wrong in a play. When some player produces an action that
∗ This article is based on the author’s master’s thesis, Tada (2018). An earlier version ofthis article was presented at the 2018 Japanese Economic Association Autumn Meeting at
Gakushuin University, September 8–9, 2018, Tokyo. The author thanks Norimasa Kobayashi,
Yasuo Sasaki, Toichiro Asada and Hirokazu Takizawa for insightful comments on this study.
I would like to thank Editage (www.editage.com) for English language editing.
† Graduate School of Economics, Chuo University, 742-1, Higashinakano, Hachioji-shi,
Tokyo 192-0393, Japan‡ yoshihiko.tada.4@gmail.com
1 Schipper (2014) provides a historical survey on “unawareness” and “games with unawareness.”1

another player is unaware of, another player is surprised at the action and would
revise her belief about the game’s structure. Then, we must revise the original
game with unawareness.
Schipper (2018) first introduces and formulates the revision process known
as a discovery process.2 A study of discovery processes analyzes a convergence ofeach player’s update to her subjective game and belief hierarchy. In the process,each player updates her higher-order subjective games by adding played actions
that she is unaware of. Through the revision process, each player arrives atsome situation improving each player’s unawareness of the opponents’ actions
and replays the situation.
Schipper (2018) shows that in any extensive-form game with unawareness,
if every player implements a rationalizable strategy, then the (rationalizable)
discovery process converges to some discovered game, in which each player revises her beliefs about her subjective view and her opponents’ play, possessing
a self-confirming equilibrium3 . The present study provides another discovery
process. Simply, we focus on only a normal-form game with unawareness andassume that our player implements a best response to an immediately preceding
play, called a Markov best response. In contrast to Schipper (2018), although
our player’s strategy might not be rationalizable, our discovery process undersome condition converges to some discovered game possessing a cognitively stable generalized Nash equilibrium.
It might not be possible to apply the analysis in this study to normal-form
games with unawareness in general, because some game with unawareness might
not have a cognitively stable generalized Nash equilibrium and each player might
not play her own action that some opponent is unaware of. Then, no player
can discover any novel action that they are unaware of and thus, we cannot
update to the (normal-form) game with unawareness. To resolve this issue, we
focus on closedness under rational behavior (CURB ). Basu and Weibull (1991)
propose a CURB set that is a closed set of best responses to the opponents’actions in a standard model and refinement of rationalizability (Bernheim 1984;
Pearce 1984). Tada (2020) is the first to apply CURB to static games withunawareness. He shows that if a static game with unawareness has a CURB set
that is commonly known (common CURB set), then there is a cognitively stable
generalized Nash equilibrium. He focuses on CURB sets only on an objective
game in a normal-form game with unawareness; our study, meanwhile, focuseson CURB sets not only on an objective game but also on the realizable action
set that is the Cartesian product of non-empty sets of each player’s own actions
that she is aware of.
Our result shows that any discovery process with Markov best responses
converges to a discovered game in which the support of the objective outcome
2 A discovery process is diﬀerent to a learning process. Roughly, in a learning process, eachplayer learns if she replaces previous probabilities with novel probabilities about the same
event when the novel event that some player is unaware of does not occur; meanwhile, in a
discovery process, each player discovers if she adds novel events that she does not know about
and assigns probabilities to the events.
3 Schipper (2018) calls the game a “rationalizable self-confirming game.”2

induced from Markov best responses is a subset of some CURB set on the realizable action set (Theorem 1). Moreover, for any initial normal-form gamewith unawareness, when there exists a CURB set in the objective game which ismutually known, called mutual CURB set, some discovery process with Markov
best responses converges to some discovered game possessing a non-empty common CURB set, called a cognitively stable game under CURB (Theorem 2).
Then, the cognitively stable game under CURB has a cognitively stable generalized Nash equilibrium by Tada (2020) (Corollary 1). Furthermore, if every
CURB set on realizable action set is a mutual CURB set in any initial normalform game with unawareness, then every discovery process with Markov best
responses converges to a cognitively stable game under CURB (Corollary 2).
This rest of this paper organized as follows. Section 2 provides preliminaries.
Section 3 defines a discovery process and Section 4 formulates one of discovery
processes, called a discovery process with Markov best responses. Finally, Section 5 shows the mathematical results.

2

Preliminaries

2.1

Normal-Form Games with Unawareness

Let G = (I, A, u) be a finite normal-form game. I is a finite set of players and
I−i = I \ {i}. A = ×i∈I Ai , where Ai is the non-empty finite set of i’s actions
and each element on the set is ai ∈ Ai . u = (ui )i∈I , where ui : A → R is i’sutility function. Denote i’s mixed action on Ai by mi ∈ M (Ai ), where M (Ai ) is
the set of i’s mixed actions, and a mixed action profile on A by m = (mi )i∈I ∈
M (A) = ×i∈I M (Ai ). We denote i’s expected utility for m ∈ M (A) by Eui (m).
First, we define normal-form games with unawareness.4 For any standard
normal-form game G, let V = ×i∈I (2Ai \ {∅}) be the set of possible views of
the G. Like most previous works, this study assumes that the set of players iscommonly known and that each player’s utility for each action profile does notdepend on awareness. Let v ∈ V and Avi be the set of i’s actions in v = ×j∈I Avj .
Here, when player i is given v, i is aware of a ∈ v and unaware of a ∈ A \ v. For′
any v, v ′ ∈ V , v is contained in v ′ if Avi is a subset of Avi for any i ∈ I, that is,′
Avi ⊆ Avi . Let M (Avi ) = {mi ∈ M (Ai )|Σai ∈Avi mi (ai ) = 1}.
Let Γ = (G, (Ti )i∈I , (vi )i∈I , (bi )i∈I ) be a static game with unawareness asfollows: for each i ∈ I,
• Ti is a finite and non-empty set of i’s type, one of which is her actual typet∗i .
• vi : Ti → V is i’s view function.
4 Our definition is similar to that by Perea (2018). Note that there are two diﬀerences.
First, his model does not fix belief hierarchies on views, whereas we do so. We assume
that the “actual type” of the players is given. Second, he deals with probabilistic beliefs onawareness, whereas we do not. Our players always have point beliefs on their opponents’awareness, as is often assumed in the literature of games with unawareness.

3• bi : Ti → T−i is i’s belief function, where T−i = ×j∈I\{i} Tj . If bi (ti ) =(tj )j∈I\{i} , then for each j ∈ I \ {i} must be contained in vi (ti ).
Let us call G an objective game (in Γ). An objective game can be interpreted
as the “true game” in Γ.5 i’s type ti describes her view about the game andbelief about the opponents’ types. At ti , vi (ti ) = v means that i is aware of v
and unaware of A \ v; while bi (ti ) = (tj )j∈I\{i} means that at ti , i believes thatthe others’ types are (tj )j∈I\{i} and that each j’s view is vj (tj ). We can write
j’s type in bi (ti ) as bi (ti )(j). In a normal-form game with unawareness, eachplayer may be unaware of some types of players, including her own.
v (t )For any i ∈ I, let si : Ti → M (Ai ). Then, given ti , si (ti ) ∈ M (Ai i i ) is i’slocal action at ti . We denote i’s generalized strategy by si = (si (ti ))ti ∈Ti , anda generalized strategy profile by s = (si )i∈I . In a generalized strategy profile s,each player i’s actual play is mi ∈ M (Ai ) with mi = si (t∗i ), and then the profile
is called the objective outcome induced from s. The set of each player’s actualv (t∗ )
play Ai i i may be a proper subset of i’s full action set Ai . Then, she cannotv (t∗ )v (t∗ )
play ai ∈ Ai \ Ai i i . Let ×i∈I Ai i i be the realizable action set.
Halpern and Rêgo (2014) introduce a solution concept in games with unawareness as generalized Nash equilibrium: s∗ is a generalized Nash equilibrium
if for any i ∈ I and ti ∈ Ti ,s∗i (ti ) ∈ arg

Eui (x, (s∗j (bi (ti )(j))j∈I\{i} )).

maxv (ti )x∈M (Ai i)

As they point out, a generalized Nash equilibrium is best interpreted as “anequilibrium in beliefs.” (Halpern and Rêgo 2014: 50) However, as pointed out
by Schipper (2014), there exists some generalized Nash equilibrium, which consists of wrong beliefs. Then, each player would revise her own beliefs about agame’s structure and the opponents’ play and they might not play the same generalized Nash equilibrium. To avoid this case, Sasaki (2017) proposes cognitive
stability about generalized Nash equilibrium. A generalized Nash equilibriums∗ is cognitively stable if for any i ∈ I and ti ∈ Ti , s∗i (ti ) = s∗i (t∗i ).6
Cognitively stable generalized Nash equilibria have the following property.
Remark 1. For any normal-form game with unawareness Γ, let s∗ be a cognitively stable generalized Nash equilibrium. Then, the objective outcome(s∗i (t∗i ))i∈I is a Nash equilibrium on the realizable action set.
proof. Suppose that s∗ is a cognitively stable generalized Nash equilibrium, thatis, for any (i, ti ) ∈ I × Ti , s∗i (ti ) = s∗i (t∗i ). This is obviously (s∗i (t∗i ))i∈I ∈ Avj (tj )vj (t∗
j)for any (j, tj ) ∈ I × Tj . Therefore, (s∗i (t∗i ))i∈I ∈ ×j∈I Aj. Assume thatv (t∗ )(s∗i (t∗i ))i∈I is not a Nash equilibrium on the realizable action set ×i∈I Ai i i . Inv (t∗ )
other words, there exists (i, ai ) ∈ I ×Ai i i such that ai ̸∈ supp(s∗i (t∗i )) and ai ∈∗ ∗However, since s∗ is a cognitively stablearg maxv (t∗ ) Eui (x, (sj (tj ))j∈I ).
x∈Ai i i
5 Perea (2018) calls an objective game a “base game.”
6 Sasaki (2017) calls cognitive stability “stable belief hierarchy.”4

generalized Nash equilibrium, this is a contradiction. Therefore, (s∗i (t∗i ))i∈I is aNash equilibrium on the realizable action set. ■2.2

Closedness under Rational Behavior

Some game with unawareness might not have a cognitively stable generalized
Nash equilibrium. For example, see the following case7 :

v=

1/2
U
B

L
3, 3
5, 0

R
0, 5
1, 1

, v′ =

1/2
U

L
3, 3

R
0, 5

, v ′′ =

1/2
U
B

L
3, 3
5, 0

Suppose that T1 = {t∗1 , t1 } and T2 = {t∗2 , t2 } such that:v1 (t∗1 ) = v ′ and b1 (t∗1 ) = t2 ;v1 (t1 ) = v ′′ and b1 (t1 ) = t∗2 ;
v2 (t∗2 ) = v ′′ and b2 (t∗2 ) = t1 ; andv2 (t2 ) = v ′ and b2 (t2 ) = t∗1 .
This example is illustrated in Figure 1. In this static game with unawareness,a unique generalized Nash equilibrium s∗ = ([s1 (t∗1 ) = U, s1 (t1 ) = B], [s2 (t∗2 ) =L, s1 (t1 ) = R]) is cognitively unstable. Then, each player is already aware of the
opponent’s actual play. Thus, although both players’ beliefs are wrong, since
there is no novel action that some player is unaware of, we cannot revise eachplayer’s subjective game and the original game with unawareness. Therefore,
in this example, a simple discovery process, in which each player only adds
actions that some player is unaware of, cannot converge to an update to allplayers’ subjective views and belief hierarchies possessing a cognitively stable
generalized Nash equilibrium.
To avoid this case, this section focuses on closedness under rational behavior(Basu and Weibull 1991). Tada (2020) is the first to apply CURB to normalform games with unawareness.

Figure 1: Formulation of example of two players, 1 and 2

7 We borrow this situation from Schipper (2018, Example 3).

5This subsection defines CURB in standard normal-form games. Let βi (m−i ) ={ai ∈ Ai |ai ∈ supp(mi ) be such that mi ∈ arg maxx∈M (Ai ) Eui (x, m−i )} is theset of i’s pure-action∪best responses to her belief about m−i ∈ M (A−i ). For anyv ∈ V , let βi (v) = m−i ∈M (×j∈I Av ) βi (m−i ) be the set of i’s optimal actions−i junder beliefs in M (v), and let β(v) = ×i∈I βi (v). Then, a set v ∈ V is closed
under rational behavior (CURB ) (in G) if β(v) ⊆ v. Let us call the v a CURB
set.
In a standard normal-form game, as shown by Basu and Weibull (1991), a
CURB set has the following property.
Remark 2. For any standard normal-form game G and any CURB set, there
exists a Nash equilibrium such that the support is a subset of the CURB set.
Tada (2020) defines a common CURB set as follows: For any normal-form
game with unawareness Γ and any v ∈ V , v is a common CURB set if v is a
non-empty CURB set in the objective game G and v ⊆ vi (ti ) for any i ∈ I andti ∈ Ti .
He shows the following property.
Lemma 1. Any normal-form game with unawareness possessing a common
CURB set has a cognitively stable generalized Nash equilibrium.
proof. Assume that any normal-form game with unawareness has a common
CURB set v ∈ V . Then, by Remark 2, there exists a Nash equilibrium in theobjective game G = (I, A, u), m∗ ∈ M (A), satisfying m∗ ∈ M (v). Supposethat m∗ is not a Nash equilibrium on v. In other words, there exists (i, mi ) ∈I × M (Avi ) such that Eui (mi , m∗−i ) > Eui (m∗ ). However, since v is common
CURB set, this is a contradiction. Therefore, m∗ is a Nash equilibrium on v.
Then, m∗i is a best response to m∗−i in vi (ti ) for any i ∈ I and ti ∈ Ti . Thus,s∗ with s∗i (ti ) = m∗i for any i ∈ I and ti ∈ Ti is a cognitively stable generalized
Nash equilibrium. ■As pointed out by Tada (2020), a common CURB set is a refinement ofgeneralized Nash equilibria and a coarsening of cognitively stable generalized
Nash equilibria.

2.3

Cognitively Stable Games under CURB

Finally, we define a cognitively stable games under CURB. By the definitionsof CURB and common CURB sets, all players are aware of every local actionof each player in a common CURB set. Therefore, any game with unawarenesspossessing a common CURB set is cognitively stable under playing actions in thecommon CURB set. We call the game a cognitively stable game under CURB.
Definition 1. A normal-form game with unawareness Γ is a cognitively stable
game under CURB if there exists a non-empty common CURB set in Γ.

6The concept of cognitively stable games under CURB is similar to theconcept of (rationalizable) self-confirming games (Schipper 2018). In a selfconfirming game, each player confirms her belief about a game’s structure. Furthermore, in a cognitively stable game under CURB, each player’s belief abouta game’s structure is cognitively stable as long as every player implements her(local) action in the common CURB set.
To show our main results, we introduce the following concept.
Definition 2. For any normal-form game with unawareness Γ, v ∈ V is amutual CURB set if v is a non-empty CURB set in the objective game G andv ⊆ vi (t∗i ) for any i ∈ I.
A mutual CURB set has the following property.
Lemma 2. For any normal-form game with unawareness Γ, if v ∈ V is a mutual
CURB set, then v is a CURB set on the realizable action set.
proof. Suppose that v is a mutual CURB set, that is, v ⊆ vi (t∗i ) for any i ∈ I.
∩∩v (t∗ )
In other words, v ∈ i∈I vi (t∗i ). Here, since i∈I vi (t∗i ) ⊆ ×i∈I Ai i i , v ⊆v (t∗ )

×i∈I Ai i i . ■3

Discovery Process

Schipper (2018) is the first to introduce a discovery process in (extensive-form)
games with unawareness, which is based on Heifetz, Meier, and Schipper (2013).
A discovery process represents an update process by which each player revises
her own belief about a game’s structure and the opponents’ play. Although ourdefinition given here, at first glance, may seem diﬀerent to that used in Schipper(2018), both definitions are essentially the same.
Definition 3. Γ′ = (G, (Ti′ )i∈I , (vi′ )i∈I , (b′i )i∈I ) is a discovered game with s =(si )i∈I in Γ = (G, (Ti )i∈I , (vi )i∈I , (bi )i∈I ) if for any (i, ti ) ∈ I × Ti , there exists
t′i ∈ Ti′ such that:
1. vi′ (t′i ) = ×i∈I [Aj i i ∪ supp(sj (t∗j ))], where t∗j is j’s actual type in Γ; andv (t )

2. for any (j, tj ) ∈ I−i × Tj , if bi (ti )(j) = tj and tj can be replaced with somet′j ∈ Tj′ satisfying the first condition in this definition, then b′i (t′i )(j) = t′j .
Note that some Γ, Γ′ may be T ̸⊆ T ′ and T ′ ̸⊆ T , or T ∩ T ′ = ∅.
Definition 4. A discovery process P = (⟨Γ1 , s0 ⟩, ⟨Γ2 , s1 ⟩, . . . , ⟨Γλ , sλ−1 ⟩, . . . ),is defined as follows:• for any λ, Γλ = (G, (Tiλ )i∈I , (viλ )i∈I , (bλi )i∈I );• when λ = 0, s0 = ϕ, while for any λ ≥ 1, sλ is a played generalized
strategy profile in Γλ ; and7• for any λ ≥ 2, Γλ is a discovered game with sλ−1 in Γλ−1 .
Let us call Γ1 the initial game (in P ).
By Definition 3, Definition 4 implicitly assumes perfect recall. If we exclude
the assumption, some player may forget some action at λ even if she is awareof the action at λ − 1.
Simply, this study assumes that every player can play and observe a mixed
action.8

4Discovery Process with Markov Best Responses

Schipper’s (2018) discovery process assumes that every player implements herrationalizable strategy in each discovered game. Playing a rationalizable strategy would be appropriate in a game in which every player faces the situation
for the first time. However, rationalizability notions have an issue in discovery
processes. Consider the following example:

v=

3/4
U
B

L
3, 3
5, 0

R
0, 5
1, 1

, v′ =

3/4
U
B

L
3, 3
5, 0

, v ′′ =(λ=1)∗

In initial game Γλ=1 , suppose that T3λ=1 = {t3(λ=1)∗ (λ=1){t4, t4} such that:

3/4
U
(λ=1)

, t3

L
3, 3

R
0, 5

} and T4λ=1 =v3 (t3) = v ′ and b3 (t3) = t4
;
(λ=1)
(λ=1)
(λ=1)∗′′
v3 (t3) = v and b3 (t3) = t4;(λ=1)∗(λ=1)∗(λ=1)
v4 (t4) = v ′′ and b4 (t4) = t3
; and
(λ=1)
(λ=1)
(λ=1)∗′
v4 (t4) = v and b4 (t4) = t3.
(λ=1)∗(λ=1)∗(λ=1)

Figure 2 (a) is a formulation of the example at λ = 1. Then, a rationalizable(λ=1)∗(λ=1)(λ=1)∗
strategy play is s(λ=1)∗ = ([s3 (t3) = B, s3 (t3) = U ], [s4 (t4
) =
(λ=1)
R, s4 (t4
) = L]), player 3 discovers 4’s action R and player 4 discovers 3’s(λ=2)∗
action B. Thus, in the discovered game Γλ=2 , T3λ=2 = {t3} and T4λ=2 =(λ=2)∗{t4} such that:(λ=2)∗(λ=2)∗(λ=2)∗

v3 (t3) = v and b3 (t3) = t4;(λ=2)∗(λ=2)∗(λ=2)∗) = t3.
v4 (t4) = v and b4 (t48 In proofs of each result in Section 5, since we assume that not that every player implements
a generalized Nash equilibrium, as in Tada (2018), but rather that every player implements
any generalized strategy profile, our main results do not depend on the assumption. In fact,a pure action is a mixed action assigning probability 1 to the action. The proofs of our main
results are provided in Section 5.

8

Figure 2: Formulation of example of two players, 3 and 4
At λ = 2, the formulation is depicted in Figure 2 (b). Here, each player
discovers novel action profiles: 3 discovers (U, R) and (U, L); while 4 discovers(B, L) and (B, R). Then, rationalizability assumes that 3 is aware of 4’s payoﬀ
u4 (U, R) = 5 and 4 is aware of 3’s payoﬀ u3 (B, L) = 5. However, even if
each player were unaware of each profile and the profiles were not realized in
the initial game Γλ=1 , it would not explain why each player is aware of every
opponent’s utility in the next game Γλ=2 . This seems to be a strict assumption.
By contrast, this study assumes that in each discovered game, every player
implements a best response to the opponents’ play in the immediately preceding
discovered game. Then, since each player has to know only the opponents’
immediately preceding play but not the opponents’ novel payoﬀ, we can avoid
the abovementioned issue. Let us call the best response a Markov best response.
Definition 5. For any discovered game Γλ from Γλ−1 , sλi is i’s Markov best
response if for any ti ∈ Ti ,sλi (ti ) ∈ arg(λ−1)∗Eui (x, (sλ−1
(tj
j

max
v (ti )x∈M (Ai i)j∈I−i )).

)(λ−1)∗

Note that for any j ∈ I−i , tj
∈ Tj is j’s actual type in Γλ−1 . Let us callthe generalized strategy profile sλ = (sλi )i∈I a Markov best response profile.
Each player’s Markov best response is not a best response in belief hierarchiesin each discovered game. Therefore, her Markov best response might not be
rationalizable in her belief hierarchy.
Next, we define a discovery process with Markov best response as follows.
Definition 6. Any discovery process P = (⟨Γ1 , s0 ⟩, ⟨Γ2 , s1 ⟩, . . . , ⟨Γλ , sλ−1 ⟩, . . . ),is a discovery process with Markov best responses if for any λ ≥ 2, sλ is Markov
best response profile at λ.

5

Results

This section shows a convergence of a discovery process with Markov best responses. By Definition 4, every player adds realized novel actions to every view.
9By Definition 5, a discovery process with Markov best responses is essentially asequence of best responses on the realizable action set. Therefore, we first show
convergence to a CURB set.
Theorem 1. For any normal-form game with unawareness, every discovery
process with Markov best responses converges to some discovered game. Inthat game, support of an objective outcome induced from the Markov best
response profile is a subset of a CURB set on the realizable action set.
proof. Since we consider a discovery process with Markov best responses, it isnecessary only to focus on the realizable action set. For any objective outcomein the initial game m, let β λ (m) be an objective outcome induced from a Markov
best response profile and it is defined as follows: β 0 (m) = supp(m), β 1 (m) =β ◦ β 0 (m), β 2 (m) = β ◦ β 1 (m), . . . , β λ (m) = β ◦ β λ−1 (m), . . . . Suppose thatv (t∗ )
for any CURB set on the realizable action set v ⊆ ×i∈I Ai i i and natural
number λ, β λ (m) ̸⊆ v. As pointed out by Basu and Weibull (1991), sincev (t∗ )v (t∗ )
the set of rationalizable strategy profile on ×i∈I Ai i i , R ⊆ ×i∈I Ai i i , is
CURB,9 β λ (m) ̸⊆ R for any λ. This is obviously a contradiction. Therefore,v (t∗ )
there exists a CURB set v on ×i∈I Ai i i and natural number n such thatβ n (m) ⊆ v. Suppose that there exist λ ≥ n satisfying β λ (m) ̸⊆ v. In otherwords, β ◦ · · · ◦ β ◦ β n (m) ̸⊆ v. However, since v is CURB, that is, β(v ′ ) ⊆ v for′any v ′ ⊆ v with ∅ ̸= Avi ⊆ Avi , this is a contradiction. Therefore, β λ (m) ⊆ v forany λ ≥ n. Since β λ (m) supports an objective outcome induced from a Markov
best response profile at λ and v is a CURB set on the realizable action set, thesupport is a subset of a CURB set on the realizable action set. ■It is known that many intuitively appealing adjustment processes eventually
settle down in a minimal curb set, cf. Hurkens (1995) and Young (1998). Theorem 1 adds to the previous literature, highlighting the importance of CURB
set. However, the process therein converges to a general CURB set, and notnecesssarily a “minimal” CURB set like Hurkens (1995) and Young (1998).
By Definition 3, for any discovery process with Markov best responses P ,since an objective outcome induced from each Markov best response profile in
P is added in vi (ti ) for any (i, ti ) ∈ I × Ti , the support must be commonly
known through P . Note that a CURB set on the realizable action set that iscommonly known might not be a common CURB set, because a CURB set on
the realizable action set might not be a CURB set in an objective game.10
The following theorem suggests a condition for which a CURB set on therealizable action set is a common CURB set in a discovery process with Markov
best responses.

9 Specifically, R is a (maximum) tight CURB set. An action profile set v ∈ V is a tight
CURB set if β(v) = v.
10 In this case, the CURB set on the realizable action set might not be CURB in each player’s
view.

10

Theorem 2. Suppose a normal-form game with unawareness has a mutual
CURB set. Then, there exists a discovery process with Markov best responses
converging to some cognitively stable game under CURB.
proof. Suppose a normal-form game with unawareness has a mutual CURB
set. Assume that every discovery process with Markov best responses does
not converge to any cognitively stable game under CURB, i.e., every discovery
process with Markov best responses does not converge to any discovered gamepossessing a common CURB set. That is, any action profile in the mutual
CURB set is not realized in any discovery process with Markov best responses.
However, by Lemma 2, since every mutual CURB set is a CURB set on therealizable action set, it contradicts. Therefore, since every action profile on themutual CURB set is realizable, in some discovery process with Markov best
responses the set is a common CURB set. ■By Lemma 1, we can deduce the following corollary.
Corollary 1. Suppose a normal-form game with unawareness has a mutual
CURB set. Then, there exists a discovery process with Markov best responses
converging to some discovered game possessing a cognitively stable generalized
Nash equilibrium.
Example 1. Consider the following game played by Alice (A) and Bob (B):
A/B
a1
v0 =
a2
a3

b1
3, 3
5, 0
-1, 0

b2
0, 5
1, 1
0, 1

b3
0, -1
1, 0
2, 2

A/B
a1
, v =
a3
1

(λ=1)∗At λ = 1, suppose that TAλ=1 = {tAsuch that:(λ=1)∗(λ=1)∗

(λ=1)

, tA

b2
0, 5
0, 1

b3
0, -1
2, 2

A/B
a1
, v =
a2
2

(λ=1)∗} and TBλ=1 = {tB

(λ=1)

, tB

}

(λ=1)

vA (tA) = v 1 and bA (tA) = tB
;
(λ=1)
(λ=1)
(λ=1)∗2vA (tA) = v and bA (tA) = tB;(λ=1)∗(λ=1)∗(λ=1)
2vB (tB) = v and bB (tB) = tA
; and
(λ=1)
(λ=1)
(λ=1)∗vB (tB) = v 1 and bB (tB) = tA.
The formulation at λ = 1 is Figure 3 (a). Then, the realizable action set is
as follows:

v̂ =

A/B
a1
a3

b1
3, 3
-1, 0

b3
0, -1
2, 2

In v̂, there are three CURB sets: X1 = {a1 } × {b1 }, X2 = {a2 } × {b2 } andX3 = {a2 , a3 } × {b2 , b3 }. Moreover, X2 is a mutual CURB set.
11

b1
3, 3
5, 0

b3
0, -1
1, 0

Figure 3: Formulation of example of two players, Alice and Bob
At λ = 1, suppose that both players play a generalized Nash equilibrium:(λ=1)∗s1(λ=1)∗= ([sA (tA(λ=1)) = a1 , sA (tA(λ=1)∗) = a2 ], [sB (tB(λ=1)) = b1 , sB (tB) = b2 ]).

The generalized Nash equilibrium is obviously cognitively unstable and the ob(λ=1)∗(λ=1)∗
jective outcome is (sA (tA), sB (tB)) = (a1 , b1 ). Then, since Alice isunaware of b1 , she is surprised by it and revises her beliefs as follows:
v3 =

A/B
a1
a3

b1
3, 3
-1, 0

b2
0, 5
0, 1

b3
0, -1
2, 2

(λ=2)∗(λ=2)

Then, at λ = 2, suppose that TAλ=2 = {tAsuch that:(λ=2)∗(λ=2)∗, tA(λ=2)∗} and TBλ=2 = {tB

(λ=2)

, tB

}

(λ=2)

vA (tA) = v 3 and bA (tA) = tB
;
(λ=2)
(λ=2)
(λ=2)∗2vA (tA) = v and bA (tA) = tB;(λ=2)∗(λ=2)∗(λ=2)
vB (tB) = v 2 and bB (tB) = tA
; and
(λ=2)
(λ=2)
(λ=2)∗3vB (tB) = v and bB (tB) = tA.
(λ=1)∗

The formulation playing s1
is depicted as Figure 3 (b). At λ = 2, when
they play a Markov best response, the generalized strategy profile is:(λ=2)∗s1(λ=2)∗= ([sA (tA(λ=2)) = a1 , sA (tA(λ=2)∗) = a1 ], [sB (tB(λ=2)) = b1 , sB (tB) = b1 ]).

Although there is no generalized Nash equilibrium in the discovered game, the(λ=2)∗(λ=2)∗(λ=2)∗(λ=2)∗)) = (a1 , b1 ) satisfies (sA (tA), sB (tB)) ∈), sB (tBobjective outcome (sA (tA
X1 and X1 is a CURB set in the realizable action set in the discovered game.
This case suggests Theorem 1.
Next, suppose that both players implement a diﬀerent generalized Nash equilibrium at λ = 1 as follows:(λ=1)∗s2(λ=1)∗= ([sA (tA(λ=1)) = a3 , sA (tA(λ=1)∗) = a2 ], [sB (tB

12

(λ=1)

) = b3 , sB (tB) = b3 ]).

Figure 4: Formulation of example of two players, Alice and Bob (continued. )The generalized Nash equilibrium is cognitively unstable and the objective out(λ=1)∗(λ=1)∗
come is (sA (tA), sB (tB)) = (a3 , b3 ). Then, since Bob is unaware of a3 ,he is surprised at it and revises his beliefstw as follows:

A/B
a1
v4 =
a2
a3

b1
1, 1
0, 0
-1, 0
(λ=2)∗

Then, at λ = 2, suppose that T̂Aλ=2 = {t̂Asuch that:(λ=2)∗(λ=2)∗

b3
0, 0
1, 1
2, 2
(λ=2)

, t̂A

(λ=2)∗} and T̂Bλ=2 = {t̂B

(λ=2)

, t̂B

(λ=2)

;
) = t̂B) = v 1 and bA (t̂AvA (t̂A(λ=2)(λ=2)(λ=2)∗vA (t̂A) = v 4 and bA (t̂A
) = t̂B;(λ=2)(λ=2)∗(λ=2)∗; and) = t̂A) = v 4 and bB (t̂BvB (t̂B(λ=2)(λ=2)(λ=2)∗vB (t̂B) = v 1 and bB (t̂B
) = t̂A.
(λ=2)

Figure 4 (b’) is a formulation at λ = 2 playing s2
in a previous situation.
At λ = 2, when they play a Markov best response, the generalized strategy
profile is:(λ=2)∗s2(λ=2)∗= ([sA (t̂A

(λ=2)

) = a3 , sA (t̂A(λ=2)∗) = a3 ], [sB (t̂B

(λ=2)

) = b3 , sB (t̂B

) = b3 ]).

This is a cognitively stable generalized Nash equilibrium, the objective outcome(λ=2)∗(λ=2)∗(λ=2)∗(λ=2)∗(sA (t̂A), sB (t̂B)) = (a3 , b3 ) satisfies (sA (t̂A), sB (t̂B)) ∈ X2 andX2 is a common CURB set in the discovered game. In other words, the discovered game is a cognitively stable game under CURB. This case suggests
Theorem 2. □In Example 1, although the initial game in Figure 3 (a) has mutual CURB
set X2 , some discovery process with Markov best responses may converge toa discovered game, as in Figure 3 (b), which is not a common CURB set.
13}

However, as shown by the proof of Theorem 2, a mutual CURB set in the initial
game is a common CURB set in cognitively stable game under CURB to whichsome discovery process with Markov best responses converge. Therefore, we candeduce the following corollaries.
Corollary 2. Suppose that every CURB set on the realizable action set isa mutual CURB set in a normal-form game with unawareness. Then, every
discovery process with Markov best responses converges to a cognitively stable
game under CURB.
Corollary 3. Suppose that every CURB set on the realizable action set isa mutual CURB set in a normal-form game with unawareness. Then, every
discovery process with Markov best responses converges to a discovered gamepossessing a cognitively stable generalized Nash equilibrium.
Note that the process we consider in the present paper starts from an arbitrary generalized strategy profile. Our convergence result holds even if thestarting point is not necessarily a generalized Nash equilibrium.11

References[1] Kaushik Basu and Jörgen W. Weibull. Strategy subsets closed under rational behavior. Economics Letters, 36:141–146, 1991.
[2] B. Douglas Bernheim. Rationalizable strategic behavior. Econometrica,
52(4):1007–1028, 1984.
[3] Joseph Y. Halpern and Leandro C. Rêgo. Extensive games with possibly
unaware players. Mathematical Social Sciences, 70:42–58, 2014.
[4] Aviad Heifetz, Martin Meier, and Burkhard C. Schipper. Dynamic unawareness and rationalizable behavior. Games and Economic Behavior,
81:50–68, 2013.
[5] Sjakk Hurkens. Learning by forgetful players. Games and Economic Behavior, 11:304–329, 1995.
[6] David G. Pearce. Rationalizable strategic behavior and the problem of
perfection. Econometrica, 52(4):1029–1050, 1984.
[7] Andrés Perea. Common beleif in rationality in games with unawareness.
Technical report, Maastricht University, 2018.

11 Tada (2018) discusses a revision process, where players play a generalized Nash equilibrium
at each round, and conjectures that the process converges to a cognitively stable generalized
Nash equilibrium, if there is any. However, the conjecture was wrong in assuming that players
play a generalized Nash equilibrium at each round. This paper provide a result in the same
spirit under another condition that players play Markov best responses.

14[8] Yasuo Sasaki. Generalized Nash equilibrium with stable belief hierarchies instatic games with unawareness. Annals of Operations Research, 256(2):271–
284, 2017.
[9] Burkhard C. Schipper. Unawareness: A gentle introduction to both theliterature and the special issue. Mathematical Social Sciences, 70:1–9, 2014.
[10] Burkhard C. Schipper. Discovery and equilibrium in games with unawareness. Technical report, University of California, Davis, 2018.
[11] Yoshihiko Tada. A study of an agent’s epistemic revision for the games’
structure and the other agents’ perceptions: Formulation to replay of gameswith unawareness. Master’s thesis, Chuo University, 2018. (in japanese).
[12] Yoshihiko Tada. Unawareness of actions and closedness under rational behavior in static games with unawareness. Technical report, Chuo University,
2020.
[13] H. Peyton Young. Individual Sstrategy and Social Structure. Princeton
University Press, 1998.

15