Q. 193 Explain "Optimal Stopping Problem" and its impact on business problem solving with suitable examples. Also explain what is the best approach to address this problem. 

 

Note for website visitors - Two questions are asked every week on this platform. One on Tuesday and the other on Friday.

• All questions so far can be seen here - https://www.benchmarksixsigma.com/forum/lean-six-sigma-business-excellence-questions/
• Please visit the forum home page at https://www.benchmarksixsigma.com/forum/ to respond to the latest question open till the next Tuesday/ Friday evening 5 PM as per Indian Standard Time.  
• The best answer is always shown at the top among responses and the author finds honorable mention in our Business Excellence dictionary at https://www.benchmarksixsigma.com/forum/business-excellence-dictionary-glossary/ along with the related term.

 

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.

On 9/10/2019 at 4:48 PM, Vishwadeep Khatri said:

and its impact on business problem solving with suitable examples. Also explain what is

Life is full of choices. One has to rationally balance alternatives, assess uncertain outcomes, gather additional information and - when ready - pick the best action.

 

Optimal stopping problem can be best described as the number of samples to be looked / verified before taking a judgement on the best.

 

optimal stopping or early stopping is concerned with the time taken to perform a action or take a decision in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems are solved using dynamic programming many times and written as Bellman equation.

 

Optimal stopping problem can be best described as the number of samples to be looked / verified before taking a judgement on the best.

 

For example – If we have N number of candidates to be interviewed for a position the optimal stopping theory will help us to identify the best candidate without interviewing all the candidates.

Optimal stopping can be best explained by the 37% rule According to 37% rule when we need to take a decision based on screening the available choices in limited time, the best time to take the decision is after screening 37% of the choices.

 

Rule 37% is best explained by Brian Christian “Be prepared to immediately commit to the first thing you see that’s better than what you saw in the first 37.

 

Optimal stopping theory will also help us in taking business decision during uncertainty with multiple constraints.

Optimal Stopping problems are also known as "Look and Leap" problems as it helps us in understanding the point till which we should keep looking for options and then be ready to leap the best option

Congratulations to both Natwar and Jayaram for giving perfect response for this question. Winner among the two is Natwar based on his introductory assumptions that are better explained clarifying the context.