Improved Bounds for Single-Nomination Impartial Selection
成果类型：
Article; Early Access
署名作者：
Cembrano, Javier; Fischer, Felix; Klimm, Max
署名单位：
Max Planck Society; Technical University of Berlin; University of London; Queen Mary University London
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2024.0431
发表日期：
2025
关键词：
摘要：
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 alpha-optimal if the expected number of nominations received by the selected individual is always at least alpha times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is 1/2-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 2/3-optimal in this case, and we design a new mechanism that is alpha-optimal for alpha > 2/3. We further prove that no impartial mechanism can be better than 76/105-optimal.
来源URL：