The Sultan’s Dowry Problem
I found this puzzle while cruising the Internet today.
A sultan has granted a commoner a chance to marry one of his N daughters. The commoner will be presented with the daughters one at a time and, when each daughter is presented, the commoner will be told the daughter’s dowry (which is fixed in advance). Upon being presented with a daughter, the commoner must immediately decide whether to accept or reject her (he is not allowed to return to a previously rejected daughter). However, the sultan will allow the marriage to take place only if the commoner picks the daughter with the overall highest dowry. Then what is the commoner’s best strategy, assuming he knows nothing about the distribution of dowries?
This is a cool problem because forms of it occur all the time, the classic example being dating/marriage like in this puzzle, but its applicability is definitely not limited to just that. The strategy indicated in the solution is itself not that surprising because I think that’s what most of us do, or least I do, most of the time–that is after a while we pick something. The real question being how long do you wait to pick? What I found surprising is how long to wait under the optimal strategy, and that it’s (only or incredibly) 37% likely to produce the best result. So the bottom line is don’t stress about this kind of problem the next time you encounter it, because there really is no perfect solution and not one that “works” more than 37% of the time anyway.
March 1st, 2006 at 12:05 pm
How often can you not go back and choose the best? If you are shopping for shoes or new cars… you can usually go back and put your money down. I see it as most useful in hot markets (hot women?)… perhaps even when hiring employees. Because if your decision process takes too long, then the good women, good employees, good deals of many kinds, will get snapped up by someone else.
So my thinking is, in a hot market, predetermine some sample size depending on how much time/energy I want to invest shopping. Then, after I have seen one third of that number, pick the next one that is better than the rest.