Tytuł pozycji:
Secretary problem revisited: Optimal selection strategy for top candidates using one try in a generalized version of the problem
This paper explores a novel variation of the classical secretary problem, commonly referred to as the marriage or best choice problem. In this adaptation, a decision-maker sequentially dates n ∈ N candidates, each uniquely ranked without ties from 1 to n. The decision strategy involves a preliminary non-selection phase of the first d ∈ N candidates where, d < n, following which the decision-maker commits to the first subsequent candidate who surpasses all previously evaluated candidates in quality. The central focus of this study is the derivation and analysis of P (d, n, k), which denotes the probability that the selected candidate, under the prescribed strategy, ranks among the top k ∈ N overall candidates, where k ≤ n. This investigation employs combinatorial probability theory to formulate P (d, n, k) and explores its behavior across various parameter values of d, n, and k. Particularly, we seek to determine in what fraction of the entire decision process should a decision-maker stop the non-selection phase, i.e., we search for the optimal proportion d/n ,that maximizes the probability P (d, n, k), with a special focus on scenarios where k is in generally low. While for k = 1, the problem is simplified to the classical secretary problem with d/n ≈ 1/e , our findings suggest that the strategy’s effectiveness is optimized for portion d/n decreasing below 1/e as k increases. Also, intuitively, probability P (d, n, k) increases as k increases, since the number of acceptable top candidates increases. These results not only extend the classical secretary problem but also provide strategic insights into decision-making processes involving ranked choices, sequential evaluation, and applications of searching not necessarily the best candidate, but one of the best candidates.
1. This paper is supported by the grant IG410023 with no. F4/50/2023, which has been provided by the Internal Grant Agency of the Prague University of Economics and Business.
2. Thematic Sessions: Short Papers
