Department of Social Systems and Management
Discussion Paper Series

No.1285

Belief Revison for Inductive Game Theory

byKoji HASEBE and Ryuichiro ISHIKAWA

November 2011

UNIVERSITY OF TSUKUBA
Tsukuba, Ibaraki 305-8573
JAPAN

Belief revision for inductive game theory
Koji Hasebe† and Ryuichiro Ishikawa‡
Faculty of Engineering, Information and Systems,
University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan

E-mail† : hasebe@cs.tsukuba.ac.jp
E-mail‡ : ishikawa@sk.tsukuba.ac.jp

Abstract
Inductive game theory captures how a player inductively derives his/her personal views fromexperiences. The player may have multiple views, some of which differ 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 a belief
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 asmodels for the current belief set. We also present an application of our framework to a class of
inductive games, called festival games, and show how to derive prejudices and discrimination insociety.

JEL Classification: A12; C70; D83.
Keywords: Belief revision; Levi identity; Perceived experiences; Inductive game theory.

1

2

K. Hasebe, R. Ishikawa

1.

Introduction and Overview

Standard game theory assumes players to have sufficient 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 the experiences of individuals with bounded cognitive abilities and is revised through time. Inductive game theory, originally introduced by Kaneko
and Matsui [15] and Kaneko and Kline [12, 13, 14], explores this issue andcaptures how a player inductively derives his/her knowledge and beliefs ofthe 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 a given situation.
They therefore accumulate their experiences through their choices of available actions, and construct their personal views from their experiences. In
the players’ construction of personal views, the players have different personal views based on their different experiences even when the players face
an identical situation. Moreover, a player may have multiple views, some differing from the objective situation, which the player may revise with further
experiences.
The difference in players’ views is due not only to their experiences, butalso to their memories, which are represented by memory functions. By introducing memory functions, players’ memory capacities can be represented
in various ways, although extensive games in standard game theory placesome restrictions on the representations. Therefore, even when gathering
many experiences, a player may only partially recall his experiences.
While inductive game theory provides a framework to derive a personalview consistent with a player’s memories of the experiences, it has been lessstudied how the derived view is revised by additional experiences. This paper
provides a framework for revision in inductive game theory based on the ideaof AGM (Alchourrón-Gärdenfors-Makinson) theory of belief revision [1]. By
introducing the revision process, we reflect a player’s inductive inference indecision-making.
Since standard game theory assumes players to have sufficient knowledge
or common belief of the structure, it is not good at treating inductive inferences of the structure. Revision of beliefs in (epistemic) logic has also
been applied to standard game theory as in Binmore [2], Bonnano [4], vanBenthem [17], Board [3], and Feinberg [6, 7]1 . However, such studies usually1

A theory of belief revision in itself is now a very active area of research, and it connects

Belief revision for inductive game theory3

focus on beliefs about opponent players’ actions. While it is important toconsider belief formations of opponents’ actions in interactive situations, weneed to ask whether such beliefs are plausible when the formation heavily depends on (common) knowledge of the structure. Inductive game theory andthis paper truly ask the question: How do players cognize the (interactive)
situations that they face?
Our logic is based on standard classical propositional logic. Basic statements in inductive game theory, such as the histories of players’ actions andpayoffs are associated with propositional atomic formulas, thereby describing causality relations between histories or players’ strategies as compound
formulas. In terms of this language, a player’s belief state is described by abelief set of formulas; thus, a revision process for the belief states is describedusing a revision operation in AGM theory. In this setting, the player’s personal views are described as models for the current belief set (i.e., assignments of truth values that satisfy all the formulas of the belief set) in thesemantics.
By means of this logic, we also present an application to festival games,
which are specific 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 the mechanisms of prejudices and discriminations resulting fromexperiences. We demonstrate that our logic handles the revision processthat generates prejudices and discriminations.
This paper is organized as follows. The following section gives the definition of inductive game theory following Kaneko and Kline [14]. Section
3 presents our logic for belief revision. Section 4 presents an application of
our belief revision to festival games. Finally, Section 5 gives conclusions anddiscusses further research.

2.

Inductive Game Theory

2.1.

Information protocols

We define an information protocol Π below. Let W be a nonempty finite
set of information! pieces, A be am nonempty finite set of actions, and ≺ be a
finite subset of ∞m=0 ((W × A) × W ). Aw ⊆ A is the available action atw ∈ W . When m = 0, (W × A)0 × W is regarded as W of a unary relation
on W .
with dynamic epistemic logic. Comprehensive surveys were published by van Ditmarsch,
et al. [5], van der Hoek and Pauly [10].

4

K. Hasebe, R. Ishikawa

The relation ≺ is called a causality relation. Each element %(w1 , a1 ), . . . ,(wm , am ), wm+1 & ∈≺ is called a!sequence of length m + 1. Expression %ξ, w&mdenotes a generic element of ∞m=0 ((W × A) × W ), and %w& is that of(W × A)0 × W . Using a causal relation ≺, we give a partition on W . That
is, W D := {w ∈ W | %(w, a), v& for some a ∈ A and v ∈ W } is called a set ofdecision pieces and W 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 payoff assignment is given as a function hi : W E → R for all i ∈ N .
We then complete the definition of an information protocol as a quintupleΠ = (W, A, ≺, (π, N ), (hi )i∈N ).

To describe a player’s personal view and an objective situation withinformation protocols, we require two basic axioms and three non-basic axioms.
the basic axioms, we define a subsequence of a sequence in!∞ To stipulate
m × W ). We say that %(w , a ), . . . , (w , a ), w
((W
×
A)
1 1
m m
m+1 & is a subm=0
sequence of %(v1 , b1 ), . . . , (vk , bk ), vk+1 & iff [(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 %ξ, wm+1 & ( %ζ, vk+1 & to state that %ξ, wm+1 & is a subsequenceof %ζ, vk+1 &. A supersequence is defined likewise. A sequence %ξ, w& is maxial iff there is no proper supersequence in ≺. A position %ξ, v& is an initial
segment of some maximal sequence. The set of positions is denoted Ξ.
We now state the basic axioms.
Axiom B1 If %ξ, w& ∈≺ and %ζ, v& ( %ξ, w&, then %ζ, v& ∈≺.
Axiom B2 If %ξ, w& ∈≺ and w ∈ W D , then there are a ∈ A and v ∈ Wsuch that %ξ, (w, a), v& ∈≺.
Axiom B1 requires that ≺ is closed under a subsequence relation, while axiom
B2 states that a sequence ending with a decision piece can be extended toa longer sequence in ≺. When an information protocol satisfies these basic
axioms, we call it a basic protocol.
As we shall see in the next subsection, basic protocols are used to describe a player’s personal views. On the other hand, to describe an objective
situation, inductive game theory introduces the concept of the full protocol,
which is a restricted form of basic protocols. For the detailed definition offull protocols, see [14].

Belief revision for inductive game theory

2.2.

5

Players’ memories and inductively derived views

The central idea behind inductive game theory is the consideration of aplayer’s memories, from which he/she derives a personal view of the objective
situation. Kaneko and Kline [14] formulated a player’s memories in termsof a memory function, which maps each objective history of his/her play tothe recollection in the player’s mind.
Definition 2.1 (Memory function). Let Π be a basic protocol and Ξi theset of player i’s positions in Π; i.e., Ξi = {%ξ, w& ∈ Ξ | i ∈ π(w)}. A
memory function mi for player i is a function mapping each element in a set
Di with Ξi ⊆ Di ⊆ Ξ to a finite sequence %ζ, v& = %(v1 , b1 ), . . . , (vm , bm ), v&
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)
is the objective description of player i’s accumulated experiences. Condition
1 guarantees that the latest information piece is what player i receives atthe current 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 eachsequence %ζ, v& given by 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/her memory function.
We now present a basic framework for an objective world.
Definition 2.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 withho = (ho1 , . . . , hon ) and mo = (mo1 , . . . , mon ) is an n-tuple of memory functionsin Π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 themind of player i, is defined as TDi := {moi %ξ, w& | %ξ, w& ∈ Di }. Basicexperiences for player i are the set of all subsequences of every sequence in
TDi , denoted ∆TDi . In terms of the basic experiences, we define a player’s
inductively derived view (or i.d.view, for short) as follows 2 .
2The original definition in [14] requires one additional condition that mi is a perfect-

6

K. Hasebe, R. Ishikawa








































































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

Definition 2.3 (I.d.view). Suppose the objective situation (Πo , mo ) is fixed.
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 iff
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 ;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 definition of inductive game theory, we present a simple example called the absent-minded
driver game [14].
Example 2.4. Consider the one-player protocol (Πo , mo1 ) described by theupper figure in Fig 1 (C). Now suppose that player 1 plays the game Πothree times and experiences the sequences leading to w1 , w2 , and w3 in thisorder. After each of the plays, the objective history of his/her behavior isdescribed as the following sequence: D10 := φ, D11 := {%(w, e), w1 &}, D12 :=D11 ∪ {%(w, c), (w, e), w2 &}, D13 := D12 ∪ {%(w, c), (w, c), w3 &}.
Let us consider the memory functions mR1 describing that player 1 canrecall only the latest memory knots within his experiences; that is, mR1 is
information memory function (i.e., mi !ξ, w" = !ξ, w"). However, we omit this conditionin this paper since our formulation does not explicitly treat the classification of memory
functions.

Belief revision for inductive game theory7

defined as mR1 %w& = %w&, mR1 %(w, c), w& = %(w, c), w&, mR1 %(w, e), w1 & =%(w, e), w1 &, mR1 %(w, c), (w, e), w2 & = %(w, e), w2 &, mR1 %(w, c), (w, c), w3 & =%(w, c), w3 &.
Thus, the corresponding sequence of basic experiences is ∆TD0 1 := φ,∆TD1 1 := {%w&, %(w, e), w1 &}, ∆TD2 1 := ∆TD1 1 ∪ {%(w, c), w&, %(w, e), w2 &},∆TD3 1 := ∆TD2 1 ∪ {%(w, c), w3 &}, and some of the player’s i.d.views obtained
from the basic experiences are depicted as figures (A)–(C) in Fig. 1.
As the example shows, we may consider (possibly an infinite number of)multiple i.d.views that differ from the objective situation, examples of which
are given as the lower figures of (B) and (C) in Fig 1, respectively.

3.

Logical Formulation of Inductive Game Theory

In this section, we first briefly overview the AGM theory of belief revision[1] and then present our logical formulation of inductive game theory. We
here introduce a minimal setting that formulates a player’s beliefs about
experienced sequences. An extension, including the concepts of a player’strategy and payoff, is considered in the next section.
3.1.

AGM theory of belief revision

We suppose a propositional language L over a finite 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 classicalpropositional logic. Consequence relation . is defined by this logic. The setof all logical consequences 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 # , . . . 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 σ satisfies ϕ inthe classical sense. A model of a set of propositions Γ is a truth assignment
σ that satisfies all ϕ ∈ Γ.
The AGM theory of belief revision considers three types of operations on
belief sets: expansion +̇, contraction −̇ and revision (. For a belief set K anda formula ϕ, the expansion operation is defined as K +̇ϕ := Cn(K ∪ {ϕ}).
The contraction operation is assumed to satisfy the following postulates.
P1 K −̇ϕ is a theory;

8

K. Hasebe, R. Ishikawa

P2 K −̇ϕ ⊆ K;

P3 If ϕ 0∈ K then K −̇ϕ = K;
P4 If 0. ϕ then ϕ 0∈ K −̇ϕ;

P5 If ϕ ∈ K then K ⊆ (K −̇ϕ)+̇ϕ;

P6 If . ϕ ↔ ψ then K −̇ϕ = K −̇ψ;

P7 (K −̇ϕ) ∩ (K −̇ψ) ⊆ K −̇(ϕ ∧ ψ);

P8 If ϕ 0∈ K −̇(ϕ ∧ ψ) then K −̇(ϕ ∧ ψ) ⊆ K −̇ϕ.
The revision operation can be defined by Levy identity, i.e.
(K −̇¬ϕ)+̇ϕ (cf. Chapter 1 in [9]).
3.2.

K ( ϕ :=

Logical 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 a player’s accumulated memories are described by basic experiences ∆TDi . Thus, an accumulation process for the memories of player
i can be represented by a sequence ∆TD0 i , ∆TD1 i , . . . which is obtained froma sequence Di0 , Di1 , . . . of his/her objective histories.
Our logical formulation of inductive game theory comprises the following steps. We first fix the propositional language L whose atomic formulas
are used to denote statements of the form “a sequence %ξ, w& may occur”.
Thus, relations over sequences, such as negation and causality, can be represented by (compound) formulas. We next define a player’s belief state
as a belief set, which consists of beliefs about experienced sequences andsome ex-ante beliefs about causality relations over sequences. For a given
sequence ∆TD0 i , ∆TD1 i , . . . of basic experiences, the corresponding sequence
Ki0 , Ki1 , . . . of belief sets is defined by the revision operator in AGM theory. On the other hand, as explained in the previous subsection, we canobtain (possibly multiple) i.d.views from given basic experiences ∆TDj i . In
our framework, an i.d.view (Πi , mi ) is defined by an assignment function σsuch that σ(%ξ, w&) = 1 if and only if %ξ, w& ∈≺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 a personalview constructed from the current belief state.
We here fix the objective situation (Πo , mo )=(W o ,
o
o
o
o
o
o
0
1
A , ≺ , (π , N ), h , m ), the sequence Di , Di , . . . of domains, and the corresponding sequences ∆TD0 i , ∆TD1 i , . . . of basic experiences. For convention,
we consider the initial domain Di0 := φ.

Belief revision for inductive game theory

9

The language L is defined as follows.
Definition 3.1 (Language). The propositional language L is defined byconsidering an alphabet Σ that provides a sufficient number of atomic propositions to denote any sequence in ≺o . That is, we suppose that there is abijective mapping ∗ : Σ →≺o .
To simplify our discussion, throughout we omit sequences whose lengthis 1; i.e., sequences of the form %w&.
Next, for ∆TD0 i , ∆TD1 2 , . . ., we define the corresponding sequence of theplayer’s belief sets.
Definition 3.2 (Belief sets). Suppose that ∆TDj+1
is obtained from ∆TDj i byiadding a sequence %ζ, v& ∈≺o for each j = 0, 1, . . .. That is, ∆TDj+1:= ∆TDj i ∪i{%ζ, v&}. (If ∆TDj+1\ ∆TDj i includes multiple sequences, then the followingirules are applied one by one to each of the sequences.) The corresponding
sequence of player i’s belief sets Ki0 , Ki1 , . . . is inductively defined as follows.
• For each j = 0, 1, . . ., Kij is defined to be the deductive closure of thejjunion of two kinds of sets Ki,EX(called experienced beliefs) and Ki,CA(called beliefs about causality), and Ki0 is fixed 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∗ ( s∗ }.

jj• For given Kij = Cn(Ki,EX∪ Ki,CA), the belief set Kij+1 is defined by
j+1
jR2-1 Ki,EX:= Ki,EX\{¬t | t ∈ Σ, and s∗ ( %ζ, v&} ∪ {s | s∗ = %ζ, v&}
j+1
jR2-2 Ki,CA:= Ki,CA.

Intuitively, R1-1 represents the player’s initial belief in the impossibilityof 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 3.3. For a given objective situation (Πo , mo ) and sequence of basic
experiences ∆TD0 i , ∆TD1 i , . . . obtained from a sequence of domains Di0 , Di1 , . . .,the corresponding sequence Ki0 , Ki1 , . . . can be characterized by revision operation ( in AGM theory.

10

K. Hasebe, R. Ishikawa

Proof. Using the Levy identity, it is enough to show that R2-1 in Definition
3.2 can be characterized by contraction and expansion operations. That is,for any s ∈ Σ with s∗ = %ξ, w&, if we define 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 0∈ Kij , then¬t 0∈ Kij for any t with t∗ ( s∗ because s → t ∈ Kij . Therefore, by definition,
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 a consistent belief state fromexperiences.
Finally, for given basic experiences ∆TDj i (j = 0, 1, . . .), we define thecorresponding assignment function as follows.
Definition 3.4 (Assignment function). For each ∆TDj i (j = 0, 1, . . .), thecorresponding assignment σij is an assignment satisfying the following conditions.
A1 For any s, t ∈ Σ with t∗ ( 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 ∈ Σ suchthat s∗ ( t∗ and σij (t) = 1.
A3 For any s ∈ Σ such that the length of s∗ is 2, if s 0( %ξ, w& for all%ξ, w& ∈ ∆TDj i then σij (s) = 0.
A4 For any s ∈ Σ, if s∗ ∈ ∆TDj i then σij (s) = 1.

A5 Any s∗ with σ(s) = 1 satisfies conditions ID1, ID2, and ID4 in thedefinition of i.d.view (i.e., Definition 2.3).
Intuitively, A1 and A2 respectively correspond to the basic axioms B1
and B2. A3 means that a sequence consisting of any unexperienced sequence
does not appear in the i.d.view. A4 represents condition ID3 in the definitionof i.d.view. A5 stipulates that the set of sequences determined by σij satisfies
all the conditions except for ID3 in the definition of i.d.view. With A5, we
restrict our attention to the assignments that can be regarded as an i.d.view.
By condition A4 in Definition 3.4, the following theorem holds.
Theorem 3.5. Suppose that an objective situation (Πo , mo ) and a sequenceof domains Di0 , Di1 , . . . in (Πo , mo ) are given. For j = 0, 1, . . ., let ∆TDj i be

Belief revision for inductive game theory

11

basic experiences and Kij be the belief set obtained from ∆TDj i . If σij is an
assignment function obtained from ∆TDj i , then σij is a model for Kij .
In closing this section, we demonstrate a revision process for a player’s
beliefs in terms of our logic in the case of the absent-minded driver gamepresented in Example 2.4.
Example 3.6. Consider the protocol (Πo , mo1 ) described as the left figure in
Fig 1. Propositional atoms and the bijective mapping ∗ from Σ to ≺o are
fixed ass∗1 = %(w, e), w1 &,s∗2 = %(w, c), (w, e), w2 &,s∗3 = %(w, c), (w, c), w3 &,s∗4 = %(w, c), w&,s5∗ = %(w, e), w2 &,s6∗ = %(w, c), w3 &,s7∗ = %(w, c), (w, e), w1 &.

In fact, infinitely many sequences other than those in the list above can beconsidered, but for simplicity, we here focus attention on sequences whose
length is less than 3. Let us consider the situation that player 1 repeatedly
plays the game and accumulates experiences. Suppose that the process ofaccumulation 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 sequence of basic experiences ∆TD0 , . . . , ∆TD3 is φ,{s∗1 }, {s∗1 , s∗4 , s∗5 }, {s∗1 , s∗4 , s∗5 , s∗6 }. For this sequence, the revision process ofthe belief sets is
0 := {¬s , ¬s , ¬s , ¬s },
KEx
1
4
5
6
0 := {s → s ∧ s , s → s ∧ s , s → s ∧ s },
KCA
2
4
5 3
4
6 7
1
4
1 := {s , ¬s , ¬s , ¬s },
KEx
1
4
5
6
2 := {s , s , s , ¬s },
KEx
1 4 5
6
3 := {s , s , s , s },KEx
1 4 5 6j0
where KCA
= KCA
for j = 1, 2, 3. Note that for ∆TD1 , both ¬s2 and¬s3 are derivable, while for ∆TD2 and for ∆TD3 , none of s2 , s3 , s7 or their
negations can be derived. On the other hand, the corresponding sequenceof assignment functions (denoted σ j ) is defined 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.

12

K. Hasebe, R. Ishikawa

For both σ 2 and σ 3 , any values are 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,
the corresponding i.d.view is the upper figure in Fig 1 (B), while in the casethat σ 2 (s2 ) = 0 and σ 2 (s7 ) = 0, it is the lower figure in Fig 1 (C).

4.

Application to Festival GamesIn this section, we apply our logic to a specific 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 our logic, 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 thisobjective, we first introduce the definition 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 this framework, Kaneko and Matsui [15] studied how prejudices,
as a fallacious image of ethnic groups, arise from players’ experiences andhow discrimination arises as an unfriendly attitude.
Let us define 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 first stage of choosing festival
locations and the second stage of acting in festivals. Since the first stage isindeed a simultaneous decision stage, we assume that player i chooses his/herfestival location at the position1%ξ 1 , wi1 & = %(w11 , l1 ), . . . , (wi−1, ln ), wi2 &with i ≤ n, and l1 , . . . , li−1 ∈ {f1 , . . . , fm }. At that position, the player
obtains a memory thread mi %ξ 1 , wi1 & = %wi1 &. This means that the players decide their festival locations in order of their indices, but each cannot
observe the choices of the other players before making the decision.

Belief revision for inductive game theory

13

In the second stage, player i’s position is given as2%ξi2 , wi2 & = %(w11 , l1 ), . . . , (wn1 , ln ), (w12 , a1 ), . . . , (wi−1, ai−1 ), wi2 &with i ≤ n, and a1 , . . . , ai−1 ∈ {frd, unfrd}. For the position %ξi2 , wi2 &, player
i obtains a memory thread as mi %ξi2 , wi2 & = %(wi1 , li ), wi2 &. Unlike the setting of Kaneko and Matsui [15], information piece wi2 conveys to player iinformation about the number of participants in festival fj with li = fj foreach ethnicity group. Formally, this information (denoted Ej ) is definedby Ej = (x1 , x2 , . . . , x! )j , where xk indicates the number of participants inethnic group k = 1, . . . , ). We use notation wi2 = Ej to denote that player i
receives ethnic configuration Ej .
Finally, player i’s position after the second stage is given as%ξ 3 , wj3 & = %(w11 , l1 ), . . . , (wn1 , ln ), (w12 , a1 ), . . . , (wn2 , an ), wj3 &with wj3 ∈ W E . Here, j = 1, . . . , m|N | · 2|N | since the resulting position isdetermined by the players’ choices of locations (among m alternatives) andattitude (between frd and unfrd). For the position %ξ 3 , wj3 &, player i obtains
a memory thread as mi %ξ 3 , wj3 & = %(wi1 , li ), (wi2 , ai ), wj3 &. The information
piece wj3 provides the numerical payoffs.
According to the above setting, ≺o consists of m|N | · 2|N | maximal sequences of the form %ξ 3 , wj3 & and their subsequences. The set W o is determined by ≺o , and π is defined such that π(wij ) = {i} for any wij ∈ W oD andπ(wj3 ) = N for any wj3 ∈ W E .
For determination of players’ payoffs ho = (ho1 , . . . , hon ), we first introduce players’ strategies. A strategy of player i (denoted sti ) is a pair (li , ri )of choices for the first and second stages. Here, ri is a function mapping{f1 , . . . , fm } × E to {frd, unfrd}, where E is the collection of all possible ethnicity configurations. We here note that every player may change strategy inthe recurrent plays of the game (Πo , mo ). To indicate strategy st#i that is deviated from sti by replacing the choice of location li with li# , we use expressionsti [li /li# ]. The replacement of a player’s attitude is indicated analogously.
Let Si be the set of strategies for player i. For a strategy profile st ∈S1 × · · · × Sn , the player’s payoff is determined by his/her attitude and themood of the location he/she chose. The mood of festival fk with fk = li forplayer i (denoted µi ) is given by" the number of friendly people at li otherthan player i; i.e., µi (l, r) =lj =li ,j&=i rj (lj , Ej ), where l = (l1 , . . . , ln ),r = (r1 , . . . , rn ), and frd and unfrd are interpreted as 1 and 0, respectively.
We then define the payoff function of player i as hi (li , ri ) = ri (li , Ei ) · µ(l, r).

14

K. Hasebe, R. Ishikawa

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 andpayoffs. We first introduce the following language:
Definition 4.1 (Language for festival games). The language L is definedby fixing 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 configuration 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 payoff is x”, denoted payoff i = x.
For readability, we introduce equational expressions instead of single
characters to denote these propositional atoms.
In terms of this language, we next give the definition of the sequence of
player i’s belief sets, Ki0 , Ki1 , . . .. The idea behind our definition is as follows. In addition to Definition 3.2, we also consider the player’s belief about
his/her current strategy and experienced ethnicity configurations. 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 theexpression {frd, unfrd} denotes one of frd and unfrd. The latest decisions oflocation and attitude, as well as the resulting payoff, are uniquely determinedin the current belief set.
Definition 4.2 (Belief sets in festival games). Suppose that ∆TDj+1
is obiotained by adding a sequence %ζ, v& ∈≺ for each j = 0, 1, . . .. That is,∆TDj+1:= ∆TDj i ∪ {%ζ, v&}. Let stji = (fj , ri ) be a strategy of player i atithe j-th play of the game. (For convention, we consider st0i := st1i .) The
corresponding sequence of his/her belief sets Ki1 , Ki2 , . . . is defined as follows.
• For each j = 0, 1, . . ., Kij is defined to be the deductive closure of thejjjjunion of four kinds of sets Ki,EX, Ki,CA, Ki,ST, Ki,AUX(where the thirdand fourth are respectively called beliefs about strategy and auxiliary beliefs), and Ki0 is fixed as:0
R1-1 Ki,EX:= {¬s | s ∈ Σ and the length of s∗ is 2},

Belief revision for inductive game theory

150
R1-2 Ki,CA:= {s → t | s, t ∈ Σ and t∗ ( s∗ }∪{li = fj ↔ ¬li = fk | k 0= j, j ≥ l, k ≥ m}∪{Ej ↔ ¬Ek | Ej 0= Ek , Ej , Ek ∈ E}∪{ai = {frd, unfrd} ↔ ¬ai = {unfrd, frd}}∪{li = fk ∧Eh → {frd, unfrd} ↔ ¬(li = fk ∧Eh → {frd, unfrd})}∪{payoff i = x → ¬payoff i = x# | x 0= x# },0
R1-3 Ki,ST:= {fj } ∪ {fj ∧ Ej → ai = {frd, unfrd} | Ej ∈ E, {frd, unfrd}
is determined by ri0 in st0i },0R1-4 Ki,AUX:= {(s → payoff i = x) ∧ (s# → payoff i = x# ) → ¬s |x < x# }.

jjjj• For given Kij = Cn(Ki,EX∪ Ki,CA∪ Ki,ST∪ Ki,AUX), the belief set Kij+1
is defined by

R2-1 (1) Kij+1 := Θ \ {¬s | s ∈ Σ and s∗ ( %ζ, v&} ∪ {s | s∗ = %ζ, v&},
where Θ is obtained by the following rules R2-1 (2)–(4):jR2-1 (2) if %ζ, v& = %(wi1 , fk ), wi2 &, then Θ := Ki,EX\ {¬li = fk } ∪ {li =fk },jR2-1 (3) if %ζ, v& = %(wi1 , fk ), wi2 & where wi2 = Ek , then Θ := Ki,EX\{¬Ek } ∪ {Ek },R2-1 (4) if %ζ, v& = %(wi1 , fk ), (wi2 , ai ), w3 & where wi2 = Ek and hi (w3 ) =jx, then Θ := Ki,EX\ {¬ϕ} ∪ {ϕ} where ϕ ≡ li = fk ∧ (li = fk ∧ Ek →ai = {frd, unfrd}) → payoff i = x},j+1
jR2-2 Ki,CA:= Ki,CA,

j+1
jR2-3 (1) if stj+1= stji [fk /fh ], then Ki,ST:= Ki,ST\ {¬li = fh } ∪ {li =
i
fh },
j+1
j
#
R2-3 (2) if stj+1= stji [ri /ri#i ], then Ki,ST := Ki,ST \{¬ρi }∪{ρi } where ρi
is a 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 refer to the beliefs about causality. These are essentiallythe same as Definition 3.2, but R1-2 is extended to maintain the uniquenessof choices of locations, attitude, the resulting payoff, and ethncity configurations. 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 that can improve on
the latest payoff.

16

K. Hasebe, R. Ishikawa

We here note that for all the operations in the above definition except
for the belief revision for experienced sequences, every removed formula isidentical to the negation of the 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 3.3, we canprove the following theorem.
Theorem 4.3. For a given objective situation (Πo , mo ) in a festival game,sequence of basic experiences ∆TD0 i , ∆TD1 i , . . ., and sequence of strategies
st0i , st1i , . . ., the corresponding sequence Ki0 , Ki1 , . . . defined by Definition 4.2
can be realized by revision operation ( in AGM theory.
Moreover, by our construction of the initial belief set, Ki0 , and by thistheorem, every belief set appearing in the sequence is guaranteed to beconsistent.
We finally define assignment functions that are obtained from given basic
experiences and a player’s strategy.
Definition 4.4 (Assignment functions). For each ∆TDj i and the strategy
stji of the j-th play of the game for player i, the corresponding assignmentσij is an assignment function satisfying conditions A1–A5 in Definition 3.4
and the following.
A6 σ(li = fk ) = 1 iff (wi1 , fk ) appears in the sequence %ξ j,3 , wj,3 &.

A7 σ(Ek ) = 1 iff f1 , . . . , fm appears in the sequence %ξ j,3 , wj,3 & and Ek is theethnicity configuration derived from f1 , . . . , fm .
A8 σ(ai = frd) = 1 iff (wij,2 , frd) appears in the sequence %ξ j,3 , wj,3 &.
Intuitively, A6 means that player i chooses fj as his/her location. A7
represents the location configuration. A8 means that player i chooses frd(or unfrd) as the attitude. For these semantics, the following theorem stillholds.
Theorem 4.5. Suppose that an objective situation (Πo , moi ) and a sequenceof domains Di0 , Di1 , . . . in (Πo , moi ) are given. For j = 0, 1, . . ., let ∆TDj i be
basic experiences, stji be the strategy of player i, and Kij be the belief set
obtained from ∆TDj i . If σij is an assignment function obtained from ∆TDj i ,then σij is a model for Kij .

17

Belief revision for inductive game theory














































Figure 2. Example of a festival game

4.3.

ExampleTo demonstrate a revision process in our logic, we finally consider the following example.
Example 4.6 (Festival game). Let N = {1, . . . , 5} be the set of players
consisting of two ethnicity groups e1 = {1, 2, 3} and e2 = {4, 5}. We consider
three repeated plays of the game depicted in Fig 2. In the first play of thegame, players 1, 2 and 4 go to festival f1 , while players 3 and 5 go to festival
f2 . Here, all the players in f1 behave in a friendly manner, because they do
not have any prejudice against different ethnicities, whereas the players in f2
discriminate against different ethnicities, and thus behave in an unfriendly
manner. In the second play, all players maintain their strategy, except that
player 1 changes location. After the play, player 1 returns to f1 havingsome prejudice against e2 as he experienced player 5’s unfriendly attitudein f2 . Thus, player 1 changes his strategy for attitude; however, player 1’s
prejudice is not exposed as discriminatory behavior whenever his ethnicity
is a majority at his location. Finally, in the third play, player 4 comes tolocation f1 . This results in a situation that e1 becomes the major ethnicity,and player 1 then takes an unfriendly attitude.
We here focus on the revision of player 1’s beliefs and suppose his/her
perfect recall memory function. Let D1j be the domain consisting of theexperienced sequences up to the end of the j-th play of the game (for j =0, . . . , 3). For readability, we identify the expression for sequences with thecorresponding atomic formulas.
In the first play of the game, strategy st11 of player 1 is described as thefollowing functions for given positions %vi1 & and %(vi1 , li ), vi2 &.
• st11 %vi1 & = f1 ,• st11 %(vi1 , li ), vi2 & = frd for any Ej with li = fj .

18

K. Hasebe, R. Ishikawa

The strategy is that a friendly attitude is taken whatever ethnicity configuration is at the location.
According to Definition 4.2, player 1 has the initial belief set K10 consisting of the following.
• ¬s for any sequence s∗ of length 2 in (Πo , mo ) (by R1-1);#• li = f1 and Ej ∈E (l1 = f1 ∧ Ej → ai = frd) (by R1-3);• beliefs about causality (determined by R1-2 and R1-4).

At the end of the first play, new belief set K11 is obtained from K10 by
the following revisions.
• Both ¬%(w11 , f1 ), w12 & and ¬%(w12 , frd), w3 & are removed, and then %(w11 , f1 ),(w12 , frd), w3 & is added (by R2-1 (1));• Ethnicity configuration (2, 1)1 is added (by R2-1 (3)), and the negationof any other configuration can thus be derived by R1-2;• l1 = f1 ∧ (l1 = f1 ∧ (2, 1)1 → a1 = frd) → payoff 1 = 2 is added (by R2-1
(4)).
At the end of the second play, new belief set K12 is obtained by thefollowing revisions.
• Both ¬%(w1#1 , f2 ), w1#2 & and ¬%(w1#2 , frd), w#3 & are removed, and then%(w1#1 , f2 ), (w1#2 , frd), w#3 & is added (by R2-1 (1));• Ethnicity configuration (2, 1)2 is added (by R2-1 (3));• ¬l1 = f2 (which is derived from the previous belief about location l1 = f1
and belief about causality l1 = f1 ↔ ¬l1 = f2 ) is removed, and thenl1 = f2 is added (by R2-3);• l1 = f2 ∧ (l1 = f2 ∧ (2, 1)2 → frd) → payoff i = 0 is added (by R2-1 (4)).
By accumulating experiences about payoffs, the player recognizes that thedeviation of location worsens the payoff. Thus, by (R1-4), it is suggested
that the player deviates from the current strategy; i.e., ¬l1 = f2 ∨ l1 =f2 ∧ (2, 1)2 → frd is derived. The revised strategy st##1 in the third play canbe defined as follows.
• st##1 %v11 & = f1 ,• st##1 %(v11 , l1 ), v12 & =$unfrd if x > 2y for Ej = (x, y) with l1 = fj.
frd
otherwise

Belief revision for inductive game theory

19

The intuitive meaning of this strategy is that the player’s hidden prejudice
is exposed as discriminatory behavior (i.e., the player takes an unfriendly
attitude) if his/her ethnicity becomes more than twice as large as e2 . Thisdeviation results in the following belief revisions:• Both ¬%(w1##1 , f1 ), w1##2 & and ¬%(w1##2 , unfrd), w1##3 & are removed, and then%(w1##1 , f1 ), (w1##2 , unfrd), w1##3 & is added (by R2-1 (1));• ¬l1 = f1 is removed, and then l1 = f1 is added (by R2-3);• ¬(2, 1)1 is removed, and then (3, 1)1 is added (by R2-1 (3));• ¬(l1 = f2 ∧ (2, 1)2 ) → a1 = frd) is removed, and then l1 = f1 ∧ (x, y)1 →a1 = frd for x > 2 · y is added (by R2-1 (4)).

5.

Concluding 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 finally comment on our findings. First, our inductive derivation differs from learning theory approaches in the literature such as those of Fudenberg and Levine [8]. Standard learning theories do not focus on thelearning of structure, but on the learning of beliefs of opponents’ actions.
Second, while making use of the framework of inductive game theory developed by Kaneko and Kline and Kaneko and Matsui, our theory focuses ona permanent revision process based on the player’s experiences. While thedevelopers of inductive game theory focused on how to construct a player’sview consistent with his/her experiences, we focused on how to change aplayer’s personal view when he/she has a new experience.
Finally, the treatment of experiences in our theory slightly differs fromthe standard belief revision theory pioneered by Alchourrón, Gärdenfors
and Makinson [1] (so-called AGM theory). In contrast to AGM theory, ourtheory distinguishes between what a player originally believes and what helogically derives from the original belief. This is based on our motivation thatthe players are not simply a database, but have some logical abilities. Thisapproach is similar to the belief base theory, which distinguishes between
the belief base and the consequence.3 However, the theory of the belief basefocuses neither on the new observations as the experiences in our theory
3

See Chapter 1 in Gärdenfors [9].

20

K. Hasebe, R. Ishikawa

nor on their accumulation. Our theory combines the use of accumulated
observations and beliefs logically derived from them for decision-making.
In further research, we will investigate (i) how players with different
views make decisions in our theory and (ii) the direction of various players’
views after repetitive revision. In standard game theory, players face anidentical situation and know that even when considering incomplete information games. Our theory is a first step to inquiring whether it is possible toachieve and to analyze misunderstandings pointed out by Kaneko [11]. In asociety in which people do not necessarily 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
and Nobu-Yuki Suzuki for the valuable comments and stimulative discussions. The second author also thank Kim Cranney, Tai-Wei Hu, and Oliver
Schulte for giving comments on the early version of this paper. And hereceives Grants-in-Aid for Young Scientists (B), No. 21730151.
References[1] Alchourrón, C. E., P. Gärdenfors, and D. Makinson, ‘On the logic of theorychange: Partial meet contraction and revision functions’, Journal of Symbolic Logic,
50 (1985), 2, 510–530.
[2] Binmore, K., ‘Modeling rational players (part i)’, Economics and Philosophy, 3(1987), 179–214.
[3] Board, O., ‘Dynamic interactive epistemology’, Games and Economic Behavior, 49(2004), 1, 49–80.
[4] Bonanno, G., ‘The logical representation of extensive games’, International Journalof Game Theory, 22 (1991), 153–169.
[5] Ditmarsch, H. van, W. van der Hoek, and B. Kooi, Dynamic Epistemic Logic,
Springer Publishing Company, Incorporated, 2007.
[6] Feinberg, Y., ‘Subjective reasoning–dynamic games’, Games and Economic Behavior, 52 (2005), 54–93.
[7] Feinberg, Y., ‘Subjective reasoning–splutions’, Games and Economic Behavior, 52(2005), 94–132.
[8] Fudenberg, D., and D. K. Levine, ‘Self-confirming equilibrium’, Econometrica, 61(1993), 3, 523–545.
[9] Gärdenfors, P., (ed.) Belief Revision, Cambridge Unviersity Press, Cambridge,
UK, 1992.

Belief revision for inductive game theory

21[10] Hoek, W. van der, and M. Pauly, ‘Modal logic for games and information’, inJ. van Benthem, P. Blackburn, and F. Wolter, (eds.), Handbook of Modal Logic,
chap. 20, Elsevier, 2007, pp. 1077–1148.
[11] Kaneko, M., Game Theory and Mutual Misunderstanding, Scientific Dialogues inFive Acts, Springer, Cambridge, MA, 2004.
[12] Kaneko, M., and J. J. Kline, ‘Inductive game theory: A scenario’, Journal of
Mathematical Economics, 44 (2008), 1332–1363. Corrigendum: This journal, 46: 620–
622, 2010.
[13] Kaneko, M., and J. J. Kline, ‘Information protocols and extensive games in inductive game theory’, Game Theory and Applications, 13 (2008), 57–83.
[14] Kaneko, M., 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] Kaneko, M., and A. Matsui, ‘Inductive game theory: Discrimination and prejudices’, Journal of Public Economic Theory, 1 (1999), 1, 101–137. Erratum: thisjournal, 3(3):347, 2001.
[16] Kaneko, M., and A. Mitra, ‘Discrimination in festival games with limited observability and accessibility’, Mathematical Social Science, 62 (2011), 34–45.
[17] van Benthem, J., ‘Extensive games as process models’, Journal of Logic, Language,
and Information, 11 (2002), 289–313.

Koji Hasebe, Ryuichiro Ishikawa
Graduate School of Systems and Information Engineering
University of Tsukuba
Tsukuba, Ibaraki 305-8573, Japan
hasebe@cs.tsukuba.ac.jp (K. Hasebe)
ishikawa@sk.tsukuba.ac.jp (R. Ishikawa)