Quiero un breve esquema de cómo este tipo de problemas pueden ser resueltos de una manera sistemática. Uno no tiene que confiar en la intuición, hacer garabatos y mano saludando.
La formulación del problema es, de hecho, un tanto imprecisa.
No está claro cómo Albert trata de su primera declaración.
El enunciado del problema debe ser cambiado a la siguiente (nótese el punto 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] ...
En otras palabras, las reglas del juego (que Albert sabe sólo el mes y Bernard sólo conoce el día) debe ser de conocimiento común.
Si las reglas son de conocimiento común, podemos modelar el conocimiento específico tanto de jugadores como de sigma álgebra de operadores en el espacio finito de opciones. En particular, ambos jugadores pueden hacer uso de los llamados Aumann-conocimiento del operador con el fin de calcular los acontecimientos como "a sabe que B sabe x".
La modificación del espacio de las opciones disponibles puede ser modelado por las huellas de sigma-álgebras. Consulte [Maschler, Solan, Zamir - "Teoría de juegos"] y algún libro acerca de la Probabilidad / Teoría de la Medida de su elección para obtener más detalles.
Todo el procedimiento puede ser realizado lo suficientemente rigurosas como para que podamos implementar en un ordenador, como los siguientes Scala-fragmento de código muestra. La primera parte es un poco denso, pero la definición del problema en sí es más o menos legible, incluso para los no programadores:
// 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)
La salida se ve de la siguiente manera:
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)}}
Esta solución funciona con arbitrariamente profundamente anidada "yo sé que Usted sabe que yo no sé Que"las sentencias arbitrarias y número de jugadores.
Por cierto: esta es una máquina generado solución de Cheryl Cumpleaños del problema, y la máquina nos dice que la respuesta correcta es el 16 de julio.
