Albert, Bernard and Cheryl popular question (Please comment on my theory)
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.
Cheryl sure is a good one for wasting people's time. :-)
The convention in these kinds of problems is to be conservative: No one says anything that we are not told they said. In particular, Albert deduces that Bernard doesn't know Cheryl's birthday, not because Bernard told him, but because his knowledge of the month permits him to conclude that.
What does Albert's first statement mean? It means that the month that Cheryl told him her birthday is in does not contain any choices that are unique to that month. That means that her birthday cannot be in May, because if it were, Albert could not conclude that Bernard doesn't know her birthday, because it might be May 19, and then Bernard would know her birthday. Similarly, it cannot be in June, because of June 18. So Cheryl's birthday is in either July or August.
What does Bernard's statement mean? Bernard can follow the same logic that we just did above, meaning that he also knows now that Cheryl's birthday is in either July or August. Now that he knows the month is restricted to those two choices, he knows her birthday. That means that her birthday is not a date that is common to both July and August. That eliminates both July 14 and August 14, and leaves only July 16, August 15, and August 17.
What does Albert's last statement mean? It means that based on his knowledge of the month and what we just concluded above (eliminating all but three possibilities), he now knows Cheryl's birthday. But he could not do that if the month were August; there would be two possibilities: August 15 and August 17. Ergo, her birthday must be in July, where there is only one possibility, July 16.
To check: Albert is told that Cheryl's birthday is in July, and Bernard is told that it is the 16th. Initially, neither of them knows her birthday, but after Bernard learns that Albert knows Bernard doesn't know her birthday yet, he deduces that the month cannot be May, so her birthday must be July 16. Now Albert knows that the date cannot be the 14th, and he knows that it must be July 16.
And now we know it too. :-)
Case 1: The reason is because Bernard told him.
If that was the case, the dialog would start with:
Bernard: I don't know when her birthday is.
In mathematics we never make any extra assumptions, is always understood that no information is withhold. Bernard telling something to Albert, information which is needed to solve the problem, would automatically have been stated in the problem.
P.S. Just to make things clearer in what I mean, you are right that the Case 1 is the right one, the problem you are solving in case one is the following:
Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl marks 10 possible dates: May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, or August 17.
Then Cheryl tells Albert the month of her birthday, but not the day. She tells Bernard the day of her birthday, but not the month. Then she asked if they can figure it out.
Bernard: I don't know when Cheryl's birthday is.
Albert: I don't know when Cheryl's birthday is, but I know Bernard doesn't know either.
Bernard: At first I didn't know when Cheryl's birthday is, but now I know.
Albert: If you know, then I know too!
When is Cheryl's birthday?
This is a different problem, and would had been stated with this dialogue.