Finding the second-best candidate under the Mallows model
Finding the second-best candidate under the Mallows model
复制标题
在 Mallows 模型下寻找第二好的候选者
DOI：
10.1016/j.tcs.2022.06.029
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Milenkovic, Olgica
中科院分区：
文献类型：
--
作者：
Liu, Xujun;Milenkovic, Olgica
序列分析和最优停止理论中著名的秘书问题要求在实时做出接受/拒绝决策的约束下，在序列检验列表中找到最优候选人的概率最大化。这个问题在数学界引起了极大的兴趣，并且与在线搜索、数据流、日常购买建模和多臂强盗机制中出现的实际问题有关。这个问题的另一个版本是所谓的博士后问题，其感兴趣的问题是设计一种策略，以确定成功可能性最高的次优候选人。我们以组合形式研究博士后问题。在这种情况下，根据对称群sn上的某种分布对长度为N的排列π进行采样，π的元素从左到右一个接一个地显示，因此在每一步中，人们只能确定迄今为止显示的元素的相对顺序。在每个步骤中，必须决定接受或拒绝当前呈现的元素，并且将来不能回忆该决定。我们感兴趣的问题是找到选择第二大值位置的最优策略。我们解决了非传统情况下的博士后问题，在这种情况下，候选人不是均匀随机地呈现，而是根据从Mallows分布中得出的排列。malallows分布为每个置换π∈sn分配一个权值θ c (π)，其中函数c表示π与单位置换（即π中的反转数）之间的Kendall τ距离。为了确定更具挑战性的博士后问题的最佳停止标准，我们采用了一种组合方法，与秘书问题设置中首次引入的分析相比，该方法包括新的证明技术和新的方法扩展。最优策略取决于Mallows分布的参数θ，可以通过求解定义良好的递归关系精确确定。
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 S N 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 π∈ S N a weight θ c (π), where the function c represents the Kendall τ distance between π and the identity permutation (ie, 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.