365体育网站

Advertisement

Springer Nature is making SARS-CoV-2 and COVID-19 research free. View research | View latest news | Sign up for updates

Exploiting polyhedral symmetries in social choice

Abstract

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.

References

  1. 365体育网站Arrow KJ (1951) Social choice and individual values. Cowles Commission monograph no. 12. Wiley, New York

  2. 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

  3. 365体育网站Barvinok A (2008) Integer points in polyhedra. Zurich lectures in advanced mathematics. European Mathematical Society (EMS), Zürich

  4. Berg S, Bjurulf B (1983) A note on the paradox of voting: anonymous preference profiles and May’s formula. Public Choice 40: 307–316

  5. 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)

  6. 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

  7. 365体育网站Beck M, Robins S (2007) Computing the continuous discretely: integer-point enumeration in polyhedra. Undergraduate texts in mathematics. Springer, New York

  8. 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

  9. De Loera JA, Dutra B, Köppe M, Moreinis S, Pinto G, Wu J (2011a) A user guide for latte integrale v1.5.

  10. 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.

  11. 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

  12. 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

  13. 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

  14. Gehrlein WV (1982) Condorcet efficiency of constant scoring rules. Math Soc Sci 2(2): 123–130

  15. 365体育网站Gehrlein WV (2001) Condorcet winners on four candidates with anonymous voters. Econ Lett 71: 335–340

  16. Gehrlein WV (2002) Obtaining representations for probabilities of voting outcomes with effectively unlimited precision integer arithmetic. Soc Choice Welf 19(3): 503–512

  17. 365体育网站Gehrlein WV, Fishburn PC (1976) The probability of the paradox of voting: a computable solution. J Econ Theory 13(1): 14–25

  18. 365体育网站Gehrlein WV, Lepelley D (2011) Voting paradoxes and group coherence Studies in Choice and Welfare. The Condorcet efficiency of voting rules. Springer, Heidelberg

  19. 365体育网站Huang HC, Vincent CH Chua (2000) Analytical representation of probabilities under the IAC condition. Soc Choice Welf 17(1): 143–155

  20. Lepelley D, Louichi A, Smaoui H (2008) On Ehrhart polynomials and probability calculations in voting theory. Soc Choice Welf 30(3): 363–383

  21. 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

  22. Schechter M (1998) Integration over a polyhedron: an application of the Fourier-Motzkin elimination method. Am Math Mon 105(3): 246–251

  23. 365体育网站Schreuders MB (2011) Plurality Voting vs. Plurality Runoff Voting: chances for different outcomes in large elections. Bachelor Thesis, TU Delft

  24. Tabak F (2010) Counting lattice points in polyhedra using the Ehrhart theory, applied to voting theory. Bachelor Thesis, TU Delft

  25. Taylor AD, Pacelli AM (2008) Mathematics and politics. Strategy, voting, power and proof, 2nd edn.. Springer, New York

  26. 365体育网站Verdoolaege S, Bruynooghe M (2008) Algorithms for weighted counting over parametric polytopes, a survey and a practical comparison. Eighth ACES Symposium, Edegem

  27. Wilson MC, Pritchard G (2007) Probability calculations under the IAChypothesis. Math Soc Sci 54(3): 244–256

Software

  1. barvinok by S. Verdoolaege, ver. 0.34 (2011),

  2. Convex by M. Franz, ver. 1.1.3 (2009),

  3. LattE integrale by J.A. DeLoera, M. Köppe et al., ver. 1.5 (2011),

  4. Normaliz365体育网站 by W. Bruns, B. Ichim, and C. Söger, ver. 2.7 (2011),

  5. SymPol365体育网站 by T. Rehn and A. Schürmann, ver. 0.1.4 (2011),

Download references

Author information

Correspondence to Achill Schürmann.

Rights and permissions

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

Keywords

  • Condorcet Winner
  • Polyhedral Cone
  • Candidate Case
  • Vote Situation
  • Plurality Vote