Editing Common knowledge (logic)

{{short description|Statement that players know and also know that other players know (ad infinitum)}}
'''Common knowledge''' is a special kind of [[knowledge]] for a group of [[agent-based model|agents]]. There is ''common knowledge'' of ''p'' in a group of agents ''G'' when all the agents in ''G'' know ''p'', they all know that they know ''p'', they all know that they all know that they know ''p'', and so on ''[[ad infinitum]]''.<ref name=Osborne>Osborne, Martin J., and [[Ariel Rubinstein]]. ''A Course in Game Theory''. Cambridge, MA: MIT, 1994. Print.</ref> It can be denoted as <math>C_G p</math>.

The concept was first introduced in the philosophical literature by [[David Kellogg Lewis]] in his study ''Convention'' (1969).  The sociologist Morris Friedell defined common knowledge in a 1969 paper.<ref>Morris Friedell, "On the Structure of Shared Awareness," Behavioral Science 14 (1969): 28–39.</ref>  It was first given a mathematical formulation in a [[set theory|set-theoretical]] framework by [[Robert Aumann]] (1976). [[computer science|Computer scientists]] grew an interest in the subject of [[epistemic logic]] in general&nbsp;– and of common knowledge in particular&nbsp;– starting in the 1980s.{{ref|CSTexts}}  There are numerous [[Logic puzzle|puzzles]] based upon the concept which have been extensively investigated by mathematicians such as [[John Horton Conway|John Conway]].<ref>{{Cite book |title=Math Hysteria| author=Ian Stewart |year=2004 |publisher=OUP |chapter=I Know That You Know That... }}</ref>

The philosopher [[Stephen Schiffer]], in his 1972 book ''Meaning'', independently developed a notion he called "[[mutual knowledge]]" (<math>E_G p</math>) which functions quite similarly to Lewis's and Friedel's 1969 "common knowledge".<ref>Stephen Schiffer, ''Meaning'', 2nd edition, Oxford University Press, 1988.  The first edition was published by OUP in 1972.  For a discussion of both Lewis's and Schiffer's notions, see Russell Dale, ''[http://www.russelldale.com/dissertation/1996.RussellDale.TheTheoryOfMeaning.pdf The Theory of Meaning]'' (1996).</ref> If a trustworthy announcement is made in [[Dynamic epistemic logic#Public Events|public]], then it becomes common knowledge; However, if it is transmitted to each agent in private, it becomes mutual knowledge but not common knowledge. Even if the fact that "every agent in the group knows ''p''" (<math>E_G p</math>) is transmitted to each agent in private, it is still not common knowledge: <math>E_G E_G p \not \Rightarrow C_G p</math>. But, if any agent <math>a</math> publicly announces their knowledge of ''p'', then it becomes common knowledge that they know ''p'' (viz. <math>C_G K_a p</math>). If every agent publicly announces their knowledge of ''p'', ''p'' becomes common knowledge <math>C_G E_G p \Rightarrow C_G p</math>.

== Example ==

=== Puzzle ===

The idea of common knowledge is often introduced by some variant of [[induction puzzles]] (e.g. [[Induction puzzles#Muddy Children Puzzle|Muddy children puzzle]]):{{ref|Sevitan}}

On an island, there are ''k'' people who have blue eyes, and the rest of the people have green eyes. At the start of the puzzle, no one on the island ever knows their own eye color. By rule, if a person on the island ever discovers they have blue eyes, that person must leave the island at dawn; anyone not making such a discovery always sleeps until after dawn. On the island, each person knows every other person's eye color, there are no reflective surfaces, and there is no communication of eye color.

At some point, an outsider comes to the island, calls together all the people on the island, and makes the following [[Dynamic epistemic logic#Public Events|public announcement]]: "At least one of you has blue eyes". The outsider, furthermore, is known by all to be truthful, and all know that all know this, and so on: it is common knowledge that they are truthful, and thus it becomes common knowledge that there is at least one islander who has blue eyes (<math>C_G[\exists x\! \in\! G ( Bl_{x})]</math>). The problem: finding the eventual outcome, assuming all persons on the island are completely logical (every participant's knowledge obeys the [[Epistemic modal logic#The properties of knowledge|axiom schemata for epistemic logic]]) and that this too is common knowledge.

=== Solution ===

The answer is that, on the ''k''th dawn after the announcement, all the blue-eyed people will leave the island.<ref>{{cite news |last1=Bennett |first1=Jay |title=Solution to Riddle of the Week #27: The Blue-Eyed Islanders |url=https://www.popularmechanics.com/science/math/a26564/solution-to-riddle-of-the-week-27/ |access-date=31 May 2025 |work=Popular Mechanics |date=18 May 2017}}</ref>

==== Proof ====
The solution can be seen with an inductive argument. If ''k''&nbsp;=&nbsp;1 (that is, there is exactly one blue-eyed person), the person will recognize that they alone have blue eyes (by seeing only green eyes in the others) and leave at the first dawn. If ''k''&nbsp;=&nbsp;2, no one will leave at the first dawn, and the inaction (and the implied lack of knowledge for every agent) is observed by everyone, which then becomes ''common knowledge'' as well (<math>C_G[\forall x\! \in\! G ( \neg K_{x}Bl_{x})]</math>). The two blue-eyed people, seeing only one person with blue eyes, ''and'' that no one left on the first dawn (and thus that ''k''&nbsp;>&nbsp;1; and also that the other blue-eyed person does not think that everyone except themself are not blue-eyed <math>\neg K_{a}[\forall x\! \in\! (G-a) (\neg Bl_{x})]</math>, so ''another'' blue-eyed person <math>\exists x\! \in\! (G-a) (Bl_{x})</math>), will leave on the second dawn. Inductively, it can be reasoned that no one will leave at the first ''k''&nbsp;−&nbsp;1 dawns if and only if there are at least ''k'' blue-eyed people. Those with blue eyes, seeing ''k''&nbsp;−&nbsp;1 blue-eyed people among the others and knowing there must be at least ''k'', will reason that they must have blue eyes and leave.

For ''k''&nbsp;>&nbsp;1, the outsider is only telling the island citizens what they already know: that there are blue-eyed people among them. However, before this fact is announced, the fact is not ''common knowledge'', but instead [[Mutual knowledge (logic)|mutual knowledge]].

For ''k''&nbsp;=&nbsp;2, it is merely "first-order" knowledge (<math>E_G[\exists x\! \in\! G ( Bl_{x})]</math>). Each blue-eyed person knows that there is someone with blue eyes, but each blue eyed person does ''not'' know that the other blue-eyed person has this same knowledge.

For ''k''&nbsp;=&nbsp;3, it is "second order" knowledge (<math>E_GE_G[\exists x\! \in\! G ( Bl_{x})]=E_G^2[\exists x\! \in\! G ( Bl_{x})]</math>). Each blue-eyed person knows that a second blue-eyed person knows that a third person has blue eyes, but no one knows that there is a ''third'' blue-eyed person with that knowledge, until the outsider makes their statement.

In general: For ''k''&nbsp;>&nbsp;1, it is "(''k''&nbsp;&minus;&nbsp;1)th order" knowledge (<math>E_G^{k-1} [\exists x\! \in\! G ( Bl_{x})]</math>). 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''&nbsp;&minus;&nbsp;1 levels) a ''k''th person has blue eyes, but no one knows that there is a "''k''th" 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.

In particular:
# <math>E_G^{i} [|G ( Bl_{x})| \ge j]</math> is free (i.e. known prior to the outsider's statement) [[iff]] <math>i + j \le k</math>.
# <math>E_G^{i} [|G ( Bl_{x})| \ge j]</math>, with a passing day where no one leaves, implies the next day <math>E_G^{i - 1} [|G ( Bl_{x})| \ge j + 1]</math>.
# <math>E_G^{i} [|G ( Bl_{x})| \ge j]</math> for <math>j \ge k</math> is thus reached iff it is reached for <math>i + j > k</math>.
# The outsider gives <math>E_G^{i} [|G ( Bl_{x})| \ge j]</math> for <math>i = \infty, j = 1</math>.

== Formalization ==
{{Unreferenced section|date=March 2022}}

=== Modal logic (syntactic characterization) ===

Common knowledge can be given a logical definition in [[Multimodal logic|multi-modal logic]] systems in which the modal operators are interpreted [[epistemic logic|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<sub>i</sub>'' (with ''i'' = 1,&nbsp;...,&nbsp;''n'') with the intended meaning that "agent ''i'' knows." Thus ''K<sub>i</sub> <math>\varphi</math>'' (where <math>\varphi</math> is a formula of the logical calculus) is read "agent ''i'' knows <math>\varphi</math>." We can define an operator ''E<sub>G</sub>'' with the intended meaning of "everyone in group ''G'' knows" by defining it with the axiom

: <math>E_G \varphi \Leftrightarrow \bigwedge_{i \in G} K_i \varphi,</math>

By abbreviating the expression <math>E_GE_G^{n-1} \varphi</math> with <math>E_G^n \varphi</math>  and defining <math>E_G^0 \varphi = \varphi</math>, common knowledge could then be defined with the axiom

: <math>C \varphi \Leftrightarrow \bigwedge_{i = 0}^\infty E^i \varphi</math>

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" <math>C_G \varphi=[\varphi\wedge E_G (C_G \varphi)]=E_G^{\aleph_0} \varphi</math>. Here, <math>\aleph_0</math> is the [[Aleph-naught]]. In this way, it is possible to find a formula <math>\psi</math> implying <math>E_G (\varphi \wedge C_G \varphi)</math> from which, in the limit, we can infer common knowledge of <math>\varphi</math>.

From this definition it can be seen that if <math>E_G \varphi</math> is common knowledge, then <math>\varphi</math> is also common knowledge (<math>C_G E_G \varphi \Rightarrow C_G \varphi</math>).

This ''syntactic'' characterization is given semantic content through so-called ''[[Kripke structure (model checking)|Kripke structures]]''. A Kripke structure is given by a set of states (or possible worlds) ''S'', ''n'' ''accessibility relations'' <math>R_1,\dots,R_n</math>, defined on <math>S \times S</math>, intuitively representing what states agent ''i'' considers possible from any given state, and a valuation function <math>\pi</math> assigning a [[truth value]], in each state, to each primitive proposition in the language. The [[Kripke semantics]] for the knowledge operator is given by stipulating that <math>K_i \varphi</math> is true at state ''s'' iff <math>\varphi</math> is true at ''all'' states ''t'' such that <math>(s,t) \in R_i</math>. The semantics for the common knowledge operator, then, is given by taking, for each group of agents ''G'', the [[reflexive closure|reflexive]] (modal axiom '''T''') and [[transitive closure]] (modal axiom '''4''') of the <math>R_i</math>, for all agents ''i'' in ''G'', call such a relation <math>R_G</math>, and stipulating that <math>C_G \varphi</math> is true at state ''s'' iff <math>\varphi</math> is true at ''all'' states ''t'' such that <math>(s,t) \in R_G</math>.

=== 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).  Starting with a set of states ''S''.  An event ''E'' can then be defined as a subset of the set of states ''S''.  For each agent ''i'', define a [[Partition of a set|partition]] on ''S'', ''P<sub>i</sub>''.  This partition represents the state of knowledge of an agent in a state.  Intuitively, if two states ''s''<sub>''1''</sub> and ''s''<sub>''2''</sub> are elements of the same part of partition of an agent, it means that ''s''<sub>''1''</sub> and ''s''<sub>''2''</sub> are indistinguishable to that agent. In general, in state ''s'', agent ''i'' knows that one of the states in ''P''<sub>''i''</sub>(''s'') obtains, but not which one. (Here ''P''<sub>''i''</sub>(''s'') denotes the unique element of ''P<sub>i</sub>'' containing ''s''. This model excludes cases in which agents know things that are not true.)

A knowledge function ''K'' can now be defined in the following way:

<math block>K_i(e) = \{ s \in S \mid P_i(s) \subset e\}</math>

That is, ''K''<sub>''i''</sub>(''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,  an operator for the idea that "everyone knows can be defined as ''e''".

<math block>E(e) = \bigcap_i K_i(e)</math>

As with the modal operator, we will iterate the ''E'' function, <math>E^1(e) = E(e)</math> and <math>E^{n+1}(e) = E(E^{n}(e))</math>.  Using this we can then define a common knowledge function,

<math block>C(e) = \bigcap_{n=1}^{\infty} E^n(e).</math>

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 the same space ''S'', accessibility relations <math>R_i</math> that define the equivalence classes corresponding to the partitions <math>P_i</math>, and a valuation function such that it yields value ''true'' to the primitive proposition ''p'' in all and only the states ''s'' such that <math>s \in E^p</math>, where <math>E^p</math> 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 <math>R_G</math> defined in the previous section corresponds to the finest common coarsening of the partitions <math>P_i</math> for all <math>i \in G</math>, which is the finitary characterization of common knowledge also given by Aumann in the 1976 article.

== Applications ==
{{Unreferenced section|date=March 2022}}
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 [[Aumann's agreement theorem|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 two-player games, common knowledge of rationality is not needed as an epistemic condition for [[Nash equilibrium]] [[strategy (game theory)|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|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.<ref>{{cite arXiv |eprint=2310.00264 |last1=Liang |first1=Xiaolong |last2=Wáng |first2=Yì N. |title=Epistemic Logic over Similarity Graphs: Common, Distributed and Mutual Knowledge |date=2023 |class=cs.LO }}</ref>

== In popular culture ==

The comedy movie [[Hot Lead and Cold Feet]] has an example of a chain of logic that is collapsed by common knowledge. 
The Denver Kid tells his allies that Rattlesnake is in town, but that he [the Kid] has “the edge”: “He's here and I know he's here, and he knows I know he's here, but he ''doesn't'' know I know he knows I know he's here.”
So both protagonists know the main fact (Rattlesnake is here), but it is ''not'' “common knowledge”. Note that this is true even if the Kid is wrong: maybe Rattlesnake ''does'' know that the Kid knows that he knows that he knows, the chain still breaks because the Kid doesn't know that.
Moments later, Rattlesnake confronts the Kid. We see the Kid realizing that his carefully constructed “edge” has collapsed into common knowledge.

== See also ==
{{Portal|Philosophy}}

* [[Global game]]
* [[Mutual knowledge (logic)]]
* [[Pluralistic ignorance]]
* [[Stag hunt]]
* [[Stephen Schiffer]]
* [[Two Generals' Problem]] for the impossibility of establishing common knowledge over an unreliable channel

== Notes ==

# {{note|CSTexts}}  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).
# {{note|Sevitan}}  A structurally identical problem is provided by [[Herbert Gintis]] (2000); he calls it "The Women of Sevitan".

== References ==
{{reflist}}

== Further reading ==

* [[Robert Aumann|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}}
* {{cite book | first1=Ronald | last1=Fagin | first2=Joseph | last2=Halpern | first3 = Yoram | last3 = Moses |first4=Moshe | last4=Vardi | title=Reasoning about Knowledge | location=Cambridge | publisher=[[MIT Press]] | year=2003 | isbn=978-0-262-56200-3}}.
* [[David Kellogg Lewis|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}}
* {{cite book | last1=Rescher | first1=Nicolas | title=Epistemic Logic: A Survey Of the Logic Of Knowledge | publisher=[[University of Pittsburgh Press]] | year=2005 | isbn=978-0-8229-4246-7}}. See Chapter 3.
* {{cite book | last1=Shoham | first1=Yoav | last2=Leyton-Brown | first2=Kevin | title=Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations | publisher=[[Cambridge University Press]] | isbn=978-0-521-89943-7 | url=http://www.masfoundations.org | year=2009 | location=New York}}. See Section 13.4; [http://www.masfoundations.org/download.html 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}}
* {{Cite journal | last1 = Halpern | first1 = J. Y. |author-link1=Joseph Halpern| last2 = Moses | first2 = Y. |author-link2=Yoram Moses| doi = 10.1145/79147.79161 | title = Knowledge and Common Knowledge in a Distributed Environment| journal = [[Journal of the ACM]]| volume = 37 | issue = 3 | pages = 549–587 | year = 1990 | arxiv = cs/0006009| s2cid = 52151232 }}

== External links ==

* {{cite SEP |url-id=common-knowledge |title=Common Knowledge |first=Peter |last=Vanderschraaf |first2=Giacomo |last2=Sillari }}
* [http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/ Prof. Terence Tao's blog post (Feb 2008)]
* Carr, Kareem. [http://twofoldgaze.wordpress.com/2009/11/07/in-the-long-run-we-are-all-dead/ "In the Long Run We Are All Dead"], [http://twofoldgaze.wordpress.com/2009/11/12/in-the-long-run-we-are-all-dead-ii/ "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 [https://www.physics.harvard.edu/uploads/files/undergrad/probweek/prob2.pdf "Green-eyed Dragons Problem"] {{Webarchive|url=https://web.archive.org/web/20141201054814/https://www.physics.harvard.edu/uploads/files/undergrad/probweek/prob2.pdf |date=2014-12-01 }}, [https://www.physics.harvard.edu/uploads/files/undergrad/probweek/sol2.pdf "Green-eyed Dragons Solution"] {{Webarchive|url=https://web.archive.org/web/20141201053023/https://www.physics.harvard.edu/uploads/files/undergrad/probweek/sol2.pdf |date=2014-12-01 }} (Sept 2002)

{{game theory}}

[[Category:Game theory]]
[[Category:Concepts in logic]]
[[Category:Fixed points (mathematics)]]
[[Category:Knowledge transfer]]
[[Category:Social epistemology]]
[[Category:Epistemic logic]]
[[Category:Concepts in epistemology]]