HW# The Hiring Problem Mathematically
The problem. Searching for a new hire and interviewing potential candidates. When is the
candidate good enough? What’s the stopping criteria?
Formalize an abstract problem. Let us consider each candidate as an integer, the integer
representing a ranking criterion. For example: nine candidates whose rank = {1,3,7,5,8,3,1,9,4}.
This problem would be trivial, just pick the element with maximum value, if it weren’t for two
properties.
There is no look-ahead. When I’m selecting any one candidate, you are unable to look
forward into the future and consider who you will select in the future. No crystal ball.
There is no undo. If you select a candidate and after a while decide to fire them in a
misguided attempt to find someone better, there’s a good chance this person will be
unavailable in the future gone working for a competitor.
We can think of it visually as a machine which is fed a tape of integers. It has two actions:
it can either stop; or
it can consider the next integer.
The machine’s objective is to stop on the highest integer.
Real world problem. At the heart of the hiring problem is conflict. Do I reject the current
possibility in hopes of landing something better if I keep looking, or do I stick with what I have?
Can be applied to almost anything a selection choice decision is required. Take it or leave it?
Solving the hiring problem analytically.
Random selection. Choose the 7th element in the list. No reason just 7th element in the list.
The probability, then, of picking the best element from an integer sequence of length N with
this random pick rule is (1 divided by N).
To improve on this random selection strategy, search for a while, gain some insight, determine
your options, and then choose the next best element that presents itself.
In terms of the hiring problem, such a strategy would be to scan through the first r integers and
then choose the first option that is greater than any of the integers in [1,r].
How does this new strategy compare to random selection? The above image is a prop to help
understand the discussion that follows. Assume that i, is the greatest integer, occurs at n+1.
In order for this strategy to return the maximum integer, two conditions must hold:
- The maximum integer cannot be contained in [1,r]. Our strategy is to scan
through [1,r], so if the solution is in [1,r], we necessarily lose. This can also be
stated as n≥r. - Our strategy is going to select the first integer, i, in [r,N] that’s greater
than max([1,r]) Given this, there cannot be any integers greater than i that come
after i, otherwise the strategy will lose. Alternatively put, the
condition max([1,r])==max([1,n]) must be true.
Thus, to calculate the effectiveness of our strategy, we need to know the probability that both
of these will hold. For some given n, this is: (r divided by n) multiplied by (1 divided by N).
(1 divided by N) is the probability that i occurs at n+1 (remember, this is the probability
for some n, not the n), while (r divided by n) is a consequence of the second condition, the
probability that the condition max([1,r])==max([1,n]) is true.
To calculate the probability for some r, P®, not for arbitrary n, but for everything, we need
to sum over n≥r:
This is a Riemann1
approximation of an integral so we can rewrite it. By letting
Now, we can find the optimal r by solving for P′®=0.
By plugging roptimal back into P® we will find the probability of success.
What The Math Says
Well, the optimal solution is for us to estimate how many people we believe we might
reasonably interview in the future, say 20. We plug this into the equation (N divided by e),
where N=20, (20 divided by e) ≈7.
This result says that, if we want to maximize our probability of ending up with the best possible
candite, we should interview 7 candidates and then, choose the next candidate who is better
than all of those candidates.
1 Gary L. Miller. Riemann’s hypothesis and tests for primality. Journal of Computer and System Sciences, 13(3):300–317, 1976.
However, the typical hiring problem maximizes the chances of landing the best candidate and
considers all other outcomes equally bad. Most on the choosers are not thinking this way, they
want to maximize the probability that they end up with a pretty good candidate. It is not all or
nothing.
Maximizing the Probability of a Good Outcome
Fear not, there’s a modification of the hiring problem that maximizes the probability of finding
a high-value candidate. Suffice it to say, the strategy is the same except we use a cutoff of √N
rather than (N divided by e).
What Sort of Optimal?
At the end of the day, the secretary problem is a mathematical abstraction and fails to take into
account much of complexity of, you know, reality.
The solution to the secretary problem suggests that the optimal hiring strategy is to estimate
the maximum number of people you are willing to interview, N, and then
interview √N people and hire the next person who is better than all of those. In laboratory
experiments, people often stop searching too soon when solving searching problems. This
suggests that the average person doesn’t search enough candidates prior to choosing.
At the end of the day, the hiring problem is a mathematical abstraction and there is more to
finding the “right” candidate than interviewing a certain number of people.
Question: Who would you choose? Quantity thirty elements. Each with a ranking criterion.
3 8 3 9 2 3 8 5 1 4 2 7 9 2 4 4 9 7 1 0 1 7 4 2 1 8 1 9 5 1