Anonymity-Proof Voting Rules

Abstract

A (randomized, anonymous) voting rule maps any multiset of total orders of
(aka. votes over) a fixed set of alternatives to a probability distribution over these alternatives. A voting rule f is neutral if it treats all alternatives symmetrically. It satisfies participation if no voter ever benefits from not casting her vote. It is falsename-proof if no voter ever benefits from casting additional (potentially different)
votes. It is anonymity-proof if it satisfies participation and it is false-name-proof. We
show that the class of anonymity-proof neutral voting rules consists exactly of the
rules of the following form. With some probability kf in [0, 1], the rule chooses an
alternative at random. With probability 1-kf , the rule first draws a pair of alternatives
at random. If every vote prefers the same alternative between the two (and there
is at least one vote), then the rule chooses that alternative. Otherwise, the rule flips a
fair coin to decide between the two alternatives.