Optimal Dynamic Policies for the Multisecretary Problem with Many Candidates

The multi-secretary problem involves sequentially accepting at most K candidates from a pool of N applicants to maximize expected total value. Recent advances have established that constant or logarithmic regret is achievable under a linear scaling regime, where the number of positions grows linearly with the candidate pool, using policies that rely on the ratio of remaining positions to candidates. We depart from this framework to analyze the many-candidates regime, where the number of positions remains fixed as the pool of candidates grows indefinitely. This asymptotic setting offers a more faithful model for high-stakes selection environments, such as elite hiring, venture capital, or competitive admissions, where the goal is to identify rare outliers rather than to regulate a selection rate. We provide a complete characterization of the optimal dynamic policy and the associated value function in this regime, demonstrating that the optimal strategy deviates from the standard ratio-based structure by replacing the raw number of remaining candidates with an effective number of remaining candidates explicitly governed by the distribution's tail behavior. Using Extreme Value Theory, we prove that this effective count is strictly greater than the true number for short-tailed distributions (Weibull Domain), equal to the true number for light-tailed distributions (Gumbel Domain), and strictly less than the true number for heavy-tailed distributions (Frechet Domain). We further derive asymptotically optimal dynamic threshold policies that achieve o(1) for an appropriately scaled regret relative to the optimal value function. These results demonstrate that unlike the proportional regime, maximizing value in large markets requires calibrating to this effective candidate scale rather than relying on the ratio of remaining positions to candidates.