Analysis of 'hiring above the median': a 'Lake Wobegon' strategy for the hiring problem

摘要

The hiring problem is a recent research problem, which has been introduced and studied first by Broder et al. [2] in 2008. It belongs to the category of on-line decision making under uncertainty. In such kind of research, the input is a sequence of instances and a decision must be taken for each instance depending on the instances seen so far while no information on the future is available. The hiring problem can be considered as a natural extension of the well-known secretary problem [4], where the employer is now looking for many candidates rather than only one (as it is the case for the secretary problem). Here the goal is to design some hiring strategy to meet the demands of the employer, which essentially are to obtain a good quality staff at a reasonable hiring rate, which is a main difference to the secretary problem, where an optimization policy, namely the demand of hiring the best candidate, occurs. Broder et al. introduced two so-called "Lake Wobegon strategies", namely "hiring above the current mean" and "hiring above the current median", applied for a continuous probabilistic model for the sequence of scores of the candidates.