Secretary Problem Gets a Reselection Twist: 1/e Strategy Still Wins

A new paper by Dillon Hanson, Brant Jones, and Hyejin Kim (arXiv:2607.27033) revisits the famous 'best choice' problem, also known as the secretary problem, where an interviewer must pick the best candidate from a randomly ordered sequence seen one at a time. The authors introduce a 'reselection' variant: candidates are filtered over time (e.g., applicants drop out or are pre-screened), creating a dynamic pool. They leverage Steck's distribution from the 1970s—a probability distribution on permutations tied to bottom-to-top maxima (left-to-right maxima of the inverse permutation)—to model this process.

The key finding: under optimal play with a single filtering step, the probability of selecting the best candidate still approaches 1/e asymptotically, matching the classic result. However, the optimal strategy is not a simple position-based rule (e.g., reject the first 1/e then pick the next best). Instead, the interviewer must consider the relationship between the current interview position and the next bottom-to-top maximum value after the filter. The optimal rejection-to-acceptance transition region lies between positions (1/e) and (1/e)+(1-1/e)y, where y is the fraction of unfiltered candidates. This work provides new combinatorial formulas for Steck's distribution and connects to earlier results by Pitman and Stanley.