Archive

Posts Tagged ‘knowledge’

Reasoning about Knowledge

April 16th, 2011 No comments

Last week, I went to Petra in Jordan together with Vasilis Syrgkanis and in the road we kept discussing about the Blue-Eyed Islanders Puzzle, posted by Terry Tao on his blog. It is a nice puzzle because it allows us to reflect on how to think about knowledge and how to make statements like “A knows that B knows that C doesn’t know fact F”. My goal in this post is not to discuss about the puzzle itself, but about a framework that allows us to think about it in a structured way. Nevertheless, I strongly recommend the puzzle, first because it is a lot of fun, and second, because it gives a great non-trivial example to think about this kind of thing. But first, a photo from Petra:

And then some references:

I first read Aumann’s classic, which is a very beautiful and short paper — but where I got most intuition (and fun) was reading Chapter 2 of Reasoning About Knowledge.  So, I’ll show here something in between of what Chapter 2 presents and what Geanakoplos’ survey presents (which is also an amazing source).

We want to reason about the world and the first thing we need is a set \Omega representing all possible states the world can take. Each \omega \in \Omega is called a state of the world and completely described the world we are trying to reason about. To illustrate the example, consider the situation where there are n people in a room and each person has a number x_i \in \{0,1\} in his head. Person i can see the number of everyone else, except his. We want to reason about this situation, so a good way to describe the world is to simply define \Omega = \{0,1\}^n of all 0,1-strings. We define an event to be simply a subset of the possible states of the world, i.e., some set E \subseteq \Omega. For example, the even that player 1 has number 0 in his head is simply: E = \{ x \in \Omega; x_1 = 0 \}. We could also think about the event E' that the sum of the numbers is odd, which would be: E' = \{ x \in \Omega; \sum_i x_i \text{ mod } 2 = 1 \}. Now, we need to define what it means for some person to know some event.

For each person i, his knowledge structure is defined by a partition P_i of  \Omega. The rough intuition is that player i is unable to distinguish two elements \omega_1, \omega_2 in the same cell of partition P_i. For each \omega, P_i(\omega) is the cell of partition P_i containing \omega . The way I see knowledge representation is that if \omega is the true state of the world, then person i knows that the true state of the world is some element in P_i(\omega).

Definition: We say that person i knows event E on the state of the world \omega is P_i(\omega) \subseteq E. Therefore, if person i knows event E, the world must be in some state K_i(E) := \{\omega \in \Omega; P_i(\omega) \subseteq E\}.

Above we define the knowledge operator K_i(\cdot). Below, there is a picture in which we represent its action:

Now, this allows us to represent the fact that person 1 knows that person 2 knows of event E as the event K_1(K_2(E)). Now, the fact the person 1 knows that person 2 doesn’t know that person 1 knows event E can be represented as: K_1(\neg K_2(K_1(E))), where \neg E := \Omega \setminus E.

An equivalent and axiomatic way of defining the knowledge operator is by defining it as an operator K_i: 2^\Omega \rightarrow 2^\Omega such that:

  1. K_i(\Omega) = \Omega
  2. K_i(A) \cap K_i(B) = K_i(A \cap B)
  3. K_i(A) \subseteq A
  4. K_i(K_i(A)) = K_i(A)
  5. \neg K_i(A) = K_i(\neg K_i(A))

Notice that axioms 1-4 define exactly a topology and together with 5 it is a topology that is closed under complement. The last two properties are more interesting: they say that if player i knows something, then he knows that he knows and if the doesn’t know something, he knows that he doesn’t know. Aumann goes ahead and defines the notion of common knowledge:

Definition: We say that an event E is common knowledge at \omega if for any k and for any sequence i(1), \hdots, i(k) where i(j) are players, then \omega \in K_{i(1)} K_{i(2)} \hdots K_{i(k)} E.

Suppose that P' is a partition that is a simultaneous coarsening of P_1, \hdots, P_k, then for all cells C of this partition, either C or \neg C is common knowledge.

An alternative representation is to represent $\Omega$ as nodes in a graph and add an edge between \omega_1 and \omega_2 labeled with i if they are in the same cell of P_i. Now, given the true state of the world \omega \in \Omega, one can easily calculate the smallest event E such that i knows E: this is exactly the states that are reached from \omega just following edges labeled with i, which is easily recognizable as P_i(\omega).

Now, what is the smallest set that 1 knows that 2 knows ? Those are the elements that we can arrive from a path following first an edge labeled 1 and then an edge labeled 2. Extending this reasoning, it is easy to see that the smallest set that is common knowledge at \omega are all the elements reachable from some path in this graph.

More about knowledge representation and reasoning about knowledge in future posts. In any case, I can’t recommend enough the references above.

Categories: theory Tags: ,