 Common knowledge (logic)

For common knowledge in general, see Common knowledge.
Common knowledge is a special kind of knowledge for a group of 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^{[1]}.
The concept was first introduced in the philosophical literature by David Kellogg Lewis in his study Convention (1969). It was first given a mathematical formulation in a settheoretical framework by Robert Aumann (1976). Computer scientists grew an interest in the subject of epistemic logic in general – and of common knowledge in particular – starting in the 1980s.^{[1]} There are numerous puzzles based upon the concept which have been extensively investigated by mathematicians such as John Conway.^{[2]}
Contents
Example
The idea of common knowledge is often introduced by some variant of the following puzzle:^{[2]} On an island, there are k people who have blue eyes, and the rest of the people have green eyes. There is at least one blueeyed person on the island (k ≥ 1). If a person ever knows they have blue eyes, they must leave the island at dawn the next day. Each person can see every other person's eye color, there are no reflective surfaces, and there is no discussion of eye color. At some point, an outsider comes to the island, calls together all the people on the island, and makes the following 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 he is truthful, and thus it becomes common knowledge that there is at least one islander who has blue eyes. The problem: assuming all persons on the island are completely logical and that this too is common knowledge, what is the eventual outcome?
The answer is that, on the kth dawn after the announcement, all the blueeyed people will leave the island.
This can be easily seen with an inductive argument. If k = 1, the person will recognize that he or she has blue eyes (by seeing only green eyes in the others) and leave at the first dawn. If k = 2, no one will leave at the first dawn. The two blueeyed people, seeing only one person with blue eyes, and that no one left on the 1st dawn, will leave on the second dawn. So on, it can be reasoned that no one will leave at the first k1 dawns if and only if there are at least k blueeyed people. Those with blue eyes, seeing k1 blueeyed people among the others and knowing there must be at least k, will reason that they have blue eyes and leave.
What's most interesting about this scenario is that, for k > 1, the outsider is only telling the island citizens what they already know: that there are blueeyed people among them. However, before this fact is announced, the fact is not common knowledge.
For k = 2, it is merely "firstorder" knowledge. Each blueeyed person knows that there is someone with blue eyes, but each blue eyed person does not know that the other blueeyed person has this same knowledge.
For k = 3, it is "second order" knowledge. After 2 days, each blueeyed person knows that a second blueeyed person knows that a third person has blue eyes, but no one knows that there is a "third" blueeyed person with that knowledge, until the third day arrives.
In general: For k > 2, it is "(k − 1)th order" knowledge. After k − 1 days, each blueeyed person knows that a second blueeyed person knows that a third blueeyed 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" blueeyed person with that knowledge, until the kth day arrives. 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) becomes common knowledge, the blueeyed people on this island eventually deduce their status, and leave.
Formalization
Modal logic (syntactic characterization)
Common knowledge can be given a logical definition in multimodal 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} φ (where φ is a formula of the calculus) is read "agent i knows φ." We can define an operator E_{G} with the intended meaning of "everyone in group G knows" by defining it with the axiom
By abbreviating the expression with and defining , we could then define common knowledge with the axiom
 with
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 wellformed formula of the language. To overcome this difficulty, a fixedpoint definition of common knowledge can be given. Intuitively, common knowledge is thought of as the fixed point of the "equation" . In this way, it is possible to find a formula ψ implying from which, in the limit, we can infer common knowledge of φ.
This syntactic characterization is given semantic content through socalled Kripke structures. A Kripke structure is given by (i) a set of states (or possible worlds) S, (ii) n accessibility relations , defined on , intuitively representing what states agent i considers possible from any given state, and (iii) a valuation function π 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 is true at state s iff φ is true at all states t such that . 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 R_{i}, for all agents i in G, call such a relation R_{G}, and stipulating that C_{G}φ is true at state s iff φ is true at all states t such that .
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:
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".
As with the modal operator, we will iterate the E function, E^{1}(e) = E(e) and E^{n + 1}(e) = E(E^{n}(e)). Using this we can then define a common knowledge function,
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 R_{i} that define the equivalence classes corresponding to the partitions 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 , where 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 R_{G} defined in the previous section corresponds to the finest common coarsening of the partitions P_{i} for all , 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 gametheoretical 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 socalled 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 2player 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 firstorder 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
 Two Generals' Problem for the impossibility of establishing common knowledge over an unreliable channel
 Mutual knowledge (logic)
Notes
 ^ 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).
 ^ A structurally identical problem is provided by Herbert Gintis (2000); he calls it "The Women of Sevitan".
References
 ^ Osborne, Martin J., and Ariel Rubinstein. A Course in Game Theory. Cambridge, MA: MIT, 1994. Print.
 ^ Ian Stewart (2004). "I Know That You Know That...". Math Hysteria. OUP.
 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 0521567459
 Fagin, Ronald; Halpern, Joseph; Moses, Yoram; Vardi, Moshe (2003). Reasoning about Knowledge. Cambridge: MIT Press. ISBN 9780262562003..
 Lewis, David (1969) Convention: A Philosophical Study Oxford: Blackburn. ISBN 0631232575
 JJ 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 052146014X
 Rescher, Nicolas (2005). Epistemic Logic: A Survey Of the Logic Of Knowledge. University of Pittsburgh Press. ISBN 9780822942467.. See Chapter 3.
 Shoham, Yoav; LeytonBrown, Kevin (2009). Multiagent Systems: Algorithmic, GameTheoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 9780521899437. http://www.masfoundations.org.. See Section 13.4; downloadable free online.
 Gintis, Herbert (2000) Game Theory Evolving Princeton University Press. ISBN 0691140510
 Gintis, Herbert (2009) The Bounds of Reason Princeton University Press. ISBN 0691140529
Further reading
 Halpern, J. Y.; Moses, Y. (1990). "Knowledge and Common Knowledge in a Distributed Environment". Journal of the ACM 37 (3): 549–587. doi:10.1145/79147.79161.
External links
 Common Knowledge entry by Peter Vanderschraaf and Giacomo Sillari in the 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 blueeyed islander problem, with solution.
Categories: Game theory
 Philosophical terminology
 Fixed points
 Knowledge
Wikimedia Foundation. 2010.
Look at other dictionaries:
Common knowledge (disambiguation) — * Common knowledge what everybody knows * Common knowledge (logic) a mathematical concept used primarily in game theory and epistemic logic. * Common Knowledge an information publishing system … Wikipedia
Common knowledge — For the logical concept, see Common knowledge (logic). Common knowledge is knowledge that is known by everyone or nearly everyone, usually with reference to the community in which the term is used. Common knowledge need not concern one specific… … Wikipedia
Mutual knowledge (logic) — Mutual knowledge is a fundamental concept about information in game theory and logic. An event is mutual knowledge if all agents know that the event occurred [1]:73. However, mutual knowledge by itself implies nothing about what agents know about … Wikipedia
Knowledge relativity — In philosophy, knowledge relativity is the notion that knowledge can be seen as the relation between a form of representation with up to two sorts of intent ndash; communication and use goals ndash; and with up to three subjects ndash; one who… … Wikipedia
Logic programming — is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy s [1958] advice taker proposal, logic is used as a purely declarative… … Wikipedia
Common logic — (CL) is a framework for a family of logic languages, based on first order logic, intended to facilitate the exchange and transmission of knowledge in computer based systems. The CL definition permits and encourages the development of a variety of … Wikipedia
Logic — • A historical survey from Indian and Pre Aristotelian philosophy to the Logic of John Stuart Mill Catholic Encyclopedia. Kevin Knight. 2006. Logic Logic … Catholic encyclopedia
Knowledge Science — is the discipline of understanding the mechanics through which humans and software based machines know, learn, change, and adapt their own behaviors. Throughout recorded history, knowledge has been made explicit through symbols, text and graphics … Wikipedia
Knowledgebased engineering — (KBE) is a discipline with roots in computer aided design (CAD) and knowledge based systems but has several definitions and roles depending upon the context. An early role was support tool for a design engineer generally within the context of… … Wikipedia
Knowledge engineering — (KE) has been defined by Feigenbaum, and McCorduck (1983) as follows: KE is an engineering discipline that involves integrating knowledge into computer systems in order to solve complex problems normally requiring a high level of human expertise … Wikipedia