Query-based selection of optimal candidates under the Mallows model

Xujun Liu, Olgica Milenkovic, George V. Moustakides

Research output: Contribution to journalArticlepeer-review

Abstract

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 opportunities to query an infallible expert 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. Our optimal interview strategy, as well as the expected number of candidates interviewed and expected number of queries used can be determined 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 θ of the Mallows distribution but are independent on the maximum number of queries.

Original languageEnglish (US)
Article number114206
JournalTheoretical Computer Science
Volume979
DOIs
StatePublished - Nov 10 2023

Keywords

  • Best candidate
  • Dowry problem
  • Mallows model
  • Permutations
  • Query-based
  • Secretary problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Query-based selection of optimal candidates under the Mallows model'. Together they form a unique fingerprint.

Cite this