Beauty Contest Problem
Beauty Contest ProblemA problem in GameTheory, with lots of practical applications. It works like this:
Sultan's Dowry Problem
A sultan has 100 daughters. A sultan has granted a commoner a chance to marry 1 of his 100 daughters. The commoner will be presented the daughters one at a time. When a 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. The commoner has only one chance to accept or reject each daughter -- he cannot return to a previously rejected daughter.
The sultan's catch is that the commoner may only marry the daughter with the highest dowry. If he rejects that one daughter, then he gets nothing. If he accepts some previous daughter, he gets nothing.
What is the commoner's best strategy, assuming he knows there are 100 daughters, but knows nothing about the distribution of dowries?
Basically the same problem has been re-stated various ways
You are the judge in a beauty contest. You are presented with the contestants one-by-one. After evaluating each contestant, you have make a choice before seeing the next contestant. You must either:
What is the optimal strategy for picking the best contestant, given these rules? (Assume that if you were able to examine all contestants at the same time, determining the winner would be trivial; in other words, there is a clear way of determining who is best. Problem is, you don't get to consider all opportunities simultaneously).
The setup I read had it as a stakeout problem. You're a cop on a stakeout. You know that the target of the secret criminal conspiracy you're watching is the tallest of the group. You also know that there are 10 people in the conspiracy. But you see them leaving one by one! How do you find the right one?
Originally called "the Secretary Problem."
The Secretary Problem, also known as The Sultan's Dowry Problem, is believed to have been first stated in Martin Gardner's Mathematical Recreations column in the February 1960 issue of The Scientific American It is posed (under the name of the .The Game of Googol.) in Martin Gardner, New Mathematical Diversions from Scientific American, Simon & Schuster 1966, p. 35, with a very accessible solution by Moser and Pounder on p. 41.
Solutions
Some people claim since the prettiest is as likely to be first as last, or any in between, any choice is as good as any other and we'll only pick the prettiest 1/n of the time (unless we know something about the prettiness distribution among contestants). They are incorrect (except for the special case of 1 or 2 daughters).
If there are 3 daughters, reject the 1st daughter (then reject the 2nd daughter only if she is clearly lower than the 1st). That strategy picks the best one of the three 1/2 of the time.
If there are 10 daughters, reject the first 4.
The optimum strategy is:
Wait until you have interviewed roughly N/e candidates (about 36.88 percent of the total). Then take the next candidate better than any one to date.
"The problem is most commonly stated with n = 100 daughters, which gives the result that the commoner should wait until he has rejected 37 of the daughters. Then pick the first daughter with a dowry that is bigger than any preceding one. With this strategy, his odds of choosing the daughter with the highest dowry are surprisingly high: about 37.10%. As the number of daughters increases, this tends towards 1/e = 37.787...%" -- http://mathworld.wolfram.com/SultansDowryProblem.html
http://www25.brinkster.com/ranmath/problems/secy.htm (BrokenLink 2005-08-31)
http://www.mathsoft.com/article/0,,2301,00.html (BrokenLink 2005-08-31)
Sultan's Dowry (http://rec-puzzles.org/new/sol.pl/decision/dowry)
Considered definitive: Ferguson, T. S., "Who solved the secretary problem? Statistical Science Vol.4, pp. 282-296 (1989)
Related algorithms: Bluffer's Guide to Algorithms http://www.imm.dtu.dk/~jv/ip/jv.pdf (BrokenLink 2005-08-31)
Recent work unearthing new subtleties: http://www-abc.mpib-berlin.mpg.de/users/ptodd/publications/todd97/todd97.pdf
Why is this called the beauty contest problem when it has nothing to do with real beauty contests?
Or you could go with the DatingProblem?, but that could refer to pairing up n people together. Perhaps the CommitmentProblem?? Too abstract ....
variations
The problem, as stated, is to find a strategy that maximizes the the probability that we end up with *THE* best.
However, what if we have a slightly different goal:
Assume the contestants are ranked 1, 2, 3, ... N with N being the best. What's our best strategy for maximizing the rank of our selection ? (In other words, what if instead of getting *nothing* if I pick the wrong daughter, I get *that* daughter and her dowry ?)
This is closer to the "practical applications" mentioned below.
Does that have a different strategy ?
Isn't "maximizing the probability we end up with *THE* best," and "maximizing the rank" the same thing? i.e. expectation of no. of times = no. of times x expectation of rank any given time
Not at all. You could have a maximal ranking where you catch the number 2 contestant every single time. This would be better by that measure than catching the #1 contestant only 30% of the time and #10 70% of the time.
Another slightly different game:
To make the question game-theoretic interesting, you could takes turns with another judge and then between the two of you the winner would be whoever chose the prettier contestant.
Real-life application
Practical applications include job-hunting (do you take the offer on the table, or keep looking, knowing the offer is only good for a week).
But that has added elements. You don't know how many offers you'll get or how much time will pass between them. You don't know your opportunity cost of not waiting for something better, but you do know that there will be a cost of waiting for something better. If you are willing to suffer a bit, you can go beyond the 'last one' (last that you can afford) instead of having to accept it.
Practical application.
You are dating. You find you can only get to know someone if you date only one person at a time. Sooner or later you are going to have to get serious. How will you know the right one?
Tip. Meet lots of people when you are young and not serious.
Tip. When you make your selection, stop looking.
I stopped with contestant #1. It's worked pretty well so far (23 years of relationship, 19 of marriage, and counting)
I think what happens in reality is that the threshold drops over time. At first the threshold is high, and only seemingly perfect mates are courted. If you do not or cannot encounter the high ideal, then your threshold slowly drops over time. Eventually you meet somebody meeting the current threshold. A blunt way to put this is that your time alone is evidence that you are a loser, so your expectations drop the longer you are alone.
The beauty contest would be similar, I expect, except that you would probably use the first few contestants to calibrate your expectations (estimated range of rankings). As you get closer to the end of the contest, you lower your threshold, otherwise risk defaulting to the last one, who may be a real dog. How to optimize the threshold lowering function and feeding it continuous calibration info is probably the hard part.
Fortunately, there's a theoretical foundation to this with actual working algorithms. Now if anyone here on wiki could remember these algorithms!
There Are No Practical Applications
Folk, this is game theory. There are no practical applications for this mess. Any situation where you are being forced into making a decision with incomplete information despite the fact that the information is available is an artificial and bullshit construct.
I have had the situation where a recruiter said that an offer for a job/contract/whatever was only good until the end of the week/month/phone call. You know what? If the hiring authority really wants my skills and expertise then they'll make some kind of exception to get me. Otherwise I'm just another disposable flunky to you, so why would I want to put myself in that situation?
If there are many beauty contestants I want to see them all at once. If you prevent me from doing so then you are yanking my chain, and I'll tell you to take a hike just like I told the recruiter trying to pressure me into taking a gig I won't like.
I came across this problem expressed as having to award a construction contract in Lastland. Rather than opening all submitted bids and selecting the lowest, the bids were to be opened one-at-a-time and the last one opened would be accepted. I remember the solution being the same (open N/e bids and then stop with the next one that is lower). Being in the midst of a job search, the comment on job-hunting and offers strikes a chord, but I don't have even the first offer to turn down yet! -- RobBiedenharn (2005-05-16)
He should accept the daughter if her dowry is higher than any daughter he has seen so far, and she is clearly less attractive than any woman he has ever seen before. She would require a high dowry to make her acceptable, and the sultan would not feel that he has given up a daughter he values to a commoner.
That results in choosing the second daughter 1/4 of the time. It's a poor strategy if there are many daughters.
EditText of this page
(last edited May 2, 2011)
or FindPage with title or text search