# Secretary hiring game

This is an extension of the classical secretary problem.

In the hiring game you have a set of candidates $$\mathcal C=\{c_1,\ldots,c_N\}$$, and order on how skilled each worker is.

W.l.o.g, we assume that $$c_1$$ is the most skilled, followed by $$c_2$$, etc.

The order in which the candidates interview is picked uniformly at random and it is (obviously) unknown to the employers.

Now suppose you have a market with 2 potential employers. In every round, a new candidate is interviewing for both companies (call them $$A,B$$). During the interview, both $$A$$ and $$B$$ observe the partial ordering of all of the past candidates, including the current interviewee. The firms then (independently) decide whether to hire today's applicant.

Unfortunately for $$B$$, it can not compete financially with $$A$$'s offer, so if both extends an offer for a worker, $$A$$ gets preference.

Also, once a secretary signs, the company may not interview any further candidates and the competitor becomes aware of the signing.

The goal of each company is to hire the better skilled candidate (as opposed to the classic problem, where a single company wishes to find the best secretary), as it is known that the company with the better secretary should be able to take over the market.

What is the optimal strategy as the big firm ($$A$$)?

What about the smaller company ($$B$$)?

If both companies play their equilibrium strategies, what is the probability $$B$$ gets the better worker?

In a related work, Kalai et al. discusses the symmetric version of this problem, where both companies have the same power of attracting candidates.

In this setting, the simple (symmetric) equilibrium is that you hire a secretary iff the chance of she being better than the remaining candidates is at least 50%.

How does this result changes in our setting?

For company $A$/the firm/giant corporation/"big pharma"/"THE MAN", the strategy does not change from the symmetric version:

Consider a round where the probability of seeing only lesser candidates thereafter is $> .5$. If company $A$ keeps the candidate, then it has a chance of winning $> .5$. If $A$ does not keep the candidate, then company $B$ can hire the candidate and company $A$ has a chance of winning $< .5$. So, obviously, company $A$ would hire (and company $B$ would attempt to hire) in this situation.

For a candidate with winning odds of exactly $.5$, $A$ may or may not choose to hire, but $B$ would choose to hire because $B$ can never get odds better than $.5$.

If company $A$ hired before it saw a candidate with winning chance $>= .5$, then the odds of a better future candidate existing (and hence $B$ winning) would be $> .5$. So $A$ will not hire until it sees a candidate of winning odds $>= .5$.

Therefore, $A$'s strategy is identical to the symmetric case: hire the first candidate that yields winning odds of $> .5$.

$B$'s strategy, then, is formed with $A$'s strategy in mind. Obviously, if $A$ hires (at or) before $B$, then $B$'s strategy is to hire the next candidate that is better than $A$'s, if any. Also, if a candidate comes by with winning odds $> .5$, $B$ should try to hire, even though $A$ will also try to hire (and force $B$ to keep looking).

The only question left is: is it ever beneficial for $B$ to hire when the odds of winning is $<= .5$. The answer is: yes.

Intuitively, say there is a round where the odds of winning with the candidate is $.5 - \epsilon$. Also, there is "likely to be" (explained later) a future candidate with winning odds $> .5 + \epsilon$. Then it would benefit $B$ to choose the earlier candidate.

Let $d_r$ be the candidate interviewing in round $r$ for all $1 <= r <= N$.

Officially, $B$'s strategy is: "hire $d_r$ if doing so yields better odds of winning than if not". The following is how we calculate such a decision.

Let $p_{r,i}$ be the probability of winning after interviewing and hiring $d_r$ given $d_r$ is the $i$th best interviewed candidate. Then:

$p_{r,i} =$ probability that $d_s < d_r$ for $s > r$

$= (1-\frac{i}{r+1})(1-\frac{i}{r+2})\times ... \times (1-\frac{i}{N})$

...

$= \frac{(N-i)!r!}{(r-i)!N!}$

Notably, $p_{r,i}$ is easily computable to constant accuracy.

Let $P_{B,r}$ be the probability that $B$ wins given that neither company hired in rounds $1$ through $r-1$.

Then $B$ would hire $d_r$ if the probability of winning after hiring $d_r$ is better than $P_{B,r+1}$.

Note that $P_{B,N} = 0$, because if it is the last round, then $A$ is guaranteed to hire and $B$ will not hire anyone and loose.

Then, in round $N-1$, $B$ is guaranteed to try to hire and will succeed unless $A$ hires as well. So: $$P_{B,N-1} = \sum_{i=1}^{N-1}\frac{1}{N-1} \left\{ \begin{array}{lcl} p_{N-1,i} & : & p_{N-1,i} < .5 \\ 1-p_{N-1,i} & : & p_{N-1,i} >= .5 \end{array} \right.$$

Which leads to the recursive function:

$$P_{B,r} = \sum_{i=1}^{r}\frac{1}{r} \left\{ \begin{array}{lcl} 1-p_{r,i} & : & p_{r,i} >= .5 \\ p_{r,i} & : & P_{B,r+1} < p_{r,i} < .5 \\ P_{B,r+1} & : & \text{else} \end{array} \right.$$

It's pretty obvious that $P_{B,r}$ can be calculated to constant accuracy in polynomial time. The final question is: "what is the probability of $B$ winning?" The answer is $P_{B,1}$ and varies with $N$.

As to the question of how often does $B$ win? I have not calculated exactly, but looking at $N$ from 1 to 100, it appears that as $N$ grows, that $B$'s winning rate approaches .4 or so. This result may be off as I just did a quick python script to check and did not pay close attention to rounding errors with floating numbers. It may very well end up that the real hard limit is .5.