The construction of group search algorithm for the secretary problem

Authors

DOI:

https://doi.org/10.15587/1729-4061.2026.353251

Keywords:

optimal stopping, conditional probability, optimal choice, odds theorem, Monte Carlo simulation

Abstract

The object of this study is a generalized secretary problem in which candidates are divided into groups of varying sizes and are observed simultaneously within each group. The problem addressed is to determine the optimal order of reviewing such groups in order to maximize the probability of selecting the best candidate.

The results obtained consist in the development of an efficient group ordering algorithm that combines theoretical findings based on Bruss’s odds theorem with numerical modeling using the Monte Carlo method. Owing to its specific features and distinctive advantages, the proposed approach increases the probability of selecting the best candidate by 8–15% compared to a random group order. This is achieved through two proven lemmas that restrict consideration only to those permutations in which the groups considered as candidates for stopping are ordered in non-increasing size, and the search begins with the largest group. Such an algorithm makes the problem computationally feasible even for a moderately large number of groups.

The obtained results are explained by the fact that uneven distributions of group sizes introduce exploitable structural asymmetries. The proposed ordering strategy effectively leverages this unevenness, which is confirmed by numerical experiments demonstrating a positive correlation between the degree of unevenness and the probability of successful selection.

The practical applicability of the results extends to scenarios involving online resource allocation, adaptive algorithms with real-time updates, and decision-support systems. The proposed framework can be efficiently implemented in adaptive recruitment platforms and similar applications, making it relevant not only for theoretical research on optimal stopping problems but also for practical use in operations research, economics, and artificial intelligence

Author Biographies

Serhii Dotsenko, Taras Shevchenko National University of Kyiv

Associate Professor

Department of Software Systems and Technologies

Anastasia Vecherkovskaya, Taras Shevchenko National University of Kyiv

Associate Professor

Department of Software Systems and Technologies

References

  1. Ferguson, T. S. (1989). Who Solved the Secretary Problem? Statistical Science, 4 (3). https://doi.org/10.1214/ss/1177012493
  2. Dubynetska, P., Sodoma, R. (2023). Osoblyvosti metodiv pidboru kadriv na pidpryiemstvo. Abstracts of the І International Scientific-Practical Conference «Problems and Prospects of Business Structures in the Conditions Unstable Processes of Economic Development». Kyiv, 36–38. Available at: https://sci.ldubgd.edu.ua/bitstream/123456789/13000/1/%D0%97%D0%B1%D1%96%D1%80%D0%BA%D0%B0_%D0%9A%D0%BE%D0%BD%D1%84_%D0%9A%D0%95%D0%91%D0%A2_06.04.23.pdf
  3. Correa, J., Cristi, A., Epstein, B., Soto, J. A. (2024). Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality. Mathematics of Operations Research, 49 (1), 441–475. https://doi.org/10.1287/moor.2023.1363
  4. Semsar-Kazerooni, E., Khorasani, K. (2009). Multi-agent team cooperation: A game theory approach. Automatica, 45 (10), 2205–2213. https://doi.org/10.1016/j.automatica.2009.06.006
  5. Hsiau, S.-R., Yang, J.-R. (2000). A natural variation of the standard secretary problem. Statistica Sinica, 10 (2), 639–646. Available at: https://www.jstor.org/stable/24306737
  6. Bruss, F. T. (2000). Sum the odds to one and stop. The Annals of Probability, 28 (3). https://doi.org/10.1214/aop/1019160340
  7. Tamaki, M. (2009). Optimal Choice of the Best Available Applicant in Full-Information Models. Journal of Applied Probability, 46 (4), 1086–1099. https://doi.org/10.1239/jap/1261670690
  8. Ano, K., Kakinuma, H., Miyoshi, N. (2010). Odds Theorem with Multiple Selection Chances. Journal of Applied Probability, 47 (4), 1093–1104. https://doi.org/10.1239/jap/1294170522
  9. Feldman, M., Izsak, R. (2017). Building a Good Team: Secretary Problems and the Supermodular Degree. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1651–1670. https://doi.org/10.1137/1.9781611974782.109
  10. Blanc, P., Borthagaray, J. P., Kohen, D., Mereb, M. (2017). Secretary problem with quality-based payoff. arXiv. https://doi.org/10.48550/arXiv.1605.06478
  11. Goldstein, D. G., McAfee, R. P., Suri, S., Wright, J. R. (2017). Learning in the Repeated Secretary Problem. Proceedings of the 2017 ACM Conference on Economics and Computation, 541–541. https://doi.org/10.1145/3033274.3085112
  12. Correa, J., Cristi, A., Feuilloley, L., Oosterwijk, T., Tsigonias-Dimitriadis, A. (2025). The Secretary Problem with Independent Sampling. Management Science, 71 (4), 2778–2801. https://doi.org/10.1287/mnsc.2021.01580
  13. Dotsenko, S., Shevchenko, G. (2020). Secretary problem with vanishing objects. Mathematical Game Theory and Applications, 12 (2), 63–81. https://doi.org/10.17076/mgta_2020_2_16
  14. Nuti, P., Vondrák, J. (2023). Secretary Problems: The Power of a Single Sample. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015–2029. https://doi.org/10.1137/1.9781611977554.ch77
  15. Fujii, K., Yoshida, Y. (2024). The Secretary Problem with Predictions. Mathematics of Operations Research, 49 (2), 1241–1262. https://doi.org/10.1287/moor.2022.0031
  16. Braun, A., Sarkar, S. (2024). The Secretary Problem with Predicted Additive Gap. Advances in Neural Information Processing Systems 37, 16321–16341. https://doi.org/10.52202/079017-0521
  17. Antoniadis, A., Gouleakis, T., Kleer, P., Kolev, P. (2023). Secretary and online matching problems with machine learned advice. Discrete Optimization, 48, 100778. https://doi.org/10.1016/j.disopt.2023.100778
  18. Albers, S., Ladewig, L. (2021). New results for the k-secretary problem. Theoretical Computer Science, 863, 102–119. https://doi.org/10.1016/j.tcs.2021.02.022
  19. Brera, R., Fu, F. (2023). The satisficing secretary problem: when closed-form solutions meet simulated annealing. arXiv. https://doi.org/10.48550/arXiv.2302.03220
  20. Hahn, N., Hoefer, M., Smorodinsky, R. (2020). The Secretary Recommendation Problem. Proceedings of the 21st ACM Conference on Economics and Computation, 189–189. https://doi.org/10.1145/3391403.3399478
  21. Chun, Y. H., Moskowitz, H., Plante, R. D. (1993). Optimal Selection Strategy for the Group Interview Problem. Decision Sciences, 24 (2), 295–314. https://doi.org/10.1111/j.1540-5915.1993.tb00476.x
  22. Pinsky, R. G. (2023). The secretary problem with non-uniform arrivals via a left-to-right minimum exponentially tilted distribution. Latin American Journal of Probability and Mathematical Statistics, 20 (2), 1631. https://doi.org/10.30757/alea.v20-62
The construction of group search algorithm for the secretary problem

Downloads

Published

2026-02-27

How to Cite

Dotsenko, S., & Vecherkovskaya, A. (2026). The construction of group search algorithm for the secretary problem. Eastern-European Journal of Enterprise Technologies, 1(4 (139), 56–64. https://doi.org/10.15587/1729-4061.2026.353251

Issue

Vol. 1 No. 4 (139) (2026): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2026 Serhii Dotsenko, Anastasia Vecherkovskaya

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.