Secretary Problem
A classic problem in online decision-making that requires selecting the best candidate without knowledge of future candidates. The optimal strategy is to observe for an initial period, then select the first candidate better than all previously seen candidates.
Timeline (last 90 days)
In the secretary problem, candidates appear one by one, the decision-maker only knows the current candidate's rank relative to the candidates already seen and does not know the situation of future candidates, and the goal is to maximize the probability of selecting the best candidate.
The optimal strategy for the secretary problem is: first wait for a period (probationary period) without hiring anyone, and afterwards, as soon as a candidate better than all previous ones appears, select that candidate immediately.
Under the assumption that the input order is uniformly random, the competitive ratio of the classic strategy for the secretary problem (first rejecting the first n/e candidates, then selecting the first applicant better than all previous candidates) is approximately 1/e≈0.368, that is, the best candidate can be selected with a probability of at least 37%, and this ratio is optimal.
The simplified strategy for the secretary problem reminds us: in an uncertain environment, setting an observation period and then decisively choosing an option better than the past may be a reasonable heuristic.
The optimal strategy for the secretary problem is to wait through an observation period without deciding, then choose the first candidate better than everyone before.
All Facts (5)
In the secretary problem, candidates appear one by one, the decision-maker only knows the current candidate's rank relative to the candidates already seen and does not know the situation of future candidates, and the goal is to maximize the probability of selecting the best candidate.
50%UnverifiedThe optimal strategy for the secretary problem is: first wait for a period (probationary period) without hiring anyone, and afterwards, as soon as a candidate better than all previous ones appears, select that candidate immediately.
50%UnverifiedUnder the assumption that the input order is uniformly random, the competitive ratio of the classic strategy for the secretary problem (first rejecting the first n/e candidates, then selecting the first applicant better than all previous candidates) is approximately 1/e≈0.368, that is, the best candidate can be selected with a probability of at least 37%, and this ratio is optimal.
50%UnverifiedThe simplified strategy for the secretary problem reminds us: in an uncertain environment, setting an observation period and then decisively choosing an option better than the past may be a reasonable heuristic.
50%UnverifiedThe optimal strategy for the secretary problem is to wait through an observation period without deciding, then choose the first candidate better than everyone before.
50%