共有知識

共有知識 (きょうゆうちしき、common knowledge) とは、エージェントの集団における特殊な知識のひとつ。エージェントの集団 G で p が共有知識であるとは、G に属するエージェント全員が p を知っていて、また「全員が p を知っている」ということを全員が知っていて、また「『全員が p を知っている』ということを全員が知っている」ということを全員が知っていて、というように際限なく続くときをいう。

この概念が哲学の文献においてはじめて導入されたのは、デイヴィド・ルイスの Convention (1969) においてであった。その数学的定式化は集合論の枠組みを用いてロバート・オーマンによってなされた。1976 年、計算機科学者が一般に認識論理の問題、なかんずく共有知識の問題に興味を強めていったのは 1980 年代であった。この概念にもとづくパズルは多数あり、ジョン・コンウェイをはじめとする数学者たちによって幅広く研究されてきた。

例

共有知識の考えは、しばしば次のようなパズルの変種によって紹介される： ある島にいる人びとのうち、青色の目をもったものが k 人いて、残りは緑色の目をしているとする。青い目の人は少なくとも1人はいるものとする (k ≥ 1)。自分の目が青いということを知った人は明くる日の夜明けに島を出なければならない。それぞれの人は、他人の目の色を見ることはできるが、この島には反射するような面はなく、自分の目の色は知ることができない。ある時点において、1 人のよそ者がこの島にやってきて、この島の人たち全員に呼びかけ、「あなたがたのなかに少なくとも 1 人青い目の者がいる」という発表を行う。さらに、このよそ者は正直者であるということが全員に知られており、またそのことを全員が知っているということを全員が知っており、以下同様とする：このよそ者が正直者であるということが共有知識であり、したがって青い目の島民がいるということが共有知識になる。問題は次のようである：「この島の全員が完全に論理的であり、またそのことが共有知識であるとすると、最終的に何が起こるか」。

その答えは、このよそ者の発表のあとの k 度めの夜明けに、青い目の人びと全員が島を出ることになるというものである。

このことは帰納的な議論によって簡単にわかる。k = 1 のとき、この唯一の青い目の人は、(他人が全員緑色の目をしていることを見て) 自分が青い目の人なのだと認め、最初の夜明けに島を出る。k = 2 のとき、最初の夜明けには誰も島を出ない。青い目の 2 人の人たちは、ただ 1 人の青い目の人を目にしており、かつ、最初の夜明けに誰ひとり島を出なかったことを見て、2 日めの夜明けに島を出る。同様にして、少なくとも k 人の青い目の人がいるとき、またそのときに限り、最初の k − 1 日間には誰も島を出ないことがわかる。青い目の人びとは、自分以外のなかに k − 1 人の青い目の人がいることを見て、なおかつ少なくとも k 人青い目の人がいなければならないことを知って、自分の目も青いということを推論し島を出ることになる。

このシナリオにおいていちばん興味深いのは、k > 1 のとき，このよそ者は島民に対して、「島民のなかに青い目の人がいる」という、島民がすでに知っていることしか言っていないということである。しかしながら、この事実が発表されるまえは、この事実は「共有知識」ではないのである。

k = 2 のとき、これは単なる「1 階の」知識である。2 人の青い目の人物はそれぞれ、青い目の人間がいるということは知っているが、そのもう一方の青い目の人物がまったく同じ知識を有しているということは知らない。

k = 3 のとき、これは「2 階の」知識になる。2 日経ったあと、青い目の人物のそれぞれは、「『3 人めが青い目をしている』ということを 2 番めの青い目の人物が知っている」ということを知るが、そういう知識をもった「3 人め」の青い目の人物がいるということは 3 日めが来るまでは誰も知らないのである。

一般的には次のようになる。k > 2 に対し、これは「(k − 1) 階の」知識になる。k − 1 日経ったあと、青い目の人物のそれぞれは、「『k 人めが青い目をしている』ということを……」ということを 3 番目めの青い目の人物が知っている』ということを 2 番めの青い目の人物が知っている」ということを知る (k − 1 階にわたって反復) が、そういう知識をもった「k 人め」の青い目の人物がいるということは、k 日めが来るまで誰も知らない。共有知識の概念はこうして明白な効果をもつ。全員が知っているということを知るということが重要なのである。よそ者の発表 (事実としてはすでに周知のこと) が共有知識になると、青い目の人びとは最終的に自分の目の色について演繹し、島を出ることになるのである。

定式化

様相論理（構文論的特徴づけ）

共通認識は、認識論的に解釈される複数の様相演算子をもつ多様相論理の体系において論理学的な定義を与えうる。命題のレベルでは、このような体系は命題論理の拡張となっている。付け加えられるのは、エージェントたちの集団 G と、「エージェント i が知っている」ということを意味するものとする n 個の様相演算子 K_i (i = 1, ..., n) である。したがって K_i $\varphi$（$\varphi$ はこの論理における式）は、「エージェント i は $\varphi$ を知っている」と読まれる。「G の全員が知っている」という意味の演算子 E_G を、

$E_{G}\varphi \Leftrightarrow \bigwedge _{i\in G}K_{i}\varphi ,$

によって定義することができるだろう。

$E_{G}E_{G}^{n-1}\varphi$ を $E_{G}^{n}\varphi$ と書く省略記法を用い、また $E_{G}^{0}\varphi =\varphi$ と約束することによって、共有知識を、

$C\varphi \Leftrightarrow \bigwedge _{i=1}^{n}E^{n}\varphi ,\;n=1,2,\ldots$

で定義することができる。

しかしここにはまだ問題が残っている。認識論理の言語はふつう有限的 (finitary) であるが、上の定義では共有知識を式の無限個の連言によって定めており、したがってこれはこの言語における論理式になっていない。この問題を克服するため「不動点」(fixed-point) としての共有知識の定義が与えられる。直観的に、共有知識は「方程式」$E_{G}(\varphi \wedge C_{G}\varphi )$ の不動点とみなせる。こうして、$E_{G}(\psi \wedge C_{G}\varphi )$ を含意する式 $\psi$ を見つけることができ、そこから極限において、$\varphi$ の共有知識を推論することができる。

この「構文論的」な特徴づけには、いわゆる「クリプキ構造」を通して意味論的な内容が与えられる。クリプキ構造は、

1. 状態 (ないし可能世界) の集合 S,
2. S × S 上に定義された n 個の「アクセス可能関係」(accessibility relations) $R_{1},\ldots ,R_{n}$, これは直観的には、任意の所与の状態から、エージェント i が可能であると考える状態を表現する。
3. 各状態において、言語の原子命題のそれぞれに真理値を割りあてる付値関数 π,

によって与えられる。知識演算子の意味論は、$K_{i}\varphi$ が状態 s で真であるのは $(s,t)\in R_{i}$ なるすべての状態 t で $\varphi$ が真であるとき、またそのときに限る。と定めることで与えられる。すると共有知識演算子の意味論は、まずエージェントの集団 G のそれぞれに対し、その G に属するすべてのエージェント i について R_i の反射的かつ推移的閉包をとり、その 2 項関係を R_G と呼ぶことにして、$C_{G}\varphi$ が状態 s で真であるのは、$(s,t)\in R_{G}$ なるすべての状態 t で $\varphi$ が真であるとき、またそのときに限る、と定めることで与えられる。

集合論（意味論的特徴づけ）

（等価な）代替案として、共有知識は集合論を用いて定式化することもできる（これはノーベル賞受賞者ロバート・オーマンがその独創的な 1976 年論文においてとった方法である）。 まず状態の集合 S から始める。状態の集合 S の部分集合として事象 E を定義できる。それぞれのエージェント i について，S 上の分割 P_i を定義する。この分割が、ある状態におけるエージェントの知識の状態を表現している。状態 s において、エージェント i は、P_i (s) のうちのどれかの状態が起きていることを知るのだが、それがどれなのかは知らない（ここで P_i (s) は、s を含む分割 P_i の一意な要素を表す。このモデルではエージェントが真でないことを知ってしまうというケースは排除されていることに注意せよ）。

ここで知識関数 K を次のようにして定められる：

$K_{i}(e)=\{s\in S|P_{i}(s)\subset e\}$

すなわち、K_i (e) は、事象 e が起こっていることをエージェントが知っているような状態の集合である。これは e の部分集合になる。

上の様相論理による定式化と同じようにして、「全員が e を知っている」ということを表す演算子を定義できる：

$E(e)=\bigcap _{i}K_{i}(e)$

様相演算子の場合と同じく、関数 E は再帰的に用いることができ、$E^{1}(e)=E(e),E^{n+1}(e)=E(E^{n}(e))$ とする。これを使うと共有知識関数を、

$C(e)=\bigcap _{n=1}^{\infty }E^{n}(e)$

と定義できる。

上で素描した構文論的なアプローチとの等価性は簡単に確認できる：いま定義したオーマン構造を考えよ．これと対応するクリプキ構造を、

1. 同じ集合 S,
2. 分割 P_i に一致する同値類を定めるアクセス可能関係 R_i,
3. 原子命題 p に対応する、オーマン構造における事象を E^p とする。これに属する状態 $s\in E^{p}$ のすべてにおいてだけ、原子命題 p に「真」という値を与えるような付値関数、

として定められる。前節で定義した共有知識アクセス可能性関数 R_G が、すべての $i\in G$ の分割 P_i の finest common coarsening に一致することを確認するのは難しくなく、これはオーマンの 1976 年論文で与えられた共有知識の有限的な特徴づけになっている。

応用

共有知識は、デイヴィド・ルイスによって、慣習についての先駆的なゲーム理論的説明のために用いられた。この意味で共有知識は、ルイス主義、言語の規約主義的説明を支持する言語学者と言語哲学者にとって、いまだ中心的な概念なのである（Clark 1996 を見よ）。

ロバート・オーマンは共有知識の集合論的定式化を導入し（上で与えたものと理論的に等価なもの）、次のことを通していわゆるオーマンの一致定理を証明した：特定の事象について 2 人のエージェントが共通の事前確率をもっており、また事後確率が共有知識であるとき、その事後確率は 2 人のあいだで等しい。一致定理にもとづく結果として、ミルグロムは、市場の効率性と情報についての特定の条件のもとで投機的取引が不可能であることを示した。

共有知識の概念はゲーム理論において中心的である。長いあいだ、ゲームにおけるプレーヤーたちの合理性が共有知識であるという仮定は、基本的で必須のものと考えられてきた。Aumann and Brandenburger (1995) によって、2 人ゲームでは合理性が共有知識であることはナッシュ均衡戦略のための認識論的条件としては不要であることがわかった。

計算機科学者は、分散システムについての議論のために認識論理（および共有知識）を含む言語を用いている。そのような体系は、簡単な命題認識論理よりも複雑な論理学に基づいている。それについては、Wooldridge Reasoning about Artificial Agents, 2000（認識演算子と時間演算子を含む 1 階論理を用いている）または van der Hoek et al. "Alternating Time Epistemic Logic" を見よ。

2007年の著書 The Stuff of Thought: Language as a Window into Human Nature でスティーブン・ピンカーは風刺にかかわる間接話法の分析のために共有知識の観念を用いた。

関連項目

• グローバルゲーム
• 二人の将軍問題 — 信頼できないチャネルを通しては共有知識を確立することが不可能であること。
• 相互知識

脚注

1. ^ Fagin, Halpern, Moses and Vardi (1995), Reasoning about knowledge や Meyer and van der Hoek (1995), Epistemic Logic for computer science のような教科書を見よ。
2. ^ 構造的に同形の問題が Herbert Gintis (2000) に与えられている。ギンタスはこれを "The Women of Sevitan" と呼んだ。

参考文献

• Aumann, Robert (1976) "Agreeing to Disagree" Annals of Statistics 4(6): 1236–1239.
• Aumann Robert and Adam Brandenburger (1995) "Epistemic Conditions for Nash Equilibrium" Econometrica 63(5): 1161–1180.
• Clark, Herbert (1996) Using Language, Cambridge University Press ISBN 0-521-56745-9
• Fagin, Ronald; Halpern, Joseph; Moses, Yoram; Vardi, Moshe (2003). Reasoning about Knowledge. Cambridge: MIT Press. ISBN 978-0-262-56200-3 .
• Lewis, David (1969) Convention: A Philosophical Study Oxford: Blackburn. ISBN 0-631-23257-5
• J-J Ch. Meyer and W van der Hoek Epistemic Logic for Computer Science and Artificial Intelligence, volume 41, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1995. ISBN 0-521-46014-X
• Rescher, Nicolas (2005). Epistemic Logic: A Survey Of the Logic Of Knowledge. University of Pittsburgh Press. ISBN 978-0-8229-4246-7 . See Chapter 3.
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 978-0-521-89943-7. http://www.masfoundations.org . See Section 13.4; downloadable free online.
• Gintis, Herbert (2000) Game Theory Evolving Princeton University Press. ISBN 0-691-14051-0
• Gintis, Herbert (2009) The Bounds of Reason Princeton University Press. ISBN 0-691-14052-9

外部リンク

• Common Knowledge （英語） - スタンフォード哲学百科事典「Peter Vanderschraaf and Giacomo Sillari」の項目。
• Prof. Terence Tao's blog post (Feb 2008)
• Carr, Kareem. "In the Long Run We Are All Dead", "In the Long Run We Are All Dead II" at The Twofold Gaze. Detailed description of the blue-eyed islander problem, with solution.