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!