×

zbMATH — the first resource for mathematics

Computations of volumes and Ehrhart series in four candidates elections. (English) Zbl 1430.91039
Summary: We describe several analytical results obtained in four candidates social choice elections under the assumption of the impartial anonymous culture. These include the Condorcet and Borda paradoxes, as well as the Condorcet efficiency of plurality voting with runoff. The computations are done by Normaliz. It finds precise probabilities as volumes of polytopes and counting functions encoded as Ehrhart series of polytopes.

MSC:
91B12 Voting theory
91B14 Social choice
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
Software:
CoCoA; LattE; Normaliz; R
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbott, J., Bigatti, A. M., & Lagorio, G. (2018). CoCoA-5: A system for doing Computations in Commutative Algebra. http://cocoa.dima.unige.it.
[2] Almendra, V., & Ichim, B. (2018). jNormaliz: A graphical interface for Normaliz. www.math.uos.de/normaliz.
[3] Avis, D. (2018). lrs: A revised implementation of the reverse search vertex enumeration algorithm. http://cgm.cs.mcgill.ca/ avis/C/lrs.html. · Zbl 0960.68171
[4] Baldoni, V., Berline, N., De Loera, J. A., Dutra, B., Köppe, M., Moreinis, S., Pinto, G., Vergne, M., & Wu, J. (2013). A user’s guide for LattE integrale v1.7.2, 2013. Software package LattE is available at http://www.math.ucdavis.edu/ latte/.
[5] Baldoni, V., Berline, N., De Loera, J. A., Köppe, M., & Vergne, M. (2011). How to integrate a polynomial over a simplex. Mathematics of Computation, 80, 297-325. · Zbl 1216.68120
[6] Baldoni, V., Berline, N., De Loera, J. A., Köppe, M., & Vergne, M. (2012). Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. Foundations of Computational Mathematics, 12, 435-469. · Zbl 1255.05006
[7] Brandt, F., Geist, C., & Strobel, M. (2016). Analyzing the practical relevance of voting paradoxes via Ehrhart theory, computer simulations, and empirical data. In Proceedings of the 2016 international conference on autonomous agents and multiagent systems (pp. 385-393).
[8] Brandt, F., Hofbauer, J., & Strobel, M. (2019). Exploring the no-show paradox for condorcet extensions using Ehrhart theory and computer simulations. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). IFAAMAS.
[9] Bruns, W., & Gubeladze, J. (2009). Polytopes, rings and K-theory. Berlin: Springer. · Zbl 1168.13001
[10] Bruns, W., Hemmecke, R., Ichim, B., Köppe, M., & Söger, C. (2011). Challenging computations of Hilbert bases of cones associated with algebraic statistics. Experimental Mathematics, 20, 25-33. · Zbl 1273.13052
[11] Bruns, W., & Ichim, B. (2010). Normaliz: Algorithms for affine monoids and rational cones. Journal of Algebra, 324, 1098-1113. · Zbl 1203.13033
[12] Bruns, W., & Ichim, B. (2018). Polytope volume by descent in the face lattice and applications in social choice. Preprint arXiv:1807.02835.
[13] Bruns, W., Ichim, B., Römer, T., Sieg, R., & Söger, C. (2018). Normaliz: Algorithms for rational cones and affine monoids. http://normaliz.uos.de.
[14] Bruns, W., Ichim, B., & Söger, C. (2016). The power of pyramid decomposition in Normaliz. Journal of Symbolic Computation, 74, 513-536. · Zbl 1332.68298
[15] Bruns, W., & Koch, R. (2001). Computing the integral closure of an affine semigroup. Universitatis Iagellonicae Acta Mathematica, 39, 59-70. · Zbl 1006.20045
[16] Bruns, W.; Sieg, R.; Söger, C.; Böckle, G. (ed.); Decker, W. (ed.); Malle, G. (ed.), Normaliz 2013-2016, 123-146 (2017), Cham · Zbl 1400.52012
[17] Bruns, W., & Söger, C. (2015). Generalized Ehrhart series and integration in Normaliz. Journal of Symbolic Computation, 68, 75-86. · Zbl 1320.52018
[18] Chevalier de Borda, J.-C. (1781). Mémoire sur les élections au scrutin. Histoire de’Académie Royale Des Science, 102, 657-665.
[19] De Loera, J. A., Dutra, B., Köppe, M., Moreinis, S., Pinto, G., & Wu, J. (2013). Software for exact integration of polynomials over polyhedra. Computational Geometry, 46, 232-252. · Zbl 1259.65054
[20] El Ouafdi, A., Lepelley, D., & Smaoui, H. (2018). Probabilities of electoral outcomes in four-candidate elections. Preprint https://doi.org/10.13140/RG.2.2.27775.87201.
[21] Gehrlein, W. V. (2001). Condorcet winners on four candidates with anonymous voters. Economics Letters, 71, 335-340. · Zbl 0983.91019
[22] Gehrlein, W. V., & Fishburn, P. (1976). Condorcet’s paradox and anonymous preference profiles. Public Choice, 26, 1-18.
[23] Gehrlein, W. V., & Lepelley, D. (2010). On the probability of observing Borda’s paradox. Social Choice and Welfare, 35, 1-23. · Zbl 1230.91037
[24] Gehrlein, W. V., & Lepelley, D. (2011). Voting paradoxes and group coherence. Berlin: Springer. · Zbl 1252.91001
[25] Gehrlein, W. V., & Lepelley, D. (2017). Elections, voting rules and paradoxical outcomes. Berlin: Springer. · Zbl 1429.91003
[26] Lepelley, D., Louichi, A., & Smaoui, H. (2008). On Ehrhart polynomials and probability calculations in voting theory. Social Choice and Welfare, 30, 363-383. · Zbl 1149.91028
[27] Marquis de Condorcet, N. (1785). Éssai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. Paris: Imprimerie Royale.
[28] R Core Team. (2013). R: A language and environment for statistical computing. Vienna: R Foundation for Statistical Computing. http://www.R-project.org/
[29] Schürmann, A. (2013). Exploiting polyhedral symmetries in social choice. Social Choice and Welfare, 40, 1097-1110. · Zbl 1288.91076
[30] Wilson, M. C., & Pritchard, G. (2007). Probability calculations under the IAC hypothesis. Mathematical Social Sciences, 54, 244-256. · Zbl 1141.91379
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.