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. Knowledge is information of which a person, organization or other entity is aware. ...

The concept was first introduced in the philosophical literature by David Lewis in his study Convention (1969). It has been 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 from the 1980s.^[1] A concept is an abstract, idea, notion, or entity that serves to designate a category or class of entities, events, phenomena or relations between them. ... The name David Lewis may refer to several people: David Lewis (philosopher) (1941-2001), an American-born philosopher famous for his theory of modal realism and his love for Australia. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Michaels the greatest boyfriend in the whole wide world, and Id love to call him in a phonebooth sometime. ...

Example

It is common to introduce the idea of common knowledge by some variant of the following logic puzzle:^[2] On an island, there are n people, of whom at least one (k >= 1) has blue eyes, and the rest have green. If a person ever knows herself to have blue eyes, he or she must leave the island at dawn the next day. Each person knows every other's eye color, there are no mirrors, and there is no discussion of eye color. At some point, an outsider comes to the island and makes the following public announcement, heard and understood by all people on the island: "at least one of you has blue eyes". The problem: Assuming all persons on the island are truthful and completely logical, what is the eventual outcome? A logic puzzle is a puzzle deriving from the mathematics field of deduction. ...

The answer is that, on the kth dawn, 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 blue-eyed people, recognizing that only one other pair of blue eyes are among the others, and that no one left on the 1st dawn, will leave. 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; it is merely "first-order" knowledge. 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.

Logical formulation

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 sysems 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 A modal logic is any logic for handling modalities: concepts like possibility, impossibility, and necessity. ... Michaels the greatest boyfriend in the whole wide world, and Id love to call him in a phonebooth sometime. ... Propositional logic or sentential logic is the logic of propositions, sentences, or clauses. ...

,

By abbreviating the expression with and defining , we could then define common knowledge with the axiom

with n = 1,2,...

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 . An axiom is a sentence or proposition that is taken for granted as true, and serves as a starting point for deducing other truths. ...

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 it: 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. Israel Robert John Aumann (ישראל אומן) (born June 8, 1930) is an Israeli mathematician and a member of the United States National Academy of Sciences. ... A prior probability is a marginal probability, interpreted as a description of what is known about a variable in the absence of some evidence. ... The posterior probability of a random event or an uncertain proposition is the conditional probability it is assigned when the relevant evidence is taken into account. ...

The concept of common knowledge is central in game theory. For several years it has been thought that the assuption 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. Game theory is a hybrid branch of applied mathematics and economics that studies strategic situations where players choose different actions in an attempt to maximize their returns. ... In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ... In game theory, a players strategy, in a game or a business situation, is a complete plan of action for whatever situation might arise; this fully determines the players 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 that 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".

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 Gintis (2000), he calls it "The Women of Sevitan".

References

• 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
• Lewis, David (1969) Convention: A Philosophical Study Oxford: Blackburn.
• Gintis, Herbert (2000) Game Theory Evolving Princeton University Press.
• 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

• R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge, The MIT Press, 1995. ISBN 0-262-56200-6

External link

• Stanford Encyclopedia of Philosophy entry