Common knowledge (logic)
Encyclopedia
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.
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 set-theoretical
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. There are numerous puzzles
based upon the concept which have been extensively investigated by mathematicians such as John Conway
.
The answer is that, on the kth dawn after the announcement, all the blue-eyed 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 blue-eyed 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 k-1 dawns if and only if there are at least k blue-eyed people. Those with blue eyes, seeing k-1 blue-eyed 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 blue-eyed people among them. However, before this fact is announced, the fact is not common knowledge.
For k = 2, it is merely "first-order" knowledge. 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 = 3, it is "second order" knowledge. After 2 days, 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 third day arrives.
In general: For k > 2, it is "(k − 1)th order" knowledge. After k − 1 days, 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 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 blue-eyed people on this island eventually deduce their status, and leave.
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 Ki (with i = 1, ..., n) with the intended meaning that "agent i knows." Thus Ki
(where 
is a formula of the calculus) is read "agent i knows 
." We can define an operator EG 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 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"
. 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 so-called 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 
, for all agents i in G, call such a relation 
, and stipulating that 
is true at state s iff 
is true at all states t such that 
.
(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, Pi. 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 Pi(s) obtains, but not which one. (Here Pi(s) denotes the unique element of Pi 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, Ki(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,
and 
. 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
that define the equivalence classes corresponding to the partitions 
, 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 
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 
defined in the previous section corresponds to the finest common coarsening of the partitions 
for all 
, which is the finitary characterization of common knowledge also given by Aumann in the 1976 article.
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.
Knowledge
Knowledge is a familiarity with someone or something unknown, which can include information, facts, descriptions, or skills acquired through experience or education. It can refer to the theoretical or practical understanding of a subject...
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.
The concept was first introduced in the philosophical literature by David Kellogg Lewis
David Kellogg Lewis
David Kellogg Lewis was an American philosopher. Lewis taught briefly at UCLA and then at Princeton from 1970 until his death. He is also closely associated with Australia, whose philosophical community he visited almost annually for more than thirty years...
in his study Convention (1969). It was first given a mathematical formulation in a set-theoretical
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
framework by Robert Aumann
Robert Aumann
Robert John Aumann is an Israeli-American mathematician and a member of the United States National Academy of Sciences. He is a professor at the Center for the Study of Rationality in the Hebrew University of Jerusalem in Israel...
(1976). Computer scientists
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
grew an interest in the subject of epistemic logic
Epistemic logic
Epistemic modal logic is a subfield of modal logic that is concerned with reasoning about knowledge. While epistemology has a long philosophical tradition dating back to Ancient Greece, epistemic logic is a much more recent development with applications in many fields, including philosophy,...
in general – and of common knowledge in particular – starting in the 1980s. There are numerous puzzles
Logic puzzle
A logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...
based upon the concept which have been extensively investigated by mathematicians such as John Conway
John Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
.
Example
The idea of common knowledge is often introduced by some variant of the following puzzle: 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 blue-eyed 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 blue-eyed 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 blue-eyed 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 k-1 dawns if and only if there are at least k blue-eyed people. Those with blue eyes, seeing k-1 blue-eyed 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 blue-eyed people among them. However, before this fact is announced, the fact is not common knowledge.
For k = 2, it is merely "first-order" knowledge. 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 = 3, it is "second order" knowledge. After 2 days, 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 third day arrives.
In general: For k > 2, it is "(k − 1)th order" knowledge. After k − 1 days, 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 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 blue-eyed people on this island eventually deduce their status, and leave.
Modal logic (syntactic characterization)
Common knowledge can be given a logical definition in multi-modal logicModal logic
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
systems in which the modal operators are interpreted epistemically
Epistemic logic
Epistemic modal logic is a subfield of modal logic that is concerned with reasoning about knowledge. While epistemology has a long philosophical tradition dating back to Ancient Greece, epistemic logic is a much more recent development with applications in many fields, including philosophy,...
. 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 Ki (with i = 1, ..., n) with the intended meaning that "agent i knows." Thus Ki
(where is a formula of the calculus) is read "agent i knows ." We can define an operator EG with the intended meaning of "everyone in group G knows" by defining it with the axiomBy 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
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
above defines common knowledge as an infinite conjunction of formulas, hence not a well-formed formula
Well-formed formula
In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...
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"
. 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 so-called 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 , for all agents i in G, call such a relation , and stipulating that 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 theorySet theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
(this was the path taken by the Nobel laureate Robert Aumann
Robert Aumann
Robert John Aumann is an Israeli-American mathematician and a member of the United States National Academy of Sciences. He is a professor at the Center for the Study of Rationality in the Hebrew University of Jerusalem in Israel...
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
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
on S, Pi. 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 Pi(s) obtains, but not which one. (Here Pi(s) denotes the unique element of Pi 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, Ki(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,
and . 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
that define the equivalence classes corresponding to the partitions , 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 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 defined in the previous section corresponds to the finest common coarsening of the partitions 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 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
Robert Aumann
Robert John Aumann is an Israeli-American mathematician and a member of the United States National Academy of Sciences. He is a professor at the Center for the Study of Rationality in the Hebrew University of Jerusalem in Israel...
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
Prior probability
In Bayesian statistical inference, a prior probability distribution, often called simply the prior, of an uncertain quantity p is the probability distribution that would express one's uncertainty about p before the "data"...
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
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
. 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
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
strategies
Strategy (game theory)
In game theory, a player's strategy in a game is a complete plan of action for whatever situation might arise; this fully determines the player's behaviour...
.
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
The Stuff of Thought
The Stuff of Thought: Language As a Window Into Human Nature is a New York Times best-selling book by Harvard experimental psychologist Steven Pinker published in 2007...
, Steven Pinker
Steven Pinker
Steven Arthur Pinker is a Canadian-American experimental psychologist, cognitive scientist, linguist and popular science author...
uses the notion of common knowledge to analyze the kind of indirect speech involved in innuendoes.
See also
- Global gameGlobal gameIn economics and game theory, global games are games of incomplete information where players receive possibly-correlated signals of the underlying state of the world. Global games were originally defined by Carlsson and van Damme...
- Two Generals' ProblemTwo Generals' ProblemIn computing, the Two Generals' Problem is a thought experiment meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link...
for the impossibility of establishing common knowledge over an unreliable channel - Mutual knowledge (logic)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 . However, mutual knowledge by itself implies nothing about what agents know about other agents' knowledge: i.e...
External links
- 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.