Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputations of volumes and Ehrhart series in four candidates elections
62
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We describe several experimental results obtained in four candidates social choice elections. These include the Condorcet and Borda paradoxes, as well as the Condorcet efficiency of plurality voting with runoff. The computations are done by Normaliz. It finds precise probabilities as volumes of polytopes and counting functions encoded as Ehrhart series of polytopes.
rate research
Read More
We describe several analytical results obtained in five candidates social choice elections under the assumption of the Impartial Anonymous Culture. These include the Condorcet and Borda paradoxes, as well as the Condorcet efficiency of plurality, negative plurality and Borda voting, including their runof
A lattice polytope is free (or empty) if its vertices are the only lattice points it contains. In the context of valuation theory, Klain (1999) proposed to study the functions $alpha_i(P;n)$ that count the number of free polytopes in $nP$ with $i$ vertices. For $i=1$, this is the famous Ehrhart polynomial. For $i > 3$, the computation is likely impossible and for $i=2,3$ computationally challenging. In this paper, we develop a theory of coprime Ehrhart functions, that count lattice points with relatively prime coordinates, and use it to compute $alpha_2(P;n)$ for unimodular simplices. We show that the coprime Ehrhart function can be explicitly determined from the Ehrhart polynomial and we give some applications to combinatorial counting.
We generalize valuations on polyhedral cones to valuations on fans. For fans induced by hyperplane arrangements, we show a correspondence between rotation-invariant valuations and deletion-restriction invariants. In particular, we define a characteristic polynomial for fans in terms of spherical intrinsic volumes and show that it coincides with the usual characteristic polynomial in the case of hyperplane arrangements. This gives a simple deletion-restriction proof of a result of Klivans-Swartz. The metric projection of a cone is a piecewise-linear map, whose underlying fan prompts a generalization of spherical intrinsic volumes to indicator functions. We show that these intrinsic indicators yield valuations that separate polyhedral cones. Applied to hyperplane arrangements, this generalizes a result of Kabluchko on projection volumes.
Let $P(b)subset R^d$ be a semi-rational parametric polytope, where $b=(b_j)in R^N$ is a real multi-parameter. We study intermediate sums of polynomial functions $h(x)$ on $P(b)$, $$ S^L (P(b),h)=sum_{y}int_{P(b)cap (y+L)} h(x) mathrm dx, $$ where we integrate over the intersections of $P(b)$ with the subspaces parallel to a fixed rational subspace $L$ through all lattice points, and sum the integrals. The purely discrete sum is of course a particular case ($L=0$), so $S^0(P(b), 1)$ counts the integer points in the parametric polytopes. The chambers are the open conical subsets of $R^N$ such that the shape of $P(b)$ does not change when $b$ runs over a chamber. We first prove that on every chamber of $R^N$, $S^L (P(b),h)$ is given by a quasi-polynomial function of $bin R^N$. A key point of our paper is an analysis of the interplay between two notions of degree on quasi-polynomials: the usual polynomial degree and a filtration, called the local degree. Then, for a fixed $kleq d$, we consider a particular linear combination of such intermediate weighted sums, which was introduced by Barvinok in order to compute efficiently the $k+1$ highest coefficients of the Ehrhart quasi-polynomial which gives the number of points of a dilated rational polytope. Thus, for each chamber, we obtain a quasi-polynomial function of $b$, which we call Barvinoks patched quasi-polynomial (at codimension level $k$). Finally, for each chamber, we introduce a new quasi-polynomial function of $b$, the cone-by-cone patched quasi-polynomial (at codimension level $k$), defined in a refined way by linear combinations of intermediate generating functions for the cones at vertices of $P(b)$. We prove that both patched quasi-polynomials agree with the discrete weighted sum $bmapsto S^0(P(b),h)$ in the terms corresponding to the $k+1$ highest polynomial degrees.
The univariate Ehrhart and $h^*$-polynomials of lattice polytopes have been widely studied. We describe methods from toric geometry for computing multivaria
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
