A conjecture on the construction of orderings by Borda’s rule

Abstract

For a fixed number n of individuals, and a given weak ordering of m alternatives, we ask: is there a profile of n preferences that maps to that ordering under Borda’s rule? Evidence is presented for a conjectured answer, which is settled except for the case of odd n and even m.

1 Introduction

In an important early paper in modern social choice theory, McGarvey (1953), showed the following: given a set X of m alternatives, and an arbitrary complete and reflexive relation R on X, there exists a number n, and a profile of strong preferences for n individuals, such that the relation “defeats or ties by simple majority voting” is identical with R.

McGarvey’s result has been extended in the later literature. Stearns (1959) gave more information about the number n required, although almost nothing is known even now about the range of simple majority voting for fixed n. Hollard and Le Breton (1996) have considered separable preferences and Mala (1999) has treated $\lambda$-majorities. Gibson and Powers (2012) use a result of Saari (1989) to extend McGarvey’s theorem to the plurality social choice mechanism. Gilboa (1990) and Shepardson and Tovey (2009) consider what super-majority rules can yield all pairwise voting outcomes.

Analogous work has been done by Echenique and Ivanov (2011), Sprumont (2001) and Qi (2015a) establishing, for small fixed n, conditions on a given quasi-order such that that quasi-order is the Pareto ranking at some profile on n individuals. The same question for any fixed number n was initially raised by Dushnik and Miller (1941) (regarding partial orders) and was recently revisited by Qi (2015b).

This paper addresses such questions about relations generated by the Borda’s rule, for fixed n. We present evidence for a conjecture that, for fixed $n\ge 2$, any weak ordering of the alternatives is in the range of Borda’s rule unless, for odd n, there is a barrier presented by the parity of the total Borda score.

2 Notation and terminology

We begin with a finite set $N=\{1,\ldots ,n\}$ of individuals, $n\ge 2$, and a finite set X of alternatives, with $\left| X\right| =m\ge 2$. A binary relation R on X is a non-empty subset of the Cartesian product, $X\times X$; if $(x,y)\in R$, we will usually write xRy. Relation R is

• 1. reflexive if xRx for all x in X;

• 2. asymmetric if for all x, y in X: xRy and yRx imply $x=y$;

• 3. complete if for all for all x, y in X such that $x\ne y$, either xRy or yRx;

• 4. transitive if xRy and yRz imply xRz for all x, y, z in X.

Relation R is a weak ordering on X if it is a reflexive, complete, and transitive relation on X; R is a strong ordering on X if it is a weak ordering on X and is also asymmetric. The set of all strong orderings on X is denoted L(X). If R is a strong ordering on X, then R[1] is the top-ranked alternative in R; that is, xRy for all y in $X\backslash \{x\}$. More generally, R[k] is the $k^{th}$ -ranked alternative in R. The inverse $R^{-1}$ of a binary relation R is defined by $xR^{-1}y$ if and only if yRx. A profile is an ordered n-tuple $u=(u(1),u(2),\ldots ,u(n))\in L(X)^{n}$ of strong orderings.

Given a profile u in $L(X)^{n}$, define $s(u,x,i)=k$, if $u(i)[k]=x$. Then the Borda score of x at u, S(u, x), is the sum of the s(u, x, i) over i, for $1\le i\le n$; the Borda ranking at u is a binary relation $\succsim$ on X that sets $x\succsim y$ if and only if $S(u,x)\le S(u,y)$. It is straightforward to check that the Borda ranking is a weak ordering on X. Borda’s rule, denoted by $f_{B}$ , is a mapping from $L(X)^{n}$ to the set of all weak orderings on X: it assigns to each profile u the Borda ranking. See Pattanaik (2002) for more details on Borda’s rule and related positional rules.

The outcome of Borda’s rule at a given profile u could be alternatively viewed as a weak ordering $\succsim$ (defined on subsets of X):

$$\begin{aligned} X_{1}\succ X_{2}\succ \cdots \succ X_{T} \end{aligned}$$

where: (i) $\succ$ denotes the asymmetric part of $\succsim$, (ii) each $X_{i}\subset X$, (iii) the $X_{i}$ are pairwise disjoint, (iv) alternatives within an $X_{i}$ all have the same Borda score (i.e., $X_{i}$ is an equivalence class of the Borda ranking), and (v) $i<j$ if and only if all alternatives in $X_{i}$ have Borda score less than all alternatives in $X_{j}$. To distinguish from the Borda ranking, in what follows, we use $\mathcal {L}$ to denote a given weak ordering $X_{1}\succ X_{2}\succ \cdots \succ X_{T}$; each $X_{i}$ is called a level of $\mathcal {L}$.

The inverse problem asks: are all weak orderings on X images of some profile under $f_{B}$? Borda’s rule can be extended to allow individual indifference, but then the question is trivial: a weak ordering $\succsim$ is then the image under Borda of a profile made up of n copies of $\succsim$. So we follow McGarvey and others in requiring individual preference orderings to be strong, i.e., no non-trivial indifference. Also, McGarvey allowed n to vary but, as we shall soon see, any weak ordering $\succsim$ is the image under Borda’s rule of a profile of any even number of individuals. Our problem becomes interesting only if we both fix n and focus primarily on the cases where n is odd.

3 Four principles

Before directly attacking our problem, we first introduce four principles that will make our arguments easier.

Principle #1 Because Borda’s rule satisfies neutrality, we can usefully abbreviate our descriptions of weak ordering images under Borda’s rule. For a given X, we only have to be concerned with the number of alternatives in each level, not with exactly which alternatives are in each level. Showing $\mathcal {L}=\{a,b,c\}\succ \{d,e\}\succ \{f\}\succ \{g,h,i,j\}$ is in the image of $f_{B}$ also shows that $\mathcal {L}^{*}=\{i,b,e\}\succ \{c,h\}\succ \{j\}\succ \{g,e,a,f\}$ is in the range. We indicate this by asking if the sequence (3,2,1,4) is in the range. More generally, with a slight abuse of language, we say a weak ordering generated by Borda’s rule is a sequence $(m_{1},m_{2},\ldots ,m_{T})$ where the $m_{i}$ are the cardinalities of the sets $X_{i}$ of alternatives with the same Borda score.

Principle #2 Suppose ordering $\mathcal {L} =(m_{1},m_{2},\ldots ,m_{T})$ is in the image of $f_{B}$ at a profile for n individuals. Then $\mathcal {L}$ is also in the image of $f_{B}$ at a profile for $n+2k$ individuals for any non-negative integer k. All that is needed is to augment the profile with pairs of inverse individual orderings.

Principle #3 Suppose weak ordering $\mathcal {L} =(m_{1},m_{2},\ldots ,m_{T})$ is in the image of $f_{B}$ at a profile $u=(u(1),u(2),\ldots ,u(n))$ on set X and $\mathcal {L}^{*}=(m_{1}^{*},m_{2}^{*},\ldots ,m_{S}^{*})$ is in the image of $f_{B}$ at a profile $v=(v(1),v(2),\ldots ,v(n))$ on set $X^{*}$ (disjoint from X). Then the concatenation

$$\begin{aligned} (m_{1},m_{2},\ldots ,m_{T},m_{1}^{*},m_{2}^{*},\ldots ,m_{S}^{*}) \end{aligned}$$

is also in the image of $f_{B}$ at the profile

$$\begin{aligned} (u(1)\succ v(1),u(2)\succ v(2),\ldots ,u(n)\succ v(n)) \end{aligned}$$

on the set $X\cup X^{*}$ where $u(i)\succ v(i)$ is the ordering obtained by concatenating ordering v(i) below ordering u(i).

Principle #4 Suppose ordering $\mathcal {L} =(m_{1},m_{2},\ldots ,m_{T})$ is in the image of $f_{B}$ at profile $u=(u_{1},u_{2},\ldots ,u_{n})$. Then $\mathcal {L}^{-1}=(m_{T,}\ldots ,m_{2},m_{1})$ is in the image of $f_{B}$ at profile $(u_{1}^{-1},u_{2}^{-1},\ldots ,u_{n}^{-1})$.

4 Even n

Theorem 1

If $n\ge 2$ is even, and $\mathcal {L}$ is a weak ordering on X, then there is a profile u in $L(X)^{n}$ such that $\mathcal {L}=f_{B}(u)$.

Proof

First we treat the case $n=2$. Start with a weak ordering $\mathcal {L}=C_{1}\succ C_{2}\succ \cdots \succ C_{T}$, and, for each i, let $P_{i}$ be an arbitrary strong ordering on level $C_{i}$. Then at the profile

$$\begin{aligned} u=(u(1),u(2))=(P_{1}\succ P_{2}\succ \cdots \succ P_{T},P_{1}^{-1}\succ P_{2}^{-1}\succ \cdots \succ P_{T}^{-1}) \end{aligned}$$

we have $f_{B}(u)=\mathcal {L}$. Principle #2 then extends this to any even $n\ge 2$. $\square$

5 Odd n

Theorem 1 allows us to focus, for the rest of this paper, on the case where n is odd. Here the results are mixed. If $\mathcal {L}=(1,1,\ldots ,1)$, then for all odd n, sequence $\mathcal {L}$ is in the range of $f_{B}$:

Lemma 1

If $\mathcal {L}=(m_{1},m_{2},\ldots ,m_{T})$ is a strong ordering on X then for all n there is a profile u in $L(X)^{n}$ such that $\mathcal {L}=f_{B}(u)$.

Proof

Just construct u as n copies of $\mathcal {L}$.

If $\mathcal {L}=(m_{1},m_{2},\ldots ,m_{T})$ is not a strong ordering on X, then there may or may not exist a profile u for odd n such that $f_{B}(u)=\mathcal {L}$. We first illustrate with some claims:

• (7) is in the range for all odd $n\ge 3$; while (6) is not in the range for any odd n.

• (4, 4) is in the range for all odd $n\ge 3$; while (8) is not in the range for any odd n.

• (2, 2, 2, 3) and (2, 2, 2, 2) are both in the range for all odd $n\ge 3$, but (2, 2, 2, 4) is not in the range for any odd n.

Let’s first provide details for one of the cases above. Failure of a weak ordering to be in the range of $f_{B}$ will be seen to stem from a conflict about parity of the total Borda scores assigned across all alternatives and all individuals, as illustrated by

Example 1

Let $\mathcal {L}=(6)$, i.e., all six alternatives have the same Borda score. Then for every odd positive integer n, there does not exist a profile u such that $f_{B}(u)=\mathcal {L}$. To see this, we count the total of the Borda scores in two ways. First, each individuals assigns scores of $1, 2, \ldots , 6,$ which add up to 21. Summing over $n=2t+1$ individuals, the total of the Borda scores is $21(2t+1)$, which is odd. But the total score must also be 6S where S is the common Borda score of each alternative. But this is even, a contradiction.

This parity barrier, a possible conflict between two ways of determining the total Borda score will be seen to be at the heart of all cases where we can show $\mathcal {L}$ is not in the range of $f_{B}$ for odd $n\ge 3$.

The remainder of this section shows that all weak orderings $\mathcal {L}$ with at least one odd level are in the range of Borda’s rule for all odd $n\ge 3$. We start with the case of a single level.

Example 2

Suppose $\mathcal {L}=(m)$, i.e., all $m\ge 1$ alternatives have the same Borda score and assume $m=2t+1$ is odd. (The case of even m will be covered by Lemma 2.) Then we can construct a profile u for $n=3$ such that $f_{B}(u)=\mathcal {L}$.

A profile u that generates ($2\mathrm{t}+1$) is:

Here, the t even-labeled alternatives (in red) are above the $t+1$ odd-labeled alternatives for individual #2 and below them for individual #3. The common Borda score for all alternatives is $3t+3$.

The appendix uses the following modification of the profile, u above.

Example 3

We alter the profile in Example 2 to generate sequence (t, t). For each individual, remove the $x_{2t+1}$ entry.

• 1. For individual 1, no remaining alternatives have their Borda score changed;

• 2. For individual 2, no even-labeled alternatives have their Borda score changed; all odd-labeled alternatives have their Borda score lowered by 1;

• 3. For individual 3, all remaining alternatives have their Borda score lowered by 1;

As a consequence, the t even-labeled alternatives have a common score $3t+2$, which is exactly one more than the common Borda score $3t+1$ of the t odd-labeled alternatives.

Lemma 2

Suppose $\mathcal {L}=(m_{1},m_{2},\ldots ,m_{T})$ is not a strong ordering on X but exactly one $m_{i}$ is odd. Then for all odd $n\ge 3$ there is a profile u in $L(X)^{n}$ such that $\mathcal {L} =f_{B}(u)$.

Proof

Since exactly one $m_{i}$ is odd, $(m_{1}+m_{2}+\cdots +m_{T})$ is an odd number and Example 2 shows we can construct a profile v for three individuals yielding a single level with $(m_{1}+m_{2}+\cdots +m_{T})$ alternatives:

We construct a profile u from v by modifying v(1) while keeping v(2) and v(3) unchanged. In particular, describe v(1) as

$$\begin{aligned} v(1)=P_{m_{T}}\succ P_{m_{T-1}}\succ \cdots \succ P_{m_{2}}\succ P_{m_{1}} \end{aligned}$$

where

$$\begin{aligned} P_{m_{T}}= & {} x_{1}\succ x_{2}\succ \cdots \succ x_{m_{T}},\\ P_{m_{T-1}}= & {} x_{m_{T}+1}\succ x_{m_{T}+2}\succ \cdots \succ x_{m_{T}+m_{T-1}} ,\\&\vdots \\ P_{m_{2}}= & {} x_{(m_{T}+m_{T-1}+\cdots +m_{3})+1}\succ x_{(m_{T}+m_{T-1}+\cdots +m_{3})+2}\\&\succ \cdots \succ x_{(m_{T}+m_{T-1}+\cdots +m_{3})+m_{2}},\\ P_{m_{1}}= & {} x_{(m_{T}+m_{T-1}+\cdots +m_{3}+m_{2})+1}\succ x_{(m_{T}+m_{T-1}+\cdots +m_{3}+m_{2})+2}\\&\succ \cdots \succ x_{(m_{T}+m_{T-1}+\cdots +m_{3}+m_{2})+m_{1}}. \end{aligned}$$

Then define

$$\begin{aligned} \hat{v}(1)=P_{m_{1}}\succ P_{m_{2}}\succ \cdots \succ P_{m_{T-1}}\succ P_{m_{T}} \end{aligned}$$

and let $u=(\hat{v}(1),v(2),v(3))$.

Given the definition of $\hat{v}(1)$, of u, and that $f_{B}(v)$ is a single level, for any single k, from v to u, options on which $P_{m_{k}}$ is defined remain having the same Borda score; for any $k<j$, from v to u, options on which $P_{m_{k}}$ is defined have larger Borda score than options on which $P_{m_{j}}$ is defined. Therefore, $f_{B}(u)=(m_{1},m_{2},\ldots ,m_{T})$. Principle #2 then extends this to any odd $n\ge 3$. $\square$

Lemma 3

Suppose $\mathcal {L}=(m_{1},m_{2},\ldots ,m_{T})$ is not a strong ordering on X but at least one $m_{i}$ is odd. Then for all odd $n\ge 3$ there is a profile u in $L(X)^{n}$ such that $\mathcal {L} =f_{B}(u)$.

Proof

By induction on K, the number of odd levels in $\mathcal {L}$. The basis case, $K=1$, is settled by Lemma 2. Now assume the result holds for $K=k$, and let $\mathcal {L}=(m_{1},m_{2},\ldots ,m_{T})$ be a sequence with $k+1$ odd levels. Split $\mathcal {L}$ into two subsequences of contiguous levels: $\mathcal {L}^{*}=(m_{1},\ldots ,m_{W})$ and $\mathcal {L}^{**}=(m_{W+1},\ldots ,m_{T})$, where $m_{W}$ is the smallest i such that $m_{i}$ is odd. Let $m^{*}=m_{1}+\cdots +m_{W}$ and $m^{**}=m_{W+1}+\cdots +m_{T}$. By Lemma 2, there is an n-individual profile $u^{*}$ on a set $X^{*}$ of $m^{*}$ alternatives such that $f_{B}(u^{*})=\mathcal {L}^{*}$. By the induction hypothesis, there is an n-individual profile $u^{**}$ on a set $X^{**}$ (which we may choose to be disjoint from $X^{*}$) of $m^{**}$ alternatives such that $f_{B}(u^{**})=\mathcal {L}^{**}$. Property #3 then implies that the profile w obtained by concatenating the preferences in $u^{**}$ below the preferences in $u^{*}$ satisfies $f_{B}(w)=\mathcal {L}$. $\square$

Lemma 3 applies to both odd and even m, while the next theorem shows that Lemma 3 completely determines the answer to our question for odd m.

Theorem 2

Suppose m is odd and $\mathcal {L} =(m_{1},m_{2},\ldots ,m_{T})$. Then for all odd $n\ge 3$ there is a profile u in $L(X)^{n}$ such that $\mathcal {L}=f_{B}(u)$.

Proof

If m is odd, at least one $m_{i}$ in the sequence must be odd. Then apply Lemma 3. $\square$

6 Odd n, even m

What remains is the case where m is even and where n is odd. Of course by Lemma 3, if in $\mathcal {L}=(m_{1},m_{2},\ldots ,m_{T})$ even one $m_{i}$ is odd, $\mathcal {L}$ is in the range of Borda’s rule. So we need only consider the case where all the $m_{i}$ are even. We have already seen that, for example, (6) is not then in the range of Borda’s rule because of a parity barrier. This generalizes to many possible $\mathcal {L}$.

Let $2^{k}$ for $k\ge 1$ be the largest power of 2 dividing all the $m_{i}$, so $\mathcal {L}=(2^{k}s_{1},2^{k}s_{2}\ldots ,2^{k}s_{T}).$ We call $s_{1}+s_{2}+\cdots +s_{T}=m/2k$ the index of ordering $\mathcal {L}$, denoted $I(\mathcal {L})$.

Theorem 3

Suppose $\mathcal {L}=(m_{1},m_{2},\ldots ,m_{T})$ is not a strong ordering on X; in fact, assume every $m_{i}$ is even. If $I( \mathcal {L})$ is odd, then for every odd positive integer n, there does not exist a profile u such that $f_{B}(u)=\mathcal {L}$.

Proof

Assume for contradiction there is a profile u such that $f_{B}(u)=\mathcal {L}$. Then each individual has total score

$$\begin{aligned} 2^{k}(s_{1}+s_{2}+\cdots +s_{T})[2^{k}(s_{1}+s_{2}+\cdots +s_{T})+1]/2=2^{k-1}N \end{aligned}$$

(1)

where N is odd.

Summing Eq. (1) over the n individuals yields $2^{k-1}Nn$, where Nn is then odd if n is odd.

From a different perspective, if the alternatives in the levels have scores $p_{1}$, $p_{2}$, ..., $p_{T}$ (integers) respectively, then the total score would be

$$\begin{aligned} 2^{k}s_{1}p_{1}+2^{k}s_{2}p_{2}+\cdots +2^{k}s_{T}p_{T}. \end{aligned}$$

But

$$\begin{aligned} 2^{k-1}Nn=2^{k}s_{1}p_{1}+2^{k}s_{2}p_{2}+\cdots +2^{k} s_{T}p_{T}=2^{k}(s_{1}p_{1}+s_{2}p_{2}+\cdots +s_{T}p_{T}) \end{aligned}$$

implies 2 divides Nn, a contradiction. $\square$

Finally, we need to consider the remaining case where m is even and n is odd, where $I(\mathcal {L})$ is even (so m is divisible by 4). We have a few partial theoretical results and many numerical examples. All are consistent with $\mathcal {L}$ being in the range of Borda’s rule. The first theoretical result treats the case where $\mathcal {L} =(2^{k}s_{1},,2^{k}s_{2}\ldots ,2^{k}s_{T})$ and all the $s_{i}$ are odd.

Lemma 4

Suppose $\mathcal {L}=(m_{1},m_{2},\ldots ,m_{T})$ is not a strong ordering on X; in fact, assume every $m_{i}$ is even. If $I( \mathcal {L})$ is even and all $s_{i}$ are odd, then for every odd $n\ge 3$, there exists a profile u such that $f_{B}(u)=\mathcal {L}$.

The proof of Lemma 4 is in an appendix.

The result in Lemma 4 covers more cases than might be apparent. Consider (2, 2, 6, 10, 6, 14, 4, 12). The value of the largest power of 2 dividing all these levels is 2; but dividing by 2 does not yield only odd numbers. However we can split this sequence into parts. Lemma 4 shows that each of (2, 2), (6, 10, 6, 14), and (4, 12) are in the range of Borda’s rule. Concatenating the relevant profiles and applying Principle #3 then implies (2, 2, 6, 10, 6, 14, 4, 12) is in the range of Borda’s rule.

7 Conclusion

Summarizing the evidence for our claim that only the parity barrier of Theorem 3 keeps a profile from being in the range of Borda’s rule, we first note that half of all cases we have considered have m odd, for which any ordering is in the range of Borda’s rule for all odd n. Of the remaining half with m even, the vast majority of orderings $\mathcal {L}$ have at least two odd levels and all such orderings are in the range of Borda’s rule for all odd n. For the smaller number of orderings with m even and all levels even, none of those with odd index are in the range of Borda’s rule for any odd n. We are left with orderings for even m, all levels even, and even index. We conjecture that all such rules are in the range of Borda’s rule for all odd n.

Further evidence for this includes:

• 1. Calculations on small number examples confirms the conjecture for all $m<24$.

• 2. For each such m, there are a few orderings of the form $(2^{k}(2t+1),2^{k}(2t+3),2^{k}(2t+5))$ and each such ordering can be proved to be in the range of Borda’s rule for all odd n.

• 3. For each such m, there are many (long) sequences made up entirely of 2’s and 4’s; all are in the range of Borda’s rule for all odd n . See Kelly and Qi (2015) for this result and a generalization.

As a bonus of the analysis in this paper, we also get the solution of the inverse Borda correspondence problem. The Borda correspondence, $G_{B}:L(X)^{n}\rightarrow X$, maps profiles of strong preferences to non-empty subsets of X. Here $G_{B}(u)$ is the set of alternatives with maximal Borda score. The inverse Borda correspondence problem starts from a fixed n and non-empty subset S of X and asks if there is a profile u such that $G_{B}(u)=S$. But, $G_{B}(u)=S$ if and only if $f_{B}(u)=(m_{1},\ldots )$ where $m_{1}=|S|$.

Our results on $f_{B}$ then imply there is a profile u with $G_{B}(u)=S$ unless n is odd and $S=X$ where |X| is even. (Most situations are covered by picking a profile u with $f_{B}(u)=(m_{1},1,1,\ldots ,1)$.)

8 Appendix (proof of Lemma 4)

Recall that $s_{1}+s_{2}+\cdots +s_{T}$ is even and all $s_{i}$ are odd, while T is even.

Case 1 $T=2$, i.e., $\mathcal {L}=(2^{k}s_{1},2^{k}s_{2})$ where $s_{1},s_{2}$ are both odd.

We start by constructing a profile v of $2^{k}(s_{1}+s_{2})$ options with two equal even levels as in Example 3. Note that the score of the blue options (odd-subscript) is larger than that of the red ones (even-subscript) by exactly one:

No changes will be made for individual #1, so that part of the profile will not be displayed from now on. Similarly, nothing in the bottom half of the orderings for #2 and #3 will be changed and those suborderings are not displayed. We focus on the red part for individual #2 and blue part for individual #3:

Note that the two parts combined include all $2^{k}(s_{1}+s_{2})$ alternatives. Now we partition them into $2^{k}$ blocks, each consisting of $(s_{1}+s_{2})$ options:

We will now modify each block, and to illustrate the idea, we separate two blocks below, the one consisting of $\{x_{1},x_{2},\dots ,x_{(s_{1}+s_{2})}\}$ and the one consisting of $\{x_{(s_{1}+s_{2})+1},x_{(s_{1}+s_{2})+2},\dots ,x_{2(s_{1}+s_{2})}\}$:

For each block, we separate the $s_{1}+s_{2}$ options (combined over the two individuals) into a group of $s_{1}$ options (circled) and a group of $s_{2}$ options:

For each block, we move the circled alternatives above the others:

Note that nothing is changed between blocks, or, within a block, among the circled alternatives or among the non-circled alternatives.

Recall that before moving options, the Borda score of blue options (odd-subscript) is larger than the score of red options (even-subscript) by exactly one. Therefore, after moving options, within each block, all the circled options have equal Borda score; similarly, all the non-circled ones have equal Borda score; and the score of the uncircled ones is larger than that of circled ones. In addition, between blocks, all circled options also have equal Borda score; similarly, all non-circled options also have equal Borda score. Adding up all circled options across blocks, there are $2^{k}s_{1}$ and adding up all non-circled options, there are $2^{k}s_{2}$. The constructed profile has $f_{B}(u)= \mathcal {L}=(2^{k}s_{1},,2^{k}s_{2})$.

Case 2 T is even and $T>2$.

When T is even and $T>2$, we can split levels of $\mathcal {L}$ into parts, each of which consists of only two levels. Case 1 shows that each part is in the range of Borda’s rule for every odd $n\ge 3$. Concatenating the relevant profiles and applying Principle #3 then implies $\mathcal {L}$ is in the range for every odd $n\ge 3$.