×

On Ehrhart polynomials and probability calculations in voting theory. (English) Zbl 1149.91028

The function of \(n\) that gives the number of lattice points in the dilation \(nP\) of a rational polytope \(P\) was studied by E. Ehrhart [see for instance, Polynômes arithmétiques et méthode des polyedres en combinatoire. International Series of Numerical Mathematics. Vol. 35. Basel - Stuttgart: Birkhäuser Verlag. (1977; Zbl 0337.10019)], who proved that the function is given by a polynomial if \(P\) is a lattice polytope and a cyclically repeating list of polynomials in general. Since then, the Ehrhart polynomials have been studied by many researchers; for an exposition see [A. Barvinok, “Integer points in polyhedra,” Zürich Lectures in Advanced Mathematics. Zürich: European Mathematical Society (EMS). (2008; Zbl 1154.52009)].
Such mathematical techniques are important in the theory of voting because voting profiles of particular types are naturally identified with lattice points in certain polytopes. In the paper under review the authors give a brief exposition of the Ehrhart theory and associated algorithms of Barvinok, Clauss and Loechner, and they observe that these ideas and techniques underlie recent work of H. C. Huang and V. C. H. Chua [Soc. Choice Welfare 17, No. 1, 143–155 (2000; Zbl 1069.91529)] and W. V. Gehrlein [Soc. Choice Welfare 19, No. 3, 503–512 (2002; Zbl 1072.91530)]. To illustrate the usefulness of the Clauss and Barvinok algorithms, the authors use them to analyze voting profiles that exhibit three specific properties. In one of these analyses they show that for three-candidate elections with many voters, slightly more than half of the voting situations allow strategic manipulation of the Borda count by coalitions; this result confirms a prediction based on small examples given by P. Favardin et al. [Rev. Econ. Des. 7, No. 2, 213–228 (2002; Zbl 1048.91040)].

MSC:

91B12 Voting theory
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
11J25 Diophantine inequalities

Software:

PolyLib; LattE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barvinok A (1993) A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. In: 34th annual symposiumon foundations of computer science, November 1993. IEEE, pp. 566–572
[2] Barvinok A, Pommersheim J (1999) An algorithmic theory of lattice points in polyhedra. New Perspect Algebraic combinat 38:91–147 · Zbl 0940.05004
[3] Brion M (1998) Points entiers dans les polyhèdres convexes. Ann Sci École Normale Supérieure 21(4):653–663
[4] Clauss P, Loechner V (1996) Parametric analysis of polyhedral iteration spaces. In: Proceedings of the international conference on application specific array processors, ASAP’96, August
[5] Clauss P, Loechner V, Wilde D (1997) Deriving formulae to count solutions to parameterized linear systems using ehrhart polynomials: applications to the analysis of nested-loop programs. Technical report
[6] De Loera JA, Hemmecke R, Tauzer J, Yoshida R (2004) Effective lattice point counting in rational convex polytopes. J Symb Comput 38:1273–1302 · Zbl 1137.52303 · doi:10.1016/j.jsc.2003.04.003
[7] Ehrhart E (1962) Sur les polyhèdres rationnels homothétiques à n dimensions. C R Acad Sci Paris 254:616–618 · Zbl 0100.27601
[8] Ehrhart E (1967) Sur un problème de géométrie diophantienne linéaire. PhD thesis. J R A Math 226:1–49
[9] Ehrhart E (1977) Polynomes arithmétiques et méthodes des polyhèdres en combinatoire. International series of numerical mathematics, vol 35. Birkhhauser, Basles/Stuttgart 35
[10] Favardin P, Lepelley D (2006) Some further results on the manipulability of social choices rules. Soc Choice Welf 26:485–509 · Zbl 1098.91032 · doi:10.1007/s00355-006-0106-2
[11] Favardin P, Lepelley D, Serais J (2002) Borda rule, Copeland method and strategic manipulation. Rev Econ Des 7:213–228 · Zbl 1048.91040
[12] Gehrlein W (2002) Obtaining representations for probabilities of voting outcomes with effectively unlimited precision integer arithmetic. Soc Choice Welf 19:503–512 · Zbl 1072.91530 · doi:10.1007/s003550100127
[13] Gehrlein W (2004) Consistency of measures of social homogeneity: a connection with proximity to single peaked preferences. Quality Quantity 38:147–171 · doi:10.1023/B:QUQU.0000019391.85976.65
[14] Gehrlein W (2006a) Probabilities of election outcomes with two parameters: The relative impact of unifying and polarizing candidates. Rev Econ Des 9:317–336 · Zbl 1124.91322
[15] Gehrlein W (2006b) The sensitivity of weight selection for scoring rules to profile proximity to single peaked preferences. Soc Choice Welf 26:191–208 · Zbl 1132.91397 · doi:10.1007/s00355-006-0084-4
[16] Gehrlein W, Fishburn P (1976) Condorcet’s paradox and anonymous preference profiles. Public Choice 26:1–18 · doi:10.1007/BF01725789
[17] Huang H, Chua VCH (2000) Analytical representation of probabilities under the IAC condition. Soc Choice Welf 17:143–155 · Zbl 1069.91529 · doi:10.1007/s003550050011
[18] Lepelley D, Mbih B (1994) The vulnerability of four social choice functions to coalitional manipulation of preferences. Soc Choice Welf 11:253–265 · Zbl 0822.90006 · doi:10.1007/BF00193810
[19] Loechner V (1999) Polylib: A library for manipulating parameterized polyhedra. Technical Report, ICPS, Université Louis Pasteur de Strasbourg, France, March
[20] Loechner V, Wilde D (1997) Prameterized polyhedra and their vertices. Int J Parallel Programm 25(6):525–549 · doi:10.1023/A:1025117523902
[21] Pritchard G, Wilson M (2005) Exact results on manipulability of positional voting rules. Technical report, University of Auckland, December · Zbl 1180.91097
[22] Verdoolaege S, Beyls K, Bruynooghe M, Seghir R, Loechner V Analytical computation of ehrhart polynomials and its applications for embedded systems. In: Workshop on optimizations for DSP and embedded systems, in conjunction with IEEE/ACM international symposium on code generation, March 2004 · Zbl 1123.68023
[23] Verdoolaege S, Seghir R, Beyls K, Loechner V, Bruynooghe M Analytical computation of ehrhart polynomials: Enabling more compiler analysis and optimizations. In: Proceedings of international conference on compilers, architecture, and synthesis for embedded systems, September 2004b, Washington D.C, pp. 248–258
[24] Verdoolaege S, Woods K, Bruynooghe M, Cools R (2005) Computation and manipulation of enumerators of integer projections of parametric polytopes. Technical Report CW 392, Katholieke Universiteit Leuven, Departement of Computer Sciences, Celestijnenlaan 200A–B-3001 Heverlee, Belgium, March
[25] Wilson M, Pritchard G (2006) Probability calculations under the IAC hypothesis. Working paper · 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. 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.