Gap between outcomes of voting rules

Abstract

Through the course of history, a variety of voting rules have been used to determine election outcomes. The traditional way in social choice theory to evaluate a voting rule is by checking whether it satisfies axioms deemed to be desirable for voting rules. Celebrated results in social choice theory say that even for a small set of seemingly necessary axioms, no voting rule exists satisfying them. In the face of such impossibility results, it becomes challenging to justify why certain voting rules work well in practice. Although in theory, these rules may yield drastically different outcomes, for real-world datasets, behavioural social choice analyses have found that the rules are often in perfect agreement with each other! This work attempts to give a mathematical explanation of this phenomenon. In this work, we formulate a quantitative approach towards comparing voting rules by viewing them as two players engaged in a zero-sum game. If rule A selects candidate C? while rule B selects candidate C?, the payoff for A is the number of voters who prefer C? to C? minus the number who prefer C? to C?. The optimal voting rule according to this criterion (corresponding to the optimal randomized strategy for the game) is the game-theoretic rule (GT) [RS10], while the best deterministic strategy is the well-known Minimax voting rule. We investigate rigorously how various common voting rules fare against each other in terms of the minimum payoff they receive for arbitrary voting profiles. We also study the case when the voting profiles are drawn from a mixture of multinomial logit distributions. This scenario corresponds to a population consisting of a small number of groups, each voting according to a latent preference ranking. We supplement the theoretical findings by empirically comparing the payoff of voting rules when they are applied to user preferences for movies as determined from the Netflix competition dataset [BL07]. On this dataset, we find that the Minimax rule, the Schulze rule, and a deterministic variant of the GT rule perform the best in our framework.