The Voter Basis and the Admissibility of Tree Characters

摘要

Let greater than or similar to be a total order on the power set of a finite set [n]. A subset S subset of [n] is separable when for any X,Y subset of S and any Z subset of [n] - S, the ordering of X and Y is the same as the ordering of X boolean OR Z and Y boolean OR Z. The character of a preference order is the collection of all separable subsets. Motivated by questions in the theories of voting, marketing and social choice, the admissibility problem asks which collections C subset of P([n]) can arise as characters of preference orders. We introduce a linear algebraic technique to construct preference orders. Each vector in our 2(n)-dimensional voter basis induces a simple preference preorder (where ties are allowed) with nice separability properties. Given any collection C subset of P([n]) that contains both theta and [n], and such that all pairs of subsets are either nested or disjoint, we use the voter basis to construct a preference order with character C.