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].

This publication has 25 references indexed in Scilit: