An Efficient Strategy for Making a Choice from a Finite Stream of Offers

Overview

Objectives/Goals 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. Methods/Materials 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. Results 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. Conclusions/Discussion 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.

Awards (1)

• Category Award

Competition history

• CSEF 2005 Mathematics & Software · Entry J1205

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2005 project