Optimal Stopping Methodology for the Secretary Problem with Random Queries
Preprint
Abstract
Candidates arrive sequentially for an interview process which results in them being ranked relative to their predecessors. Based on the ranks available at each time, one must develop a decision mechanism that selects or dismisses the current candidate in an effort to maximize the chance to select the best. This classical version of the ``Secretary problem'' has been studied in depth using mostly combinatorial approaches, along with numerous other variants. In this work we consider a particular new version where during reviewing one is allowed to query an external expert to improve the probability of making the correct decision. Unlike existing formulations, we consider experts that are not necessarily infallible and may provide suggestions that can be faulty. For the solution of our problem we adopt a probabilistic methodology and view the querying times as consecutive stopping times which we optimize with the help of optimal stopping theory. For each querying time we must also design a mechanism to decide whether we should terminate the search at the querying time or not. This decision is straightforward under the usual assumption of infallible experts but, when experts are faulty, it has a far more intricate structure.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Query-based selection of optimal candidates under the Mallows modelTheoretical Computer Science, 2023
- Finding the second-best candidate under the Mallows modelTheoretical Computer Science, 2022
- Weighted Games of Best ChoiceSIAM Journal on Discrete Mathematics, 2020
- Opportunity Costs in the Game of Best ChoiceThe Electronic Journal of Combinatorics, 2019
- The Secretary Problem and Its Extensions: A ReviewInternational Statistical Review, 1983
- A Problem of Optimal Choice and AssignmentOperations Research, 1982
- A SECRETARY PROBLEM WITH DOUBLE CHOICESJournal of the Operations Research Society of Japan, 1979
- On a Generalization of the Best Choice ProblemTheory of Probability & Its Applications, 1977
- The Problem of Choice and the Sptimal Stopping Rule for a Sequence of Independent TrialsTheory of Probability & Its Applications, 1966
- Dynamic Programming and Decision TheoryJournal of the Royal Statistical Society Series C: Applied Statistics, 1961