Polytope volume by descent in the face lattice and applications in social choice (Q823891)

In toric geometry, volumes of polytopes are defined as the leading coefficients of the Hilbert (quasi) polynomials. It can be also computed precisely by recursion to faces of the polytope. Before this paper, the only computational approach for volumes was based on lexicographic (or placing) triangulations. This means the volume of a polytope is calculated as sum of simplex volumes. It turns out that for certain complicated or higher-dimensional calculations the approach of lexicographic triangulations proves to be insufficient. Thus the authors implement the so-called descent algorithm in Normaliz for the volume of a polytope that is based on descent in the face lattice of the polytope. They also explore the connection of the algorithm to reverse-lexicographic triangulations. The authors also demonstrate the efficiency of their algorithm in the field of voting theory. They explain that their algorithm was motivated by many challanges of computations in this area. In voting theory, the results of the election with \(n\) candidates is identified with lattice points in the positive orthant \(\mathbb{R}^{n!}\). Moreover, the probability of a certain event with large number of voters can be computed as lattice normalized volume of a rational polytope. It is quoted in [\textit{A. El Ouafdi} et al., Theory Decis. 88, No. 2, 205--229 (2020; Zbl 1433.91065)] that their algorithm in Normaliz is the most efficient one to obtain the IAC probabilities of electoral outcomes when more than three alternatives are in contention.