Jump to content
  • 0

When to stop looking for solutions


Go to solution Solved by Natwar Lal,

When to stop looking for solutions

 

Optimal Stopping Problem deals with selecting a time to take a particular action or finalizing a solution in such a way that the reward is maximized or the cost is minimized. This selection has to be from a random set of variables each associated with a particular reward of cost. These variables are reviewed sequentially (one after the other) and one may choose to stop at a particular variable (get the associated reward), else can review all variables. If all variables are observed, you will have to choose the last variable as one is not allowed to go back and choose a different variable

 

An application-oriented question on the topic along with responses can be seen below. The best answer was provided by Natwar Lal  on 13th September 2019.

 

Applause for the respondents- Natwar Lal & Jayaram T

Question

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.

 

Link to post
Share on other sites

3 answers to this question

Recommended Posts

  • 0
  • Solution

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.

Link to post
Share on other sites
  • 0
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

Link to post
Share on other sites
Guest
This topic is now closed to further replies.
  • Who's Online (See full list)

    There are no registered users currently online

  • Forum Statistics

    • Total Topics
      2,855
    • Total Posts
      14,452
  • Member Statistics

    • Total Members
      55,018
    • Most Online
      888

    Newest Member
    Rosalin
    Joined
×
×
  • Create New...