As a side note, the absence of an algebraic structure for these matrices was part of the motivation for our definition of the preference space Pn. Looking at election outcomes more globally, Daughtery et al. introduced the profile space Mn ∼= Qn! to decompose an election according to the actual ballots cast. For example, a ballot for a ranked choice election with n candidates corresponds to a permutation of [n]. Using a basis {vσ | σ ∈ Sn}, where we view σ ∈􏰈Sn a linear ordering of [n], the collection of voter ballots corresponds to the linear combination σ∈Sn aσvσ where aσ is the number of ballots cast with candidate ranking σ. To capture such aggregate behavior of the electorate in the preference space Pn, we would create a linear combination of the preference vectors across the electorate. Simplifying would give a single preference vector that captures the overall utility score for each election outcome. Finally, we note that a preference vector v ∈ Pn is equivalent to the value function as defined in Bradley et al. [3], though our vector space viewpoint is crucial to the methods herein.
1.3 Roadmap
The remainder of this paper is organized as follows. Section 2 develops the voter basis. We prove Theorem 1.5, consider the separability properties of voter basis vectors, and introduce some helpful notation for describing and combining partial outcomes. We then introduce a rank function on P([n]) and use it to construct a nonseparable vector whose coefficients will be useful later on. In Section 3, we prove Theorem 1.3: tree characters are admissible. We conclude in Section 4, suggesting some directions for future research.
2 The Voter Basis
In this section, we formulate and prove some elementary results using bitstring notation, and prove Theorem 1.5, Let XS denote the set of all bitstrings on S ⊂ [n]. Taking S = [n], we define X[n] = Zn2 to be the set of all possible outcomes. Similarly, we define XS to be the set of all partial outcomes on the subset S. The simplest preference order on S arises when a voter is indifferent between all the outcomes.
Definition 2.1. A set S is trivially separable with respect to ≽ if for all xS,yS ∈ XS and all u−S ∈ X−S, we have equation.
Lemma 2.2. If S is trivially separable then −S is separable.
Proof. Consider xS,yS ∈ XS and u−S,v−S ∈ X−S. Suppose that xSu−S ≽ xSv−S. Then ySu−S ∼ xSu−S ≽ xSv−S ∼ ySv−S, so that ySu−S ≽ ySv−S. In other words, our preference on the outcomes on −S is independent of the outcome on S.
Bradley, Hodge and Kilgour showed that set intersections preserve separability. We include a proof as an opportunity to acquaint the reader with the general flow of the bitstring proofs that follow.
Lemma 2.3. If S and T are separable with respect to ≽, then so is S ∩ T . Proof. We partition each bitstring z as euqation.
Suppose that xS∩T u−S∩T ≽ yS∩T u−S∩T , and let v−S∩T be any other bitstring on −S ∩ T . Then euqation.
Therefore S ∩ T is separable with respect to ≽.
We now proving that Vn is a basis for the preference space Pn, and then investigate the separability properties of a voter basis vector vS. The following elementary lemma, suggested to us by Jeremy Martin, leads to a quick proof that Vn is a basis.
Lemma 2.4. Let Wn be the 2n × 2n matrix whose entries are indexed by subsets of [n] and whose (S,T)-th entry is equation.
Then det(W1) = −2 and det(Wn) = 2n2n−1 for n ≥ 2.
Proof. We have equation where we have used the ordering (∅,{1}) and (∅,{1},{2},{1,2}) for the rows and columns of W1 and W2, respectively. Clearly, det(W1) = −2. Elementary row operations on W2 yield euqation and these row addition operations do not change the determinant. Therefore det(W2) = (−2)2 det(W1)2 = 24. The same matrix structure holds for Wn in terms of Wn−1, where we order by subsets of [n − 1] followed by subsets containing element n. Induction gives equation of Theorem 1.5(a). Let wS denote the column of Wn indexed by S ⊂ [n]. Observe that wS = 2vS − v∅ where v∅ = 1 is the all-ones vector. Therefore Vn is a basis for Pn.
It is important to note that the row/column order in this proof is different from the order displayed in Table 1, which adheres to preference relation conventions. The recursive ordering is essential for the inductive proof. Also, we could have used the wS vectors as our basis, but the plentiful zeros of the vS vectors simplify the arguments below. Next, we introduce some terminology and notation for outcomes.
Definition 2.5. The outcome x is even (odd) when the size of the corresponding set |x􏰋| is even (odd). The outcome x is even in A (odd in A) when |x􏰋 ∩ A| is even (odd). Furthermore, x is even in A if and only if the vector entry vA(x) = 1.
For example, consider the set X[3] = Z23. The outcomes 011, 010, 001, and 000 are even in {1} whereas the remaining four outcomes are odd in {1}. The outcomes 000, 001, 110 and 111 are even in {1, 2}, while the other four outcomes are odd in {1, 2}.
Each voter basis vector vA induces a preference ordering in which outcomes that are even in A are preferred to outcomes that are odd in A. The vector v∅ induces the trivial preference ordering (complete indifference). The vector v[n] prefers the even subsets of [n] over the odd subsets. More generally, for nonempty A ⊂ [n], the vector vA partitions the outcomes into a set of 2n−1 preferred outcomes and a set of 2n−1 undesirable outcomes. For example, when n = 3, the voter basis vector v{1} = v100 induces the ordering equation.
When n = 4, the vector v{1,2} = v1100 induces the ordering equation.
The following notation streamlines our nonseparability proofs. Let S be a set that we want to prove is nonseparable. We let 1i and 0i denote that the outcome of element i ∈ S is fixed as 1 or 0, respectively on element i ∈ S. We let 0∗ denote the partial outcome that is all-zero on elements in S that have not already been specified. For example, if S = {1, 2, 3, 4, 5} then xS = 120∗ denotes the outcome 01000. In the proofs below, we will often use this notation to construct sparse partial outcomes xS,yS and u−S,v−S so that xSu−S ≻ ySu−S while xSv−S ≺ yS v−S . As an example of the four resulting outcomes, suppose that n = 6 and let S = {1, 2, 3}. Consider the partial outcomes xS = 0∗ and yS = 120∗ on S and the partial outcomes u−S = 0∗ and v−S = 15 0∗ on −S = {4, 5, 6}. Concatenating each pairing gives euqation, equation, equation, equation.
We are now ready to prove Theorem 1.5(b): the vector VA includes a preference order that is separable on S if and only if A ⊆ S or A ∩ S = ∅. Applying this theorem for n = 4,the preference ordering induced by v{1} (or any other singleton set) induces a completely separable ordering. The preference ordering induced by v{1,2} has character equation.
Finally, v{1,2,3,4} induces a completely nonseparable ordering on [4]. As these examples show, the voter basis vectors have very useful separability properties. Theorem 1.5 (b) reveals the potential of these basis vectors as building blocks for constructing preference orders. In particular, the nonseparable properties of v[n] will be essential for removing unwanted separabilities. of Theorem 1.5(b). Given S ⊂ [n], let x and y be outcomes that are identical on −S. There are three cases to consider; we handle the two separable cases first.
Case 1: A ⊆ S. We decompose x = xSu−S = xAxS−Au−S and y = ySu−S = yAyS−Au−S. We claim that preference relation between these outcomes is independent of the shared binary digits u−S. Indeed, if xA and yA are the same parity, then both or neither are even in A, so that vA(xSu−S) = vA(ySu−S) for all u−S ∈ X−S. If xA and yA are not the same parity, then we may assume that xA is even and yA is odd, so that vA(xSu−S) = 1 > 0 = vA(ySu−S) for all u−S ∈ X−S. Either way, the preference between outcomes x and y depends only on the parities of x and y in A, which is independent of u−S. Therefore, S is separable on vA whenever A ⊂ S.
Case 2: A∩S = ∅. We decompose x and y as x = xSuAu−S−A and y = ySuAu−S−A. The outcomes are identical on A, so their parity in A is the same. Therefore vA(xSuAu−S−A) = vA(ySuAu−S−A) for all u−S ∈ X−S which means that S is trivially separable on vA.
Case 3: equation Note that this includes the case where equation. We construct a pair of outcomes on S that certify that S is not separable. Let s ∈ S ∩ A and let a ∈ A − S. Let xS = 0∗ be the all-zero outcome and let yS = 1s0∗ be the singleton outcome on s. Now let u−S = 0∗ be the all-zero outcome and v−S = 1a0∗ be the singleton outcome on a. We have equation so that our preference between xS and yS depends on the outcome on −S. Therefore the set S is not separable.
We conclude this subsection with a trio of results concerning the entries of vT . The corro- laries will be used frequently in the next section to construct preference vectors with desired properties.
Lemma 2.6. Let S,T ⊂ [n]. Consider outcomes x = xSu−S and y = ySu−S that agree on −S. We have vT (x) = vT (y) if and only if the partial outcomes xS∩T and yS∩T have the same parity.
Proof. The values of the entries vT (x) and vT (y) depend solely on the respective parity of the partial outcomes xS∩TuT−S and yS∩TuT−S. These parities agree if and only if the parities of xS∩T and yS∩T agree.
Corollary 2.7. If T ⊂ −S and the outcomes x = xSu−S and y = ySu−S agree on −S, then vT (x) = vT (y).
Corollary 2.8. If S ⊂ T and the outcomes x = xSu−S and y = ySu−S agree on −S, then vT (x) = vT (y) if and only if xS and yS have the same parity.
Lemma 2.6 highlights that fact that when outcomes agree on some subset U, then the voter basis vectors indexed by subsets of U do not contribute to preference differences between the two outcomes. The two corollaries are analogous to observations we made in the proof of Theorem 1.5(b): the voter basis vector vT is trivially separable on sets disjoint from T and separable on supersets of T.
2.1 A Nonseparable Vector
In this subsection, we introduce a rank function on P([n]) and then use it to construct a preference vector w that induces a total order that is completely nonseparable. The proof is elementary, but is valuable in that it provides an opportunity to evaluate the separabilty of a preference vector, prior to grappling with the more intricate arguments below. Moreover, vectors derived from w will be used in the proof of Theorem 1.3.
Definition 2.9. The rank function ρ : P([n]) → [2n] maps a subset A ⊂ [n] to its position in the ordering of subsets of [n] that lists the sets by increasing set size, and then within a fixed size, lists the sets lexicographically.
For example, when n = 3, our ordering is equation, so that ρ(∅)=1,and ρ({1,3})=6,and so on. Note that,in general,if equation then ρ(A) < ρ(B). In other words, the rank function ρ provides a total ordering on P([n]) that is monotone with respect to set containment.
Lemma 2.10. The preference ordering induced by the vector equation is completely nonseparable. In other words, char(w) = char(≽w) = {∅, [n]}.
Proof. Let A be a nontrival proper subset of [n],and let a ∈ A and b ∈ [n] − A.