Thursday, December 8, 2011

The Next Best Mate

The so-called "Sultan's Dowry Problem" (a.k.a "Beauty Pageant Problem", "Secretary Problem" etc.) is sometimes used as a model for searching a mate. It is a nice model for decision-making under a certain type of uncertainty.

According to the wikipedia entry:
The basic form of the problem is the following. Imagine an administrator willing to hire the best secretary out of N rankable applicants for a position. The applicants are interviewed one-by-one in random order. A decision about each particular applicant is to be taken immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator can rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants.
There is an elegant solution to the problem, when the objective of the game is to maximize the probability that the candidate chosen has the highest quality. We assume quality can be reduced to a simple number. The so called "1/e" or "37%" solution to this problem involves letting the first 37% of the candidates pass, remembering the quality Q of the best candidate from this set. Thereafter, the first candidate whose quality exceeds Q is chosen.

Todd argues that the way humans search for their mates is very different from this optimal solution. He points out that the 37% rule finds the best solution more often than any other algorithm, 37% of the time. However, what happens during the 63% of the times is not very flattering:
For instance, if applied to a set of 100 dowries ranging from 1 to 100, the 37% rule returns an average value of about 82, that is, the mean of all dowries chosen by this rule. Only 67% of the individuals selected by this rule lie in the top 10% of the population, while 8% fall in the bottom 25%. And it takes the 37% rule an average of 74 tests of potential mates that is, double the 37 that must be checked before selection can begin before a mate is chosen.
This probably explains why normal people do not apply this strategy. It turns out that normal people tend to use a much smaller "screening" period. It turns out that the length of the screening period is dependent on your appetite for risk.

If you are fixated on maximizing the probablity of ending up with the best candidate, then the 37% rule works fine. But if you are a risk minimizer - if you would rather protect your downside - while accepting anybody in the top 10% for example, the optimal screening period is much shorter - closer to 10%.

I first heard about this problem more than a decade ago, and have been fascinated by it ever since. I used this problem to create a programming assignment in the class I am currently teaching.

No comments: