Leaderboard

Imagine you got to choose a solution from a list of probable solutions with the following conditions 1. all solutions will be evaluated one after the other 2. a solution if evaluated and rejected cannot be selected again 3. each solution has a different reward or benefit associated with it which you are unaware of. You will be aware of the rewards for only those solutions that have been evaluated 4. probable solutions are in no particular order 5. If you reject all solutions, by default the last solution will be selected even though it may no give you the best result In such a scenario, the biggest challenge is to determine where to stop? Ideally you want the maximum reward or the best solution. However, you do not know if it is still to be evaluated or whether you have already rejecting it assuming that there is a better solution yet to be evaluated. Optimal Stopping Problem provides a solution in such situations. It says that if you have to choose from 'n' solutions, always reject the first 'n/e' (where e = 2.71) solutions. Let us call this number as 'x'. Then select the next solution which is better than the 'x' solutions already evaluated. Working with this rule, you will select the best solution in about 37% of the cases (which as per Wikipedia is a very good success rate - i have not gone into the validation part of it yet). 'x' is basically a sample that is drawn from the population 'n'. And 'n/e' ensures that we have a sufficient sample size to consider. E.g. picked from the classic 'Secretary Problem' associated with Optimal Stopping Problem (source: Wikipedia) You have 100 applicants for the position of Secretary. All the above rules (points 1 through 5) apply here and you have to select the best candidate. As per the Optimal Stopping Problem, one should reject the first 100/2.71 ~ 37 candidates and then select the next candidate who is the best fit from among the candidates interviewed so far. P.S. This will ideally not happen as the interviewer will always have the option to go back to any candidate. I do not have examples of any practical application of this this concept is new to me. Hoping someone shares practical examples here.