Query-Based Selection of Optimal Candidates under the Mallows Model

We study the secretary problem in which rank-ordered lists are generated by the Mallows model and the goal is to identify the highest ranked candidate through a sequential interview process which does not allow rejected candidates to be revisited. The main difference between our formulation and existing models is that, during the selection process, we are given a fixed number of questions to ask whether the current candidate is the highest-ranked or not. If the response is positive, the selection process terminates, otherwise, the search continues until a new potentially optimal candidate is identified. For the solution of our problem, we adopt a combinatorial method with new ideas and significant extensions compared to the work of Jones for the secretary problem with one selection. Our optimal interview strategy, as well as the expected number of candidates interviewed and expected number of queries used, can be determined exactly through the evaluation of well-defined recurrence relations. Specifically, if we are allowed to query $s-1$ times and to make a final selection without querying (thus, making $s$ selections in total) then the optimum scheme is characterized by $s$ thresholds that depend on the parameter $\theta$ of the Mallows distribution. These thresholds are independent from the maximal number of queries $s$.