论文标题
通过迭代删除，具有添加剂保证的公正选择
Impartial Selection with Additive Guarantees via Iterated Deletion
论文作者
论文摘要
公正的选择是基于该小组其他成员的提名，以个人无法影响自己选择的机会的方式选择一个人。对于这个问题，我们在带有$ n $个人的设置中给出了$ o（n^{（1+κ）/2}）$的添加性能保证的确定性机制，其中每个人都会在[0,1] $中投射$ o（n^κ）$提名，其中$κ\。对于$κ= 0 $，即，当每个人以最多恒定的提名投射时，此界限为$ o（\ sqrt {n}）$。这匹配了随机机制和单一提名的最著名保证。对于$κ= 1 $，限制为$ o（n）$。这是微不足道的，因为即使是从未选择的机制也提供了$ n-1 $的添加保证。但是，我们表明这也是最好的：对于每个确定性的公正机制，存在某些人提名的情况，而其他人则没有选择或选择任何人提名的人。
Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. For this problem, we give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+κ)/2})$ in a setting with $n$ individuals where each individual casts $O(n^κ)$ nominations, where $κ\in[0,1]$. For $κ=0$, i.e., when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $κ=1$ the bound is $O(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.
