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). The sociologist Morris Friedell defined common knowledge in a 1969 paper.^[2] 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.^[3]

The philosopher Stephen Schiffer, in his book Meaning, independently developed a notion he called "mutual knowledge" which functions quite similarly to Lewis's "common knowledge".^[4]

Example

Puzzle

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. 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 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?

Solution

The answer is that, on the kth dawn after the announcement, all the blue-eyed people will leave the island.

Proof

The solution can be seen with an inductive argument. If k = 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 = 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 (and thus that k > 1), will leave on the second dawn. Inductively, 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 must 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 > 1, 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.

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 $\varphi$ (where $\varphi$ is a formula of the calculus) is read "agent i knows $\varphi$ ." We can define an operator E_G with the intended meaning of "everyone in group G knows" by defining it with the axiom

E_G \varphi \Leftrightarrow \bigwedge_{i \in G} K_i \varphi,

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

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" $C_G \varphi=\varphi\wedge E_G (C_G \varphi)$ . In this way, it is possible to find a formula $\psi$ implying $E_G (\varphi \wedge C_G \varphi)$ from which, in the limit, we can infer common knowledge of $\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 $R_1,\dots,R_n$ , defined on $S \times S$ , intuitively representing what states agent i considers possible from any given state, and (iii) a valuation function $\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 $K_i \varphi$ is true at state s iff $\varphi$ is true at all states t such that $(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 $R_{i}$ , for all agents i in G, call such a relation $R_{G}$ , and stipulating that $C_G \varphi$ is true at state s iff $\varphi$ is true at all states t such that $(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:

K_i(e) = \{ s \in S | 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".

E(e) = \bigcap_i K_i(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,

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 $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 $s \in E^p$ , 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 $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.

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.
↑ Morris Friedell, "On the Structure of Shared Awareness," Behavioral Science 14 (1969): 28-39.
↑ Ian Stewart (2004). "I Know That You Know That...". Math Hysteria. OUP.
↑ 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, The Theory of Meaning (1996).

External links

Vanderschraaf, Peter; Sillari, Giacomo. "Common Knowledge". 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 "Green-eyed Dragons Problem", "Green-eyed Dragons Solution" (Sept 2002)

Topics in game theory

Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game Potential game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia - version of the 7/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.