Analysis of the Strategy 'Hiring Above the m-th Best Candidate'

摘要

The hiring problem is a simple model for on-line decision-making, inspired by the well-known and time-honored secretary problem (see, for instance, the surveys of Freeman Int Stat 51:189-206, 1983 or Samuels Handbook of sequential analysis, 1991). In the combinatorial model of the hiring problem (Archibald and Martinez Proc. of the 21st Int. Col. on Formal Power Series and Algebraic Combinatorics (FPSAC), 2009), there is a sequence of candidates of unknown length, and we can rank all candidates from best to worst without ties; all orders are equally likely. Thus any finite prefix of the sequence of candidates can be modeled as a random permutation. Candidates come one after another, and a decision must be taken immediately either to hire or to discard the current candidate, based on her relative rank among all candidates seen so far. In this paper we analyze in depth the strategy hiring above the m-th best candidate (or hiring above the m-th best, for short), formally introduced by Archibald and Martinez (Proc. of the 21st Int. Col. on Formal Power Series and Algebraic Combinatorics (FPSAC), 2009). This hiring strategy hires the first m candidates in the sequence whatever their relative ranks, then any further candidate is hired if her relative rank is better than the m-th best candidate seen so far. The close connection of this hiring strategy to the notion of records in sequences and permutations is quite evident; records and their generalizations (namely, m-records) have been throughly studied in the literature (see, for instance, the book of Arnold et al. Records, Wiley Series in Probability and Mathematical Statistics, 1998), and we explore here that relationship. We also discuss the relationship between this hiring strategy and the seating plan (0, m) for the well-known Chinese restaurant process (Pitman Combinatorial stochastic processes, 2006). We analyze in this paper several random variables (we also call them hiring parameters) that give us an accurate description of the main probabilistic features of "hiring above the m-th best", from the point of view of the hiring rate (number of hired candidates, waiting time to hire a certain number of candidates, time between consecutive hirings,...) and also of the quality of the hired staff (rank of the last hired candidate, best discarded candidate,...). We are able to obtain the exact and asymptotic probability distributions for the most fundamental parameter, namely, the number of hired candidates, and also for most of the other parameters. Another novel quantity that we analyze here is the number of replacements, a quantity naturally arising when we consider "hiring above the m-th best" endowed with a replacement mechanism: that is, an incoming candidate can be: (1) hired anew, because the candidate is among the m best seen so far, (2) hired to replace some previously hired worse candidate, or (3) discarded.