Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS)

DOI: http://dx.doi.org/10.15439/2024F3882

Citation: Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 39, pages 719–724 (2024)

Full text

Abstract. 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 \in \mathbb{N}$ candidates, each uniquely ranked without ties from $1$ to $n$. The decision strategy involves a preliminary non-selection phase of the first $d \in \mathbb{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 \in \mathbb{N}$ overall candidates, where $k \leq 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 $\frac{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 $\frac{d}{n} \approx \frac{1}{e}$, our findings suggest that the strategy's effectiveness is optimized for portion $\frac{d}{n}$ decreasing below $\frac{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.

References

1. F. Thomas Bruss. “A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options”. In: The Annals of Probability 12.3 (Aug. 1984). ISSN: 0091-1798. http://dx.doi.org/10.1214/aop/1176993237.
2. Robert J. Vanderbei. “The postdoc variant of the secretary problem”. In: Mathematica Applicanda 49.1 (Dec. 2021). ISSN: 1730-2668. DOI : 10.14708/ma.v49i1.7076.
3. Yogesh Girdhar and Gregory Dudek. “Optimal Online Data Sampling or How to Hire the Best Secretaries”. In: 2009 Canadian Conference on Computer and Robot Vision. IEEE, May 2009. DOI : 10.1109/crv.2009.30.
4. John P. Gilbert and Frederick Mosteller. “Recognizing the Maximum of a Sequence”. In: Journal of the American Statistical Association 61.313 (Mar. 1966), pp. 35–73. ISSN : 1537-274X. http://dx.doi.org/10.1080/01621459.1966.10502008.
5. Tomomi Matsui and Katsunori Ano. “Lower Bounds for Bruss’ Odds Problem with Multiple Stoppings”. In: Mathematics of Operations Research 41.2 (May 2016), pp. 700–714. ISSN: 1526-5471. http://dx.doi.org/10.1287/moor.2015.0748.