Optimal Stopping Algorithm

There is a project you have to start in a month. You will hire a team leader and you have to select the best one with the features you are looking for from among 500 applicants.

You found a new job in another city, so you have to move to the city in a month. Your aim is to find the best house that should be near your office, affordable, new, and secure.

You are going to the pub newly opened. It is so popular and there is a parking problem. The weather is cold and you hate valet parking like me. You should find a good place near the pub. Do you park immediately as soon as you find a free space or feel lucky for the best place and ignore some places at first?

You have the luck of the devil and met 5 girls from Tinder last night. You arranged a face-to-face appointment with them in 2 weeks. How can you select the best (sexy) one? :)

I can increase these examples. We race against time in all of these problems. Although we want to evaluate all options, our resources are not unlimited. we need to stop somewhere and make our decision. Where will we stop? We are looking for where we should stop the investigation. Those difficulties are called “optimal stopping” problems. The main point in an optimal stopping problem is not which of the options to choose, but how many to consider. The solution to the problem is an approach that gives us the answer to the question of whether I should wait a little longer when buying a car or house, in the fields of economy, statistics, and finance. If we give real-life examples, in summary, it is an approach that aims to stop at the best time and make the most efficient decision.

The most famous of these problems is known as the secretary problem. For this reason, the name of the algorithm is also referred to as the “secretary problem”. Ferguson (1989) has an extensive bibliography and points out that a similar (but different) problem had been considered by Arthur Cayley in 1875 and even by Johannes Kepler long before that.

Now time to inspect the algorithm; Suppose we manage interviews with applicants in an advertisement for the secretarial staff. There are two errors that can be committed. One is to leave the research early and another is to end the search late to find a better candidate. The more candidates we come across, the less likely we are to find the best candidate for the secretary we are looking for. If it is taken hastily, there is a possibility that we will never meet the best, and if the decision is made too late, maybe they have waited in vain for the better that was never there and there is a possibility of losing the previous ones. If there is only one candidate, the probability of this candidate being the best is 100%. If there is a second candidate, his / her probability of being the best is 50%, the fifth candidate’s 20%, and the hundredth candidate’s 1%. Therefore, there may be a possibility of interviews a better candidate in the next interview, but this possibility will gradually decrease.

Let’s examine the recruitment process step by step. If we have 2 applicants, can select first or ignore and select the second applicant. In both cases, our probability of choosing the best candidate is 50%. If we have three candidates, we have a 33% chance of picking the best candidate by random selection. If we ignore the last 2 applicants and select the first applicant, the probability is %33, if we ignore the first 2 applicants, select the last applicant, the probability is %33. But you can increase your chance by the algorithm like that:

1. Evoulate first applicant
2. Evoulate second applicant
3. If the second applicant is better than the first, select the second one
4. if the second applicant is NOT better than the first, select the third one

Now your probability of selecting the best candidate is %50. It is recommended that we start the selection process after the second candidate when the number of candidates is four, and after the third candidate when it is five. It is no coincidence these numbers. In fact, as the number of candidates increases, the probability tends to be stable.

This algorithm says:

• Evaluate at 37% of candidates without selecting any
• Choose the best candidate you have seen so far after exceeding 37% of the total candidates

Here, there is an important challenge selecting %37 candidates from between all candidates. At first, we must set some rules to eliminates candidates. For example; experience, education, knowing languages, etc… We can create qualification lists and select the top of the list for a group of 37%. Optimal stopping can be found in areas of statistics, economics, and finance. It has also been explored within fields like experimental psychology in order to simulate and understand real-world decision-making. I am even trying to use it over some of my basic behaviors in my life to make an easy decision. For example; I am an indecisive person. Especially, while buying simple electronic devices. Last month, I decided to buy a Bluetooth device but there are lots of brands and types of devices. At first, I created a list (17 items) of proper devices by my expectations. The list was highly crowded, so I sorted the list depends on buyer scores in a well-known e-commerce site. At last, I created my group of 37% (17 / 2.71 =~ 6 items) and decided on one from this group. :)

Optimal stopping is also a software algorithm but more of a real-life algorithm. There are many such patterns that real life and software algorithms are intertwined. See you in another pattern.