18
$\begingroup$

In the classical secretary problem (also known as Marriage, Sultan's Dowry, Gogol problems),

1) There are $n$ candidates ordered from the best to the worst (no ties). We know $n$.

2) The candidates arrive sequentially in random order (uniform distribution).

3) We can only determine the relative ranks as they arrive (and can not know the absolute ranks).

4) We can either accept or reject a candidate. When a candidate is rejected she cannot be recalled.

We want to choose the very best candidate and have to find the optimal strategy and its probability of success.

There are a lot of extensions of this problem (for example: $n$ is not known, not uniform distribution for $k$ less than $n$, to select the $k$ best candidates, etc.). Mike gave us very useful information about an extension (to select the $2,4,k$ best) in his answer to the "Generalization of the Sultan's dowry problem".

In these 3 new extensions (with 1,2,3,4 as in the Classical Secretary problem) , we have to to find the optimal strategy and its probability of success if:

Problem 1: We want to choose the very best OR the worst (only one selection).

Problem 2: We want to choose the median candidate (only one selection).

Problem 3: We want to choose the very best AND the worst (two selections).

  • 6
    Problem 3 was solved by Clawfinger: http://www.lyrics007.com/Clawfinger%20Lyrics/The%20Best%20&%20The%20Worst%20Lyrics.html -- take "the last and the first".2011-04-16
  • 0
    Are there other variants of this problem using different payoff functions, for example, using the actual secretary value as the payoff, and then maximize the expected payoff? In this case, the standard "allow n/e secretaries to pass and then choose the best after" algorithm wouldn't be optimal, since the payoff is 0 if the best candidate was in the evaluation set. I'm particularly curious if the best algorithm would differ if the secretary distribution is not normal, for example, a power law.2017-04-17

2 Answers 2