常識（論理）

共通知識は、エージェントのグループにとって特別な種類の知識です。エージェントのグループGには、 G内のすべてのエージェントがpを知っていて、全員がpを知っていることを知っていて、全員がp を知っていることを全員が知っていることを知っていて、以下同様に無限に続く場合、 pに関する共通知識があります。^[1]これは と表記されます。 ${\displaystyle C_{G}p}$

この概念は、哲学文献の中でデイヴィッド・ケロッグ・ルイスの研究「コンベンション」（1969年）で初めて紹介されました。社会学者モリス・フリーデルは1969年の論文で共通知識を定義しました。^[2]ロバート・オーマン（1976年）によって集合論的枠組み で初めて数学的な定式化が行われました。コンピュータ科学者は、 1980年代から認識論的論理一般、特に共通知識という主題に興味を持ち始めました。 ^{[1]この概念に基づく}パズルは 数多くあり、ジョン・コンウェイなどの数学者によって広範囲に研究されてきました。^[3]

哲学者スティーブン・シファーは、1972年の著書Meaningで、独自に「相互知識」( )と呼ぶ概念を展開した。これは、ルイスとフリーデルが1969年に提唱した「常識」と非常によく似た機能を持つ。^{[4]信頼できる発表が}公になされれば、それは常識となる。しかし、それが各エージェントに内密に伝えられれば、それは相互知識にはなるが常識にはならない。「グループ内のすべてのエージェントがpを知っている」( )という事実が各エージェントに内密に伝えられたとしても、それは依然として常識ではない。しかし、いずれかのエージェントがpについての自分の知識を公に発表すれば、そのエージェントがpを知っていることは常識となる(すなわち)。すべてのエージェントがpについての自分の知識を公に発表すれば、pは常識となる。 ${\displaystyle E_{G}p}$${\displaystyle E_{G}p}$${\displaystyle E_{G}E_{G}p\not \Rightarrow C_{G}p}$${\displaystyle a}$${\displaystyle C_{G}K_{a}p}$${\displaystyle C_{G}E_{G}p\Rightarrow C_{G}p}$

共通知識の考え方は、しばしば誘導パズルの変形（例：泥だらけの子供パズル）によって導入される：^[2]

ある島に、青い目をしたk人の人がいて、残りの人々は緑の目をしています。パズルの開始時には、島にいる誰も自分の目の色を知りません。ルールにより、島の誰かが自分の目が青いことに気付いた場合、その人は夜明けに島を去らなければなりません。そのようなことに気付かなかった人は、夜明けまで必ず眠ります。島では、誰もが他の人の目の色を知っており、反射面はなく、目の色を伝えることはありません。

ある時点で、部外者が島にやって来て、島の住民全員を呼び集め、次のように公に発表します。「あなたたちのうち少なくとも 1 人は青い目をしています。」 さらに、部外者は全員に正直であることが知られており、全員がこれを知っていることを全員が知っている、などとなります。つまり、彼が正直であることは常識であり、したがって、少なくとも 1 人の青い目をした島民がいる ( ) ことは常識になります。問題は、島のすべての人が完全に論理的であり (すべての参加者の知識が認識論的論理の公理スキーマに従う)、これも常識であると仮定して、最終的な結果を見つけることです。 ${\displaystyle C_{G}[\exists x\!\in \!G(Bl_{x})]}$

答えは、発表後のk日の夜明けに、青い目の人々は全員島を去るということです。

解決法は帰納的議論で見ることができます。k  = 1 (つまり、青い目の人がちょうど 1 人いる) の場合、その人は (他の人の目が緑色であることから) 自分だけが青い目であることを認識し、最初の夜明けに出発します。k = 2 の場合、最初 の夜明けには誰も出発せず、その不作為 (および各エージェントの暗黙の知識不足) は全員に観察され、これも共通知識になります ( )。青い目の 2 人は、青い目の人を 1 人だけ見ており、最初の夜明けには誰も出発しなかったこと (したがってk  > 1 であり、もう 1 人の青い目の人は自分以外の全員が青い目ではないとは考えていないため、もう 1 人の青い目の人は) から、2 回目の夜明けに出発します。帰納的に、 少なくともk 人の青い目の人がいる場合に限り、最初のk − 1 回の夜明けには誰も出発しないと推論できます。青い目の人は、他の人々の中に青い目の人がk  − 1 人いることに気づき、少なくともk 人はいるはずだと知りながら、彼らは青い目をしているに違いないと考え、立ち去るでしょう。 ${\displaystyle C_{G}[\forall x\!\in \!G(\neg K_{x}Bl_{x})]}$${\displaystyle \neg K_{a}[\forall x\!\in \!(Ga)(\neg Bl_{x})]}$${\displaystyle \exists x\!\in \!(Ga)(Bl_{x})}$

k > 1の場合 、部外者は島の住民に、彼らの中に青い目の人がいるということだけを伝えます。ただし、この事実が発表される前は、その事実は共通知識ではなく、相互知識です。

k = 2の場合 、それは単なる「一次」知識 ( ) です。青い目の人はそれぞれ、青い目の人がいることを知っていますが、青い目の人はそれぞれ、もう 1 人の青い目の人が同じ知識を持っていることを知りませ ん。${\displaystyle E_{G}[\exists x\!\in \!G(Bl_{x})]}$

k = 3の場合 、これは「2 次」の知識です ( )。青い目の人はそれぞれ、2 番目の青い目の人が 3 番目の人が青い目を持っていることを知っていることを知っていますが、部外者が発言するまで、その知識を持つ3 番目の青い目の人がいることは誰も知りません。 ${\displaystyle E_{G}E_{G}[\exists x\!\in \!G(Bl_{x})]=E_{G}^{2}[\exists x\!\in \!G(Bl_{x})]}$

一般的に、k  > 1 の場合、それは「( k  − 1) 次」の知識です ( )。青い目の人はそれぞれ、2 番目の青い目の人が 3 番目の青い目の人がそれを知っていることを知っていることを知っています... (合計k  − 1 レベル繰り返します) k番目の人は青い目をしていますが、その知識を持つ「 k番目の」青い目の人がいることは、部外者が発言するまで誰も知りません。したがって、共通知識の概念には明白な効果があります。誰もが知っていることを知ることは、違いを生みます。部外者の公の発表 (k=1 でない限り、すべての人に既に知られている事実であり、青い目の 1 人の人は発表まで知りません) が共通知識になると、この島の青い目の人々は最終的に自分たちの地位を推測し、島を去ります。 ${\displaystyle E_{G}^{k-1}[\exists x\!\in \!G(Bl_{x})]}$

特に：

1. ${\displaystyle E_{G}^{i}[|G(Bl_{x})|\geq j]}$は自由である（つまり、部外者の発言の前に知られている）場合に限られます 。${\displaystyle i+j\leq k}$
2. ${\displaystyle E_{G}^{i}[|G(Bl_{x})|\geq j]}$誰も帰らない日が過ぎるということは、次の日を意味します。${\displaystyle E_{G}^{i-1}[|G(Bl_{x})|\geq j+1]}$
3. ${\displaystyle E_{G}^{i}[|G(Bl_{x})|\geq j]}$したがって、 に到達するのは、 に到達する場合のみです。${\displaystyle j\geq k}$${\displaystyle i+j>k}$
4. 部外者はに与えます。${\displaystyle E_{G}^{i}[|G(Bl_{x})|\geq j]}$${\displaystyle i=\infty,j=1}$

共通知識は、様相演算子が認識論的に解釈されるマルチモーダル論理システムで論理的に定義できます。命題レベルでは、このようなシステムは命題論理の拡張です。拡張は、エージェントのグループGと、 "エージェントi が知っている"という意味を持つn 個の様相演算子K _i ( i = 1, ...,  n ) の導入で構成されます。したがって、K _i (ここで、は論理計算の式) は "エージェントi が知っている" と読みます。次の公理で定義することにより、 "グループGの全員が知っている" という意味を持つ演算子E _{G を定義できます。} ${\displaystyle \varphi}$${\displaystyle \varphi}$${\displaystyle \varphi}$

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

を と省略して と定義すると、共通知識は公理で定義できる。 ${\displaystyle E_{G}E_{G}^{n-1}\varphi }$${\displaystyle E_{G}^{n}\varphi }$${\displaystyle E_{G}^{0}\varphi =\varphi }$

${\displaystyle C\varphi \Leftrightarrow \bigwedge _{i=0}^{\infty }E^{i}\varphi }$

しかし、複雑な点があります。認識論的論理の言語は通常有限ですが、上記の公理は共通知識を式の無限連言として定義しており、したがって言語の整形式の式ではありません。この困難を克服するために、共通知識の不動点定義を与えることができます。直感的には、共通知識は「方程式」の不動点と考えられます。ここで、はアレフ・ノートです。このようにして、を意味する式を見つけることができ、その極限で、 の共通知識を推論することができます。 ${\displaystyle C_{G}\varphi =[\varphi \wedge E_{G}(C_{G}\varphi )]=E_{G}^{\aleph _{0}}\varphi }$${\displaystyle \aleph_{0}}$${\displaystyle \psi}$${\displaystyle E_{G}(\varphi \wedge C_{G}\varphi )}$${\displaystyle \varphi}$

この定義から、 が一般知識である場合、も一般知識であることがわかります( )。 ${\displaystyle E_{G}\varphi }$${\displaystyle \varphi}$${\displaystyle C_{G}E_{G}\varphi \Rightarrow C_{G}\varphi }$

この統語的特徴付けには、いわゆるクリプキ構造を通じて意味内容が与えられます。クリプキ構造は、上で定義される状態（または可能世界）の集合S、n 個の アクセス可能関係 （エージェントi が任意の状態から可能と見なす状態を直感的に表す）、および各状態での言語の各基本命題に真理値を割り当てる評価関数によって与えられます。知識演算子のクリプキ意味論は、 が状態sで真である場合とが成り立つすべての状態tで真である場合に限り、と規定することによって与えられます。次に、共通知識演算子の意味論は、 の各エージェント グループGについて、の反射（様相公理T）および推移閉包（様相公理4）を取り、 G内のすべてのエージェントiについて、そのような関係 を呼び、 が状態sで真である場合と が成り立つすべての状態tで真である場合に限り、と規定することによって与えられます。 ${\displaystyle R_{1},\dots ,R_{n}}$${\displaystyle S\times S}$${\displaystyle \pi }$${\displaystyle K_{i}\varphi }$${\displaystyle \varphi }$${\displaystyle (s,t)\in R_{i}}$${\displaystyle R_{i}}$${\displaystyle R_{G}}$${\displaystyle C_{G}\varphi }$${\displaystyle \varphi }$${\displaystyle (s,t)\in R_{G}}$

あるいは、 (それでも同等ですが) 共通知識は集合論を使用して形式化できます (これは、ノーベル賞受賞者のロバート・オーマンが 1976 年の画期的な論文で採用した方法です)。状態集合Sから始めます。イベントE は、状態集合Sのサブセットとして定義できます。各エージェントiについて、S上のパーティションP _{i を}定義します。このパーティションは、ある状態におけるエージェントの知識の状態を表します。直感的には、 2 つの状態 s 1 と s 2 がエージェントのパーティションの同じ部分の要素である場合、s ₁とs ₂はそのエージェントにとって区別がつかないことを意味します。_一般に、_状態sでは、エージェントi はP _i ( s )の状態の 1 つが得られることは知っていますが、どの状態が得られるかは知りません (ここで、P _i ( s ) はsを含むP _iの一意の要素を表します。このモデルでは、エージェントが真実でない事柄を知っているケースは除外されます。)

知識関数K は次のように定義できます。

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

つまり、K _i ( e ) は、エージェントがイベントe が発生することを知る状態の集合です。これはeのサブセットです。

上記の様相論理の定式化と同様に、「誰もが知っている」という考えの演算子はeとして定義できます。

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

様相演算子と同様に、E関数を反復し、これを使用して共通知識関数を定義できます。 ${\displaystyle E^{1}(e)=E(e)}$${\displaystyle E^{n+1}(e)=E(E^{n}(e))}$

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

上で概説した統語論的アプローチとの同値性は容易に見ることができます。今定義した Aumann 構造を考えてみましょう。同じ空間S、パーティション に対応する同値類を定義するアクセス可能性関係、および となるすべての状態sでのみ基本命題pに真の値を生成する評価関数を取ることで、対応する Kripke 構造を定義できます。ここで は基本命題pに対応する Aumann 構造のイベントです。前のセクションで定義した共通知識アクセス可能性関数が、すべての に対するパーティションの最も細かい共通粗大化に対応していることは容易にわかります。これは、Aumann が 1976 年の論文でも示した共通知識の有限特徴付けです。 ${\displaystyle R_{i}}$${\displaystyle P_{i}}$${\displaystyle s\in E^{p}}$${\displaystyle E^{p}}$${\displaystyle R_{G}}$${\displaystyle P_{i}}$${\displaystyle i\in G}$

共通知識は、デイヴィッド・ルイスが慣習に関する先駆的なゲーム理論的説明で使用しました。この意味で、共通知識は、ルイス流の慣習主義的言語説明を主張する言語学者や言語哲学者にとって、今でも中心的な概念です (Clark 1996 を参照)。

ロバート・オーマンは、共通知識の集合論的定式化（理論的には上記と同等）を導入し、いわゆる合意定理を証明しました。合意定理とは、2 人のエージェントが特定のイベントに対して共通の事前確率を持ち、事後確率が共通知識である場合、そのような事後確率は等しいというものです。合意定理に基づき、ミルグロムによって証明された結果は、市場の効率性と情報に関する特定の条件が与えられた場合、投機的な取引は不可能であることを示しています。

共通知識の概念はゲーム理論の中心です。長年、ゲーム参加者が合理性について共通知識を持っているという仮定が基本であると考えられてきました。2人プレイのゲームでは、合理性についての共通知識はナッシュ均衡 戦略の認識論的条件として必要ではないことが判明しました (Aumann and Brandenburger 1995) 。

コンピュータ科学者は、分散システムについて推論するために、認識論的論理 (および共通知識) を組み込んだ言語を使用します。このようなシステムは、単純な命題認識論的論理よりも複雑な論理に基づくことができます。Wooldridge Reasoning about Artificial Agents、2000 (認識論的演算子と時間的演算子を組み込んだ一階論理を使用) または van der Hoek らの「Alternating Time Epistemic Logic」を参照してください。

スティーブン・ピンカーは、2007 年の著書『 思考の素材: 人間の性質を垣間見る言語』の中で、 共通知識の概念を使用して、ほのめかしに含まれる間接話法の種類を分析しています。

コメディ映画「ホット・リード・アンド・コールド・フィート」には、常識によって崩壊する論理の連鎖の例があります。デンバー・キッドは仲間に、ラトルスネークが町にいるが、彼 [キッド] が「優位」であると伝えます。「彼はここにいて、私は彼がここにいることを知っている。そして彼は私が彼がここにいることを知っていることを知っているが、彼は私が彼がここにいることを知っていることを知っていることを知らない。」つまり、主人公は両方とも主要な事実 (ラトルスネークがここにいる) を知っているが、それは「常識」ではないのです。キッドが間違っていたとしても、これは当てはまることに注意してください。ラトルスネークは、キッドが彼が知っていることを知っていることを知っていることを知っているかもしれませんが、キッドがそれを知らないため、連鎖はやはり壊れます。しばらくして、ラトルスネークはキッドと対峙します。キッドは、彼が慎重に構築した「優位」が常識に崩壊したことに気づきます。

• グローバルゲーム
• 相互知識（論理）
• 多元的な無知
• 鹿狩り
• スティーブン・シファー
• 信頼性の低いチャネルを介して共通知識を確立することが不可能であるという2人の将軍の問題

1. ^ 教科書『Reasoning about knowledge』（Fagin、Halpern、Moses、Vardi 著、1995 年）および『Epistemic Logic for computer science』（Meyer および van der Hoek 著、1995 年）を参照してください。
2. ^ 構造的に同一の問題がハーバート・ギンティス（2000）によって提示されており、彼はそれを「セビタンの女性​​たち」と呼んでいる。

• オーマン、ロバート（1976）「意見の相違に同意する」統計年報4（6）：1236-1239。
• オーマン・ロバートとアダム・ブランデンブルガー (1995) 「ナッシュ均衡の認識条件」Econometrica 63(5): 1161–1180。
• クラーク、ハーバート (1996) 『言語の使用』、ケンブリッジ大学出版局ISBN 0-521-56745-9 
• フェイギン、ロナルド、ハルパーン、ジョセフ、モーゼス、ヨラム、ヴァルディ、モシェ (2003)。知識についての推論。ケンブリッジ: MIT 出版。ISBN 978-0-262-56200-3。。
• ルイス、デイヴィッド（1969）『コンベンション：哲学的研究』オックスフォード ：ブラックバーン。ISBN 0-631-23257-5 
• JJ Ch. Meyer と W van der Hoek 著「コンピュータサイエンスと人工知能のための認識論的論理」第 41 巻、Cambridge Tracts in Theoretical Computer Science、Cambridge University Press、1995 年。ISBN 0-521-46014 -X 
• レッシャー、ニコラス（2005）。認識論的論理：知識の論理の概観。ピッツバーグ大学出版局。ISBN 978-0-8229-4246-7。第3章を参照してください。
• ショーハム、ヨアブ、レイトンブラウン、ケビン (2009)。マルチエージェントシステム：アルゴリズム、ゲーム理論、論理的基礎。ニューヨーク：ケンブリッジ大学出版局。ISBN 978-0-521-89943-7。セクション 13.4 を参照してください。オンラインで無料でダウンロードできます。
• ギンティス、ハーバート（2000）ゲーム理論の進化プリンストン大学出版局。ISBN 0-691-14051-0 
• ギンティス、ハーバート（2009）理性の境界プリンストン大学出版局。ISBN 0-691-14052-9 
• Halpern, JY ; Moses, Y. (1990). 「分散環境における知識と共通知識」Journal of the ACM . 37 (3): 549–587. arXiv : cs/0006009 . doi :10.1145/79147.79161. S2CID  52151232.

• ヴァンダーシュラーフ、ピーター。シッラーリ、ジャコモ。 「常識」。 『ザルタ』、エドワード N. (編)。スタンフォード哲学百科事典。
• テレンス・タオ教授のブログ投稿 (2008 年 2 月)
• Carr, Kareem。「長い目で見れば、私たちはみんな死んでいる」、「長い目で見れば、私たちはみんな死んでいる II」、The Twofold Gaze にて。青い目の島民問題の詳細な説明と解決策。
• physics.harvard.edu 「緑の目をしたドラゴンの問題」 2014-12-01 にWayback Machineでアーカイブ、「緑の目をしたドラゴンの解決策」 2014-12-01 にWayback Machineでアーカイブ(2002 年 9 月)