Binary choice, subset choice, random utility, and ranking: A unified perspective using the permutahedron

The d-permutahedron Π_d−1⊂R^d is defined as the convex hull of all d-dimensional permutation vectors, namely, vectors whose components are distinct values of a d-element set of integers [d]≡{1,2,…,d}. By construction, Π_d−1 is a convex polytope with d! vertices, each representing a linear order (ranking) on [d], and has dimension dim(Π_d−1)=d−1. This paper provides a review of some well-known properties of a permutahedron, applies the geometric-combinatoric insights to the investigation of the various popular choice paradigms and models by emphasizing their inter-connections, and presents a few new results along this line.Permutahedron provides a natural representation of ranking probability; in fact it is shown here to be the space of all Borda scores on ranking probabilities (also called “voters profiles” in the social choice literature). The following relations are immediate consequences of this identification. First, as all d! vertices of Π_d−1 are equidistant to its barycenter, Π_d−1 is circumscribed by a sphere S^d−2 in a (d−1)-dimensional space, with each spherical point representing an equivalent class of vectors whose components are defined on an interval scale. This property provides a natural expression of the random utility model of ranking probabilities, including the condition of Block and Marschak. Second, Π_d−1 can be realized as the image of an affine projection from the unit cube of dimension d(d−1)/2. As the latter is the space of all binary choice vectors describing probabilities of pairwise comparisons within d objects, Borda scores can be defined on binary choice probabilities through this projective mapping. The result is the Young's formula, now applicable to any arbitrary binary choice vector. Third, Π_d−1 can be realized as a “monotone path polytope” as induced from the lift-up of the projection of the cube onto the line segment [0,d]⊂R¹. As the 2^d vertices of the d-cube are in one-to-one correspondence to all subsets of [d], a connection between the subset choice paradigm and ranking probability is established. Specifically, it is shown here that, in the case of approval voting (AV) with the standard tally procedure (Amer. Pol. Sci. Rev. 72 (1978) 831), under the assumption that the choice of a subset indicates an approval (with equal probability) of all linear orders consistent with that chosen subset, the Brams-Fishburn score is then equivalent to the Borda score on the induced profile. Requiring this induced profile (ranking probability) to be also consistent with the size-independent model of subset choice (J. Math. Psychol. 40 (1996) 15) defines the “core” of the AV Polytope. Finally, Π_d−1 can be realized as a canonical projection from the so-called Birkhoff polytope, the space of rank-position probabilities arising out of the rank-matching paradigm; thus Borda scores can be defined on rank-position probabilities. To summarize, the many realizations of a permutahedron afford a unified framework for describing and relating various ranking and choice paradigms.