A large amount of literature in social choice theory deals with quantifying the probability of certain election outcomes. One way of computing the probability of a specific voting situation under the Impartial Anonymous Culture assumption is via counting integral points in polyhedra. Here, Ehrhart theory can help, but unfortunately the dimension and complexity of the involved polyhedra grows rapidly with the number of candidates. However, if we exploit available polyhedral symmetries, some computations become possible that previously were infeasible. We show this in three well known examples: Condorcet’s paradox, Condorcet efficiency of plurality voting and in Plurality voting vs Plurality Runoff.
This is a preview of subscription content, log in365体育网站 to check access.
Buy single article
365体育网站Instant access to the full article PDF.
Price includes VAT for USA
Subscribe to journal
Immediate online access to all issues from 2019. Subscription will auto renew annually.
This is the net price. Taxes to be calculated in checkout.
365体育网站Arrow KJ (1951) Social choice and individual values. Cowles Commission monograph no. 12. Wiley, New York
Barvinok A (1994) A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math Oper Res 19(4): 769–779
365体育网站Barvinok A (2008) Integer points in polyhedra. Zurich lectures in advanced mathematics. European Mathematical Society (EMS), Zürich
Berg S, Bjurulf B (1983) A note on the paradox of voting: anonymous preference profiles and May’s formula. Public Choice 40: 307–316
365体育网站Baldoni V, Berline N, De Loera JA, Köppe M, Vergne M (2010) Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. Found. Comput. Math. Preprint at arxiv:1011.1602. (to appear)
Baldoni V, Berline N, De Loera JA, Köppe M, Vergne M (2011) How to integrate a polynomial over a simplex. Math Comput 80(273): 297–325
365体育网站Beck M, Robins S (2007) Computing the continuous discretely: integer-point enumeration in polyhedra. Undergraduate texts in mathematics. Springer, New York
Büeler B, Enge A, Fukuda K (2000) Exact volume computation for polytopes: a practical study. Polytopes—combinatorics and computation (Oberwolfach, 1997), DMV Sem., vol. 29, Birkhäuser, Basel, pp. 131–154
De Loera JA, Dutra B, Köppe M, Moreinis S, Pinto G, Wu J (2011a) A user guide for latte integrale v1.5.
De Loera JA, Dutra B, Köppe M, Moreinis S, Pinto G, Wu J (2011b) Software for exact integration of polynomials over polyhedra. Preprint at arxiv:1108.0117.
Dyer ME, Frieze AM (1988) On the complexity of computing the volume of a polyhedron. Soc Ind Appl Math J Comput 17(5): 967–974
Ehrhart E (1967) Sur un problème de géométrie diophantienne linéaire. I. Polyèdres et réseaux. J Reine Angew Math 226: 1–29
Gawrilow E, Joswig M (2000) Polymake: a framework for analyzing convex polytopes. In: Kalai G, Ziegler GM (eds.) Polytopes—combinatorics and computation. Birkhäuser, pp. 43–74
Gehrlein WV (1982) Condorcet efficiency of constant scoring rules. Math Soc Sci 2(2): 123–130
365体育网站Gehrlein WV (2001) Condorcet winners on four candidates with anonymous voters. Econ Lett 71: 335–340
Gehrlein WV (2002) Obtaining representations for probabilities of voting outcomes with effectively unlimited precision integer arithmetic. Soc Choice Welf 19(3): 503–512
365体育网站Gehrlein WV, Fishburn PC (1976) The probability of the paradox of voting: a computable solution. J Econ Theory 13(1): 14–25
365体育网站Gehrlein WV, Lepelley D (2011) Voting paradoxes and group coherence Studies in Choice and Welfare. The Condorcet efficiency of voting rules. Springer, Heidelberg
365体育网站Huang HC, Vincent CH Chua (2000) Analytical representation of probabilities under the IAC condition. Soc Choice Welf 17(1): 143–155
Lepelley D, Louichi A, Smaoui H (2008) On Ehrhart polynomials and probability calculations in voting theory. Soc Choice Welf 30(3): 363–383
365体育网站Rehn T, Schürmann A (2010) C++ tools for exploiting polyhedral symmetries. Mathematical Software ICMS 2010. Lecture Notes in computer science, vol. 6327. Springer, Berlin, pp. 295–298
Schechter M (1998) Integration over a polyhedron: an application of the Fourier-Motzkin elimination method. Am Math Mon 105(3): 246–251
365体育网站Schreuders MB (2011) Plurality Voting vs. Plurality Runoff Voting: chances for different outcomes in large elections. Bachelor Thesis, TU Delft
Tabak F (2010) Counting lattice points in polyhedra using the Ehrhart theory, applied to voting theory. Bachelor Thesis, TU Delft
Taylor AD, Pacelli AM (2008) Mathematics and politics. Strategy, voting, power and proof, 2nd edn.. Springer, New York
365体育网站Verdoolaege S, Bruynooghe M (2008) Algorithms for weighted counting over parametric polytopes, a survey and a practical comparison. Eighth ACES Symposium, Edegem
Wilson MC, Pritchard G (2007) Probability calculations under the IAChypothesis. Math Soc Sci 54(3): 244–256
barvinok by S. Verdoolaege, ver. 0.34 (2011),
Convex by M. Franz, ver. 1.1.3 (2009),
LattE integrale by J.A. DeLoera, M. Köppe et al., ver. 1.5 (2011),
Normaliz365体育网站 by W. Bruns, B. Ichim, and C. Söger, ver. 2.7 (2011),
SymPol365体育网站 by T. Rehn and A. Schürmann, ver. 0.1.4 (2011),
About this article
Cite this article
Schürmann, A. Exploiting polyhedral symmetries in social choice. Soc Choice Welf 40, 1097–1110 (2013). http://doi.org/10.1007/s00355-012-0667-1
- Condorcet Winner
- Polyhedral Cone
- Candidate Case
- Vote Situation
- Plurality Vote