The secretary problem is a well-known optimal stopping problem, in which we interview $n \in {\mathbb N}_{\geq 2}$ candidates for a vacant job position with the intent of hiring the best one among them. We must decide on the acceptance or refusal of the candidate after each interview is completed. Since it is a long-known problem, several generalizations of the original version have surfaced through the years by changing or removing some of the problem's assumptions, increasing its general applicability in the process.
This master's thesis presents the basic secretary problem and the theory needed for its analysis. The procedure of translating the main problem into a version, for which the general optimal stopping for homogeneous Markov chains theory is applicable, is effected and the problem is then solved. Furthermore, the limit characteristics of the results as the number of candidates grows without bonds are analysed.
Additionally, the variation of the problem for a random number of candidates is discussed for specifically chosen distributions. The presented examples show that the form of the optimal hiring strategy from the original problem stays the same, while the optimal values change for each respective distribution.
|
