TY - JOUR

T1 - Finding the second-best candidate under the Mallows model

AU - Liu, Xujun

AU - Milenkovic, Olgica

N1 - Funding Information:
The work was supported in part by the NSF grants NSF CCF 15-26875 and The Center for Science of Information at Purdue University , under contract number 239 SBC PURDUE 4101-38050 . Early parts of the work were also supported by the DARPA Molecular Informatics Program . The main work was done while X. Liu was a postdoc at Coordinated Science Laboratory, University of Illinois, Urbana–Champaign.
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/9/11

Y1 - 2022/9/11

N2 - The well-known secretary problem in sequential analysis and optimal stopping theory asks one to maximize the probability of finding the optimal candidate in a sequentially examined list under the constraint that accept/reject decisions are made in real-time. The problem has received significant interest in the mathematics community and is related to practical questions arising in online search, data streaming, daily purchase modeling and multi-arm bandit mechanisms. A version of the problem is the so-called postdoc problem, for which the question of interest is to devise a strategy that identifies the second-best candidate with highest possible probability of success. We study the postdoc problem in its combinatorial form. In this setting, a permutation π of length N is sampled according to some distribution over the symmetric group SN and the elements of π are revealed one-by-one from left to right so that at each step, one can only determine the relative orders of the elements revealed so far. At each step, one must decide to either accept or reject the currently presented element and cannot recall the decision in the future. The question of interest is to find the optimal strategy for selecting the position of the second-largest value. We solve the postdoc problem for the untraditional setting where the candidates are not presented uniformly at random but rather according to permutations drawn from the Mallows distribution. The Mallows distribution assigns to each permutation π∈SN a weight θc(π), where the function c represents the Kendall τ distance between π and the identity permutation (i.e., the number of inversions in π). To identify the optimal stopping criteria for the significantly more challenging postdoc problem, we adopt a combinatorial methodology that includes new proof techniques and novel methodological extensions compared to the analysis first introduced in the setting of the secretary problem. The optimal strategies depend on the parameter θ of the Mallows distribution and can be determined exactly by solving well-defined recurrence relations.

AB - The well-known secretary problem in sequential analysis and optimal stopping theory asks one to maximize the probability of finding the optimal candidate in a sequentially examined list under the constraint that accept/reject decisions are made in real-time. The problem has received significant interest in the mathematics community and is related to practical questions arising in online search, data streaming, daily purchase modeling and multi-arm bandit mechanisms. A version of the problem is the so-called postdoc problem, for which the question of interest is to devise a strategy that identifies the second-best candidate with highest possible probability of success. We study the postdoc problem in its combinatorial form. In this setting, a permutation π of length N is sampled according to some distribution over the symmetric group SN and the elements of π are revealed one-by-one from left to right so that at each step, one can only determine the relative orders of the elements revealed so far. At each step, one must decide to either accept or reject the currently presented element and cannot recall the decision in the future. The question of interest is to find the optimal strategy for selecting the position of the second-largest value. We solve the postdoc problem for the untraditional setting where the candidates are not presented uniformly at random but rather according to permutations drawn from the Mallows distribution. The Mallows distribution assigns to each permutation π∈SN a weight θc(π), where the function c represents the Kendall τ distance between π and the identity permutation (i.e., the number of inversions in π). To identify the optimal stopping criteria for the significantly more challenging postdoc problem, we adopt a combinatorial methodology that includes new proof techniques and novel methodological extensions compared to the analysis first introduced in the setting of the secretary problem. The optimal strategies depend on the parameter θ of the Mallows distribution and can be determined exactly by solving well-defined recurrence relations.

KW - Mallows model

KW - Online algorithms

KW - Permutations

KW - Postdoc problem

KW - Second-best candidate

KW - Secretary problem

UR - http://www.scopus.com/inward/record.url?scp=85133600731&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85133600731&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2022.06.029

DO - 10.1016/j.tcs.2022.06.029

M3 - Article

AN - SCOPUS:85133600731

VL - 929

SP - 39

EP - 68

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -