Secretary Problem with 2 positions - Maximizing the difference

Question

Synopsis

Imagine the secretary problem, except the goal is to hire two secretaries with the greatest possible difference between the two.

The Problem

I'm not particularly comfortable with this type of math so below are the modified constraints. The original constraints are from Wikipedia's page on the secretary problem.

• There are 2 positions to fill
• There are n applicants for the positions any applicant may fill any position, and the value of n is known.
• NOTE: It is fine to put one person in both positions, but wouldn't be the optimal solution unless n = 1.
• The applicants, if seen altogether, can be ranked from best to worst unambiguously.
• The applicants are interviewed sequentially in random order, with each order being equally likely.
• Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable.
• The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
• The objective of the general solution is to have the highest probability of selecting a pair with the greatest difference read (The best and the worst). This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant/worst applicant pair and zero otherwise.

For Context

I realized that at work that many of the problems I'm working on at the moment are normally treated as a single optimization problem. However in reality they are pair values, and since the goal is often to maximize the distance between choosing two values over a given number of days it seems to be very close to the secretary problem. I'm not comfortable enough yet with the math to solve this myself. My intuition is that this problem is equal to having two instances of the stopping problem however I'm not sure if this is mathematically equal.

Research

I've found papers on the Secretary Problem for TradeOffs, IE. The secretary's are evaluated on two rankings, and Random Walk, IE. dependent variables, while trying to answer this question. I have not managed to find anything directly related to this variant of the problem.

Answers

Thank you for reading my problem. Any insight into solving this problem is appreciated!

Answer 1

One trivial algorithm for the problem is exactly the same as the usual algorithm: observe $n/e$ of the applicants, then pick the first (if any) secretaries who are better than, or worse than, all applicants seen so far. This succeeds with probability roughly $1/e^2$. Answers to a question on math.se which includes your question claim that this algorithm (which is proposed in the answers) is obviously optimal.

To see that the success probability is roughly $1/e^2$, we follow the analysis in Wikipedia. We will analyze a more general algorithm, in which $n/e$ is replaced by $pn$, and then will show that the best choice for $p$ is roughly $1/e$. Let $q_{ij}$ be the success probability given that the $i$th secretary is the best one and the $j$th secretary is the worst one. If $i,j > pn$ then $q_{ij}$ is the probability that:

• $i$ is the best secretary.
• $j$ is the worst secretary.
• Among the first $i-1$ secretaries, the best is one of the first $pn$.
• Among the first $j-1$ secretaries, the worst is one of the first $pn$.

Calculation shows that $$ q_{ij} = \begin{cases} \frac{pn(pn-1)}{n(n-1)(i-1)(j-2)} & i < j, \\ \frac{pn(pn-1)}{n(n-1)(i-2)(j-1)} & i > j. \end{cases} $$ The overall success probability is thus at least $$ \sum_{i=pn+1}^n \sum_{\substack{j=pn+1\\j \neq i}}^n \frac{pn(pn-1)}{n(n-1)(i-1)(j-1)} \approx p^2 \left(\int_{pn}^n \frac{dx}{x}\right)^2 = \left(p\log\frac{1}{p}\right)^2. $$ This is just the square of the usual formula, so it is maximized at $p = 1/e$, for which the success probability is roughly $1/e^2$.