## How to find the best when you can’t go back

Often when traveling or exploring a new city, I find myself with the following problem:

- I’m headed someplace
- I’m hungry and need to stop somewhere to eat
- I don’t know what restaurants there are between myself and my destination
- Once I pass a restaurant, I don’t want to turn around and return to to it
- I’d like to eat at one of the best restaurants available (where “best” is a function of both food quality and expense)

An obvious solution, of course, is to buy a smart phone and take the time to search online. An alternative, if you’re more in the mood for wandering on foot than online, is to inspect the first few restaurants you pass to get a sense of the quality of restaurants in that locale, and to then pick the next restaurant that exceeds the quality of the best of your sample (or until you run out of restaurants or time). The problem then becomes, “How many restaurants should I sample before I decide to choose the next best?”.

The last time this happened to me, I remembered that I had actually read the optimal solution to this problem^{1} in Henry Stark and John Wood’s textbook *Probability, Random Processes, and Estimation Theory for Engineers* (1994). Assuming that the order in which you encounter the restaurants is random, Stark and Wood are able to prove that in the limit of a large number of restaurants, the optimal initial sample size is *n*/*e* where *n* is the total number of restaurants you’re willing to consider and *e* is the natural number (approximately 2.718). Thus, if you’re willing to explore up to nine restaurants, to maximize your chances of selecting the best restaurant, you should examine the first three restaurants and then choose the next restaurant that’s better than the first three (or the ninth restaurant if you fail to come across a restaurant better than the first three).

Since Stark and Wood’s proof assumes a large number of restaurants and I probably don’t have the time or patience to explore more than 20, I ran some Monte Carlo simulations to see what the optimal sample size is for 20 or fewer restaurants. The results are shown in Figure 1 and closely agree with Stark & Wood’s approximately *n*/3 rule. If you fit a least-squares line to the optimal sample size as a function of the total number of restaurants, the slope is 0.37. Interestingly, if instead of trying to find the best restaurant, your goal is to maximize the mean ranking of the restaurant you choose, the number of restaurants you should sample is much less (Figure 2). The least squares line for this objective has a slope of 0.13. So one should only sample around 10% of the possible number of restaurants.

So there you have it, a solution to your restaurant wandering needs. In practice, I wonder how useful these rules of thumb are since, even when you’re a stranger, you surely can infer something about the distribution of restaurant quality in that area and recognize an exceptional restaurant even without having to take an initial sample. Also, the order in which you encounter restaurants is not random, since restaurants of similar caliber tend to group together. Anyone up for doing a randomized experiment to see how well this works?

-David Groppe

*Footnote 1*: Stark and Woods actually presented this proof as a solution to the problem of trying to find the most beautiful contestant in a beauty pageant. Perhaps they were indirectly trying to give engineers dating advice.

REFERENCES:

Stark, H. & Wood, J.W. (1994) *Probability, Random Processes, and Estimation Theory for Engineers *(2nd ed.). Upper Saddle River, N.J.: Prentice-Hall.

The problem is also known as the secretary problem or the marriage problem. There was also some leader/mathematician way back in the day who, after losing his wife, tried to rigorously implement a procedure to choose an optimal match. While he met lots of women, his choice actually turned out to be pretty close to the optimal solution if he had stuck to the sequential rules you mention.

Who Solved the Secretary Problem?

Jeremy Karnowski said this on March 27, 2011 at 5:27 pm |

Most interesting. I had no idea that this problem was so well known and had spawned a “field within mathematics-probability-optimization.” On the issue of using mathematical models and optimization to choose a mate, in the following lecture, the prominent psychologist Gerd Gigerenzer says that he has asked several economists if they used expected utility theory to optimize their choice of a mate. He’s only found one, and that marriage ended in divorce.

http://fora.tv/2008/02/08/Intelligence_of_the_Unconscious#fullprogram

The segment I’m talking about starts after the first 12 minutes 10 seconds of the video.

eeging said this on March 28, 2011 at 5:36 am |

Maybe you can simulate a scenario which allows you to go back to earlier samples and see how that changes the results. Mathematicians probably already worked it out but it’s still interesting as an experiment.

hhyu said this on April 2, 2011 at 11:06 am |