Common Knowledge
From Theory
Notes for CS 8803 - Game Theory and Computer Science. Spring 2008
Scribed by Karthekeyan
Contents |
Motivating Example
Consider a village of 100 people in which every person is wearing either a red or a blue hat. Noone knows the color of their hat. However, they are all wearing red hats. The village constitution has a rule that any person who is wearing a red hat and also knows that he is wearing a red hat should kill himself. The village is at peace until an outsider comes and gives a speech in which he tells that at least one among the villagers is wearing a red hat. After 100 days, all the villagers kill themselves. Do you see why?
Definition
Consider a finite set of states Ω, a probability distribution P defined over Ω. Let π1,π2,...,πn be a partition of Ω for the n players.
- πi:Ω − > 2Ω
Given a state 
, πi(a) defines the partition to which a belongs to, for the i-th player.
Event 
, is known as common knowledge if R = Meet(π1,...,πn). Here, Meet(.) is the finest common coarsening of the subsets.
Graph theoretically, consider each state as a vertex; now each partition defines a clique on the vertices. Meet(.) is defined as the partition of the vertex set into connected components of this graph.
Also note that, unions of sets in Meet(π1,...,πn) are also common knowledge events.
Example
In the above figure, any union of green squares could be a common knowledge set. The dashed rectangle is not a common knowledge set.
Simple Theorem
Let Ω and P be defined as above. Let . For any 
, if it is Common Knowledge that q1 = Pr(R | π1(ω)) and q2 = Pr(R | π1(ω)), then q1 = q2.
The proof follows just by definition.
The production of this material was supported in part by NSF award SES-0734780.
