﻿ Common knowledge: Josephine's problem & Blue-eyed islanders

Josephine's problem - "Shoot"
Image source

Blue-eyed islanders
Image source

# Common knowledge puzzles

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.
The concept was first introduced in the philosophical literature by David Kellogg Lewis in his study Convention (1969). 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.
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".
Wikipedia: Common Knowledge (Logic)

# Josephine's problem.

The queens of the matriarchal city-state of Mamajorca, on the continent of Atlantis,have a long record of opposing the male infidelity problem.

In Josephine's Kingdom every woman has to take a logic exam before being allowed to marry. Every marrying woman knows about the fidelity of every man in the Kingdom except for her own husband, and etiquette demands that no woman should tell another about the fidelity of her husband.
Also, a gunshot fired in any house in the Kingdom will be heard in any other house. Queen Josephine announced that unfaithful men had been discovered in the Kingdom, and that any woman knowing her husband to be unfaithful was required to shoot him at midnight following the day after she discovered his infidelity. How did the wives manage this ?

If there is only 1 unfaithful husband, then every woman in the Kingdom knows that except for his wife, who believes that everyone is faithful. Thus, as soon as she hears from the Queen that unfaithful men exist, she knows her husband must be unfaithful, and shoots him.

If there are 2 unfaithful husbands, then both their wives believe there is only 1 unfaithful husband (the other one). Thus, they will expect that the case above will apply, and that the other husband's wife will shoot him at midnight on the next day. When no gunshot is heard, they will realise that the case above did not apply, thus there must be more than 1 unfaithful husband and (since they know that everyone else is faithful) the extra one must be their own husband.

If there are 3 unfaithful husbands, each of their wives believes there to be only 2, so they will expect that the case above will apply and both husbands will be shot on the second day. When they hear no gunshot, they will realize that the case above did not apply, thus there must be more than 2 unfaithful husbands and as before their own husband is the only candidate to be the extra one.

In general, if there are n unfaithful husbands, each of their wives will believe there to be n-1 and will expect to hear a gunshot at midnight on the n-1th day. When they don't, they know their own husband was the nth.

This problem is also known as the Cheating Husbands Problem, the Unfaithful Wives Problem or the Muddy Children Problem.

# Blue-eyed islanders.

On an island, there are k people who have blue eyes, and the rest of the people have green eyes. There is at least one blue-eyed person on the island (k >= 1). If a person ever knows herself to have blue eyes, she must leave the island at dawn the next day. Each person can see every other person's eye color, there are no mirrors, and there is no discussion of eye color. At some point, an outsider comes to the island and makes the following public announcement, heard and understood by all people on the island: "at least one of you has blue eyes". The problem: Assuming all persons on the island are truthful and completely logical, what is the eventual outcome?

The answer is that, on the k dawns after the announcement, all the blue-eyed people will leave the island.
This can be easily seen with an inductive argument.
If k = 1, the person will recognize that he or she has 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, will leave on the second dawn.
So on, 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 have blue eyes and leave.