In the standard Secretary Problem, the goal is to hire the best secretary from a list of candidates. I've recently witnessed a failed hiring attempt for a needed position and it inspired a similar game:

The goal is to maximize the net score. Each candidate has a value that (if hired) would be added to the score. And each day that goes by without hiring a candidate costs the company 1 point of score. Starting score is 0.

Each day, the company either interviews a new candidate or attempts to hire a previously interviewed candidate. The value of the candidate is discovered during the interview and is uniformly distributed between $0$ and (known) $v$. There is an unlimited number of possible candidates to interview.

If the job is offered to a candidate, then the candidate will accept with a probability of $d^k$ for (known) constant $d$ and $k$ being the number of days since the candidate was interviewed. You may only attempt to hire a candidate once.

So the question is: what is the best strategy for this game given $v$ and $d$? Other natural questions: what is the best strategy if $v$ and/or $d$ are unknown?

Any insights, answers, or references to similar games would be appreciated.


Let's assume the first strategy is the best until someone comes up with a better one, ok?

So we set a threshold for value (between 0 and v). If the value of the candidate is higher than the threshold, try to hire that candidate. Otherwise, interview the next candidate. If we interview several candidates in a row whose value is below the threshold, decrease the threshold until future candidates are likely to have a higher value. If d is low and the candidates decline offers, lower the threshold further.

A few points to determine: the first threshold for value. It's probably ok to wait a few days and just interview candidates so we can see what kind of values they have. Then set a threshold so that 50% (or 20% or 80% or whatever%) of the candidates have higher values.

Another point to determine: when we fail to hire a secretary, how frequently and how much should we lower the threshold.

If v is unknown, we obviously have to observe a few values before making good guesses for a good threshold.

If d is unknown, we'll have to try to hire a few candidates before tuning the algorithm.

What was not mentioned in the question:

  1. How long does it take for the candidate to accept or decline the job offer?
  2. Is the game over when the first candidate accepts the offer?
  3. Can you play the game n times?

If you can't choose the candidates for the interview it seems like winning this game is a matter of coincidence but I might be wrong.

  • 1
    $\begingroup$ Thanks for your answer, Miro. To answer your questions: 1. one day 2. yes 3. no The goal is to get the highest score possible. Note, if $v$ is very small, then the best solution is to hire the first person who will take the job. If $v$ is very high (and $d$ "reasonable), then it is beneficial to wait until a good candidate comes along and try to hire them. $\endgroup$
    – bbejot
    Sep 11 '14 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.