Epistemic Analysis

Epistemic Logic is a method of logical reasoning used in artificial intelligence and it deals with knowledge and belief systems. In this section we analyse the puzzle presented on the homepage in lines of epistemic logic. The table below represents the various scenarios in which prisoners can wear the different coloured hats. Each scenario can be considered as a 'possible world'. Possible worlds are represented in Kripke structures. With the knowledge possessed by the prisoners they can make a public announcement about their own hat colour. The knowledge levels are graphically represented by Kripke structures. As a result of public announcements the knowledge of the agents increases which results in new Kripke structures.

Possible scenarios

As in this puzzle there are four prisoners wearing two blue and two red hats, there are six possible scenarios. These can be be represented in form of a table as shown below. The colour in the cells of the table represent the colour of the hat worn by each prisoner. The arrows in the cells indicate the direction in which the prisoners are looking. The column between A and D represents the screen or wall between the agents A and D. The wall does not allow the agent D to see the agents A, B and C and vice versa.

Scenario C B A   D
1
 => => =>   <=
2 => => =>   <=
3 => => =>   <=
4 => => =>   <=
5 => => =>   <=
6 => => =>   <=

Kripke Structures and Knowledge Distribution

A Kripke structure is represented by nodes and arrows as in the figures 1 to 7. The nodes represent the worlds analogous to the column "Scenario" in the table above. Arrows on the nodes represent the knowledge of agents in the worlds. The kripke structure for our puzzle has 6 possible worlds and 4 agents. The interconnection between the nodes show that the agents are not sure of the world they are in, if in multiple connected worlds the hat colour of a prison is different, he in not yet sure of his own hat colour in that world.

The knowledge distribution of different agents is represented in formulae. We discuss the individual knowledge gained by the agents at different stages, the public announcements and the common knowledge gained among the agents due to public announcements. Public announcements are made only when the agent is sure of his answer.

Initial situation

The picture on the homepage shows the arrangement in which the prisoners are made to stand. It also shows that each prisoner wears a hat of unknown colour.

In this arrangement, the Prisoners A and D are never able to see other prisoners and therefore they are not likely to claim the colour of their own hats. This is shown in figure 1.

Prisoner B is able to see only the hat of prisoner A, from this he can reduce the amount of possible scenarios by half. But still cannot draw conclusions about his own hat, as it can still be red or blue. This is described in figure 2.

Prisoner C can see prisoners B and A, but not D. From the table it is clear that under scenario 3 and 4, he sees two prisoners in front of him, wearing the same colour hats. Because there are two red and two blue hats in total, he can conclude that his hat is of the opposite colour. But in the other scenarios he is still unsure of the colour of his own hat. This is shown in figure 3.

Figure 1: Prisoners A and D
Figure 2: Prisoner B
Figure 3: Prisoner C
M1:The kripke structures for the initial knowledge of the prisoners. The numbers in the nodes correspond to those in the table and represent the possible worlds. The arrows show the state of knowledge of the prisoners.

Knowledge distribution at the beginning

Initially prisoners B, A and D know that prisoner C knows the colour of hat of prisoners B and A. Hence this is common knowledge. It is also common knowledge is that prisoner B knows the colour of the hat of prisoner A. One more common knowledge is that prisoner D and A do not know the colour of anybody's hat.

C's public announcement

In case C looks at the same colour hats that agents B and A are wearing, C gains the knowledge that he definitely has a hat with a colour other than B and A. He can therefore say which colour the hat is that he is wearing. In terms of epistemic logic this is seen as a public announcement. This has the following effect on the Kripke structure.

Figure 4: Prisoners A, B, C and D
M2:The kripke structures for the knowledge of the prisoners after C made a public announcement.
D has annouced his colour and is also able to see the colour of the hat of A and B, therefore he know exactly in which world he lives: either world 3, if his hat is red, or world 4, if his hat is blue. Because C announces his hat colour, all other prisoners now know this too (making it common knowledge). The other prisoners also know that there is only one world in which C could know his hat colour. This is again either world 3 (C wears red) or world 4 (C wears blue). The connections in the Kripke model are thus the same for all prisoners.

Knowledge distribution after C's public announcement:

Everyone keeps quiet

This is the opposite case from the previous, C in this case sees the hat of A and B being of different colour. For this reason he is still unsure of his own hat colour. The other prisoners have even less infomation, so they don't know either. This means that everyone will keep quiet. After a while, the prisoners will notice that no-one said anything, this can be seen as a public announcement of no-one knowing their own hat colour.

Figure 5: Prisoners A and D
Figure 6: Prisoners B and C
M3: The kripke structures for the knowledge of the prisoners, when C keeps quiet.

If everyone keeps quiet, everyone knows that no-one knows his own hat colour. Everyone knows already that in worlds 3 and 4, prisoner C would have known his hat colour. So in this case these are no longer considered as possible worlds, for this reason they also do not appear in the Kripke structures in figures 5 and 6. Prisoners A and D face the wall, so they don't see any hats and still consider any remaining possible world as possible, as seen in figure 5. Prisoner C knows the colour of the hat of prisoner B and can therefore reduce the possibilities by two, leaving him only in doubt about two worlds (see Figure 6). Prisoner B can deduce his hat colour from the hat colour of A and knowing that his is different from that, he however still has no information on the hat colour of C and D, and is therefore in doubt between that same two worlds as prisoner C.

Knowledge distribution after everyone is keeping quiet

B's public announcement

From the formulae in the previous step, it became clear that prisoner B is able to deduce his own hat colour if everyone keeps quiet. He in this case knows that C did not know his hat colour. This can only be true if A and B have different hat colours. So B knows that his hat has a different colour than prisoner A who he sees in front of him. B will then announce this so that the prisoners will be freed.

Figure 7: Prisoners A, B, C and D
M4: The kripke structures for the knowledge of the prisoners after B made a public announcement.

If B announces the colour of his hat, all other prisoners will know this. All prisoners also know that the colour of the hat of prisoner A is different, as everyone kept quiet earlier. However none of the prisoners has gotten any information on the colour of the hats of prisoners C and D. Meaning these could still be either red or blue. To summarize, all prisoners now know the colours of A and B's hats, but don't know those of C and D. Each prisoner is because of this in doubt between two possible worlds, as can be seen in the Kripke model in figure 7.

Knowledge distribution after B's public announcement: