Secretary problem with competition

A firm interviews applicants one at a time and must hire on the spot or lose them. The classical secretary problem asks how to maximise the chance of hiring the very best. Its answer is famous: watch about the first $37\%$, hire nobody, then take the next applicant who beats everyone seen so far. This note asks what changes when a second firm is chasing the same people and every applicant would rather work for the first.

The classical problem

$n$ applicants are interviewed one by one in a uniformly random order. The firm observes only relative ranks: after each interview it can rank the applicants seen so far by desirability, but it never learns their absolute ranks. It must then accept the current applicant — ending the search — or reject him and move on. A rejected applicant cannot be recalled. The aim is to maximise the probability of hiring the best of the $n$.

An optimal rule has a simple shape. Fix an integer $k \ge 0$: reject the first $k$ applicants, then accept the first later applicant who is better than all before him — the first record after $k$. Call this the $k$-strategy.

Let $B_k$ be the event that the $k$-strategy selects the best applicant, and let $X$ be the position of the best applicant, so $\Pr(X=i)=1/n$. If the best arrives at position $i>k$, the strategy catches him exactly when the best of the first $i-1$ applicants fell in the first $k$ — probability $k/(i-1)$. Hence

$$\begin{aligned} \Pr(B_k) &= \sum_{i=1}^{n}\Pr(B_k \mid X=i)\Pr(X=i) = \frac{1}{n}\sum_{i=k+1}^{n}\frac{k}{i-1} \\ &\approx \frac{k}{n}\int_{k}^{n}\frac{1}{i}\,di = \frac{k}{n}\log\!\left(\frac{n}{k}\right). \end{aligned}$$

Maximising over $k$ gives $k^{*}=n/e$ for large $n$: reject about $37\%$ and take the next record. The probability of success is also about $1/e \approx 37\%$.

Two firms, one ranking

Now two firms, $1$ and $2$, each have one post to fill from the same $n$ applicants. Every applicant strictly prefers firm $1$, and this is common knowledge. Applicants arrive in a uniformly random order; each is interviewed by both firms at once — both observe the same relative ranks, neither the absolute — and the firms decide simultaneously whether to make an offer. An applicant holding both offers joins firm $1$; an applicant with one offer takes it. A firm keeps interviewing until it hires someone or the applicants run out, with no recall. Each firm’s payoff is the probability that it hires the best applicant, and we use Nash equilibrium as the solution concept.

Firm $1\text{'}$s problem is unaffected by firm $2$: any applicant holding both offers chooses firm $1$, so firm $1$ faces exactly the single-firm problem, and its dominant strategy is the $k$-strategy with cutoff $k_1=n/e$. Because firm $2$ observes the same arrivals and the same relative ranks as firm $1$, and firm $1\text{'}$s strategy is fixed and known, firm $2$ can anticipate firm $1\text{'}$s decisions exactly. Taking those decisions as given, firm $2$ faces an ordinary optimal-stopping problem, whose solution is again a $k$-strategy.

Claim. Given that firm $1$ plays its optimal strategy $k_1=n/e$, firm $2\text{'}$s best response is to reject approximately $n/e^{3/2}$ applicants and thereafter make an offer to the best applicant it has interviewed so far.

Firm 2’s best response

Let $k_i$ be the number of applicants firm $i$ rejects, so both firms play $k$-strategies. Let $B_{k_1,k_2}$ be the event that firm $2$ hires the best applicant, $X$ the position of the best applicant, and $Y$ the position of the applicant hired by firm $1$. Since $\Pr(X=i)=1/n$,

$$\Pr(B_{k_1,k_2}) = \sum_{i=1}^{n}\Pr(B_{k_1,k_2}\mid X=i)\Pr(X=i) = \frac{1}{n}\sum_{i=1}^{n}\Pr(B_{k_1,k_2}\mid X=i).$$

We evaluate the conditional probabilities in two cases.

Case (i): $k_2 \le k_1$. Condition on the best applicant arriving in position $i$. If $i \le k_2$, firm $2$ has already passed him, so the probability is $0$. If $k_2 < i \le k_1$, the best applicant arrives after firm $2\text{'}$s cutoff but no later than firm $1\text{'}$s, firm $2$ secures him exactly when the best of the first $i-1$ applicants is among firm $2\text{'}$s first $k_2$ rejects, i.e. $\Pr(B_{k_1,k_2}\mid X=i)=k_2/(i-1)$. If $i=k_1+1$, firm $1$ will hire him, so the probability is $0$. If $i \ge k_1+2$, firm $2$ hires the best applicant only if firm $1$ hires first, at some position $j$ with $k_1 < j < i$, so that

$$\Pr(B_{k_1,k_2}\mid X=i) = \sum_{j=k_1+1}^{i-1}\Pr\!\big(B_{k_1,k_2}\cap\{Y=j\}\mid X=i\big) = \sum_{j=k_1+1}^{i-1}\left(\frac{k_2}{j-1}\right)\!\left(\frac{1}{i-1}\right).$$

Hence

$$\Pr(B_{k_1,k_2}) = \frac{1}{n}\sum_{i=k_2+1}^{k_1}\frac{k_2}{i-1} + \frac{1}{n}\sum_{i=k_1+2}^{n}\left[\sum_{j=k_1+1}^{i-1} \left(\frac{k_2}{j-1}\right)\!\left(\frac{1}{i-1}\right)\right].$$

For large $n$, approximating the sums by integrals,

$$\begin{aligned} \Pr(B_{k_1,k_2}) &\approx \frac{1}{n}\int_{k_2}^{k_1}\frac{k_2}{i}\,di + \frac{1}{n}\int_{k_1}^{n}\int_{k_1}^{i} \left(\frac{1}{i}\right)\!\left(\frac{k_2}{j}\right)dj\,di \\ &= \frac{k_2}{n}\log\!\left(\frac{k_1}{k_2}\right) + \frac{k_2}{2n}\left(\log\!\left(\frac{n}{k_1}\right)\right)^{2}. \end{aligned}$$

Substitute $k_1 = n/e$, so $\log(n/k_1)=1$ and

$$\Pr(B_{k_1,k_2}) \approx \frac{k_2}{n}\log\!\left(\frac{k_1}{k_2}\right)+\frac{k_2}{2n}.$$

Differentiating with respect to $k_2$,

$$\frac{d}{dk_2}\Pr(B_{k_1,k_2}) = \frac{1}{n}\left[\log\!\left(\frac{k_1}{k_2}\right)-\frac12\right],$$

which vanishes at $\log(k_1/k_2)=\tfrac12$, i.e. $k_2 = k_1 e^{-1/2}=n/e^{3/2}$. The second derivative equals $-1/(n k_2)<0$, so this is a local maximum, and $n/e^{3/2}<n/e=k_1$, so it lies inside the region $k_2\le k_1$. The value there is

$$\Pr(B_{k_1,k_2})\Big|_{k_2=n/e^{3/2}} = \frac{1}{e^{3/2}}\cdot\frac12+\frac{1}{2e^{3/2}} = \frac{1}{e^{3/2}}\approx 0.223.$$

Case (ii): $k_2 > k_1$. Now firm $2\text{'}$s cutoff is later than firm $1\text{'}$s, so whenever firm $2$ is still active firm $1$ may already have hired. Conditioning on $X=i$, the probability is $0$ for $i\le k_2$, and for $i>k_2$,

$$\Pr(B_{k_1,k_2}\mid X=i) = \sum_{j=k_1+1}^{k_2}\left(\frac{k_1}{j-1}\right)\!\left(\frac{k_2}{i-1}\right)\!\left(\frac{1}{j}\right) + \sum_{j=k_2+1}^{i-1}\left(\frac{k_1}{j-1}\right)\!\left(\frac{1}{i-1}\right),$$

where the first sum covers firm $1$ hiring within firm $2\text{'}$s reject window $(k_1,k_2]$ and the second covers firm $1$ hiring after firm $2\text{'}$s cutoff. Hence

$$\Pr(B_{k_1,k_2}) = \frac{1}{n}\sum_{i=k_2+1}^{n}\left[ \sum_{j=k_1+1}^{k_2}\left(\frac{k_1}{j-1}\right)\!\left(\frac{k_2}{i-1}\right)\!\left(\frac{1}{j}\right) + \sum_{j=k_2+1}^{i-1}\left(\frac{k_1}{j-1}\right)\!\left(\frac{1}{i-1}\right)\right].$$

Approximating by integrals,

$$\begin{aligned} \Pr(B_{k_1,k_2}) &\approx \frac{1}{n}\int_{k_2}^{n}\left[ \int_{k_1}^{k_2}\left(\frac{k_1}{j}\right)\!\left(\frac{k_2}{i}\right)\!\left(\frac{1}{j}\right)dj + \int_{k_2}^{i}\left(\frac{k_1}{j}\right)\!\left(\frac{1}{i}\right)dj\right]di \\ &= \frac{k_2-k_1}{n}\log\!\left(\frac{n}{k_2}\right) + \frac{k_1}{2n}\left(\log\!\left(\frac{n}{k_2}\right)\right)^{2}. \end{aligned}$$

Differentiating and factoring,

$$\frac{d}{dk_2}\Pr(B_{k_1,k_2}) = \frac{1}{n}\left(1-\frac{k_1}{k_2}\right)\left(\log\!\left(\frac{n}{k_2}\right)-1\right).$$

For $k_2>k_1=n/e$ we have $1-k_1/k_2>0$ and $\log(n/k_2)<1$, so the derivative is negative. Thus $\Pr(B_{k_1,k_2})$ is strictly decreasing on $k_2>k_1$, and the best firm $2$ can do here is the boundary $k_2=k_1$, where the payoff equals $1/(2e)\approx 0.184$.

Comparing the two cases, the boundary value $1/(2e)$ is below the interior maximum $1/e^{3/2}$ from Case (i). Therefore the global optimum is

$$k_2^{*}=\frac{n}{e^{3/2}}\approx 0.223\,n,$$

so firm $2$ rejects about $23\%$ of the applicants — fewer than firm $1\text{'}$s $37\%$ — and then offers the position to the best applicant seen so far. Its probability of hiring the best applicant is $e^{-3/2}\approx 0.223$.

Success probability against reject fraction. Firm $1\text{'}$s classical curve peaks at $k/n=1/e$; firm $2\text{'}$s response peaks earlier and lower, at $k/n=e^{-3/2}$, given that firm $1$ has chosen its best cutoff.