Skip to Main content Skip to Navigation
Conference papers

The Hiring Problem and Permutations

Abstract : The $\textit{hiring problem}$ has been recently introduced by Broder et al. in last year's ACM-SIAM Symp. on Discrete Algorithms (SODA 2008), as a simple model for decision making under uncertainty. Candidates are interviewed in a sequential fashion, each one endowed with a quality score, and decisions to hire or discard them must be taken on the fly. The goal is to maintain a good rate of hiring while improving the "average'' quality of the hired staff. We provide here an alternative formulation of the hiring problem in combinatorial terms. This combinatorial model allows us the systematic use of techniques from combinatorial analysis, e. g., generating functions, to study the problem. Consider a permutation $\sigma :[1,\ldots, n] \to [1,\ldots, n]$. We process this permutation in a sequential fashion, so that at step $i$, we see the score or quality of candidate $i$, which is actually her face value $\sigma (i)$. Thus $\sigma (i)$ is the rank of candidate $i$; the best candidate among the $n$ gets rank $n$, while the worst one gets rank $1$. We define $\textit{rank-based}$ strategies, those that take their decisions using only the relative rank of the current candidate compared to the score of the previous candidates. For these strategies we can prove general theorems about the number of hired candidates in a permutation of length $n$, the time of the last hiring, and the average quality of the last hired candidate, using techniques from the area of analytic combinatorics. We apply these general results to specific strategies like hiring above the best, hiring above the median or hiring above the $m$th best; some of our results provide a complementary view to those of Broder et al., but on the other hand, our general results apply to a large family of hiring strategies, not just to specific cases.
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 11:09:01 AM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:52:20 AM


Publisher files allowed on an open archive




Margaret Archibald, Conrado Martínez. The Hiring Problem and Permutations. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.63-76, ⟨10.46298/dmtcs.2731⟩. ⟨hal-01185423⟩



Record views


Files downloads