Return to Colloquia & Seminar listing
An algorithm for volumes of polytopes with applications to social choice
Special Events| Speaker: | Winfried Bruns, Universität Osnabrück |
| Location: | 3106 MSB |
| Start time: | Thu, Mar 22 2018, 1:40AM |
We discuss a fast algorithm for the computation of the volume of rational polytopes with few (nonsimplicial) facets. It is based on a recursive approach, originally suggested by Lasserre, that uses descent in the face lattice. For efficient computations in high dimensions it needs a sophisticated implementation that has now been realized in Normaliz.
Probabilities in social choice that are based on the Impartial Anonymous Culture can often be interpreted as volumes of rational polytopes. For 4 candidates these polytopes have dimension 24, and the computation is a challenge. Before the new algorithm had been implemented, Normaliz had to use triangulations and, where possible, symmetrization, which involves integration over rational polytopes. Descent in the face lattice makes all these computations very easy and gives access to many more that hitherto had been inaccessible.