Mathematics Colloquia and Seminars

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.