Belief Revision for Inductive Game Theory
Koji Hasebe1 and Ryuichiro Ishikawa2
1

2

Department of Computer Science,
Department of Social Systems and Management,
University of Tsukuba
1-1-1 Tennodai, Tsukuba 305-8573, Japan{hasebe@cs, ishikawa@sk}.tsukuba.ac.jp

Abstract. Inductive game theory captures how a player inductively derives his/her personal views from experiences. The player may have multiple views, some of which diﬀer from the objective situation, but may
revise them with further experiences. This paper gives a logical formulation of this revision process by focusing on the role of player’s beliefs.
For this objective, we take the AGM approach of belief revision. The
idea behind our logic is that the player’s belief state is represented by abelief set of propositional formulas, thereby describing a revision process
for the belief states by using a revision operation in AGM theory. In
this setting, the player’s personal views are described as models for thecurrent belief set. We also present an application of our framework to aclass of inductive games, called festival games.

1

Introduction and Overview

Standard game theory assumes players to have suﬃcient knowledge or common
belief of the game they play. However, in a real social or economic situation,such knowledge/belief is not given in advance, but rather emerges from theindividual experiences with bounded cognitive abilities and is revised throughtime. Inductive game theory, originally introduced by Kaneko and Matsui [15]and Kaneko and Kline [12] [13] [14], explores this issue and captures how a player
inductively derives his/her knowledge and beliefs of the game from experiences.
Inductive game theory distinguishes an objective situation and players’ personal views of the game. Players are assumed to have little initial knowledge
about the objective situation, but repetitively face given situation, to accumulate their experiences through their choices of available actions, and to constructtheir personal views with the experiences. In the players’ construction, they
have diﬀerent personal views based on their diﬀerent experiences even when theplayers face an identical situation. Moreover, a player may have multiple views,
some diﬀering from the objective situation, but may revise them with further
experiences.
The diﬀerence in players’ views is due not only to their experiences, but also
to their memories, which are represented by memory functions. By introducing
memory functions, players’ abilities of memories can be represented in various

ways, although extensive games in standard game theory place some restrictions
on the representations. Therefore, even when gathering many experiences, aplayer may only partially recall his experiences.
While inductive game theory provides a framework to derive a personal view
consistent with a player’s memories of the experiences, it has been less studied
how the derived view is revised by additional experiences. This paper provides
a framework for revision in inductive game theory based on the idea of AGM(Alchourrón-Gärdenfors-Makinson) theory of belief revision [1]. By introducing
the revision process, we reﬂect a player’s inductive inference in decision-making.
Since standard game theory assumes players to have suﬃcient knowledge orcommon belief of the structure, it is not good at treating inductive inferencesof the structure. Revision of beliefs in (epistemic) logic has also been applied
to standard game theory as in Binmore [2], Bonnano [4], van Benthem [17],Board [3], and Feinberg [6] [7]3 . However, such studies usually focus on beliefs
about opponent players’ actions. While it is important to consider belief formations of opponents’ actions in interactive situations, we need to ask whether
such beliefs are plausible when the formation heavily depends on (common)knowledge of the structure. Inductive game theory and this paper truly ask thequestion: How do players cognize the (interactive) situations that they face?
Our logic is based on the standard classical propositional logic. Basic statements in inductive game theory, such as the histories of player’s actions andpayoﬀs are associated with propositional atomic formulas, thereby describing
causality relations between histories or players’ strategies as compound formulas. In terms of this language, the player’s belief state is described by a belief set
of formulas, thus a revision process for the belief states is described by using arevision operation in AGM theory. In this setting, the player’s personal views aredescribed as models for the current belief set (i.e., assignments of truth values
which satisfy all the formulas of belief set) in the semantics.
By means of this logic, we also show an application to festival games, which
are speciﬁc inductive games proposed by Kaneko and Matsui [15]. As explained
above, the players in inductive games accumulate their experiences and inductively derive their personal views of the experiences. Festival games capture themechanisms of prejudices and discriminations resulting from experiences.
This paper is organized as follows. The next section gives the deﬁnition of
inductive game theory following Kaneko and Kline [14]. Section 3 presents ourlogic for belief revision. Section 4 presents an application of our belief revision
to festival games. Finally, Section 5 gives conclusions and discusses further research.

3

A theory of belief revision in itself is now a very active area of research, and it
connects with dynamic epistemic logic. Comprehensive surveys were published by
van Ditmarsch, et al. [5], van der Hoek and Pauly [10].

2Inductive Game Theory

2.1

Information protocols

We deﬁne an information protocol Π below. Let W be a nonempty ﬁnite setof information∪∞ pieces, A be a nonempty ﬁnite set of actions, and ≺ be a ﬁnite
subset of m=0 ((W × A)m × W ). Aw ⊆ A is the available action at w ∈ W .
When m = 0, (W × A)0 × W is regarded as W of a unary relation on W .
The relation ≺ is called a causality relation. Each element h(w1 , a1 ), . . . ,(wm , am ), wm+1 i ∈≺ is called∪∞ a sequence of length m + 1. Expression hξ, wi denotes a generic element of m=0 ((W ×A)m ×W ), and hwi is that of (W ×A)0 ×W .
Using a causal relation ≺, we give a partition on W . That is, W D := {w ∈W | h(w, a), vi for some a ∈ A and v ∈ W } is called a set of decision pieces andW E := W \ W D a set of end pieces.
Now let N = {1, . . . , n} be the set of players for an information protocol Π.
Player assignment is a function π : W → 2N that π(w) assigns a single player
for any w ∈ W D and N for any w ∈ W E . Player i’s payoﬀ assignment is given
as a function hi : W E → R for all i ∈ N . We then complete the deﬁnition of an
information protocol as a quintuple Π = (W, A, ≺, (π, N ), (hi )i∈N ).
To describe a player’s personal view and an objective situation with information protocols, we require two basic axioms and three non-basic∪axioms. To stipu∞
late the basic axioms, we deﬁne a subsequence of a sequence in m=0 ((W ×A)m ×
W ). We say that h(w1 , a1 ), . . . , (wm , am ), wm+1 i is a subsequence of h(v1 , b1 ), . . . ,(vk , bk ), vk+1 i iﬀ [(w1 , a1 ), . . . , (wm , am ), (wm+1 , a)] is a subsequence of [(v1 , b1 ),. . . , (vk , bk ), (vk+1 , b)] for some a and b. We use the notation hξ, wm+1 i v hζ, vk+1 i
to state that hξ, wm+1 i is a subsequence of hζ, vk+1 i. A supersequence is deﬁned
likewise. A sequence hξ, wi is maxial iﬀ there is no proper supersequence in ≺.
A position hξ, vi is an initial segment of some maximal sequence. The set of
positions is denoted Ξ.
We now state the basic axioms.
Axiom B1 If hξ, wi ∈≺ and hζ, vi v hξ, wi, then hζ, vi ∈≺.
Axiom B2 If hξ, wi ∈≺ and w ∈ W D , then there are a ∈ A and v ∈ W suchthat hξ, (w, a), vi ∈≺.
Axiom B1 requires that ≺ is closed under a subsequence relation, while axiom B2states that a sequence ending with a decision piece can be extended to a longer
sequence in ≺. When an information protocol satisﬁes these basic axioms, wecall it a basic protocol.
As we shall see in the next subsection, basic protocols are used to describe
player’s personal views. On the other hand, to describe an objective situation,inductive game theory introduces the concept of full protocol, which is a restricted
form of basic protocols. For the detailed deﬁnition of full protocols, see [14].
2.2Players’ memories and inductively derived views

The central idea behind inductive game theory is the consideration of a player’s
memories, from which he/she derives a personal view of the objective situation.

Kaneko and Kline [14] formulated a player’s memories in terms of a memory
function, which maps each objective history of his/her play to the recollectionin the player’s mind.
Definition 1 (Memory function). Let Π be a basic protocol and Ξ i the set ofplayer i’s positions in Π; i.e., Ξ i = {hξ, wi ∈ Ξ | i ∈ π(w)}. A memory function
mi for player i is a function mapping each element in a set Di with Ξ i ⊆ Di ⊆ Ξ
to a ﬁnite sequence hζ, vi = h(v1 , b1 ), . . . , (vm , bm ), vi satisifying two conditions:(1) v = w; and (2) m ≥ 0 and vt ∈ W , bt ∈ Avt for all t = 1, . . . , m.
Here, the set Di , called a domain of accumulation (or a domain, for short)means the objective description of player i’s accumulated experiences. Condition
1 guarantees that the latest information piece is what player i receives at thecurrent position. Condition 2 is a minimal requirement to represent players’
memories with information protocols. The above memory functions can represent
players’ forgetfulness or incorrect recollections. We call each sequence hζ, vi givenby mi a memory thread, and each component (vt , bt ) or vm+1 a memory knot. The
memory function of player i takes all of player i’s perceptions of the objective
world; i.e., each player recognizes an objective world only through his memory
function.
We now present a basic framework for an objective world.
Definition 2 (Objective situation). An objective situation is a pair(Π o , mo ) such that Π o = (W o , Ao , ≺o , (π 0 , N ), ho ) is a full protocol with ho =(ho1 , . . . , hon ) and mo = (mo1 , . . . , mon ) is an n-tuple of memory functions in Π o .
On the other hand, a player’s personal view derived from his/her memories
is formulated in terms of the memory function. Let Ξ o be a set of positions in an
objective situation (Π o , moi ). For a domain Di with Ξ i ⊆ Di ⊆ Ξ o , the memory
kit TDi , which describes the accumulated experiences in the mind of player i, isdeﬁned as TDi := {moi hξ, wi | hξ, wi ∈ Di }. Basic experiences for player i is theset of all subsequences of every sequence in TDi , denoted ∆TDi . In terms of thebasic experiences, we deﬁne a player’s inductively derived view (or i.d.view, forshort) as follows 4 .
Definition 3 (I.d.view). Suppose the objective situation (Π o , mo ) is ﬁxed.
A pair (Π i , mi ) of a protocol and a memory function for player i is called an
inductively derived view from a memory kit TDi iﬀ
ID1 W i := {w ∈ W o | w occurs in some sequence in TDi }, W iD ⊆ W oD and
W iE ⊆ W oE ;ID2 Aiw ⊆ Aow for each w ∈ W i ;ID3 ∆TDi ⊆≺i ;4

The original deﬁnition in [14] requires one additional condition that mi is a perfectinformation memory function (i.e., mi hξ, wi = hξ, wi). However, in this paper weomit this condition since our formulation does not explicitly treat the classiﬁcationof memory functions.

ID4 π i (w) = π o (w) if w ∈ W iD and π i (w) = N i if w ∈ W iE , where N i := {j ∈N o | j ∈ π i (w) for some w ∈ W iD };ID5 hi (w) = hoi (w) for all w ∈ W iE .
In closing this section, to help readers understand the deﬁnition of inductive
game theory, we present a simple example called the absent-minded driver game
[14].
Example 1. Consider the one-player protocol (Π o , mo1 ) described by the upper
ﬁgure in Fig 1 (C). Now suppose that player 1 plays the game Π o three times and$%&'%()*+'),*'-+.)'/012!!

$3&'%()*+'),*'.*4567'/012$8&'%()*+'),*'),9+7'/012

!!

!"

!!

!"

"

"

"

"

!

!

!

!"

!!

!"

!!

"

"

"

"

!

!

#

#

!

#

!#

#

!#

"
!

!

#

#

!

Fig. 1. Player 1’s i.d.views in absent-minded driver game

experiences the sequences leading to w1 , w2 , and w3 in this order. After each of
the plays, the objective history of his/her behavior is described as the following
sequence: D10 := φ, D11 := {h(w, e), w1 i}, D12 := D11 ∪ {h(w, c), (w, e), w2 i}, D13 :=D12 ∪ {h(w, c), (w, c), w3 i}.
Let us consider the memory functions mR1 describing that player 1 can recall
only the latest memory knots within his experiences; that is, mR1 is deﬁned
as mR1 hwi = hwi, mR1 h(w, c), wi = h(w, c), wi, mR1 h(w, e), w1 i = h(w, e), w1 i,
mR1 h(w, c), (w, e), w2 i = h(w, e), w2 i, mR1 h(w, c), (w, c), w3 i = h(w, c), w3 i.
0
1
Thus the corresponding sequence of basic experiences is ∆TD:= φ, ∆TD
:=
1
1
2
1
3
2
{hwi, h(w, e), w1 i}, ∆TD1 := ∆TD1 ∪ {h(w, c), wi, h(w, e), w2 i}, ∆TD1 := ∆TD∪
1{h(w, c), w3 i}, and some of the player’s i.d.views obtained from the basic experiences are depicted as ﬁgures (A)–(C) in Fig 1 .
As the example shows, we may consider (possibly an inﬁnite number of)multiple i.d.views that diﬀer from the objective situation, examples of which are
given as the lower ﬁgures of (B) and (C) in Fig 1, respectively.

3

Logical Formulation of Inductive Game Theory

In this section, we ﬁrst brieﬂy overview the AGM theory of belief revision [1] thenpresents our logical formulation of inductive game theory. We here introduce aminimal setting which formulates a player’s beliefs about experienced sequences.
An extension, including the concepts of player’s strategy and payoﬀ, shall beconsidered in the next section.
3.1

AGM theory of belief revision

We suppose a propositional language L over a ﬁnite alphabet Σ of propositional
atomic variables s, t, . . . , s1 , s2 , . . . with the usual sentential connectives (¬, ∧,∨, →, and ↔). Propositional formulas are denoted by ϕ, ψ, . . . , ϕ1 , ϕ2 , . . ..
As the syntax for L, we suppose the usual inference system of classical propositional logic. Consequence relation ` is deﬁned by this logic. The set of all logicalconsequences of a set Γ ⊆ L (i.e., the set {ϕ | Γ ` ϕ}) is denoted Cn(Γ ). Deductively closed sets of propositional formulas, i.e. K = Cn(K), are denoted
K, K 0 , . . . and are called belief sets.
As the semantics for L, we suppose the usual truth assignment and models
of propositional logic. A truth assignment is a function σ : Σ → {1, 0}. A truth
assignment σ is called a model of a proposition ϕ if σ satisﬁes ϕ in the classicalsense. A model of a set of propositions Γ is a truth assignment σ that satisﬁes
all ϕ ∈ Γ .
The AGM theory of belief revision considers three types of operations on
belief sets: expansion +̇, contraction −̇ and revision ?. For a belief set K and aformula ϕ, expansion operation is deﬁned as K +̇ϕ := Cn(K ∪ {ϕ}). Contraction
operation is assumed to satisfy the following postulates.
P1 K −̇ϕ is a theory;
P2 K −̇ϕ ⊆ K;
P3 If ϕ 6∈ K then K −̇ϕ = K;
P4 If 6` ϕ then ϕ 6∈ K −̇ϕ;
P5 If ϕ ∈ K then K ⊆ (K −̇ϕ)+̇ϕ;
P6 If ` ϕ ↔ ψ then K −̇ϕ = K −̇ψ;
P7 (K −̇ϕ) ∩ (K −̇ψ) ⊆ K −̇(ϕ ∧ ψ);
P8 If ϕ 6∈ K −̇(ϕ ∧ ψ) then K −̇(ϕ ∧ ψ) ⊆ K −̇ϕ.
Revision operation can be deﬁned by Levy identity, i.e. K ? ϕ := (K −̇¬ϕ)+̇ϕ(cf. Chapter 1 in [9]).
3.2Logical formulation

As explained in the previous section, in inductive game theory, a unique objective
situation is described by a pair (Π o , mo ) of full protocol and memory functions,while player’s accumulated memories are described by basic experiences ∆TDi .
Thus, an accumulating process of memories for player i can be represented by
0
1
a sequence ∆TD, ∆TD, . . . which is obtained from a sequence Di0 , Di1 , . . . ofiihis/her objective histories.
Our logical formulation of inductive game theory is given along with thefollowing steps. We ﬁrst ﬁx the propositional language L whose atomic formulasare used to denote statements of the form “a sequence hξ, wi may occur”. Thus,
relations over sequences, such as negation and causality, can be represented by(compound) formulas. We next deﬁne a player’s belief state as a belief set, which
consists of beliefs about experienced sequences and some ex-ante beliefs about01
causality relations over sequences. For a given sequence ∆TD, ∆TD, . . . of basicii01experiences, the corresponding sequence Ki , Ki , . . . of belief sets is deﬁned by
the revision operator in AGM theory. On the other hand, as explained in theprevious subsection, we can obtain (possibly multiple) i.d.views from a givenjbasic experiences ∆TD. In our framework, an i.d.view (Π i , mi ) is deﬁned by aniassignment function σ such that σ(hξ, wi) = 1 if and only if hξ, wi ∈≺i . Finally,
we show that any assignment σ obtained from ∆TDi is a model for belief set Ki
obtained from ∆TDi . This means that a player’s i.d.view can be regarded as apersonal view constructed from the current belief state.
We here ﬁx the objective situation (Π o , mo )=(W o ,
o
o
o
o
o
o
0
1
A , ≺ , (π , N ), h , m ), sequence Di , Di , . . . of domains, and the correspond0
1
ing sequences ∆TD, ∆TD, . . . of basic experiences. For convention, we considerii0
the initial domain Di := φ.
The language L is deﬁned as follows.
Definition 4 (Language). The propositional language L is deﬁned by considering an alphabet Σ that provides a suﬃcient number of atomic propositions todenote any sequence in ≺o . That is, we suppose that there is a bijective mapping∗ : Σ →≺o .
To simplify our discussion, throughout we omit sequences whose length is 1; i.e.,sequences of the form hwi.
0
1
Next, for ∆TD, ∆TD, . . ., we deﬁne the corresponding sequence of the player’si2
belief sets.
j+1
jDefinition 5 (Belief sets). Suppose that ∆TD
is obtained from ∆TD
by
i
i
j+1
j
o
adding a sequence hζ, vi ∈≺ for each j = 0, 1, . . .. That is, ∆TDi := ∆TDi ∪j+1j{hζ, vi}. (If ∆TD\ ∆TD
includes multiple sequences, the following rules areiiapplied one by one to each of the sequences.) The corresponding sequence of theplayer i’s belief sets Ki0 , Ki1 , . . . is inductively deﬁned as follows.

– For each j = 0, 1, . . ., Kij is deﬁned to be the deductive closure of the union ofjj
two kinds of sets Ki,EX(called experienced beliefs) and Ki,CA(called beliefs
about causality), and Ki0 is ﬁxed as0
R1-1 Ki,EX:= {¬s | s ∈ Σ and the length of s∗ is 2},0
R1-2 Ki,CA := {s → t | s, t ∈ Σ and t∗ v s∗ }.
jj– For given Kij = Cn(Ki,EX∪ Ki,CA), the belief set Kij+1 is deﬁned by
j+1
jR2-1 Ki,EX:= Ki,EX\{¬t | t ∈ Σ, and s∗ v hζ, vi} ∪ {s | s∗ = hζ, vi}
j+1
jR2-2 Ki,CA:= Ki,CA.

Intuitively, R1-1 represents the player’s initial belief in the impossibility of any
elementary sequence. R1-2 and R2-2 represent the persistent belief about causality; i.e., if a sequence may occur then its subsequence also may occur. R2-1
represents the belief that any experienced sequence may occur.
For this formulation, the following theorem holds.
Theorem 1. For a given objective situation (Π o , mo ) and sequence of basic ex10, ∆TD, . . . obtained from a sequence of domains Di0 , Di1 , . . ., theperiences ∆TDii
corresponding sequence Ki0 , Ki1 , . . . can be characterized by revision operation ?
in AGM theory.
Proof. By Levy identity, it is enough to show that R2-1 in Deﬁnition 5 can becharacterized by contraction and expansion operations. That is, for any s ∈ Σwith s∗ = hξ, wi, if we deﬁne the operation of R2-1 as Kij+1 := (Kij −̇¬s)+̇s, then−̇ and +̇ satisfy postulates P1–P8 and the condition that (Kij +̇s) = Cn(Kij ∪{s}), respectively. Clearly, operation +̇ is an expansion operator in AGM theory.
We here only consider the case for P3 of −̇, since the other cases are trivial or
shown by similar argument. If ¬s 6∈ Kij , then ¬t 6∈ Kij for any t with t∗ v s∗ut
because s → t ∈ Kij . Therefore, by deﬁnition R2-1, Kij −̇¬s = Kij .
As a corollary of this theorem, any belief set appearing in a sequence Ki0 , Ki1 , . . .
is consistent. This indicates that our logic formulates a revision process where
the player always constructs consistent belief state from experiences.
j
Finally, for given basic experiences ∆TD(j = 0, 1, . . .), we deﬁne the correi
sponding assignment function as follows.
jDefinition 6 (Assignment function). For each ∆TD(j = 0, 1, . . .), the corijresponding assignment σi is an assignment satisfying the following conditions.

A1 For any s, t ∈ Σ with t∗ v s∗ , if σij (s) = 1 then σij (t) = 1.
A2 For any s ∈ Σ, if σij (s) = 1 and s∗ ∈ W D then there exists t ∈ Σ such thats∗ v t∗ and σij (t) = 1.
A3 For any s ∈ Σ such that the length of s∗ is 2, if s 6v hξ, wi for all hξ, wi ∈j∆TDthen σij (s) = 0.
ij
A4 For any s ∈ Σ, if s∗ ∈ ∆TD
then σij (s) = 1.
i
A5 For any s∗ with σ(s) = 1 satisﬁes conditions ID1, ID2, and ID4 in thedeﬁnition of i.d.view (i.e., Deﬁnition 3).

Intuitively, A1 and A2 respectively correspond to the basic axioms B1 and B2. A3means that a sequence consisting of any unexperienced sequence does not appear
in the i.d.view. A4 represents condition ID3 in the deﬁnition of i.d.view. A5
stipulates that the set of sequences determined by σij satisﬁes all the conditions
except for ID3 in the deﬁnition of i.d.view. By A5, we restrict our attention to
the assignments which can be regarded as an i.d.view.
By condition A4 in Deﬁnition 6, the following theorem holds.

Theorem 2. Suppose that an objective situation (Π o , mo ) and a sequence ofjdomains Di0 , Di1 , . . . in (Π o , mo ) are given. For j = 0, 1, . . ., let ∆TD
be basicijjjexperiences and Ki be the belief set obtained from ∆TDi . If σi is an assignmentjfunction obtained from ∆TD, then σij is a model for Kij .
i
In closing this section, we demonstrate a revision process for player’s beliefs
in terms of our logic in the case of the absent-minded driver game presented in
Example 1.
Example 2. Consider the protocol (Π o , mo1 ) described as the left ﬁgure in Fig 1.
Propositional atoms and the bijective mapping ∗ from Σ to ≺o are ﬁxed ass∗1 = h(w, e), w1 i,s∗2 = h(w, c), (w, e), w2 i,s∗3 = h(w, c), (w, c), w3 i,s∗4 = h(w, c), wi,s∗5 = h(w, e), w2 i,s∗6 = h(w, c), w3 i,s∗7 = h(w, c), (w, e), w1 i.

In fact, inﬁnitely many sequences other than those in the list above can beconsidered, but for simplicity, we here focus attention on sequences whose lengthis less than 3. Let us consider the situation that player 1 repeatedly plays thegame and accumulates experiences. Suppose that the process of accumulation is
D0 , . . . , D3 , such that D0 := φ, and Dj := Dj−1 ∪{s∗j } for each j =1, 2, and 3. If
the player’s memory function is assumed to be mR1 , the corresponding sequence0
3of basic experiences ∆TD, . . . , ∆TD
is φ, {s∗1 }, {s∗1 , s∗4 , s∗5 }, {s∗1 , s∗4 , s∗5 , s∗6 }. For
this sequence, the revision process of the belief sets is0
KEx:= {¬s1 , ¬s4 , ¬s5 , ¬s6 },0
KCA := {s2 → s4 ∧ s5 , s3 → s4 ∧ s6 , s7 → s1 ∧ s4 },1KEx:= {s1 , ¬s4 , ¬s5 , ¬s6 },2
KEx := {s1 , s4 , s5 , ¬s6 },3KEx:= {s1 , s4 , s5 , s6 },j0
1
where KCA
= KCA
for j = 1, 2, 3. Note that for ∆TD, both ¬s2 and ¬s3 are2
3
derivable, while for ∆TD and for ∆TD , none of s2 , s3 , s7 or their negations
can be derived. On the other hand, the corresponding sequence of assignment
functions (denoted σ j ) is deﬁned as

σ 0 (si ) = 0 for i = 1, . . . , 7,
σ 1 (s1 ) = 1, σ(si ) = 0 for i = 2, . . . , 7,
σ 2 (s1 ) = σ 2 (s4 ) = σ 2 (s5 ) = 1, σ 2 (s3 ) = σ 2 (s6 ) = 0,σ 3 (s1 ) = σ(s3 ) = σ 3 (s4 ) = σ 3 (s5 ) = σ 3 (s6 ) = 1.
For both σ 2 and σ 3 , any value is possible for s2 and s7 . This results in multiple i.d.views. For example, in the case that σ 2 (s2 ) = 1 and σ 2 (s7 ) = 0, thecorresponding i.d.view is the upper ﬁgure in Fig 1 (B), while in the case thatσ 2 (s2 ) = 0 and σ 2 (s7 ) = 0, it is the lower ﬁgure in Fig 1 (C).

4

Application to Festival GamesIn this section, we apply our logic to a speciﬁc inductive game, the festival game,
which was developed by Kaneko and Matsui [15] and Kaneko and Mitra [16]. The
main objective in this section is to formulate the festival games in terms of ourlogic, thereby showing the revision process of players’ beliefs. Especially, we focus
attention on the process where players’ prejudice is exposed as discriminatory
behaviors caused by their experiences. For this objective, we ﬁrst introduce thedeﬁnition of festival games following [15] and then present the formulation of
festival games in terms of our logic.
4.1

Festival games

The festival game considers that each of the players belongs to an ethnic group,and the player’s festival location is chosen. Each player then decides his attitude,
friendly or unfriendly, after observing ethnic groups at his location. Using thisframework, Kaneko and Matsui [15] studied how prejudices, as a fallacious imageof ethnic groups, arise from players’ experiences and how discrimination arises
as an unfriendly attitude.
Let us deﬁne the objective situation (Π o , mo ) = (W o , Ao , ≺o , (π o , N ), ho ,om ) for festival games. We consider the number of ethnic groups . The set
N = {1, . . . , n} of players is then partitioned into ethnic groups, e1 , . . . , e with
|Nj | ≥ 2 for j = 1, . . . , . The set Ao of actions consists of the choices of festival
locations, {f1 , . . . , fm }, and the attitude, friendly or unfriendly, denoted by frd
and unfrd, respectively. That is, Ao = {f1 , . . . , fm } ∪ {frd, unfrd}.
The festival game consists of two stages: the ﬁrst stage of choosing festival
locations and the second stage of acting in festivals. Since the ﬁrst stage is indeed
a simultaneous decision stage, we assume that player i chooses his/her festival
location at the position1, ln ), wi2 ihξ 1 , wi1 i = h(w11 , l1 ), . . . , (wi−1with i ≤ n, and l1 , . . . , li−1 ∈ {f1 , . . . , fm }. At that position, the player obtains
a memory thread mi hξ 1 , wi1 i = hwi1 i. This means that the players decide their
festival locations in order of their indices, but each cannot observe the choicesof the other players before making the decision.
In the second stage, player i’s position is given as2, ai−1 ), wi2 ihξi2 , wi2 i = h(w11 , l1 ), . . . , (wn1 , ln ), (w12 , a1 ), . . . , (wi−1with i ≤ n, and a1 , . . . , ai−1 ∈ {frd, unfrd}. For the position hξi2 , wi2 i, player
i obtains a memory thread as mi hξi2 , wi2 i = h(wi1 , li ), wi2 i. Unlike the settingof Kaneko and Matsui [15], information piece wi2 conveys to player i information about the number of participants in festival fj with li = fj for eachethnicity group. Formally, this information (denoted Ej ) is deﬁned by Ej =(x1 , x2 , . . . , x )j , where xk indicates the number of participants in ethnic groupk = 1, . . . , . We use notation wi2 = Ej to denote that player i receives ethnic
conﬁguration Ej .
Finally, player i’s position after the second stage is given ashξ 3 , wj3 i = h(w11 , l1 ), . . . , (wn1 , ln ), (w12 , a1 ), . . . , (wn2 , an ), wj3 iwith wj3 ∈ W E . Here, j = 1, . . . , m|N | · 2|N | since the resulting position is determined by the players’ choices of locations (among m alternatives) and attitude(between frd and unfrd). For the position hξ 3 , wj3 i, player i obtains a memory
thread as mi hξ 3 , wj3 i = h(wi1 , li ), (wi2 , ai ), wj3 i. The information piece wj3 provides
the numerical payoﬀs.
According to the above setting, ≺o consists of m|N | · 2|N | maximal sequencesof the form hξ 3 , wj3 i and their subsequences. The set W o is determined by ≺o ,and π is deﬁned such that π(wij ) = {i} for any wij ∈ W oD and π(wj3 ) = N for
any wj3 ∈ W E .
For determination of players’ payoﬀs ho = (ho1 , . . . , hon ), we ﬁrst introduce
players’ strategies. A strategy of player i (denoted sti ) is a pair (li , ri ) of choices
for the ﬁrst and second stages. Here, ri is a function mapping {f1 , . . . , fm } × E to{frd, unfrd}, where E is the collection of all possible ethnicity conﬁgurations. We
here note that every player may change strategy in the recurrent plays of thegame (Π o , mo ). To indicate strategy st0i that is deviated from sti by replacing
the choice of location li with li0 , we use expression sti [li /li0 ]. The replacement ofa player’s attitude is indicated analogously.
Let Si be the set of strategies for player i. For a strategy proﬁle st ∈ S1 ×
· · · × Sn , the player’s payoﬀ is determined by his/her attitude and the mood of
the location he chose. The mood of festival fk with fk = li for player i (denotedµi ) is given∑by the number of friendly people at li other than player i; that is,µi (l, r) = lj =li ,j6=i rj (lj , Ej ), where l = (l1 , . . . , ln ), r = (r1 , . . . , rn ), and frd
and unfrd are interpreted as 1 and 0, respectively. We then deﬁne the payoﬀ
function of player i as hi (li , ri ) = ri (li , Ei ) · µ(l, r).
4.2

Logical formulation of festival games

To give a logical formulation of the above example, we here extend our logic
introduced in the previous section to capture the concepts of strategies andpayoﬀs. We ﬁrst introduce the language as follows:
Definition 7 (Language for festival games). The language L is deﬁned byﬁxing the alphabet Σ to denote:– occurrence of any sequence in ≺o ,– statements of the form “player i chooses fj as his festival location,” denoted
li = fj ,– statements of the form “the ethnicity conﬁguration at festival fj is Ej ” (denoted Ej ),– statements of the form “player i chooses frd (unfrd) as his attitude in thefestival he chose,” denoted ai = frd (ai = unfrd, respectively),– statements of the form “player i’s payoﬀ is x”, denoted payoﬀ i = x.
For readability, we introduce equational expressions instead of single charactersto denote these propositional atoms.
In terms of this language, we next give the deﬁnition of the sequence of
player i’s belief sets, Ki0 , Ki1 , . . .. The idea behind our deﬁnition is as follows. In
addition to Deﬁnition 5, we also consider the player’s belief about his/her current
strategy, experienced ethnicity conﬁgurations. Strategy sti = (li , ri ) with li = fk ,ri (li , Ej ) = frd/unfrd is described as the set of formulas li = fk ∧ (li = fk ∧ Ek ) →{frd, unfrd} for all Ek ∈ E, where the expression {frd, unfrd} denotes one of frd
and unfrd. The latest decisions of location and attitude, as well as the resulting
payoﬀ, are uniquely determined in the current belief set.
j+1
Definition 8 (Belief sets in festival games). Suppose that ∆TD
is obij+1otained by adding a sequence hζ, vi ∈≺ for each j = 0, 1, . . .. That is, ∆TDi :=j∆TD∪ {hζ, vi}. Let stji = (fj , ri ) be a strategy of player i at the j-th play ofithe game. (For convention, we consider st0i := st1i .) The corresponding sequenceof his/her belief sets Ki1 , Ki2 , . . . is deﬁned as follows.

– For each j = 0, 1, . . ., Kij is deﬁned to be the deductive closure of the union ofjjjjfour kinds of sets Ki,EX, Ki,CA, Ki,ST, Ki,AUX(where the third and fourth
are respectively called beliefs about strategy and auxiliary beliefs), and Ki0 is
ﬁxed as:0
R1-1 Ki,EX:= {¬s | s ∈ Σ and the length of s∗ is 2},0
R1-2 Ki,CA := {s → t | s, t ∈ Σ and t∗ v s∗ }∪{li = fj ↔ ¬li = fk | k 6= j, j ≥ l, k ≥ m}∪{Ej ↔ ¬Ek | Ej 6= Ek , Ej , Ek ∈ E}∪{ai = {frd, unfrd} ↔ ¬ai = {unfrd, frd}}∪{li = fk ∧ Eh → {frd, unfrd} ↔ ¬(li = fk ∧ Eh → {frd, unfrd})}∪{payoﬀ i = x → ¬payoﬀ i = x0 | x 6= x0 },0
R1-3 Ki,ST := {fj } ∪ {fj ∧ Ej → ai = {frd, unfrd} | Ej ∈ E, {frd, unfrd} isdetermined by ri0 in st0i },0R1-4 Ki,AUX:= {(s → payoﬀ i = x) ∧ (s0 → payoﬀ i = x0 ) → ¬s | x < x0 }.
j
j
j
j
j
– For given Ki = Cn(Ki,EX∪ Ki,CA∪ Ki,ST∪ Ki,AUX) the belief set Kij+1 isdeﬁned by
R2-1 (1) Kij+1 := Θ \ {¬s | s ∈ Σ and s∗ v hζ, vi} ∪ {s | s∗ = hζ, vi},
where Θ is obtained by the following rules R2-1 (2)–(4):j\ {¬li = fk } ∪ {li = fk },R2-1 (2) if hζ, vi = h(wi1 , fk ), wi2 i, then Θ := Ki,EXj
R2-1 (3) if hζ, vi = h(wi1 , fk ), wi2 i where wi2 = Ek , then Θ := Ki,EX\{¬Ek } ∪ {Ek },R2-1 (4) if hζ, vi = h(wi1 , fk ), (wi2 , ai ), w3 i where wi2 = Ek and hi (w3 ) = x,jthen Θ := Ki,EX\ {¬ϕ} ∪ {ϕ} where ϕ ≡ li = fk ∧ (li = fk ∧ Ek → ai ={frd, unfrd}) → payoﬀ i = x},j+1
jR2-2 Ki,CA:= Ki,CA,jj+1
jR2-3 (1) if stj+1=
stii [fk /fh ], then Ki,ST := Ki,ST \ {¬li = fh } ∪ {li = fh },

j+1
j
0
R2-3 (2) if stj+1= stji [ri /ri∧i ], then Ki,ST := Ki,ST \ {¬ρi } ∪ {ρi } where ρi
is formula of the form k=1,...,m, E∈E (li = fk ∧ E → ai = {frd, unfrd})
determined by ri ,j+1
jR2-4 Ki,AUX:= Ki,AUX.

Intuitively, R1-1 and R2-1 revise the beliefs about experienced sequences, while
R1-2 and R2-2 mean the beliefs about causality. These are essentially the sameas Deﬁnition 5, but R1-2 is extended to maintain the uniqueness of choicesof locations, attitude, the resulting payoﬀ, and ethncity conﬁgurations. R1-3
and R2-3 revise the current strategy. Finally, R1-4 and R2-4 revise the player’s
strategy if there is another strategy which improves the latest payoﬀ.
We here note that for all the operations in the above deﬁnition except forthe belief revision for experienced sequences, every removed formula is identicalto the negation of corresponding added formula. Thus, if we consider the subtraction (\) and the addition (∪) to be −̇ and +̇, respectively, these operations
clearly satisfy postulates P1–P8 and the condition that Kij +̇ϕ = Cn(Kij ∪ {ϕ}).
Therefore, by this fact and Theorem 1, we can prove the following theorem.
Theorem 3. For a given objective situation (Π o , mo ) in a festival game, se0
1
quence of basic experiences ∆TD, ∆TD, . . ., and sequence of strategies st0i , st1i , . . .,ii01
the corresponding sequence Ki , Ki , . . . defined by Definition 8 can be realized byrevision operation ? in AGM theory.
Moreover, by our construction of the initial belief set, Ki0 , and by this theorem, every belief set appearing in the sequence is guaranteed to be consistent.
We ﬁnally deﬁne assignment functions that are obtained from given basic
experiences and a player’s strategy.
jand the strategy stji
Definition 9 (Assignment functions). For each ∆TDiof the j-th play of the game for player i, the corresponding assignment σij is an
assignment function satisfying conditions A1–A5 in Deﬁnition 6 and the following.

A6 σ(li = fk ) = 1 iﬀ (wi1 , fk ) appears in the sequence hξ j,3 , wj,3 i.
A7 σ(Ek ) = 1 iﬀ f1 , . . . , fm appears in the sequence hξ j,3 , wj,3 i and Ek is theethnicity conﬁguration derived from f1 , . . . , fm .
A8 σ(ai = frd) = 1 iﬀ (wij,2 , frd) appears in the sequence hξ j,3 , wj,3 i.
Intuitively, A6 means that player i chooses fj as his/her location. A7 represents
the location conﬁguration. A8 means that player i chooses frd (or unfrd) as theattitude. For this semantics, the following theorem still holds.
Theorem 4. Suppose that an objective situation (Π o , moi ) and a sequence ofjdomains Di0 , Di1 , . . . in (Π o , moi ) are given. For j = 0, 1, . . ., let ∆TD
be basicijjexperiences, sti be the strategy of player i, and Ki be the belief set obtained fromjj
∆TD
. If σij is an assignment function obtained from ∆TD, then σij is a modeliijfor Ki .

5Concluding Remarks

This paper provided a dynamic framework to revise players’ personal viewsof their experiences following inductive game theory. In addition, we applied
our framework to festival games to explain how prejudices and discrimination
emerge. In a subsequent paper, we will investigate festival games within ourframework.
We ﬁnally comment on our ﬁndings. First, our inductive derivation diﬀers
from learning theory approaches in the literature such as those of Fudenberg andLevine [8]. Standard learning theories do not focus on the learning of structure,but on the learning of beliefs of opponents’ actions. Second, while making useof the framework of inductive game theory developed by Kaneko and Kline andKaneko and Matsui, our theory focuses on a permanent revision process based on
the player’s experiences. While the developers of inductive game theory focusedon how to construct a player’s view consistent with his experiences, we focusedon how to change a playerfs personal view when he has a new experience.
Finally, the treatment of experiences in our theory slightly diﬀers from thestandard belief revision theory pioneered by Alchourrón, Gärdenfors and Makinson [1] (so-called AGM theory). In contrast to AGM theory, our theory distinguishes between what a player originally believes and what he logically derives
from the original belief. This is based on our motivation that the players are
not simply a database, but have some logical abilities. This approach is similar to the belief base theory, which distinguishes between the belief base andthe consequence.5 However, the theory of the belief base focuses neither on the
new observations as the experiences in our theory nor on their accumulation.
Our theory combines the use of accumulated observations and beliefs logicallyderived from them for decision-making.
In further research, we will investigate (i) how players with diﬀerent views
make decisions in our theory and (ii) the direction of various players’ views after
repetitive revision. In standard game theory, players face an identical situationand know that even when considering incomplete information games. Our theory
is a ﬁrst step to inquiring whether it is possible to achieve and to analyze misunderstandings pointed out by Kaneko [11]. In a society in which people do notnecessarily recognize identical environments, we wonder how people harmonize
with each other. This question will drive future research.
Acknowledgment
This paper is originally circulated as “Revision of beliefs with perceived experiences in info-memory protocols.” Ishikawa is grateful to Mamoru Kaneko andNobu-Yuki Suzuki for the valuable comments and stimulative discussions. I also
thank Kim Cranney, Tai-Wei Hu, and Oliver Schulte for giving comments on theearly version of this paper. Ishikawa receives Grants-in-Aid for Young Scientists(B), No. 21730151.
5

See Chapter 1 in Gärdenfors [9].

References
1. C. E. Alchourrón, P. Gärdenfors, and D. Makinson. On the logic of theorychange: Partial meet contraction and revision functions. Journal of Symbolic Logic,
50(2):510–530, 1985.
2. K. Binmore. Modeling rational players (part i). Economics and Philosophy, 3:179–
214, 1987.
3. O. Board. Dynamic interactive epistemology. Games and Economic Behavior,
49(1):49–80, October 2004.
4. G. Bonanno. The logical representation of extensive games. International Journalof Game Theory, 22:153–169, 1991.
5. H. van Ditmarsch, W. van der Hoek, and B. Kooi. Dynamic Epistemic Logic.
Springer Publishing Company, Incorporated, 2007.
6. Y. Feinberg. Subjective reasoning–dynamic games. Games and Economic Behavior, 52:54–93, 2005.
7. Y. Feinberg. Subjective reasoning–splutions. Games and Economic Behavior,
52:94–132, 2005.
8. D. Fudenberg and D. K. Levine. Self-conﬁrming equilibrium. Econometrica,
61(3):523–545, 1993.
9. P. Gärdenfors, editor. Belief Revision. Cambridge Unviersity Press, Cambridge,
UK, 1992.
10. W. van der Hoek and M. Pauly. Modal logic for games and information. In
J. van Benthem, P. Blackburn, and F. Wolter, editors, Handbook of Modal Logic,
chapter 20, pages 1077–1148. Elsevier, 2007.
11. M. Kaneko. Game Theory and Mutual Misunderstanding, Scientific Dialogues inFive Acts. Springer, Cambridge, MA, 2004.
12. M. Kaneko and J. J. Kline. Inductive game theory: A scenario. Journal of Mathematical Economics, 44:1332–1363, 2008. Corrigendum: This journal, 46: 620–622,
2010.
13. M. Kaneko and J. J. Kline. Information protocols and extensive games in inductive
game theory. Game Theory and Applications, 13:57–83, 2008.
14. M. Kaneko and J. J. Kline. Partial memories, inductively derived views, andtheir interactions with behavior. 2010. forthcoming in Economic Theory, DOI:
10.1007/s00199-010-0519-0.
15. M. Kaneko and A. Matsui. Inductive game theory: Discrimination and prejudices.
Journal of Public Economic Theory, 1(1):101–137, 1999. Erratum: this journal,
3(3):347, 2001.
16. M. Kaneko and A. Mitra. Discrimination in festival games with limited observability and accessibility. Mathematical Social Science, 62:34–45, 2011.
17. J. van Benthem. Extensive games as process models. Journal of Logic, Language,
and Information, 11:289–313, 2002.