数理解析研究所講究録 1222 巻 2001 年 170-177

170

CONSENSUS ON p-BELIEF COMMUNICATION
石川竜一郎 (RYUICHIRO ISHlKAWA) * 一橋大学大学院経済学研究科,
松久隆 (TAKASHI MATSUHISA) \dag er 茨城工業高等専門学校, AND
赤川洋介 (YOH-SUKE AKAGAWA) 茨城大学理学部

ABSTRACT. The communication process in the pbelief system that reaches consensus
is presented: The agents communicate the events that they believe more than theirown posteriors. We show that in the long run each posterior converges and that any
two limiting values of posterior can be same.

1. INTRODUCTION

The purposes of this article are the two points: First to present the communication process according to aprotocol with the -belief system, and secondly to extend
the agreement theorem of Aumann [1] to this model in the line of Geanakoplos andPolemarchakis [4] and Krasudci [5].
In his seminal paper Aumann [1] showed his agreement theorem that if aU players commonly know their posteriors of an event then their posteriors must be same.
Geanakoplos and Polemarchakis [4] investigated acommunication process between two
players in which the players announce their posteriors to each other. In the process
players learn and revise their posteriors and they reached consensus. This is an extension of the agreement theorem of Aumann regardless of common-knowledge. Krasucki[5] extended the result for the communication process among at least three players.
The knowledge of players in the above models are given by partition. However many
researchers have been pointing out that the assumption for the partition is problematicin the decision makings among players and that the model should be constructedwithout such strong assumption.
Monderer and Samet [7] introduced the weaker model, called the pbelief system,that formalzes player’s belief of something as he believes it at least probability .
They showed the approximating agreement theorem: If all players commonly pbelieve
their posteriors of an event then the diHerence between any two players’ posteriors candiHer at most $2(1-p)$ .
We introduce the communication process with the -belief system; it is the revision
process of the values of players’ posterior of an event through the messages. Our result
is an extension of the above agreement theorems as follows:
$p$

$p$

$\mathrm{p}$2000 Mathematics Subject Classification. Primary, Secondary.
Journal of Economic Literature $Uass\dot{|}ficatiom$. C62, C79.
Key words and phrases. Consensus, Communication, Information structure, Knowledge, p-Belief
system, Protocol.
This is apreliminary version and the final form will be publshed elsewhere.
$91\mathrm{A}35$$68\mathrm{Q}55$*Corraeponding author.
Supported by the Grand-in-Aid for Scientific Research(C)(2)(N0.12640145) in the Japan Society
for the Promotion of Sciences

171
Theorem 1. In the -belief communication consensus on the limiting values of theposteriors of an event $X$ can be guaranteed if the protocol contains no cycle.
$p$

We begin in Section 2by reviewing the basic model, which consists of the standard
model of knowledge, -belief system and aprotocol. The -belief communication is
introduced on the system. In Section 3, asimple example is presented, which shows a-belief communication process among three persons. In Section 4, we show the results
and the proof and state the conclusion in the last section.

2. THE Model
Let $N$ be aset of finitely many players and denote an player. Astate-space is a
finitely non-empty set, whose members are called states. An event is asubset of thestate space If is astate space, we denote by
the field of all subsets of it. An
event $F$ is said to occur in astate if $\in F$ .
$i$$\Omega$$2^{\Omega}$$\omega$$\omega$

2.1. Partitional Information Structure 1. By this we mean aclass of mappings
such that:satisfies the three properties, Reflectivity, Transitivity
and Symmetry :$(\Pi_{i})_{i\in N}$(Ref)$\Omegaarrow 2^{\Omega}$$\Pi_{:}$$\omega$$\in\Pi_{:}(\omega)$;

implies;(Sym)
implies.
Specifically, an agent for whomknows in the state that some state in
the event $E$ has occurred. We callthethe ’sinformation partition andpossibility set at . This is interpreted as the set of states that thinks are possible
when occurs. By ’s posterior :at of agiven event $X$ we mean the conditional
probability of $X$ under the possibility set at ;i.e.; $q:=\mu(X|\Pi:(\omega))$ . We will also
it the initial posterior of $X$ at in later sections.
(TYn)$\xi\in\Pi_{:}(\omega)$$\Pi_{:}(\xi)\subseteqq\Pi_{:}(\omega)$$\xi\in\Pi_{i}(\omega)$$\omega$$i$$\in\Pi_{:}(\xi)$$\Pi_{:}(\omega)\subseteqq E$$\omega$$i’ \mathrm{s}$$\Pi_{:}$$\Pi.\cdot(\omega)$$\omega$$i$$\omega$$i$$i$$\omega$$q$$\omega$$\mathrm{c}\mathrm{a}\mathrm{U}$$\omega$

2.2. -Belief system. We assume that the partitional information structureon the given 0. Let be anumber with $0\neq<p\leqq 1$ and fix it. The -belief systemassociated with the information partitions is the tuple
consisting of the following structures and interpretations:is afinite probability spacesuch thatfor every, and theoperatoronis defined-beliefsuch thatis the set of states of in which believes that $E$ has occurred withprobability at least ;that is,$(\Pi_{:}):\in N$

$p$

$p$

$\langle\Omega,\mu, (\Pi:):\in N, (B^{p}\dot{.}):\in N\rangle$$(\Omega,\mu)$$\mu(\omega)\neq>0$$\omega$$\in\Omega$$i’ \mathrm{s}p$$B^{p}\dot{.}E$$\Omega$$2^{\Omega}$$B_{}^{p}$

$i$

$p$

$B^{p}\dot{.}E:=\{\omega\in\Omega|\mu(E|\Pi:(\omega))\geqq p\}$.

We call it the event that player $ip$ -believes $E$ . When
we say that p-believes$E$ at. We record the properties ofas:For every $E$ , $F$ of ,and;;whenever
T4;
IE.
The mutual belief operatoronis defined by, whereasis interpreted as the event that all agents believe $E$ .
$\omega$$\omega$$\mathrm{N}$$\mathrm{M}$$B^{p}.\cdot$$B^{p}.\cdot\Omega=\Omega$$\mathrm{f}\mathrm{o}\mathrm{U}\mathrm{o}\mathrm{w}\mathrm{s}^{2}$$\in B^{p}\dot{.}(E)$$i$$2^{\Omega}$$B^{p}\dot{.}\emptyset=\emptyset$$E\subseteqq F$$B^{p}\dot{.}E\subseteqq B^{p}.\cdot F$$B^{p}\dot{.}E=B^{p}\dot{.}B_{\dot{1}}^{p}E$$\mu(E|B_{\dot{1}}^{p}E)\geqq p$$B_{E}^{p}$$2^{\Omega}$$B_{E}^{p}E$

Aumann [1], Binmore [3].
Proposition 2in Monderer and Samet [7]$2\mathrm{S}\mathrm{e}\mathrm{e}$$B_{E}^{p}E:= \bigcap_{:\in N}B^{p}.\cdot E$

$p$

172
2.3. Protocol 3. We assume that players communicate by sending messages. AprOinto the product set $N\cross N$
tocol is amapping of the set of non-negative integers
that assigns to each apair of players $(s(t), r(t))$ . Here stands for time and $s(t)$and $r(t)$ are, respectively, the sender and the recipient of the communication whichtakes place at time . We can consider it as the directed graph. Aprotocol is said
to be fair if the graph is strongly-connected; in words, every player in this protocol
communicates directly or indirectly with every other player infinitely often. It is said,
to be acyclic if the graph contains no cyclic path; that is, there are players , ,, and such that
communicates directly withsuch that for all $m<k$ ,withcommunicates directly with$\mathbb{Z}_{+}$$\mathrm{P}\mathrm{r}$

$t$

$t$

$t$

$i_{1}$$k$$\geqq 3$$i_{2}$$\ldots$$i_{k}$$i_{m+1}$$i_{m}$$i_{1}$$i_{k}$

2.4. Communication with -belief system. The -belief communication process,of an event $X$ is atripleof revisions of the posteriors, $r(t)=s(t+1)$ ,is fair protocol such that for every
in which$munds^{4}$ andfor agent at
intoof
mappingistheinproceedcommunications
time that is defined inductively as follows:is the initial posterior $q:=$
and
We assume given amapping
$\pi$

$p$

$\mathrm{p}$$\langle \mathrm{P}\mathrm{r}, (Q^{t}.\cdot)_{(:,t)\in N\mathrm{x}\mathrm{Z}_{+}},X\rangle$$(q_{\dot{1}}^{t})_{(:,\iota)\in N\mathrm{x}\mathrm{z}_{+}}$$t\in \mathbb{Z}_{+}$$\mathrm{P}\mathrm{r}(t)=(s(t),r(t))$$2^{\Omega}$$\Omega$$Q^{t}.\cdot$

$i$

$t$

$Q^{0}\dot{.}:=\Pi_{:}$$\bullet$$\mu(X|Q_{\dot{1}}^{0}(\omega))$$\bullet$$q_{}^{o}$.

Supposeis defined.
-IIJ is the partition on induced by ;that is,;;denotes$-W.\cdot$ is the mapping of
which assigns to each state the event
into;
Wl (u) that consists of all the states such thatasfollows:
defined
,
is
to
then
messageat
If send the.
-If is not arecipient of amessage at time , thendefined by-If is arecipient of amessage at time , then$Q^{t}.\cdot$$\Omega$$\Pi^{t}\dot{.}(\omega):=\{\xi\in\Omega|Q^{t}\dot{.}(\xi)=$$Q^{t}.\cdot$$Q^{t}.\cdot(\omega)\}$$-q_{}^{t}(X;\omega)$$q^{t}.\cdot:=\mu(X|\Pi^{t}.\cdot(\omega))$$2^{\Omega}$$\Omega$$\omega$$\mu(X|\Pi^{t}.\cdot(\xi))\geqq q^{t}.\cdot(X;\omega)^{5}$$\xi$$\bullet$$Q^{t+1}.\cdot$

$i$

$t$

$W_{j}(\omega)$$j$$Q_{}^{t+1}=Q^{t}\dot{.}$

$t$

$i$

$Q_{}^{t+1}=Q^{t}.\cdot\cap W.\cdot$

$t$

$i$

$Q^{t+1}.\cdot(\omega)=Q_{\dot{1}}^{t}(\omega)\cap W_{j}(\omega)$.

Remark 1. The sequence of sets $\{Q^{t}.\cdot|t=0,1,2, \ldots\}$ is stationary in finitely manyrounds because it is adescending chain by definition and is finite. That is, there is,and for aU
asufficiently large time $\tau\in T$ such that for every , for all, and therefore$\Omega$$i$$\omega$$t\geqq\tau$$\in\Omega$$q^{t}.\cdot(X;\omega)=q_{\dot{1}}^{\tau}(X;\omega)$$Q^{t}\dot{.}(\omega)=Q^{\tau}.\cdot(\omega)$

exists in each state by Remark 1, and2.5. Consensus. We note that the lmit
limiting value
cffied thecan be defined. We denote
thusof $X$ at . We say that consensus on the limiting values of the posteriors about $X$ canfor each player $i,j$ andbe guaranteed in the communication process if
in aU the states .
$Q^{\infty}.\cdot$$q_{\dot{1}}^{\infty}$$\Pi^{\infty}.\cdot$$i’ \mathrm{s}$$(\omega)=\mu(X|\Pi_{\dot{1}}^{\infty}(\omega))$$\omega$$q_{}^{\infty}(\omega)=q_{j}^{\infty}(\omega)$$\omega$

3. EXAMpLE
We consider acomprehensive example as follows. Players are Alice, Bob, and Nanny.
They communicate about -belief of some event X to each other according the protocol$3\mathrm{K}\mathrm{r}\mathrm{a}\mathrm{s}\mathrm{u}\mathrm{d}\mathrm{i}$

$[5]$

.

is, there exists anatural number $m$ such that for all , $s(t)=s(t+m)$ .
specification of the message sent by :at allows that the recipient receives the information.
that :believes $X$ with probabilty at least$t$$4\mathrm{T}\mathrm{h}\mathrm{a}\mathrm{t}$$5\mathrm{T}\mathrm{h}\mathrm{e}$$t$$q_{\dot{l}}^{t}(X;\omega)$

$j$

173

FIGURE 1. Commimication protocol among three players.
and the commonwith no cycle in Figure 1. Now let be the state space$\mu(\omega)=1/8$
.
each
for
prior on defined by
Each player has his initial knowledge defined by the partition on Q. Figure 2showsis occurred. Then their
this situation. Now suppose an event
posteriors will reach consensus: the values of the posteriors are all one in each state in$X$ and the values are zero in other states.
$\{\omega_{1}, \cdots,\omega_{8}\}$$\Omega$$\Omega$$\mu$$\omega$$X=\{\omega_{2},\omega_{5},\omega_{6},\omega_{8}\}$$\Pi_{N}$$\Pi_{4}\mathrm{F}\mathrm{I}\mathrm{G}\mathrm{U}\mathrm{R}\mathrm{E}2$. Information$\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{t}_{1}^{B}\mathrm{o}\mathrm{n}\mathrm{s}\Pi$for each of players.

We show the revision process about their knowledge and posteriors. First, Alicesends her message to Bob at time $t=1$ as Table 1. He receives it and constitutes his
own partition. However the message at time $t=1$ is not useful for him because his
initial knowledge is finer. Therefore his information partition is not changed, that is. As result, the information structure at time $t=1$ for each player is thesame as the initial.
$\Pi_{B}^{1}--\Pi_{B}$In asimilar way, Bob communicates with the protocol. Table 2shows his message to
Nanny at time $t=2$ . Though she receives it, it is not useful for her as well. Therefore
her information structure is the same as the initial one. The situation continues attime $t=3$ .

174

TABLE 1. Alice’s message at time t $=1$ .

TABLE 2. Bob’s message at time t $=2$ .

At time $t=4$ , Bob sends auseful message to Alice. Table 3denotes Bob’s at thetime. That is, his message is finer than her knowledge held until now. Consequently
her knowledge is revised asin Figure 3. Therefore her message to Bob is finer as
denoted in Table 4.
$Q_{A}^{4}$

TABLE 3. Bob’s message at time t $=4$ .

$Q_{A}^{4}$$Q_{B}^{4}$$Q_{N}^{4}$

FIGURE 3. Information structures at time t $=4$ .

Seeing the Table 5, we say that consensus on the lmiting values of the posteriors
about $X$ can be guaranteed in the example. The information structures on the lmiting
values for each players is stable after time $t=5$ . Therefore the structures is the sameas the Figure 3.

175

TABLE 4. Alice’s message at time t $=5$ .

TABLE 5. The travelers’ message at time t$\geqq 5$.

4. REACHING Consensus
We show aproof of Theorem 1presented in Introduction. For the purpose, we prove
Theorem 2.
4.1. Proof of Theorem 1. Follows immediately fiiom Theorem 2below.
Theorem 2. In the -belief communication , if player communicates $his/her$ message directly to another player then.
for every
$p$

$i$

$\pi$

$j$

$q^{\infty}\dot{.}(\omega)=q_{j}^{\infty}(\omega)$$\omega$$\in\Omega$

In fact we can observe that the consensus in Theorem 1follows from Theorem 2by
inductive steps in viewing that the protocol is acyclic.

4.2. Proof of Theorem 2. The folowing lemma is akey to proving the theorem:
Lemma 1. Let be a state in , a partition of , and let;
denote $\mu(X|\Pi(\omega))$ .
If there exists a non-empty event $H$ of such that for every 4of $H$ , the two conditions
are $tme$ :(a)is contained in $H$ , and(b) $\mu(X|\square (\xi))=q(X;\omega)$ ;then we obtain that$\Omega$$\omega$$\Pi$$\Omega$$\mathrm{q}(\mathrm{X}$$2^{\Omega}$$\Pi(\xi)$$q(X;\omega)=\mu(X|H).6$

In fact, H can be decomposed into the disjoint union of components
in view of (a), and thus the result follows from (b).

Proof of Theorem Z. For each state denote$\cdot$$\omega$$H=[q_{\dot{l}}^{\infty}]\cap[q_{j}^{\infty}]$$\Pi_{l}^{\infty}(\xi)\subseteqq H$$,6- 1\backslash \mathrm{T}\mathrm{h}\mathrm{i}\mathrm{s}$

for

$\xi$

$\in H$$[q^{\infty}.\cdot]=[q^{\infty}.\cdot(X;\omega)]:=\{\xi|\mu(X|\Pi_{}^{\infty}(\xi))=$. Set;this is non-empty because
properties: For $l=i,j$ ,(a)for every $\in H$ , and$q^{\infty}\dot{.}\}$$\Pi(\xi)$$\omega$$\in H$. We can verify the two$\xi$lemma plays an essential role in the proof of the agreement theorem of Aumann (Proposition

176
.
(b)
In fact, Part (b) is obviously observed. For (a) it suffices to show that,for every(c)forwhere $l’\in\{i,j\}\backslash \{l\}$ . Indeed, it is easily verified that, and thus (a) immediately follows.
every (. We note that there exist $m$ such that
Suppose(c):prove
We will$s(t)=r(t+m)$ and $r(t)=s(t+m)$ since the protocol is acyclic, and on noting
,
and
that
it follows from the definition ofthat, $(X;\xi)$ , and thus,
. Therefore it can be observed that ,as claimed.
Now, viewing Lemma 1we obtain that $q_{l}^{\infty}=\mu(X|\Pi_{l}^{\infty}(\xi))=\mu(X|H)$ for eachas required.
, and thus
$H\subseteqq[q_{l}^{\infty}]$$\Pi_{l}^{\infty}(\xi)\subseteqq[q_{l}^{\infty}, (X;\omega)]$$\xi$$\in[q_{l}^{\infty}, (X;\omega)]$$[q_{l}^{\infty}, (X;\xi)]=[.q_{l}^{\infty}, (X;\omega)]$$\in[q_{l}^{\infty}, (X;\omega)]$$\zeta\in\Pi_{l}^{\infty}(\xi)$$Q_{l}^{\infty}(\zeta)=Q_{l}^{\infty}(\xi)$$\{Q_{l}^{t}\}_{t\in}\mathrm{z}_{+}$$\xi\in W_{l}^{\infty}$ $(\zeta)$$q_{l}^{\infty}$$(X;\zeta)=q_{l}^{\infty}$$\langle$$\in W_{l}^{\infty}$ $(\xi)$

$($

$\in$

$[q_{l}^{\infty}, (X;\xi)]$$\mathit{1}\in\{i,j\}$$\square$$q^{\infty}.\cdot(\omega)=q_{j}^{\infty}(\omega)$

5. CONCLUDING REMARKSThis article investigates how players reach consensus through pbelief communication. This research is in the Hue on the investigations on acommunication process inthe standard model of knowledge. As stated in Introduction, Geanakoplos and Polemarchakis [4] and Krasucki [5] studied how players reach consensus on the knowledge
model. Correspondingly Monderer and Samet [7] showed the approximating agreement theorem that does not guarantee consensus on the -belief model. The reason
the players cannot reach consensus in Monderer and Samet [7] is that the information
obtained from the players’ ability is ambiguous; the players’s knowledge are given notby the partitional structure but the $RT$-infomation structure similar to S4 model in
Bacharach [2]. This means that the players’ information structures satisfy reflexive
and transitive properties but not symmetric property.
To overcome the difficulty, we introduce the model of -belief communication inwhich players can generate the partitional information structures by receiving messages
though the messages are not given by partitions, and thus the players can keep theirknowledge partitional. Consequently we can obtain the result that players can reachconsensus on the -belief communication. In the -belief communication as above
the requirement that players must generate the partitional information by receiving
messages is not astrong assumption with respect to the requirement of the standard
model of knowledge.
It plays the essential role for reaching consensus through the communication onwhich players’ information structures are given by partitions. When this requirement
fails, how we can reach consensus? This problem remains open
$p$

177
REFERENCES[1] Robert J. Aumann, Agreeing to disagree, Annals of Statistics 4(1976), 12361239.
[2] Michael Bacharach, Some extensions of a claim of Aumann in an axiomatic model of knowledge,
Journal of Economic Theory 37 (1985),167-190.
[3] Ken Binmore, Fun and Games. D. C. Heath and Company, Lexington, Massachusetts USA,.
(1990),[4] John D. Ceanakoplos, and Heraklis M. Polemarchakis, We can’t disagree forever, Journal of
Economic Theory 28 (1982), 192-200.
.
[5] Paul Krasucki, Protocol forcing consensus, Journal of Economic Theory 70 (1996),[6] Takashi Matsuhisa and Shun-Suke Usami, Awareness, belief and agreeing to disagree, Far East
Journal of Mathematical Sciences 2N0.6 (2000), $83\succ 844$ .
[7] Dov Monderer and Dov Samet, Approirnating common knowledge with common belief Gamesand Economic Behavior 1(1989), 170-190.
[8] Paul Milgrom and Nancy Stokey, Information, trade and common knowledge, Journal of Economic
Theory 26 (1982), 17-27.
[9] Dov Samet, Ignoring ignorance and agreeing to disagree, Journal of Economic Theory 52 (1990),$\mathrm{x}\mathrm{x}\mathrm{x}+642\mathrm{p}\mathrm{p}$$26\triangleright 272$

190-207.
(Ryuichiro Ishikawa) GRADUATE SCHOOL OF ECONOMICS, HITOTSUBASHI UNIVERSITY, NAKA
2-1, NISHI, KUNITACHI-SHI, Tokyo 186-8601, JAPAN$E$-mail address:jP.
$\mathrm{g}\mathrm{e}\mathrm{m}7103\mathrm{Q}\mathrm{Q}\mathrm{s}\mathrm{r}\mathrm{v}$$\mathrm{c}\mathrm{c}.\mathrm{h}\mathrm{i}\mathrm{t}-\mathrm{u}.\mathrm{a}\mathrm{c}.$(Takashi Matsuhisa) DEpARTMENT OF LIBERAL ARTS AND SCIENCES, IBARAKI NATIONAL Cob

LEGE OF TECHNOLOGY, 866 NAKANE, HITACHINAKA-SHI, IBARAKI 312-8508, JAPAN-mail address: mathisa@ge.ibaraki-ct.ac.jp$E$(Yoh-Suke Akagawa) UNDERGRADUATE Course OF ELECTRIC ENGINEERING, IBARAKI NATIONALCOLLEGE OF TECHNOLOGY. Current Address: UNDERGRADUATE Course OF MATHEMATICAL SC1ENCES, IBARAKI UNIVERSITY, BUNKYO 2-1-1, MITO-SHI, IBARAKI 310-8512, JApAN.