共有知識(common knowledge)とは、ある事柄を全員が知り、全員が知っていることを全員が知り、……という入れ子が限りなく続く状態のことである。各人の知識を状態の集合の分割で表すと、事象が状態 ω で共有知識であることは、各人の分割の meet(すべての分割より粗い分割のうち最も細かいもの)の ω を含む元がその事象に含まれることと同値で、状態が有限個なら有限段の入れ子で足りる。全員が知っているだけの相互知識とは異なり、泥だらけの子どもたちのパズルでは、皆が知っている事実の公表によって共有知識が生じ、推論の結果が変わる。
共有知識(common knowledge)とは、ある事柄を全員が知っており、全員が知っていることを全員が知っており、そのことをまた全員が知っており、……という入れ子が限りなく続く状態のことである。ゲーム理論 では、たとえば完備情報の展開形ゲームを、ゲームの規則(木の形、各局面でとれる手、終局での利得)が全員の共有知識であるゲームとして扱う(KP17 p. 115。共有知識の意味は同ページの脚注 1 が上の入れ子の言葉で説明している)。
全員が知っているだけ(相互知識)と、共有知識とは違う。たとえば「泥のついた子が少なくとも 1 人いる」ことを子どもたち全員が見て知っていても、それを父親が皆の前で宣言するまでは共有知識ではない。宣言の前後で子どもたちの推論の結果が変わることを thm-ck-muddy で示す。
この記事では、各人の知識を状態の集合の分割で表す Aumann の枠組み(Aum76)で共有知識を定義し、次のことを示す。
$\Omega$ を空でない集合とし、その元を 状態、部分集合を 事象 という。参加者を $i=1,\dots,n$($n\ge1$)とし、各 $i$ に $\Omega$ の分割 $\Pi_i$ が与えられているとする。$\omega\in\Omega$ を含む $\Pi_i$ の元を $\Pi_i(\omega)$ と書く。真の状態が $\omega$ のとき、参加者 $i$ は「真の状態は $\Pi_i(\omega)$ に属する」ことだけを知らされる、と解釈する(Aum76 p. 1237)。
事象 $E$ に対し
$$
K_iE:=\{\omega\in\Omega\mid \Pi_i(\omega)\subseteq E\}
$$
を「$i$ が $E$ を知っている」事象という。さらに
$$
KE:=K_1E\cap\cdots\cap K_nE,\qquad K^1E:=KE,\qquad K^{m+1}E:=K(K^mE)\quad(m\ge1)
$$
とおく。$KE$ を「全員が $E$ を知っている」事象といい、$\omega\in KE$ のとき $E$ は $\omega$ で 相互知識 であるという。
$\omega\in K_jK_iE$ は「$j$ は、$i$ が $E$ を知っていることを知っている」ことを表す。$K^mE$ は、長さ $m$ 以下のこのような入れ子の文がすべて成り立つ事象である($K^mE\subseteq K_{i_m}\cdots K_{i_1}E$ はどの添字の列でも成り立つ。$K\subseteq K_i$ と、次の prop-ck-s5 の単調性による)。
def-ck-knowledge の状況で次のように定める。
$K_iF=F$ は、$F$ が $\Pi_i$ の元の和集合であることと同値である。実際、$K_iF$ は $F$ に含まれる $\Pi_i$ の元の和集合である。自明な事象とは、それが起きたときには誰もがそれを知っている事象である。
この記事の結果が使える条件は次のとおりである。
(i) 分割による知識:各人の知識は分割で表される。とくに真の状態はいつも $\Pi_i(\omega)$ に入る。分割でない情報の与え方では知識の性質が成り立たない(反例の表の 1 行目)。
(ii) 分割そのものの共有:各人の分割は全員に知られており、そのこと自体も共有されている。Aum76 p. 1237 は、状態の記述の中に情報の与え方まで含めれば、これで一般性を失わないと注意している。
(iii) 有限性:有限回で共有知識に達するという主張(cor-ck-finite)だけは $\Omega$ が有限であることを使う。
| 問い | 答え | 条件 | 根拠 |
|---|---|---|---|
| 知識の性質 | $K_iE\subseteq E$、$K_iK_iE=K_iE$、知らないことを知っている | (i) | prop-ck-s5 |
| 共有知識の判定 | $\omega\in CE\iff M(\omega)\subseteq E$ | (i) | thm-ck-meet |
| meet の求め方 | 各人の分割の元を、交わるものどうしつないだ連結成分 | (i) | thm-ck-meet の証明 |
| 共有知識の事象 | $E$ に含まれる最大の自明な事象 | (i) | thm-ck-meet の 3 |
| 何回の入れ子で足りるか | $\Omega$ が有限なら $\lvert\Omega\rvert-1$ 回 | (i)(iii) | cor-ck-finite |
| 相互知識との違い | $m$ 段まで成り立っても $m+1$ 段で成り立たないことがある | — | ex-ck-chain |
| 泥だらけの子どもたち | 泥のついた子が $k$ 人なら $k$ 回目の問いで泥のついた子だけが分かる | 宣言がある | thm-ck-muddy |
def-ck-knowledge の $K_i$ は、すべての事象 $E,F$ について次を満たす。
1。 $\Pi_i(\omega)\subseteq\Omega$ はいつも成り立つ。$\Pi_i(\omega)\subseteq E\cap F$ は $\Pi_i(\omega)\subseteq E$ かつ $\Pi_i(\omega)\subseteq F$ と同じである。$E\subseteq F$ なら $E=E\cap F$ なので $K_iE=K_iE\cap K_iF\subseteq K_iF$。$K$ は $K_i$ の共通部分、$K^m$ は $K$ の合成なので、同じ性質をもつ。
2。 $\omega\in\Pi_i(\omega)$ なので、$\Pi_i(\omega)\subseteq E$ なら $\omega\in E$。
3。 $\omega'\in\Pi_i(\omega)$ なら $\Pi_i(\omega')=\Pi_i(\omega)$ である(分割の元は交われば一致する)。よって $\omega\in K_iE$ なら、$\Pi_i(\omega)$ のどの点 $\omega'$ でも $\Pi_i(\omega')=\Pi_i(\omega)\subseteq E$、すなわち $\Pi_i(\omega)\subseteq K_iE$ で、$\omega\in K_iK_iE$。逆向きの包含は 2 による。
4。 3 と同じ理由で、$K_iE$ は $\Pi_i$ の元の和集合であり、その補集合 $G:=\Omega\setminus K_iE$ も $\Pi_i$ の元の和集合である。よって $\omega\in G$ なら $\Pi_i(\omega)\subseteq G$ で、$G\subseteq K_iG$。逆向きは 2 による。$\square$
1〜4 は、様相論理 の体系 $\mathbf{S5}$ の公理($\mathrm K$・$\mathrm T$・$4$・$5$)を事象の言葉で書いたものにあたる。分割は 同値関係 と同じもので、同値関係をもつフレームが $\mathbf{S5}$ に対応することは 様相論理 で扱っている。
$K$ そのものは 3 を満たさない。全員が知っていても、そのことを全員が知っているとは限らない(ex-ck-chain)。
$\omega,\omega'\in\Omega$ と $m\ge0$ について、$\omega'$ が $\omega$ から $m$ 歩で行ける とは、点の列 $\omega=\omega_0,\omega_1,\dots,\omega_m=\omega'$ と参加者の列 $i_1,\dots,i_m$ があって、各 $k$ で $\omega_k\in\Pi_{i_k}(\omega_{k-1})$ となることをいう。その全体を $R_m(\omega)$ とする。$R_0(\omega)=\{\omega\}$ で、
$$
R_{m+1}(\omega)=\bigcup_{\omega'\in R_m(\omega)}\ \bigcup_{i=1}^n\Pi_i(\omega')\qquad\text{(1)}
$$
である。$\omega'\in\Pi_i(\omega')$ なので $R_m(\omega)\subseteq R_{m+1}(\omega)$ であり、同じ点に留まる歩みを許すので「$m$ 歩以内」と「ちょうど $m$ 歩」は同じである。
すべての $m\ge1$、$\omega\in\Omega$、事象 $E$ について、$\omega\in K^mE\iff R_m(\omega)\subseteq E$。
$\omega\in KF$ は、すべての $i$ で $\Pi_i(\omega)\subseteq F$、すなわち $R_1(\omega)=\bigcup_i\Pi_i(\omega)\subseteq F$ と同値である。$F=E$ とすれば $m=1$ の場合になる。
$m$ で成り立つとする。$\omega\in K^{m+1}E=K(K^mE)$ は、$R_1(\omega)\subseteq K^mE$、すなわち帰納法の仮定により「すべての $\omega'\in R_1(\omega)$ で $R_m(\omega')\subseteq E$」と同値である。$m$ 歩の列の前に 1 歩をつなげれば分かるように、$\bigcup_{\omega'\in R_1(\omega)}R_m(\omega')=R_{m+1}(\omega)$ なので、これは $R_{m+1}(\omega)\subseteq E$ と同値である。$\square$
def-ck-knowledge の状況で、$R(\omega):=\bigcup_{m\ge0}R_m(\omega)$ とおく。
2 の (a)⇔(b) は Aum76 p. 1237 で、「$E$ が $\omega$ で共有知識」を (b) で定義したうえで、それが入れ子の文の言葉の定義と同値であることを、行ける点の言葉で説明している。
1。 $\omega\approx\omega'$ を $\omega'\in R(\omega)$ で定める。$\omega\in R_0(\omega)$ なので反射的である。列を逆にたどれば $\omega_{k-1}\in\Pi_{i_k}(\omega_k)$ なので対称的である。列をつなげば推移的である。よって $\approx$ は同値関係で、その同値類 $R(\omega)$ は $\Omega$ の分割 $\mathcal R$ をなす。
$\Pi_i(\omega)\subseteq R_1(\omega)\subseteq R(\omega)$ なので、$\mathcal R$ はどの $\Pi_i$ よりも粗い。逆に $\mathcal Q$ がどの $\Pi_i$ よりも粗い分割で、$Q$ が $\omega$ を含む元とする。$\omega_{k-1}\in Q$ なら $\Pi_{i_k}(\omega_{k-1})$ は $\omega_{k-1}$ を含む $\mathcal Q$ の元、すなわち $Q$ に含まれるので、$\omega_k\in Q$ である。帰納法で $R(\omega)\subseteq Q$。よって $\mathcal R$ はどの $\Pi_i$ よりも粗い分割のうち最も細かく、meet である。
2。 (a)⇔(b):$R_m(\omega)$ は $m$ について増大し、和集合が $R(\omega)=M(\omega)$ である。lem-ck-steps より、$\omega\in CE$ はすべての $m\ge1$ で $R_m(\omega)\subseteq E$ であることと同値で、これは $M(\omega)\subseteq E$ と同値である。
(b)⇒(c):$F:=M(\omega)$ は meet の元なので、1 よりどの $\Pi_i$ の元の和集合でもある。よって $K_iF=F$ で、$F$ は自明である。
(c)⇒(b):$F$ が自明なら、$F$ はどの $\Pi_i$ の元の和集合でもある。1 の証明と同じく、$\omega_{k-1}\in F$ なら $\omega_k\in\Pi_{i_k}(\omega_{k-1})\subseteq F$ なので、$M(\omega)=R(\omega)\subseteq F\subseteq E$。
3。 2 より $CE=\bigcup\{M(\omega)\mid M(\omega)\subseteq E\}$ で、これは $E$ に含まれる meet の元の和集合である。meet の元はどれも $\Pi_i$ の元の和集合なので、$CE$ も $\Pi_i$ の元の和集合で、$K_i(CE)=CE$。$E$ に含まれる自明な事象 $F$ と $\omega\in F$ については、(c)⇒(a) から $\omega\in CE$ なので、$F\subseteq CE$。$\square$
3 から、共有知識は「自明な事象が起きたことによってだけ」生じる。皆が同じ場所で同じ出来事を見て、互いに見ていることを見た場合がその典型である(Aum76 p. 1236)。
$\Omega$ が有限で $\lvert\Omega\rvert\ge2$ なら、$m\ge\lvert\Omega\rvert-1$ のすべての $m$ について $CE=K^mE$ である。
$N\ge1$ とし、$\Omega=\{0,1,\dots,N\}$、2 人の分割を
$$
\Pi_1=\{\{0\},\{1,2\},\{3,4\},\dots\},\qquad \Pi_2=\{\{0,1\},\{2,3\},\{4,5\},\dots\}
$$
とする(端の元は 1 点でもよい)。$E:=\{1,\dots,N\}$ とおく。確認の往復を数える状況で、$k$ は届いた確認の回数、$E$ は「少なくとも 1 回は届いた」に当たる。
主張:$1\le k\le N$ と $m\ge1$ について、$k\in K^mE\iff m\le k-1$。したがって $K^mE=\{m+1,\dots,N\}$、$CE=\emptyset$ である。
証明:どの元も連続する 2 点以下なので、1 歩で動ける距離は 1 以下である。また $j\ge1$ について $\{j-1,j\}$ は、$j$ が偶数なら $\Pi_1$ の元、奇数なら $\Pi_2$ の元である。よって $R_m(k)=\{j\in\Omega\mid \lvert j-k\rvert\le m\}$ で、これが $0$ を含まないことは $m\le k-1$ と同値である。lem-ck-steps から主張が従う。meet は $\{\Omega\}$ だけなので、thm-ck-meet からも $CE=\emptyset$ が分かる。
状態 $k$ では「全員が知っている」が $k-1$ 段まで成り立つのに、$k$ 段目で成り立たない。確認を何回往復させても共有知識にはならない。
$\Omega=\{a,b,c,d\}$、$\Pi_1=\{\{a,b\},\{c,d\}\}$、$\Pi_2=\{\{a,b,c\},\{d\}\}$、真の状態を $a$ とする(Aum76 p. 1237 の例の分割)。事象 $F:=\{a,b,c\}$ は $a$ で相互知識である($\Pi_1(a)=\{a,b\}\subseteq F$、$\Pi_2(a)=F$)。しかし $R_2(a)\ni d$($a\to c$ は $\Pi_2$、$c\to d$ は $\Pi_1$)なので $a\notin K^2F$ で、共有知識ではない。meet は $\{\Omega\}$ である。この分割の上で、各状態の確率を等しくとった事後確率の例は Aumannの合意定理 で扱う。
$n\ge1$ 人の子どもが遊んで、何人かの額に泥がついた。各人はほかの子の額は見えるが、自分の額は見えない。父親が皆の前で「少なくとも 1 人は泥がついている」と言い、続けて「自分の額に泥がついているか分かった人は手を挙げなさい」と繰り返し問う。子どもたちは賢く、正直で、同時に答え、答えは皆に見える。
状態を $x=(x_1,\dots,x_n)\in\Omega:=\{0,1\}^n$($x_i=1$ は $i$ に泥がついていること)で表し、$\lvert x\rvert:=x_1+\cdots+x_n$、$x$ の第 $i$ 成分だけを入れ替えた状態を $x^{(i)}$ と書く。子 $i$ はほかの成分を見ているので、分割は $\Pi_i(x)=\{x,x^{(i)}\}$ である。
公開の宣言や答えは、真の状態の候補の集合 $S\subseteq\Omega$ を、宣言の内容と合う状態だけに絞る、と表す。候補が $S$ に絞られている($S$ が共有知識である)とき、状態 $y\in S$ で子 $i$ が自分の額が分かるのは $\Pi_i(y)\cap S=\{y\}$、すなわち $y^{(i)}\notin S$ のときである。
真の状態 $x$ で泥のついた子が $k=\lvert x\rvert\ge1$ 人いるとする。
1。 宣言の後の候補の集合は $S_1:=E=\{y\mid\lvert y\rvert\ge1\}$ である。$1\le m\le k$ について、$m$ 回目の問いの前の候補の集合が $S_m:=\{y\mid\lvert y\rvert\ge m\}$ であることを帰納法で示し、同時に $m$ 回目の答えを求める。
$S_m$ の点 $y$ で子 $i$ が分かるかを調べる。$y_i=0$ なら $\lvert y^{(i)}\rvert=\lvert y\rvert+1\ge m$ なので $y^{(i)}\in S_m$ で、分からない。$y_i=1$ なら $\lvert y^{(i)}\rvert=\lvert y\rvert-1$ なので、分かるのは $\lvert y\rvert=m$ のときに限る。よって $S_m$ の点 $y$ で手を挙げる子がいるのは $\lvert y\rvert=m$ のときだけで、そのとき挙げるのはちょうど泥のついた子である。
真の状態 $x$ では、$m< k$ なら $\lvert x\rvert>m$ なので誰も挙げない。この答えと合う候補は、手を挙げる子のいない点 $\{y\in S_m\mid\lvert y\rvert\ne m\}=S_{m+1}$ である。$m=k$ では $\lvert x\rvert=k$ なので泥のついた子だけが挙げる。
2。 候補の集合は $\Omega$ のままである。どの $y$ でも $y^{(i)}\in\Omega$ なので誰も分からず、答え(全員が挙げない)はどの状態とも合うので、候補は $\Omega$ から変わらない。これが何回でも繰り返される。
3。 1 歩で変わる成分は 1 つ以下で、どの成分も 1 歩で変えられるので、$R_m(x)=\{y\mid d(x,y)\le m\}$ である($d$ は異なる成分の数)。$E$ の外の点は $0$ だけで、$d(x,0)=k$ なので、$R_m(x)\subseteq E\iff m\le k-1$。lem-ck-steps から主張が従う($m=0$ では $x\in E$)。$\square$
$k\ge2$ のとき、宣言は誰も知らなかった事実を伝えたわけではない。伝えたのは、$E$ が共有知識であることである。宣言の後は候補の集合が $E$ になり、$E$ 全体が自明な事象になる。宣言がなければ、1 回目の問いへの答え(全員が挙げない)からは何も絞れず、推論が始まらない。
| 外す条件 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| (i) 情報が分割で与えられる(真の状態が自分の候補に入る) | $\Omega=\{a,b\}$、1 人、候補の集合を $P_1(a)=P_1(b)=\{b\}$ とし、$K_1E:=\{\omega\mid P_1(\omega)\subseteq E\}$ | $CE\subseteq E$(thm-ck-meet の 3) |
| (iii) $\Omega$ が有限 | ex-ck-chain の分割を $\Omega=\{0,1,2,\dots\}$ の上でとる | ある有限の $m$ で $CE=K^mE$(cor-ck-finite) |
| 父親の宣言($E$ を共有知識にする) | thm-ck-muddy の 2:$k\ge2$ なら $E$ は相互知識 | $k$ 回目に泥のついた子が分かる(thm-ck-muddy の 1) |
確かめを順に書く。
1 行目:$E=\{b\}$ とすると $K_1E=\Omega$、$K_1\Omega=\Omega$ なので、1 人の場合 $K^mE=\Omega$ がすべての $m$ で成り立ち、$CE=\Omega\not\subseteq E$ である。状態 $a$ で「$b$ が起きた」と誤って知ってしまう。候補 $P_1(a)$ が $a$ を含まないことだけが分割の条件から外れている($P_1(a)=P_1(b)$ なので、候補どうしは交われば一致する)。
2 行目:$\Omega$ が無限でも ex-ck-chain の証明はそのまま通り、$K^mE=\{m+1,m+2,\dots\}$ はどの $m$ でも空でないが、$CE=\emptyset$ である。よって $CE=K^mE$ となる有限の $m$ はない。
3 行目:thm-ck-muddy の 3 から、$k\ge2$ なら宣言の前に $x\in KE$ である。それでも 2 から、誰も手を挙げない。相互知識(さらに $k-1$ 段までの入れ子)では足りず、宣言が加えたのは共有知識であることだけである。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 全員が知っていれば共有知識である | 入れ子がすべての段で成り立つ必要がある | ex-ck-chain、ex-ck-aumann4 |
| 誰もが知っている事実を公表しても何も変わらない | 公表によって共有知識になり、推論の結果が変わりうる | thm-ck-muddy |
| 共有知識は有限回の確認で必ず得られる | 確認の往復では、どの段でも次の段が欠ける | ex-ck-chain |
| meet は各人の分割の共通の細分である | 共通の細分は join(全員の情報を合わせたもの)。meet は共通の粗い分割 | def-ck-main の 2 |
| $K$ も $K_i$ と同じく $KKE=KE$ を満たす | $K^2E\subsetneq KE$ となりうる | ex-ck-chain |
分割と meet による共有知識の定式化と、それが入れ子の文の言葉の定義と同値であることは Aumann(Aum76 pp. 1236–1237)による。そこでは、各人の分割そのものが共有知識であるという仮定が一般性を失わないことも注意されている(同 p. 1237)。完備情報の展開形ゲームでは、ゲームの規則が全員の共有知識であることが前提になっている(KP17 p. 115 とその脚注 1)。事後確率が共有知識なら一致するという結果は Aumannの合意定理、各人に私的な情報のあるゲームは Bayesゲーム で扱う。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する