Asymptotic Rounding Laws for Optimal Thresholds in Secretary Problems

Abstract

We study second-order asymptotics for optimal thresholds in secretary-type problems. Under a unimodality assumption and a local affine expansion of the discrete payoff increments, we establish a general principle showing that sufficiently accurate rational approximations to the leading threshold proportion yield exact optimal integer thresholds. Continued-fraction convergents provide an immediate application. We also derive an asymptotic rounding law and apply the results to several variants of the secretary problem with fixed and random horizons.

24 pages. Expanded the shifted-threshold principle; established global optimality for power-biased random horizons; clarified a previous second-order approximation; and strengthened several technical justifications. Main results unchanged