The Secretary Problem

How can a manager select the best person as secretary out of 100 candidates lined up for interview? How likely is it that the person he selects will be the best out of the 100 who have appeared?

This problem is known as the Secretary Problem and involves optimal stopping theory. Optimal Stopping Theory deals with the time required to take a particular action and maximize an expected reward.

This post is largely based on an article written by Prof. Arnab Chakraborthy when he was a student at the Indian Statistical Institute back in 1996

What Exactly Is The Problem?

Supposing the Manager of a company wants to select a secretary and he/she needs to select one candidate on the basis of an interview. Assume, the following restrictions are in place:

• The candidates do not all come on the same day. They come in different days for the interview
• The candidates have to be told of their result right away once the interview is over: Whether they have been offered the position or rejected
• Once a candidate has been offered the position, the remaining candidates will not be interviewed and hence, need not come for the interview
• After each interview, the manager gives each candidate a score

Naturally, the manage would like to select the candidate with the highest score. But, how does the manager know before hand, which one out of all the candidates lined up is the best? If he has already interviewed 50% of the candidates, how will the manager know if some candidate out of the remaining 50% will not be better than the ones interviewed already?

Though the above restrictions might not seem realistic, there are a few real life instances where these restrictions hold. One such instance is the Indian method of finding an alliance. The alliances are considered one by one and are evaluated on the basis of a number of conditions and at the end, either accepted or rejected. Rightly so, the Secretary problem is also known as the marriage problem.

Is it possible to select the right person to marry? Though nobody can give a 100% correct answer, mathematics can give you a method to find out the best possible person to marry. How? Read on to find out

Making It Simpler

Let us convert it into a simpler form to understand it better. But this will need 2 people to play.

Start by writing 10 distinct numbers on identical pieces of paper, fold them and mix them well. Your friend, who will be playing the role of the manager, randomly picks up one piece and sees the number written in it

If your friend “accepts”, the game ends here. Else, he/she throws it away and selects another paper randomly from the remaining and the game continues. If your friend reaches the last paper, he/she has no choice but to accept it and the game ends

Your friend(manager) wins the game if the number he/she accepted is the maximum of the lot.

Repeat the above many times, with different sets of numbers (obviously) and find out how many times the manager wins

We see that the objective here is to find a strategy with the highest probability of choosing the most suitable person

After this point, there is a fair amount of mathematics and probability involved which I do not want to get into since it might be difficult to understand. Those interested can refer to the original article by Prof. Arnab Chakraborthy or refer to the other links in the references to know the math behind the secretary problem

So, Whom To Marry?

After doing all the math, it was found out that the optimal stopping point is 1/e, where e is the exponential constant = 2.71828 approximately. Hence, 1/e turns out to be 0.3678 or 36.78%

Simply put, this means: Suppose you are the MD of a company and 100 candidates have appeared to interview for the post of secretary in your company. All that you have to do is, Compute 100*(1/e) which turns out to be 36.79 or 37, when rounded off. Interview the first 37 candidates, evaluate them and not offer them the job. Then on, select the candidate whose score exceed all the previous ones

A Disclaimer

This process does not guarantee the best candidate always. All it conveys is that, by doing this process, you have a 36.79% chance of choosing the best candidate. Though you might feel this is too low a probability, this is the best we can do as of now

The same concept can be applied while you are looking for your better half with whom you are going to spend the rest of your life. Whether you do get the best or not, that is a gamble. It might not always be successful which Prof. Michael Trick, a professor at CMU found out the hard way.

Michael Trick, a professor of operations at Carnegie Mellon University has written in his blog about how he applied the above rule in finding his life partner, only to end up being rejected by her. Quite an interesting story. You can read it in detail here: Finding Love Optimally

Thanks for reading!!

References

1. Article written by Prof. Arnab Chakraborthy, ISI when he was a student at ISI back in 1996: The Secretary Problem — Optimal Stopping

2. A post in Medium: Math-Based Decision Making: The Secretary Problem

Originally published at http://infinitesimallysmallcom.wordpress.com on January 15, 2021.