2
$\begingroup$

There was a problem I have read more than 15 years ago. I just remember the problem and the rough outline of the solution, and I would like to know if it has a canonical name to look up the calculation and variations.

The problem is that you will receive a 100 offers in sequence, you can only accept or reject in order, and once you have rejected an offer, you cannot go back. What is your strategy to maximize your gains? This might also be a problem-family, and I might not remember a couple of assumptions, if they turn out to be necessary.

And the solution was roughly...

If you have N offers, you wait until some constant (some function of e maybe?) times square root N, then you accept the first offer that is larger than or equal to the maximum of the first batch.

$\endgroup$
2
  • 1
    $\begingroup$ It's "how to choose a wife" problem ;) $\endgroup$ Commented Jul 16, 2022 at 10:43
  • $\begingroup$ @DmitryKamenetsky That was it, thank you as well! $\endgroup$ Commented Jul 17, 2022 at 10:18

1 Answer 1

5
$\begingroup$

This is called the secretary problem.

The basic form of the problem is the following: imagine an administrator who wants to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator gains information sufficient to rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant. If the decision can be deferred to the end, this can be solved by the simple maximum selection algorithm of tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision must be made immediately.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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