I want to briefly sketch how this kind of problems can be solved in a systematic way. One does not have to rely on intuition, scribbling and hand-waving.
If the rules are common knowledge, we can model the specific knowledge of both players as sigma algebras on the finite space of options. In particular, both players then can make use of the so-called Aumann-knowledge operator in order to compute the events like "A knows that B knows x".
The modification of the space of available options can be modeled by traces of sigma-algebras. Refer to [Maschler, Solan, Zamir - "Game Theory"] and some book about Probability / Measure Theory of your choice for more details.
The whole procedure can be made sufficiently rigorous so that we can implement it on a computer, as the following Scala-code snippet shows. The first part is somewhat dense, but the problem definition itself is more or less readable even for non-programmers:
// Solution of "Cheryl's birthday problem".
//
// Relies on atomic sigma algebras and Aumann's knowledge operator.
//
// Language: Scala
// TAGS: ATOMIC_SIGMA_ALGEBRA AUMANN_KNOWLEDGE_OPERATOR
import scala.collection.immutable.Set
import scala.language.implicitConversions
import scala.language.reflectiveCalls
/** Atomic sigma algebra over a finite set of elementary events of
* type `X`.
*
* Essentially it's just the `Set[X]` algebra, since the `sigma-`
* properties are trivially fulfilled. The crucial property is
* that it is generated by an explicitly specified disjoint partition
* of the universal set, which allows us to define the
* Aumann-knowledge operator without any unwieldy combinatorical
* enumerations.
*
* @param partition Enumeration of disjoint subsets that partition
* the universal set and generate this sigma-algebra.
*/
case class AtomicSigmaAlgebra[X](val partition: Set[Set[X]]) {
/** Computes the universal set, that is, the union of all
* elements of the partition.
*/
lazy val universal: Set[X] =
partition.foldLeft(Set.empty[X]){_ ++ _}
/** Finds the set of the partition that contains the
* elementary event `x`.
*
* Returns empty set if `x` lies outside of the universal
* set of this sigma algebra.
*/
def containingSet(x: X): Set[X] =
partition.find(_.contains(x)).getOrElse(Set.empty[X])
/** The (Aumann)-knowledge operator for this sigma algebra.
*
* Contains all elementary events that are contained in
* atoms that are subsets of `a`.
*/
def knowledgeOperator(a: Set[X]): Set[X] = {
var acc = Set.empty[X]
for (p <- partition) if (p.subsetOf(a)) acc ++= p
acc
}
/** Syntactic sugar: if you call sigma algebras after players,
* this method name makes sense.
*/
def knows(a: Set[X]): Set[X] = knowledgeOperator(a)
/** Union of all atoms that contain exactly one elementary
* event.
*/
def exactKnowledge: Set[X] = {
var acc = Set.empty[X]
for (p <- partition) if (p.size == 1) acc ++= p
acc
}
/** Trace of this sigma-algebra on a subset of the universal set.
*
* Includes all non-empty intersections of the partition elements
* with the set `a`.
*/
def trace(a: Set[X]): AtomicSigmaAlgebra[X] = {
val newPartition =
partition.map{p => p.intersect(a)}.filterNot{_.isEmpty}
AtomicSigmaAlgebra(newPartition)
}
override def toString = {
(for (p <- partition) yield p.mkString("{", ",", "}")).
mkString("{", ",", "}")
}
}
object AtomicSigmaAlgebra {
/** Generates the finest possible sigma algebra over an
* universal set.
*/
def discrete[X](universal: Set[X]) =
AtomicSigmaAlgebra(universal.map{ x => Set(x) })
/** Computes the coarsest domain sigma algebra on the universal set
* such that the function `f` becomes domain-codomain-measurable.
*
* Contains preimages of all atoms of the codomain sigma algebra.
*
* This is what is usually denoted by `\sigma{X}` for random
* variables.
*/
def initial[X,Y](
universal: Set[X],
cod: AtomicSigmaAlgebra[Y],
f: X => Y
): AtomicSigmaAlgebra[X] = {
val grouped = universal.groupBy{x => cod.containingSet(f(x))}
val preimages = grouped.map{_._2}.toSet
AtomicSigmaAlgebra(preimages)
}
}
/** Pimp `Set[X]` with a few convenient operators */
implicit def logicalSetOps[X](set: Set[X]) = new {
def and(other: Set[X]) = set.intersect(other)
def or(other: Set[X]) = set.union(other)
def minus(other: Set[X]) = set.filterNot(other.contains)
}
/* ##################################
* CHERYL'S BIRTHDAY PROBLEM
* ##################################
*/
type Date = (String, Int) // month, day
/** List of all possible dates, given by Cheryl */
val list = Set(
("May", 15), ("May", 16), ("May", 19),
("June", 17), ("June", 18),
("July", 14), ("July", 16),
("August", 14), ("August", 15), ("August", 17)
)
/** Extract list of months and days from the list set,
* transform them into discrete sigma algebras
*/
val months = AtomicSigmaAlgebra.discrete(list.map(_._1))
val days = AtomicSigmaAlgebra.discrete(list.map(_._2))
// Albert and Bernard are dehumanized into atomic sigma
// algebras generated by the information they get from Cheryl.
// All other aspects of their personalities are completely irrelevant
// for the solution of this question.
// Albert is the sigma algebra generated by the first canonical projection
val albert = AtomicSigmaAlgebra.initial(list, months,
(x: (String, Int)) => x._1
)
// Bernard is the sigma algebra generated by the second canonical projection
val bernard = AtomicSigmaAlgebra.initial(list, days,
(x: (String, Int)) => x._2
)
// Filter the states where Albert would know the birthday immediately
val albertWouldKnowImmediately = albert.exactKnowledge
println("Albert would know immediately = " + albertWouldKnowImmediately)
// Filter the states where Bernard would know the birthday immediately
val bernardWouldKnowImmediately = bernard.exactKnowledge
println("Bernard would know immediately = " + bernardWouldKnowImmediately)
// Now the conversation starts.
// Albert says out loud that he does not know when the birthday is,
// and that at this moment he is certain that Bernard does not
// know when the birthday is either.
// "Albert Does Not Know Birthday"
val adnkb = list minus albertWouldKnowImmediately
// "Bernard does not know birthday"
val bdnkb = list minus bernardWouldKnowImmediately
// "Albert Knows Bernard Does Not Know Either"
// (The only use of Aumann's knowledge operator)
val akbdnke = albert.knows(bdnkb)
println("Albert knows that Bernard does not know either = " + akbdnke)
val albertSaysFirst = adnkb and akbdnke
println("Albert says essentially: " +
"possible states are = " + albertSaysFirst)
// Update sigma-algebras of both players,
// '1' stands for "knowledge after first statement"
val a1 = albert.trace(albertSaysFirst)
val b1 = bernard.trace(albertSaysFirst)
println("a1 = " + a1)
println("b1 = " + b1)
// Now Bernard says that he did not know previously (bdnkb again),
// but that now he suddenly knows exactly what the birthday is.
val bernardsNewExactKnowledge = b1.exactKnowledge
val bernardSays = bdnkb and bernardsNewExactKnowledge
println("Bernard now would know exactly: " + bernardsNewExactKnowledge)
println("Bernard says: valid states = " + bernardSays)
// update knowledge of both players again
val a2 = albert.trace(bernardSays)
val b2 = bernard.trace(bernardSays)
println("a2 = " + a2)
println("b2 = " + b2)
// now albert says that he knows what the birthday is
val albertsNewExactKnowledge = a2.exactKnowledge
val albertSaysSecond = albertsNewExactKnowledge
println("Albert now would know exactly: " + albertsNewExactKnowledge)
println("Albert says: valid states are = " + albertSaysSecond)
// update again
val a3 = albert.trace(albertSaysSecond)
val b3 = bernard.trace(albertSaysSecond)
println("a3 = " + a3)
println("b3 = " + b3)
// Check the knowledge state of both players:
// when is Cheryl's birthday?
println("Albert knows: " + a3)
println("Bernard knows: " + b3)
The output looks as follows:
Albert would know immediately = Set()
Bernard would know immediately = Set((May,19), (June,18))
Albert knows that Bernard does not know either = Set((August,15), (August,17), (July,14), (August,14), (July,16))
Albert says essentially: possible states are = Set((August,15), (August,17), (July,14), (August,14), (July,16))
a1 = {{(August,15),(August,17),(August,14)},{(July,14),(July,16)}}
b1 = {{(August,15)},{(August,17)},{(July,14),(August,14)},{(July,16)}}
Bernard now would know exactly: Set((August,15), (August,17), (July,16))
Bernard says: valid states = Set((August,15), (August,17), (July,16))
a2 = {{(August,15),(August,17)},{(July,16)}}
b2 = {{(July,16)},{(August,15)},{(August,17)}}
Albert now would know exactly: Set((July,16))
Albert says: valid states are = Set((July,16))
a3 = {{(July,16)}}
b3 = {{(July,16)}}
Albert knows: {{(July,16)}}
Bernard knows: {{(July,16)}}
This solution works with arbitrarily deeply nested "I know You know I don't know You know"-statements and arbitrary number of players.
By the way: this is a machine-generated solution of Cheryl's Birthday problem, and the machine tells us that the right answer is July 16th.
The wording of the problem is indeed somewhat imprecise.
It is not clear how Albert comes to his first statement.
The problem statement should be changed to the following (notice point 2):
1) Cheryl gives them a list of 10 possible dates.
2) Cheryl says (to both): "Now I will tell the month to Albert and the day to Bernard"
3) Cheryl then tells Albert and Bernard separately the month and the day of her birthday respectively.
4) ... [as in original version] ...
In other words, the rules of the game (that Albert knows only the month and Bernard knows only the day) should be common knowledge.
