Revisiting the Secretary Problem under Noisy Evaluation: Robustness and Performance Analysis

Abstract

This paper investigates how the existence of different degrees of noise in the real world affects the final results of the classic secretarial problem by constructing a noise inclusive secretarial strategy model. Rather than assuming that decision-makers know the precise rankings of all candidates, this study has set up a situation where the observed rankings of each candidate by the decisionmaker are subject to noise and, as a result, deviate from the optimal probability-maximizing outcome of the classical secretarial problem. To study the effect of this uncertainty, the noisy secretarial strategy model also uses Monte Carlo simulation. A set of indices for the new model environment also includes the success rate, average selection rank and regret value. Based on the above results, a relatively small amount of noise will still significantly reduce the final decision. With an increase in initial noise, the proportion of the selected best candidate decreases significantly. Based on the above study, the strength of the classic secretarial problem is highly sensitive to the initial observations. Although this strategy has almost the same success rate in a low-noise environment, it is still not feasible for realworld application.