Distributed secretary problem : a case of two uneven queues

Abstract

Secretary problem is one of the most widely studied online stochastic models, in which an employer wants to hire the best candidate from n candidates who arrive in a random order. It is well-known that the optimal success probability is 1/e. However, in reality, things are more complex because employers often have interviewers in different cities, interviewing candidates in a distributed manner. This motivates us to study the secretary problem with multiple queues. Feldman and Tennenholtz [EC 2012] studied this assuming the candidates are distributed evenly. In particular, when there are two even queues, the optimal success probability is 1/4. In this work, we move to the general problem when the queues are arbitrary and design the optimal online algorithm for the case of two queues. Our results characterize the exact success probability curve, connecting the cases of a single queue and two equal queues. Our technique is grounded on the linear programming framework introduced by Buchbinder et al. [Math. Oper. Res. 2014] and a novel analysis.