Secretary problem revisited: Optimal selection strategy for top candidates using one try in a generalized version of the problem

• Autorzy: Štěpánek Lubomír

Identyfikatory

DOI

10.15439/2024F3882

• Konferencja: Federated Conference on Computer Science and Information Systems (19 ; 08-11.09.2024 ; Belgrade, Serbia)
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

computer science; Monte Carlo methods; decision making; search problems

PL

informatyka; metody Monte Carlo; podejmowanie decyzji; problemy wyszukiwawcze

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2024
• Tom: Vol. 39
• Strony: 719--724
• Opis fizyczny: Bibliogr. 6 poz., tab., wykr., wz.

Twórcy

autor

Štěpánek Lubomír

• Department of Statistics and Probability
• Department of Mathematics Faculty of Informatics and Statistics Prague University of Economics and Business W. Churchill’s square 4, 130 67 Prague, Czech Republic
• Institute of Biophysics and Informatics First Faculty of Medicine Charles University Salmovská 1, Prague, Czech Republic

Bibliografia

• 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.
• 6. F. T. Bruss and G. Louchard, “Sequential selection of the κ best out of n rankable objects,” Discrete Mathematics & Theoretical Computer Science, vol. Vol. 18 no. 3, Oct. 2016.

Uwagi

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