When I started to write today, I thought to explore the other aspects of the Prisoner’s dilemma because that is such a rich source of thought about decision making, but accidentally I came upon a nifty little puzzle that shows how a bit of rational thought can change greatly the probability of making the right decision. The only drawback to this puzzle is that the solution does take a bit of math; nothing beyond what a bright high school student could do, so don’t be intimidated.
You know how when you buy a new car and you take it out for a drive; suddenly you see the same model everywhere? Well, the same thing happened to me. After I found this little gem, just for giggles, I googled it and found dozens of sites. Here’s one of the best.
Because the various sites present the same puzzle in a different way, and I don’t want to play favorites, this is my version.
In a distant land a long time ago, where sexism was still rife, a brave commoner showed uncommon bravery fighting the forces that wished to overcome the sultan. In battle, the commoner killed one of the rebel leaders, and the battle was won. Now the sultan was in a difficult position because he must reward the commoner, but the rebel he killed was one of the sultan’s many cousins. In spite of the rebellion, custom dictated that the sultan must avenge the blood debt. So he came up with a plan that would appear to reward the commoner, but in reality give him a task so difficult that he would surely fail and be subject to execution.
The plan was simple. As a reward, the commoner would be allowed to marry one of the sultan’s 100 daughters, but there was a catch. Each daughter had a dowry. The commoner would be shown the daughters one at a time and be told the value of her dowry. The commoner could chose any daughter to marry and thus get her wealth, but he must choose the one with the largest dowry, otherwise he would leave the palace with nothing. (And, it’s presumed, become prey to assassins hired by the sultan to avenge the blood debt, but that is only an assumption.)
Such a simple task. Watch the beautiful young women come in one at a time and listen to the wealth each would bring to him if he chose her. However, the odds of picking the correct daughter seem to be about 1 out of 100 and that is not good. Of course, the odds are small that the first one will not have the largest dowry. So as soon as he hears the second one, and if her dowry is larger, then he knows his odds of winning have increased to 1 in 99. If he passes again, and if – well, you get the idea.
So the poor country lad with a brave heart has only a few minutes to prepare himself and decide on a strategy that will maximize his chances of winning. What should he do?
If the sultan only had three daughters, then the commoner would pass on the first, and pass on the second if she were lower and thus a sure loser. This strategy raises his odds of winning to one of two from one of three. Can he do something similar with 100 daughters?
Since the commoner knows nothing about the distribution of the dowries, he figures the best strategy is to wait until a certain number x of daughters have been presented, then pick the next one with the highest dowry that he has seen. To calculate x, he reasons that the number to skip is determined by the condition that the odds of the highest dowry having been seen is equal to or just greater than the odds that it remains to be seen and that if it is seen it will be picked.
The charm of this puzzle is that with that rather simple analysis, one can find an optimum strategy, and that strategy can improve his odds of winning tremendously.
Interestingly enough, the best strategy is to divide the number of daughters by e (=2.71828…) And pick the next daughter with a higher dowry than what has preceded. Following that strategy will increase the odds of winning from his initial thought of 1% to about 37%!
The complete analysis is too long to present here, but one starts with writing the condition on the probabilities as:
x/n > x/n * (1/(x+1) + … + 1/( – 1))
Where x in the number of daughters to be skipped and n = 100. Solve for the smallest x that satisfies the inequality. This can be done by brute force (trivial if running on a computer), or if you recognize the properties of continued fractions, then you can solve it for very large n and in the limit of large numbers, the answer will approach n/e and it will approach slowly. Since we cannot deal with fractional daughters, that is a close enough approximation.
Adding to the charm is that, like other examples I’ve used, the solution depends on looking at the right aspect of the problem in setting up the analysis. One’s first thought is that any attempts at optimization would be hopeless, yet the commoner can improve things from 1% to 37%. Now aren’t you glad you didn’t sleep through algebra?
For those who wish to delve further into decision theory without wading through a lot of equations, I have posted a tutorial on elementary decision theory. It shows examples of faulty physicians’ diagnoses (important for those considering surgery) and how to evaluate anti-terrorist activities (important for everyone). That tutorial can be found here.