论文标题
秘书问题的效率有两种衡量标准，每个等级都有多个项目
Two measures of efficiency for the secretary problem with multiple items at each rank
论文作者
论文摘要
对于$ 2 \ le K \ in \ Mathbb {n} $，请考虑以下经典秘书问题的改编。 $ n $线性订购的排名中的每个$ k $项目。 $ kn $项目被揭示，一次以统一的随机顺序向观察者揭示其目标是选择最高等级项目的观察者。在每个阶段，观察者只知道到目前为止到达的项目的相对等级，并且必须选择当前项目，在这种情况下，该过程终止或拒绝并继续进行下一个项目。 For $M\in\{0,1,\cdots, kn-1\}$, let $\mathcal{S}(n,k;M)$ denote the strategy whereby one allows the first $M$ items to pass, and then selects the first later arriving item whose rank is \it either equal to or greater than\rm\ the highest rank of the first $M$ items (if such an item exists).令$ w _ {\ Mathcal {s}（n，k; m）} $表示事件，即人们使用策略$ \ Mathcal {s}（n，k; m）选择最高等级的项目，然后让我们 $ p_ {n，k}（w _ {\ Mathcal {s}（n，k; m）}）$表示相应的概率。我们获得了$ p_ {n，k}（w _ {\ mathcal {s}（n，k; m）}）$的公式，以及$ \ lim_ {n \ to \ in \ to \ infty} p_ {n，k}（w _ { $ c \ in（0,1）$。在经典秘书问题中，渐近最佳策略的成功概率约为$ \ frac1e \约0.368 $。对于$ k = 2 $，渐近最佳策略产生的概率约为0.701。对于$ k = 3 $，最佳概率高于0.85，对于$ k = 7 $，该概率超过0.99，对于$ k \ ge12 $，它是1.000到三个小数点的位置。在每个等级的多个项目的问题中，除了选择最高等级项目的概率外，还有一个策略效率的附加度量。即，选择最高等级项目的速度有多快。我们给出了这种效率的完整图片。
For $2\le k\in\mathbb{N}$, consider the following adaptation of the classical secretary problem. There are $k$ items at each of $n$ linearly ordered ranks. The $kn$ items are revealed, one item at a time, in a uniformly random order, to an observer whose objective is to select an item of highest rank. At each stage the observer only knows the relative ranks of the items that have arrived thus far, and must either select the current item, in which case the process terminates, or reject it and continue to the next item. For $M\in\{0,1,\cdots, kn-1\}$, let $\mathcal{S}(n,k;M)$ denote the strategy whereby one allows the first $M$ items to pass, and then selects the first later arriving item whose rank is \it either equal to or greater than\rm\ the highest rank of the first $M$ items (if such an item exists). Let $W_{\mathcal{S}(n,k;M)}$ denote the event that one selects an item of highest rank using strategy $\mathcal{S}(n,k;M)$ and let $P_{n,k}(W_{\mathcal{S}(n,k;M)})$ denote the corresponding probability. We obtain a formula for $P_{n,k}(W_{\mathcal{S}(n,k;M)})$, and for $\lim_{n\to\infty}P_{n,k}(W_{\mathcal{S}(n,k;M_n)})$, when $M_n\sim ckn$, with $c\in(0,1)$. In the classical secretary problem, the asymptotically optimal strategy yields a probability of success of $\frac1e\approx 0.368$. For $k=2$, the asymptotically optimal strategy yields yields a probability of success of about 0.701. For $k=3$, the optimal probability is above 0.85, for $k=7$, that probability exceeds 0.99, and for $k\ge12$, it is 1.000 to three decimal places. In the problem with multiple items at each rank, there is an additional measure of efficiency of a strategy besides the probability of selecting an item of highest rank; namely how quickly one selects an item of highest rank. We give a rather complete picture of this efficiency.
