Polytope volume by descent in the face lattice and applications in social choice
- PDF / 540,417 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 38 Downloads / 149 Views
Polytope volume by descent in the face lattice and applications in social choice Winfried Bruns1 · Bogdan Ichim2,3 Received: 19 August 2018 / Accepted: 28 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract We describe the computation of polytope volumes by descent in the face lattice, its implementation in Normaliz, and the connection to reverse-lexicographic triangulations. The efficiency of the algorithm is demonstrated by several high dimensional polytopes of different characteristics. Finally, we present an application to voting theory where polytope volumes appear as probabilities of certain paradoxa. Keywords Rational polytope · Face lattice · Volume · Triangulation · Voting theory Mathematics Subject Classification 52B20 · 13F20 · 14M25 · 91B12
1 Introduction The volume of a polytope is a geometric magnitude that has been studied since antiquity—formulas for the area of polygons or the volume of common 3-dimensional polytopes like pyramids were known in Babylonian and Egyptian mathematics. From a modern viewpoint one can say that these formulas are recursive: they reduce volume computations to the measurement of lengths.
The second author was partially supported by a grant of Romanian Ministry of Research and Innovation, CNCS - UEFISCDI, Project Number PN-III-P4-ID-PCE-2016-0157, within PNCDI III.
B
Bogdan Ichim [email protected]; [email protected] Winfried Bruns [email protected]
1
FB Mathematik/Informatik, Universität Osnabrück, 49069 Osnabrück, Germany
2
Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei 14, 010014 Bucharest, Romania
3
Simion Stoilow Institute of Mathematics of the Romanian Academy, Research Unit 5, C.P. 1-764, 010702 Bucharest, Romania
123
W. Bruns, B. Ichim
In toric algebra and geometry, volumes are almost a synonym for multiplicities, defined as leading coefficients of Hilbert (quasi)polynomials. For this classical connection see Teissier [34] or Bruns and Gubeladze [4, Section 6.E]. The package Normaliz [7] has contained options for the computation of Hilbert series and multiplicities from its beginnings. Until recently, the only approach to volumes was based on lexicographic (or placing) triangulations: the volume of a polytope is obtained as sum of simplex volumes, and the volume of a simplex is essentially computed as a determinant. (We refer the reader to [4] for unexplained algebraic notions and to Sect. 2 for geometric terminology.) The algorithm has been improved in several steps; see [6,8,10] for a description of the present state and [11] for a refined version computing integrals. An attractive application of polytope volumes is probabilities of certain events in voting theory where results of elections with n candidates can be identified with lattice points in the positive orthant of R N , N = n!. Several classical phenomena, most prominently the Condorcet paradox, can be described by homogeneous linear inequalities. In a suitable probabilistic model
Data Loading...
