Strategy-proof Approximations of Distance Rationalizable Voting Rules

摘要

This paper considers randomized strategy-proof approximations to distance rationalizable voting rules. It is shown that the Random Dictator voting rule (return the top-choice of a random voter) nontrivially approximates a large class of distances with respect to unanimity. Any randomized voting rule that deviates too greatly from the Random Dictator voting rule is shown to obtain a trivial approximation (i.e., equivalent to ignoring the voters' votes and selecting an al ternative uniformly at random). The outlook for consensus classes, other than unanimity is bleaker. This paper shows that for a large number of distance rationalizations, with respect to the majority and Condorcet consensus classes that no strategy-proof randomized rule can asymptotically outperform uniform random se lection of an alternative. This paper also shows that veto cannot be approximated nontrivially when approximations are measured with respect to minimizing the number of vetoes an alternative receives.