In the Sequential Selection Problem (SSP), immediate and irrevocable decisions need to be made while candidates from a finite set are being examined one-by-one. The goal is to assign a limited number of @math available jobs to the best possible candidates. Standard SSP variants begin with an empty selection set (cold-starting) and perform the selection process once (single-round), over a single candidate set. In this paper we introduce the Multi-round Sequential Selection Problem (MSSP) which launches a new round of sequential selection each time a new set of candidates becomes available. Each new round has at hand the output of the previous one, i.e. its @math selected employees, and tries to update optimally that selection by reassigning each job at most once. Our setting allows changes to take place between two subsequent selection rounds: resignations of previously selected subjects or and alterations of the quality score across the population. The challenge for a selection strategy is thus to efficiently adapt to such changes. For this novel problem we adopt a cutoff-based approach, where a precise number of candidates should be rejected first before starting to select. We set a rank-based objective of the process over the final job-to-employee assignment and we investigate analytically the optimal cutoff values with respect to the important parameters of the problem. Finally, we present experimental results that compare the efficiency of different selection strategies, as well as their convergence rates towards the optimal solution in the case of stationary score distributions.
Various extensions of the basic have been investigated; see the non-exhaustive surveys in @cite_21 @cite_2 . Important to note, a change in the setting or in the objective function, changes also the optimal cutoff. In some scenarios, the DM can not only compute the of an interviewed among those examined earlier, but also assess 's true . This score can be thought of as a random variable associated to each candidate. When the objective is to maximize the expectation of the score of the selected candidate, then the optimal cutoff becomes @math @cite_16 . On the other end, @cite_20 seeks to minimize the expectation of the rank of the selected (note: low ranks are better). However, the analytical solution to this problem remains unknown, even when the score distribution of the is known.
@cite_21 @cite_20 @cite_16 @cite_2
1989174203 2144644784 2091087027
Summary The development of what has come to be known as the secretary problem is traced from its origins in the early 1960's. All published work to date on the problem and its extensions is reviewed. Let X 1 , X 2 , ..., X n be independent, identically distributed random variables, uniform on [0,1]. We observe the X k sequentially and must stop on exactly one of them. No recollection of the preceding observations is permitted. What stopping rule τ minimizes the expected rank of the selected observation? This full-information expected-rank problem is known as Robbins' problem. The general solution is still unknown, and only some bounds are known for the limiting value as n tends to infinity. After a short discussion of the history and background of this problem, we summarize what is known. We then try to present, in an easily accessible form, what the author believes should be seen as the essence of the more difficult remaining questions. The aim of this article is to evoke interest in this problem and so, simply by viewing it from what are possibly new angles, to increase the probability that a reader may see what seems to evade probabilistic intuition. Abstract We present an extension of the secretary problem in which the decision maker (DM) sequentially observes up to n applicants whose values are random variables X 1 , X 2 , … , X n drawn i.i.d. from a uniform distribution on [ 0 , 1 ] . The DM must select exactly one applicant, cannot recall released applicants, and receives a payoff of x t , the realization of X t , for selecting the t th applicant. For each encountered applicant, the DM only learns whether the applicant is the best so far. We prove that the optimal policy dictates skipping the first sqrt( n )-1 applicants, and then selecting the next encountered applicant whose value is a maximum.