Improved Bounds for Single-Nomination Impartial Selection
研究了基于相互提名的随机选择机制，当每人只能提名一人时，改进了排列机制的近似比，并证明新机制达到最优下界。
A randomized selection mechanism returns a probability distribution over individuals based on mutual nominations among them; it is impartial if the selection probability of each individual is independent of the nominations they cast and [Formula: see text]-optimal if the expected number of nominations received by the selected individual is always at least [Formula: see text] times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is [Formula: see text]-optimal, and this is the best possible. We show that the permutation mechanism does not provide the best possible factor in the natural situation when individuals cast exactly one nomination. Specifically, we provide a tight analysis of the permutation mechanism showing that it is [Formula: see text]-optimal in this case, and we design a new mechanism that is [Formula: see text]-optimal for [Formula: see text]. We further prove that no impartial mechanism can be better than [Formula: see text]-optimal. Funding: This research was supported by the Deutsche Forschungsgemeinschaft [Grant 431465007] and by the Engineering and Physical Sciences Research Council [Grant EP/T015187/1].