The Semi-Random Satisfaction of Voting Axioms

We initiate the work towards a comprehensive picture of the worst average-case satisfaction of voting axioms in semi-random models, to provide a finer and more realistic foundation for comparing voting rules. We adopt the semi-random model and formulation in [54] , where an adversary chooses arbitrarily correlated "ground truth" preferences for the agents, on top of which random noises are added. We focus on characterizing the semi-random satisfaction of two well-studied voting axioms: Condorcet criterion and participation. We prove that for any fixed number of alternatives, when the number of voters n is sufficiently large, the semirandom satisfaction of the Condorcet criterion under a wide range of voting rules is 1, 1 -exp(-Θ(n)), Θ(n -0.5 ), exp(-Θ(n)), or being Θ(1) and 1 -Θ(1) at the same time; and the semi-random satisfaction of participation is 1-Θ(n -0.5 ). Our results address open questions by Berg and Lepelley [3] in 1994, and also confirm the following high-level message: the Condorcet criterion is a bigger concern than participation under realistic models. While the classical worst-case analysis of (dis)satisfaction of axioms can be desirable in high-stakes applications such as political elections, it is often too coarse to serve as practical criteria for comparing different voting rules in more frequent, low-stakes applications of social choice, such as business decision-making [5], crowdsourcing [34], informational retrieval [33] , meta-search engines [14], recommender systems [51], etc. A decision maker who desires both axioms would find it hard to choose between a voting rule that satisfies CC but not PAR, such as Copeland, and a voting rule that satisfies PAR but not CC, such as plurality. A finer and more quantitative measure of satisfaction of axioms is therefore called for. 35th Conference on Neural Information Processing Systems (NeurIPS 2021).