상식(논리학)

공통 지식은 에이전트 그룹에게 특별한 종류의 지식이다. 에이전트 G의 그룹에는 p에 대한 공통적인 지식이 있다. G의 모든 에이전트가 p를 알고 있고, 그들 모두가 p를 알고 있다는 것을 알고 있다. 그들은 모두 p를 알고 있다는 것을 알고 있다. 광고 infinfinitum.^[1]

이 개념은 데이비드 켈로그 루이스가 그의 연구협약(1969년)에서 철학적 문헌에 처음 소개되었다. 사회학자 모리스 프리델은 1969년 논문에서 공통 지식을 정의했다.^[2] 로버트 아우만(1976년)에 의해 처음으로 세트이론적 틀에서 수학적인 공식화가 주어졌다. 컴퓨터 과학자들은 1980년대부터 인식론적 논리학, 특히 상식 논리의 주제에 관심을 갖게 되었다.^[1] 존 콘웨이와 같은 수학자들에 의해 광범위하게 연구된 개념을 바탕으로 한 수많은 퍼즐들이 있다.^[3]

철학자인 스티븐 쉬퍼는 1972년 저서 의미에서 루이스와 프리델의 1969년 '상식 지식'^[4]과 상당히 유사한 기능을 하는 '상식 지식'이라는 개념을 독자적으로 개발했다.

예

퍼즐

상식 아이디어는 종종 유도 퍼즐의 일부 변종에서 소개된다.^[2]

섬에는 푸른 눈을 가진 k명이 있고, 나머지 사람들은 초록색 눈을 가지고 있다. 퍼즐이 시작될 때, 섬의 어느 누구도 그들 자신의 눈 색깔을 알지 못한다. 규칙적으로, 만약 섬에 사는 사람이 푸른 눈을 가진 것을 발견한다면, 그 사람은 새벽에 섬을 떠나야 한다; 그러한 발견을 하지 않은 사람은 항상 새벽이 지나도록 잔다. 섬에서는 한 사람 한 사람 한 사람 한 사람의 눈 색깔을 다 알고, 반사 표면도 없고, 눈 색깔의 소통도 없다.

어느 틈엔가 외지인이 섬에 와서 섬의 모든 사람들을 불러모으고, "적어도 한 사람은 푸른 눈을 가지고 있다"고 다음과 같은 공표를 한다. 게다가 아웃사이더는 모두가 진실한 것으로 알려져 있고, 모두 이것을 알고 있다는 것을 알고 있다. 즉, 그가 진실한 사람이라는 것은 상식이고, 따라서 적어도 푸른 눈을 가진 섬사람이 한 명 있다는 것은 상식이다. 문제는 섬의 모든 사람들이 완전히 논리적이고 이 또한 상식이라고 가정할 때 궁극적인 결과는 무엇인가?

해결책

정답은 발표 후 k일 새벽에 파란 눈의 사람들이 모두 섬을 떠난다는 것이다.

증명

그 해결책은 귀납적인 주장으로 알 수 있다. k = 1(즉, 정확히 푸른 눈의 사람이 한 명 있다)이라면, 그 사람은 자기 혼자만 푸른 눈을 가졌다는 것을 (다른 사람의 눈에는 초록색 눈만 보임으로써) 인식하고 첫새벽에 떠날 것이다. k = 2이면 첫새벽에 아무도 떠나지 않는다. 푸른 눈의 두 사람은 푸른 눈을 가진 한 사람만을 보고, 1일 새벽(따라서 k > 1)에는 아무도 떠나지 않는다는 것을 두 번째 새벽에 떠나게 된다. 결과적으로, 적어도 파란 눈의 사람들이 있다면, 그리고 그 사람들이 첫 번째 k - 1 새벽에는 아무도 떠나지 않을 것이라고 추론할 수 있다. 푸른 눈을 가진 사람들은, 다른 사람들 중에서 k - 1 푸른 눈을 가진 사람들을 보고, 적어도 k는 있어야 한다는 것을 알고, 그들이 푸른 눈을 가지고 있어야 한다고 생각하고 떠날 것이다.

이 시나리오에서 가장 흥미로운 것은, k > 1의 경우, 아웃사이더는 섬 시민들에게 그들이 이미 알고 있는 것, 즉 그들 중에 파란 눈의 사람들이 있다는 것만을 말하고 있다는 것이다. 그러나 이 사실이 발표되기 전에 그 사실은 상식이 아니다.

k = 2의 경우, 그것은 단지 "선순위" 지식일 뿐이다. 푸른 눈의 사람마다 푸른 눈을 가진 사람이 있다는 것을 알지만, 푸른 눈의 사람마다 다른 푸른 눈의 사람이 이와 같은 지식을 가지고 있다는 것을 알지 못한다.

k = 3의 경우, "2차 순서" 지식이다. 푸른 눈의 각자는 제2의 푸른 눈의 사람은 제3의 사람이 푸른 눈을 가지고 있다는 것을 알고 있지만, 그 지식을 가진 제3의 푸른 눈의 사람이 있다는 사실은 외부인이 진술할 때까지 아무도 알지 못한다.

In general: For k > 1, it is "(k − 1)th order" knowledge. Each blue-eyed person knows that a second blue-eyed person knows that a third blue-eyed person knows that.... (repeat for a total of k − 1 levels) a kth person has blue eyes, but no one knows that there is a "kth" blue-eyed person with that knowledge, until the outsider makes his statement. The notion of common knowledge therefore has a palpable effect. Knowing that everyone knows does make a difference. When the outsider's public announcement (a fact already known to all, unless k=1 then the one person with blue eyes would not know until the announcement) becomes common knowledge, the blue-eyed people on this island eventually deduce their status, and leave.

Formalization

Modal logic (syntactic characterization)

Common knowledge can be given a logical definition in multi-modal logic systems in which the modal operators are interpreted epistemically. At the propositional level, such systems are extensions of propositional logic. The extension consists of the introduction of a group G of agents, and of n modal operators K_i (with i = 1, ..., n) with the intended meaning that "agent i knows." Thus K_i ${\displaystyle \varphi }$ (where ${\displaystyle \varphi }$ is a formula of the calculus) is read "agent i knows ${\displaystyle \varphi }$." We can define an operator E_G with the intended meaning of "everyone in group G knows" by defining it with the axiom

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

By abbreviating the expression ${\displaystyle E_{G}E_{G}^{n-1}\varphi }$ with ${\displaystyle E_{G}^{n}\varphi }$ and defining ${\displaystyle E_{G}^{0}\varphi =\varphi }$, we could then define common knowledge with the axiom

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

There is however a complication. The languages of epistemic logic are usually finitary, whereas the axiom above defines common knowledge as an infinite conjunction of formulas, hence not a well-formed formula of the language. To overcome this difficulty, a fixed-point definition of common knowledge can be given. Intuitively, common knowledge is thought of as the fixed point of the "equation" ${\displaystyle C_{G}\varphi =[\varphi \wedge E_{G}(C_{G}\varphi )]=E_{G}^{\aleph _{0}}\varphi }$. In this way, it is possible to find a formula ${\displaystyle \psi }$ implying ${\displaystyle E_{G}(\varphi \wedge C_{G}\varphi )}$ from which, in the limit, we can infer common knowledge of ${\displaystyle \varphi }$.

This syntactic characterization is given semantic content through so-called Kripke structures. A Kripke structure is given by (i) a set of states (or possible worlds) S, (ii) n accessibility relations ${\displaystyle R_{1},\dots ,R_{n}}$, defined on ${\displaystyle S\times S}$, intuitively representing what states agent i considers possible from any given state, and (iii) a valuation function ${\displaystyle \pi }$ assigning a truth value, in each state, to each primitive proposition in the language. The semantics for the knowledge operator is given by stipulating that ${\displaystyle K_{i}\varphi }$ is true at state s iff ${\displaystyle \varphi }$ is true at all states t such that ${\displaystyle (s,t)\in R_{i}}$. The semantics for the common knowledge operator, then, is given by taking, for each group of agents G, the reflexive and transitive closure of the ${\displaystyle R_{i}}$, for all agents i in G, call such a relation ${\displaystyle R_{G}}$, and stipulating that ${\displaystyle C_{G}\varphi }$ is true at state s iff ${\displaystyle \varphi }$ is true at all states t such that ${\displaystyle (s,t)\in R_{G}}$.

Set theoretic (semantic characterization)

Alternatively (yet equivalently) common knowledge can be formalized using set theory (this was the path taken by the Nobel laureate Robert Aumann in his seminal 1976 paper). We will start with a set of states S. We can then define an event E as a subset of the set of states S. For each agent i, define a partition on S, P_i. This partition represents the state of knowledge of an agent in a state. In state s, agent i knows that one of the states in P_i(s) obtains, but not which one. (Here P_i(s) denotes the unique element of P_i containing s. Note that this model excludes cases in which agents know things that are not true.)

We can now define a knowledge function K in the following way:

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

That is, K_i(e) is the set of states where the agent will know that event e obtains. It is a subset of e.

Similar to the modal logic formulation above, we can define an operator for the idea that "everyone knows e".

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

As with the modal operator, we will iterate the E function, ${\displaystyle E^{1}(e)=E(e)}$ and ${\displaystyle E^{n+1}(e)=E(E^{n}(e))}$. Using this we can then define a common knowledge function,

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

The equivalence with the syntactic approach sketched above can easily be seen: consider an Aumann structure as the one just defined. We can define a correspondent Kripke structure by taking (i) the same space S, (ii) accessibility relations ${\displaystyle R_{i}}$ that define the equivalence classes corresponding to the partitions ${\displaystyle P_{i}}$, and (iii) a valuation function such that it yields value true to the primitive proposition p in all and only the states s such that ${\displaystyle s\in E^{p}}$, where ${\displaystyle E^{p}}$ is the event of the Aumann structure corresponding to the primitive proposition p. It is not difficult to see that the common knowledge accessibility function ${\displaystyle R_{G}}$ defined in the previous section corresponds to the finest common coarsening of the partitions ${\displaystyle P_{i}}$ for all ${\displaystyle i\in G}$, which is the finitary characterization of common knowledge also given by Aumann in the 1976 article.

Applications

Common knowledge was used by David Lewis in his pioneering game-theoretical account of convention. In this sense, common knowledge is a concept still central for linguists and philosophers of language (see Clark 1996) maintaining a Lewisian, conventionalist account of language.

Robert Aumann introduced a set theoretical formulation of common knowledge (theoretically equivalent to the one given above) and proved the so-called agreement theorem through which: if two agents have common prior probability over a certain event, and the posterior probabilities are common knowledge, then such posterior probabilities are equal. A result based on the agreement theorem and proven by Milgrom shows that, given certain conditions on market efficiency and information, speculative trade is impossible.

The concept of common knowledge is central in game theory. For several years it has been thought that the assumption of common knowledge of rationality for the players in the game was fundamental. It turns out (Aumann and Brandenburger 1995) that, in 2-player games, common knowledge of rationality is not needed as an epistemic condition for Nash equilibrium strategies.

Computer scientists use languages incorporating epistemic logics (and common knowledge) to reason about distributed systems. Such systems can be based on logics more complicated than simple propositional epistemic logic, see Wooldridge Reasoning about Artificial Agents, 2000 (in which he uses a first-order logic incorporating epistemic and temporal operators) or van der Hoek et al. "Alternating Time Epistemic Logic".

In his 2007 book, The Stuff of Thought: Language as a Window into Human Nature, Steven Pinker uses the notion of common knowledge to analyze the kind of indirect speech involved in innuendoes.

See also

• Global game
• Mutual knowledge (logic)
• Stephen Schiffer
• Two Generals' Problem for the impossibility of establishing common knowledge over an unreliable channel

Notes

1. ^ See the textbooks Reasoning about knowledge by Fagin, Halpern, Moses and Vardi (1995), and Epistemic Logic for computer science by Meyer and van der Hoek (1995).
2. ^ A structurally identical problem is provided by Herbert Gintis (2000); he calls it "The Women of Sevitan".

References

Further reading

• 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.. 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
• Halpern, J. Y.; Moses, Y. (1990). "Knowledge and Common Knowledge in a Distributed Environment". Journal of the ACM. 37 (3): 549–587. arXiv:cs/0006009. doi:10.1145/79147.79161. S2CID 52151232.

External links

• Vanderschraaf, Peter; Sillari, Giacomo. "Common Knowledge". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.
• 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.
• physics.harvard.edu "녹색 눈의 드래곤 문제", "녹색 눈의 드래곤 솔루션"(2002년 9월)