Home > theory > Reasoning about Knowledge

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: