Progressive stopping heuristics that excel in individual and competitive sequential search

We study the performance of heuristics relative to the performance of optimal solutions in the rich domain of sequential search, where the decision to stop the search depends only on the applicant's relative rank. Considering multiple variants of the secretary problem, that vary from one another in their formulation and method of solution, we find that descriptive heuristics perform well only when the optimal solution prescribes a single threshold value. We show that a computational heuristic originally proposed as an approximate solution to a single variant of the secretary problem performs equally well in many other variants where the optimal solution prescribes multiple threshold values that gradually relax the criterion for stopping the search. Finally, we propose a new heuristic with near optimal performance in a competitive or strategic variant of the secretary problem with multiple employers competing with one another to hire job applicants. Both heuristics share a simple computational component: the ratio of the number of interviewed applicants to the number of those remaining to be searched. We present the subgame-perfect Nash equilibrium for this competitive variant and an algorithm for its computation.