Secretary Problem - Heuristic Performance

Heuristic Performance

The remainder of the article deals again with the secretary problem for a known number of applicants.

Stein, Seale & Rapoport 2003 derived the expected success probabilities for several psychologically plausible heuristics that might be employed in the secretary problem. The heuristics they examined were:

• The cutoff rule (CR): Do not accept any of the first y applicants; thereafter, select the first encountered candidate (i.e., an applicant with relative rank 1). This rule has as a special case the optimal policy for the classical secretary problem for which y = r.
• Candidate count rule (CCR): Select the y encountered candidate. Note, that this rule does not necessarily skip any applicants; it only considers how many candidates have been observed, not how deep the decision maker is in the applicant sequence.
• Successive non-candidate rule (SNCR): Select the first encountered candidate after observing y non-candidates (i.e., applicants with relative rank > 1).

Note that each heuristic has a single parameter y. The figure (shown on right) displays the expected success probabilities for each heuristic as a function of y for problems with n = 80.