Problem of the Week 1045
Alice is a prisoner under the supervision of warden Charlie. Charlie meets with Alice, gives her an unbiased coin, and tells her to return the next day with her fist closed, and either holding the coin in it or not. He also tells her that there is another prisoner who will get the same instructions. He tells her nothing about that prisoner's identity or attributes, and she cannot communicate with the other prisoner (whose name happens to be Bob).
On the next morning, the prisoners will meet with Charlie and open their fists.
If neither holds a coin, neither is released.
If one holds a coin, then that one is released with probability r and the other is released with probability q.
If both bring the coin then both are released with probability s.
Let R(w) be the probability that Alice is released if BOTH Alice and Bob bring the coin with probability w.
Find binary fractions p, q, r, and s between 0 and 1 (inclusive) so that
(a). p is the value of w that maximizes R(w).
(b). The rational choice for Alice is to bring the coin with probability 1.
(c). R(1) < R(p), i.e., her rational choice (the "economics solution": bring the coin) is less likely to free her than the team's optimizing R(w) (the "mathematical solution").
a binary fraction is one whose denominator is a power of 2. Using such fractions means that all probabilities can be computed in finite time using the coin. As a hint, one can solve the problem using only fractions of the form i/8.
It is worth repeating that there is NOTHING here about what Alice knows. To be precise, it should be said that Alice knows absolutely nothing about the other prisoner. Certainly to ponder her rational choice she might wonder about the other prisoner. Does he have a deathly aversion to carrying coins? Does he really love carrying coins? Is he a fan of Donald Duck's theory of flipism ("At every crossroad of life, let flipism chart your course!"; i.e., flip a coin once and make the decision based on that). But as she ponders her rational choice she can use no such information: she simply has no information at all.
Source: Dan Velleman, Amherst College.
© Copyright 2005 Stan Wagon. Reproduced with permission.