Analysis of the 'Hiring Above the Median' Selection Strategy for the Hiring Problem

摘要

This paper gives a precise mathematical analysis of the behaviour of "hiring above the median" strategies for a problem in the context of "on-line selection under uncertainty" that is known (at least in computer science related literature) as the "hiring problem". Here a sequence of candidates is interviewed sequentially and based on the "score" of the current candidate an immediate decision whether to hire him or not has to be made. For "hiring above the median" selection rules, a new candidate will be hired if he has a score better than the median score of the already recruited candidates. Under the natural probabilistic model assuming that the ranks of the first n candidates are forming a random permutation, we show exact and asymptotic results for various quantities of interest to describe the dynamics of the hiring process and the quality of the hired staff. In particular we can characterize the limiting distribution of the number of hired candidates of a sequence of n candidates, which reveals the somewhat surprising effect, that slight changes in the selection rule, i.e., assuming the "lower" or the "upper" median as the threshold, have a strong influence on the asymptotic behaviour. Thus we could extend considerably previous analyses (Krieger et al., Ann. Appl. Probab., 17:360-385, 2007; Broder et al., Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1184-1193, ACM/SIAM, New York/Philadelphia, 2008 and Archibald and Martinez, Proceedings of the 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), Discrete Mathematics and Theoretical Computer Science, pp. 63-76, 2009) of such selection rules. Furthermore, we discuss connections between the hiring process and the Chinese restaurant process introduced by Pitman (Combinatorial Stochastic Processes, Springer, Berlin, 2006).