Some variations of the secretary problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911580137979904 |
|---|---|
| author | Agrawal, Sarthak Saxena, Sanjeev |
| author_facet | Agrawal, Sarthak Saxena, Sanjeev |
| contents | We consider two variations of the classical secretary problem.
* A variation of the returning secretary problem where each interviewee may appear a second time with a fixed probability p. The decision-maker observes interviewees sequentially and must choose whether to accept or reject each appearance. We characterize the optimal threshold rule and examine its dependence on the reappearance probability p, highlighting how additional information from repeated appearances improves selection performance.
* A variation of the secretary problem in which success is defined as selecting any one of the top three interviewees rather than the single best. Interviewees are observed sequentially in random order, and decisions are irreversible. We estimated the success probability under this relaxed success criterion using the threshold strategy of the classical secretary problem. The results show that allowing selection among the top three significantly increases the success probability and shifts the optimal stopping threshold earlier than in the classical problem. This model provides insight into realistic decision-making scenarios where top interviewees are more or less similar. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_08593 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Some variations of the secretary problem Agrawal, Sarthak Saxena, Sanjeev Data Structures and Algorithms Discrete Mathematics Computer Science and Game Theory We consider two variations of the classical secretary problem. * A variation of the returning secretary problem where each interviewee may appear a second time with a fixed probability p. The decision-maker observes interviewees sequentially and must choose whether to accept or reject each appearance. We characterize the optimal threshold rule and examine its dependence on the reappearance probability p, highlighting how additional information from repeated appearances improves selection performance. * A variation of the secretary problem in which success is defined as selecting any one of the top three interviewees rather than the single best. Interviewees are observed sequentially in random order, and decisions are irreversible. We estimated the success probability under this relaxed success criterion using the threshold strategy of the classical secretary problem. The results show that allowing selection among the top three significantly increases the success probability and shifts the optimal stopping threshold earlier than in the classical problem. This model provides insight into realistic decision-making scenarios where top interviewees are more or less similar. |
| title | Some variations of the secretary problem |
| topic | Data Structures and Algorithms Discrete Mathematics Computer Science and Game Theory |
| url | https://arxiv.org/abs/2604.08593 |