×

An analysis of random elections with large numbers of voters. (English) Zbl 1489.91097

Summary: In an election in which each voter ranks all of the candidates, we consider the head-to-head results between each pair of candidates and form a labeled directed graph, called the margin graph, which contains the margin of victory of each candidate over each of the other candidates. A central issue in developing voting methods is that there can be cycles in this graph, where candidate \(\mathsf{A}\) defeats candidate \(\mathsf{B},\mathsf{B}\) defeats \(\mathsf{C}\), and \(\mathsf{C}\) defeats \(\mathsf{A}\). It is known that such cycles are unlikely to occur. Under the impartial culture assumption, in a random election with three candidates and a very large number of voters there is a 91.23% chance of avoiding a cycle. By studying the geometry of the space of random elections, we give a mathematical explanation of why this is the case. Our main result is that margin graphs that are more cyclic in a certain precise sense are less likely to occur. This connects the probabilistic study of voting methods to Zwicker’s analysis of Condorcet’s paradox in terms of cycles and cuts.

MSC:

91B12 Voting theory
91B14 Social choice

Software:

Orthants; R

References:

[1] Biggs, Norman, (Algebraic graph theory. Algebraic graph theory, Cambridge Mathematical Library (1993), Cambridge University Press: Cambridge University Press Cambridge), viii+205 · Zbl 0797.05032
[2] Bjurulf, Bo H.; Niemi, Richard G., Strategic voting in Scandinavian parliaments, Scand. Political Stud., 1, 1, 5-22 (1978)
[3] Craig, Peter, A new reconstruction of multivariate normal orthant probabilities, J. R. Stat. Soc. Ser. B, 70, 1, 227-243 (2008) · Zbl 05563352
[4] Craig, Peter; Miwa, Tetsuhisa, Orthants: Multivariate normal orthant probabilities (2012), R package version 1.5
[5] David, F. N.; Mallows, C. L., The variance of Spearman’s rho in normal samples, Biometrika, 48, 19-28 (1961) · Zbl 0133.12003
[6] Debord, Bernard, Caractérisation des matrices des préférences nettes et méthodes d’agrégation associées, Math. Sci. Hum., 97, 5-17 (1987) · Zbl 0619.90005
[7] Deemen, Adrian Van, On the empirical relevance of Condorcet’s paradox, Publ. Choice, 158, 3/4, 311-330 (2014)
[8] DeMeyer, Frank; Plott, Charles R., The probability of a cyclical majority, Econometrica, 38, 2, 345-354 (1970)
[9] Diss, Mostapha; Doghmi, Ahmed, Multi-winner scoring election methods: Condorcet consistency and paradoxes, Publ. Choice, 169, 1, 97-116 (2016)
[10] (Diss, Mostapha; Merlin, Vincent, Evaluating Voting Systems with Probability Models: Essays by and in Honor of William Gehrlein and Dominique Lepelley (2021), Springer: Springer Cham) · Zbl 1477.91003
[11] Donder, Philippe De; Breton, Michel Le; Truchon, Michel, Choosing from a weighted tournament, Math. Social Sci., 40, 85-109 (2000) · Zbl 0966.91029
[12] Dutta, Bhaskar; Laslier, Jean-Francois, Comparison functions and choice correspondences, Soc. Choice Welf., 16, 513-532 (1999) · Zbl 1066.91535
[13] El Ouafdi, Abdelhalim; Moyouwou, Issofa; Smaoui, Hatem, IAC probability calculations in voting theory: Progress report, (Diss, Mostapha; Merlin, Vincent, Evaluating Voting Systems With Probability Models: Essays By and in Honor of William Gehrlein and Dominique Lepelley (2021), Springer International Publishing: Springer International Publishing Cham), 399-416 · Zbl 1504.91089
[14] Garman, Mark B.; Kamien, Morton I., The paradox of voting: Probability calculations, Behavioral Science, 13, 4, 306-316 (1968)
[15] Gehrlein, William V., Probability calculations for transitivity of the simple majority rule, Econom. Lett., 27, 4, 311-315 (1988) · Zbl 1328.91071
[16] Gehrlein, William V., The probability of intransitivity of pairwise comparisons in individual preference, Math. Social Sci., 17, 1, 67-75 (1989) · Zbl 0675.90003
[17] Gehrlein, William V., 1999. Approximating the probability that a Condorcet winner exists. In: Proceedings of International Decision Sciences Institute. pp. 626-628.
[18] Gehrlein, William V., (Condorcet’s Paradox. Condorcet’s Paradox, Theory and Decision Library C (2006), Springer) · Zbl 1122.91027
[19] Gehrlein, William V.; Fishburn, Peter C., The probability of the paradox of voting: A computable solution, J. Econ. Theory, 13, 1, 14-25 (1976) · Zbl 0351.90002
[20] Gehrlein, William V.; Fishburn, Peter C., Probabilities of election outcomes for large electorates, J. Econ. Theory, 19, 1, 38-49 (1978) · Zbl 0399.90007
[21] Gehrlein, William V.; Fishburn, Peter C., Proportions of profiles with a majority candidate, Computers & Mathematics With Applications, 5, 2, 117-124 (1979) · Zbl 0408.90011
[22] Gehrlein, William V.; Lepelley, Dominique, Voting Paradoxes and Group Coherence: The Condorcet Efficiency of Voting Rules (2011), Springer · Zbl 1252.91001
[23] Gehrlein, William V.; Lepelley, Dominique, Elections, Voting Rules and Paradoxical Outcomes (2017), Springer · Zbl 1429.91003
[24] Guilbaud, Georges-Théodule, Les théories de l’intérêt général et le problème logique de l’agrégation, Econ. Appl., 5, 501-584 (1952)
[25] Holliday, Wesley H., Pacuit, Eric, Probabilistic stability for winners in voting with even-chance tiebreaking, preprint. · Zbl 07450033
[26] Holliday, Wesley H., Pacuit, Eric, Split cycle: A new Condorcet consistent voting method independent of clones and immune to spoilers, https://arxiv.org/abs/2004.02350.
[27] Holliday, Wesley H.; Pacuit, Eric, Axioms for defeat in democratic elections, J. Theor. Politics, 33, 4, 475-524 (2021)
[28] Kramer, Gerald H., A dynamical model of political equilibrium, J. Econ. Theory, 16, 2, 310-334 (1977) · Zbl 0404.90005
[29] Kurrild-Klitgaard, Peter, An empirical example of the Condorcet paradox of voting in a large electorate, Publ. Choice, 107, 1/2, 135-145 (2001)
[30] Lepelley, Dominique; Louichi, Ahmed; Valognes, Fabrice, Computer simulations of voting systems, Adv. Complex Syst., 03, 01n04, 181-194 (2000)
[31] Mitchell, Douglas W.; Trumbull, William N., Frequency of paradox in a common N-winner voting scheme, Publ. Choice, 73, 1, 55-69 (1992)
[32] Niemi, Richard G.; Weisberg, Herbert F., A mathematical solution for the probability of the paradox of voting, Behavioral Science, 13, 4, 317-323 (1968)
[33] R Core Team, R: A Language and Environment for Statistical Computing (2013), R Foundation for Statistical Computing: R Foundation for Statistical Computing Vienna, Austria, ISBN 3-900051-07-0
[34] Ribando, Jason M., Measuring solid angles beyond dimension three, Discrete Comput. Geom., 36, 3, 479-487 (2006) · Zbl 1101.65021
[35] Riker, William H., The paradox of voting and congressional rules for voting on amendments, Am. Political Sci. Rev., 52, 2, 349-366 (1958)
[36] Schulze, Markus, A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method, Soc. Choice Welf., 36, 2, 267-303 (2011) · Zbl 1232.91185
[37] Sevcik, K. E., Exact Probabilities of a Voter’s Paradox Through Seven Issues and Seven Judges (1969), University of Chicago Institute For Computer Research Quarterly Report 22, Sec. III-B
[38] Simpson, Paul B., On defining areas of voter choice: Professor Tullock on stable voting, Quart. J. Econ., 83, 3, 478-490 (1969)
[39] Stensholt, Eivind, Voteringens kvaler: flyplassaken i stortinget 8. Oktober 1992, SosialøKonomen, 4, 28-40 (1999)
[40] Tideman, T. Nicolaus, Independence of clones as a criterion for voting rules, Soc. Choice Welf., 4, 185-206 (1987) · Zbl 0624.90005
[41] Tong, Y. L., (The Multivariate Normal Distribution. The Multivariate Normal Distribution, Springer Series in Statistics (1990), Springer-Verlag: Springer-Verlag New York), xiv+271 · Zbl 0689.62036
[42] Truchon, M., Figure skating and the theory of social choice (1998), Technical Report, Laval-Recherche en Politique Economique
[43] van der Vaart, A. W., (Asymptotic Statistics. Asymptotic Statistics, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 3 (1998), Cambridge University Press: Cambridge University Press Cambridge), xvi+443 · Zbl 0910.62001
[44] Young, H. P., An axiomatization of Borda’s rule, J. Econ. Theory, 9, 1, 43-52 (1974)
[45] Zwicker, William S., The voters’ paradox, spin, and the Borda count, Math. Social Sci., 22, 3, 187-227 (1991) · Zbl 0742.90012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.