Improved Bounds for Single-Nomination Impartial Selection
- 1 May 2026
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 51 (2) , 1486-1513
Abstract
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 [ ]-optimal if the expected number of nominations received by the selected individual is always at least [ ] times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is [ ]-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 [ ]-optimal in this case, and we design a new mechanism that is [ ]-optimal for [ ]. We further prove that no impartial mechanism can be better than [ ]-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].Keywords
This publication has 25 references indexed in Scilit:
- Manipulation and peer mechanisms: A surveyArtificial Intelligence, 2024
- Impartial selection with additive guarantees via iterated deletionGames and Economic Behavior, 2024
- PeerNomination: A novel peer selection algorithm to handle strategic and noisy assessmentsArtificial Intelligence, 2022
- Impartial Selection with Additive Approximation GuaranteesTheory of Computing Systems, 2022
- A new axiomatic approach to the impartial nomination problemGames and Economic Behavior, 2021
- Strategyproof peer selection using randomization, partitioning, and apportionmentArtificial Intelligence, 2019
- Characterizing minimal impartial rules for awarding prizesGames and Economic Behavior, 2016
- Symmetry and impartial lotteriesGames and Economic Behavior, 2015
- Impartial nomination correspondencesSocial Choice and Welfare, 2013
- Exclusion of self evaluations in peer ratings: An impossibility and some proposalsSocial Choice and Welfare, 2003