Improved Bounds for Single-Nomination Impartial Selection

We give new bounds for the single-nomination model of impartial selection, a problem proposed by Holzman and Moulin (Econometrica, 2013). A selection mechanism, which may be randomized, selects one individual from a group of n based on nominations among members of the group; a mechanism is impartial if the selection of an individual is independent of nominations cast by that individual, and α-optimal if under any circumstance the expected number of nominations received by the selected individual is at least α times that received by any individual. In a many-nominations model, where individuals may cast an arbitrary number of nominations, the so-called permutation mechanism is 1/2-optimal, and this is best possible. In the single-nomination model, where each individual casts exactly one nomination, the permutation mechanism does better and prior to this work was known to be 67/108-optimal but no better than 2/3-optimal. We show that it is in fact 2/3-optimal for all n. This result is obtained via tight bounds on the performance of the mechanism for graphs with maximum degree Delta, for any Delta, which we prove using an adversarial argument. We then show that the permutation mechanism is not best possible; indeed, by combining the permutation mechanism, another mechanism called plurality with runner-up, and some new ideas, 2105/3147-optimality can be achieved for all n. We finally give new upper bounds on α for any α-optimal impartial mechanism. They improve on the existing upper bounds for all n≥ 7 and imply that no impartial mechanism can be better than 76/105-optimal for all n; they do not preclude the existence of a (3/4-varepsilon)-optimal impartial mechanism for arbitrary varepsilon>0 if n is large.