An Approval-Voting Polytope for Linear Orders.

A probabilistic model of approval voting on n alternatives generates a collection of probability distributions on the family of all subsets of the set of alternatives. Focusing on the size-independent model proposed by Falmagne and Regenwetter, we recast the problem of characterizing these distributions as the search for a minimal system of linear equations and inequalities for a specific convex polytope. This approval-voting polytope, with n! vertices in a space of dimension 2(n), is proved to be of dimension 2(n)-n-1. Several families of facet-defining linear inequalities are exhibited, each of which has a probabilistic interpretation. Some proofs rely on special sequences of rankings of the alternatives. Although the equations and facet-defining inequalities found so far yield a complete minimal description when n<=4 (as indicated by the PORTA software), the problem remains open for larger values of n.