Logo IMG
HOME > PAST ISSUE > March-April 2009 > Article Detail


Knowing When to Stop

How to gamble if you must—the mathematics of optimal stopping

Theodore Hill

Partial Information

The case of partial information is the most difficult. Usually one does not know how many applicants there will be for a job, nor the exact probabilities of future stock values. In these situations, one method of solution is to use tools from the theory of zero-sum, two-person games, where the stopping problem can be thought of as a decision maker playing against an opponent (often called Nature or God) who may assign the values and probabilities in any way she chooses.

Ulrich Krengel of the University of Göttingen and I used this technique to discover the optimal strategy in the so-called marriage problem where only a bound on the number of applicants is known. As a concrete example, consider the problem where the objective is to select the highest number from a hat containing at least one, and at most five, numbered cards (if you do not stop and there are no cards left, you lose.) We proved that the optimal strategy in this case is to stop with the first card with probability 26/75 (which you may do using a random number generator or other method). If you do not stop with the first card, then you should continue to the second card, if there is one. If the second card’s number is higher than the first card’s number, stop with probability 26/49. Otherwise, continue, stopping with the first record thereafter (or when you run out of cards or are forced to choose the number on the fifth card). This guarantees a probability of 26/75 of stopping with the highest number, no matter how many cards Nature deposited in the hat.

There is no better strategy. We found the exact formulas and strategies for all possible bounds on the maximum number of cards and the winning probabilities are surprisingly high. For example, even if you only know that there are somewhere between 1 and 100 cards in the hat, it is still possible to win about 20 percent of the time. Exactly the same method can be employed to obtain optimal stopping rules in many real-life problems such as a situation where an employer wants to hire the very best salesperson available, and knows the maximum number of candidates available for the position, but does not know how many have already accepted other jobs.

In another type of stopping problem involving partial information, the observer knows the length of the sequence exactly (say, for example, the number of cards), but has only partial information about the random values on the cards. Instead of having no information at all, or knowing all the possible values and probabilities, he might know only the average value and standard deviation of each variable. In the case where variables are independent, Frans Boshuizen of the Free University of Amsterdam and I were able to use game theory and mass-shifting “balayage” (sweeping probability mass away from its center in both directions) arguments to determine the optimal stop rules, but those techniques fail for most other partial-information stopping problems.

» Post Comment



Subscribe to American Scientist