Published on Feb 11, 2016

The objective: My project deals with an idealized but still realistic situation described as follows. A finite number of offers arrive one at a time. If an offer is accepted, the search ends. All rejected offers vanish. The amount of offers is known.

The offers are characterized by a numeric value (e.g. price), but the range of this value is unknown. The goal of my project is to find an efficient strategy for making a good choice in such a situation and to estimate the chances of getting the top offer with the help of this strategy.

I reasoned that a good strategy is to skip the first few offers and then to choose the first offer which beats all that were skipped. To find how many offers should be skipped, I used both theoretical and experimental methods.

In the theoretical part, I computed the probability of selecting the best of N offers after skipping S offers. I found a formula, evaluated it for different N and S, and, analyzing the obtained tables and graphs, found the best amount of offers to skip. In the experimental part, I verified the prediction by simulating a big number of searches.

To imitate each search, I generated N random numbers (I used N=10 and N=50) which were considered as offers, and "ran" several searches skipping different amounts of offers. For reliability, every experiment was repeated 100 times with different random numbers.

The best strategy is to skip about 37% of the total amount of offers and then pick the first offer which beats all of the skipped offers. Amazingly, this recipe gives about 37% chances of getting the top offer, and this predicted rate of success does not decrease when the number of offers increases.

My project shows that knowledge and reasonable patience without overcautiousness secures about 37% of success in the search with no additional information about the options. This method may be used in a different situation as well.

For example, if you have to make a choice before a deadline, be patient and spend 37% of the available time plainly "observing" the situation.

This Mathematical project is to choose the best from a given number of offers, is recommended to skip the first 37% of all the offers and then to pick up the first offer topping all its predecessors --- this strategy gives about 37% of success!

- Adaptive Interference Rejection in Wireless Networking
- A. I. Connect-Four
- Centripetally Accelerating Pi
- Chess Algorithms
- Chinese Checkers Strategy