Ranking votes

Rankings and selections

We consider a simple setting of ranking, i.e., ordering multiple alternatives, $$K:=\{A_1 , A_2, A_3 ,... , A_n\}.$$ The alternatives may be candidates running for elections, movie recommendations, and other votes of personal preferences.

Recall that, even when the voters are forced to pick a strict ordering, we can't expect that the outcome of an election must also be strict. Clearly, the election of all possible votes must be a tie.

A ranking vote $r$ is a complete ordering with ties of the alternatives. It may look like this: $$r=( A_1 < A_2 = A_3 <... < A_n),$$ or $$r= \left(A_1 < \begin{array}{cc}A_2\\A_3\end{array} <... < A_n \right).$$

In particular, for $n=3$ there are strict orderings and orderings with ties: $$R(\{1,2,3\})=\left\{ 123,132,231,321,213,312, \begin{array}{cc}1\\2\end{array}3,\begin{array}{cc}1\\3\end{array}2, \begin{array}{cc}2\\3\end{array}1,... ,1\begin{array}{cc}2\\3\end{array}, \begin{array}{cc}1\\2\\3\end{array} \right\}.$$

We denote the set of all such ranking votes by $$V=R(K):=\left\{r=\left(A_1 \begin{array}{cc}<\\=\end{array} A_2 \begin{array}{cc}<\\=\end{array} ... \begin{array}{cc}<\\=\end{array} A_n \right):\ A_k\in K,\ A_i\ne A_j \right\}.$$

A ranking tally $$f: E=<R(K)> \to O=R(K)$$ converts an election into a single outcome, which is also an ordering with ties: $$f(r_1+ ...+ r_m)=r\in O.$$

We will apply the Triviality Theorem. First, the fully tied ranking is $$0:=( A_1 = A_2 = A_3 =... = A_n).$$ Second, we just need to restate Cancellation for this specific setting. The meaning of the negative of a ranking is clear; it is the reversed ranking: $$\forall A,B\in K,\quad r:A<B \ \Longleftrightarrow\ -r:B<A;$$ or $$-\left(A_1 \begin{array}{cc}<\\=\end{array} A_2 \begin{array}{cc}<\\=\end{array} ... \begin{array}{cc}<\\=\end{array} A_n \right)\ = \ \left(A_1 \begin{array}{cc}>\\=\end{array} A_2 \begin{array}{cc}>\\=\end{array} ... , \begin{array}{cc}>\\=\end{array} A_n \right).$$

We have proven the following algebraic analog of AIT.

Theorem (Triviality of Rankings). A ranking tally $f: E=<R(K)> \to O=R(K)$ that satisfies Fungibility, Unanimity, and Cancellation: $$f(r+(-r))=0,$$ is trivial.

What is the difference from the original AIT?

• In AIT, the number of voters/votes is fixed at $m$;
• AIT's pair-wise Unanimity is stronger than Unanimity we have used;
• AIT's Non-dictatorship is weaker than Interchangeability we have used;
• we don't need IIA;
• we do need Fungibility;
• we do need Cancellation.

It is more typical to expect a single winner rather than a ranking in an election.

A selection vote $r$ is an ordering of a partition of the alternatives into two groups (winners and losers). It may look like this: $$s=( A_1 = A_2=...= A_k < A_{k+1} =... = A_n).$$ We can also think of a selection as a function: $$s:K\to \{0,1\}.$$

In particular, for $n=3$ there are strict orderings and orderings with ties: $$S(\{1,2,3\})=\left\{ \begin{array}{cc}1\\2\end{array}3,\begin{array}{cc}1\\3\end{array}2, \begin{array}{cc}2\\3\end{array}1,... , 1\begin{array}{cc}2\\3\end{array} , \begin{array}{cc}1\\2\\3\end{array}\right\}.$$

We denote the set of all such selection votes by $$V=S(K):=\{ \{A_1,...,A_k\}, \{A_{k+1}...,A_n \} : \ A_i\in K,\ A_i\ne A_j \}.$$

A selection tally $$f: E=<S(K)> \to O=S(K)$$ converts an election into a single outcome, another selection vote.

We apply the Triviality Theorem again. The meaning of the negative $-s$ of a selection $s$ is clear; it is the reversed selection: $$(-s)(A)=1-s(A).$$

We have proven the following.

Theorem (Triviality of Selection). An selection tally $f: E=<S(K)> \to O=S(K)$ that satisfies Fungibility, Unanimity, and Cancellation is trivial.

Of course, any “mixed” tally $f: E=<R(K)> \to O=S(K)$ is also trivial under these three conditions because the zero and the negatives are the same.

Disallowing ranking votes with ties won't change the result.

Disallowing selection votes with more than one winner will prevent us from having an obvious choice for a negative (there may be many) of a vote. A negative vote, that is; what about an election? For a given candidate $A\in K$, define the selection vote $s_A$ with $A$ the single winner by: $$s_A(A)=1 \text{ and } s_A(B)=0 \ \forall B\ne A.$$ Then, its negative is the election given by: $$-s_A:=\sum_{B\ne A} s_B.$$

Votes vs. outcomes

For other specific choices of votes, the tally may have to be also trivial even without Unanimity. But what possible outcome can be assigned to a unanimous election? We already know the answer, it follows from Fungibility.

If all the votes in an election happen to coincide, it outcome should be a multiple of the outcome of this vote:

• Unanimity -- Constant Multiple: For any $m\in {\bf Z}$, if $u\in V$ we have:

$$f(mu)=mf(u).$$

There are further consideration. In one of the simplest cases, no vote is cast for anything but a meaningful outcome.

Outcomes $O$ include all single-vote outcomes including the failure $0$. We also require that every single-vote election produces the outcome of this vote.

• Dictatorship of a Single Voter -- Identity: $V\subset O$, $0\in O\setminus V$, and for any $u\in V\cup \{0\}$ we have:

$$f(u)=u.$$

In other words, $$f\big|_V=\operatorname{Id}.$$

Some of the elections end in failure; those are neutral elections, $$N:=f^{-1}(0)=\ker f.$$ Some of the elections result in votes, $f(w)\in V\cup \{0\}$, and some don't, $f(w)\in O\setminus (V\cup \{0\})$. We call the former elementary elections: $$E':=f^{-1}(V).$$

Example. Suppose the votes are ratings -- $1$ to $5$ stars -- of alternatives $A,B,C,...$. Then, if the first vote $v$ gives one of them $2$ points and the second $w$ gives $1$, then $f(u+v)\in V$ conceivably gives $2+1=3$ points: $$v(A)=2,\ w(A)=2 \ \Rightarrow\ f(v+w)(A)=2+2=4.$$ Then, $f(u+v)\in V$, therefore, $u+v\in E'$. On the other hand, consider: $$v(A)=5,\ w(A)=5 \ \Rightarrow\ f(v+w)(A)=5+5=10.$$ The outcome $X=f(u+v)$ with $X(A)=5+5=10$ is not an allowed vote but it is a reasonable outcome so that $X\in O\setminus V$. Then, $f(u+v)\not\in V$, therefore, $u+v\not\in E'$. $\square$

Example. For a ranking vote, the outcome of the election with the two identical votes: $A>B$ and $A>B$, could be chosen to be the vote $A>B$ again. On the other hand, the outcome of the election of $A>B$ combined with $A<B$ can't be a vote when ties are disallowed. Then, we have $f((A>B)+(A<B))\in O\setminus V$. When ties are allowed, all outcomes are votes, $O=V$, and $E'=E$. Then, $V$ is an Abelian group with respect to the addition determined by $f$, as explained above. $\square$

Example. For a selection note, suppose each vote simply picks a single winner from a list. Then, if the first vote $v$ picks $A$ and the second $w$ picks $B$, the outcome $f(u+v)$ isn't an allowed vote but it is a necessary outcome. $\square$

Example. Another example is about voting on a budget: how to distribute a total of $ \$ 1000000$ among $100$ items, i.e., each vote is a string $(x_1,...,x_{100})$ of real numbers with the same restriction: $$x_1+...+x_{100}=1000000.$$ Then, the sum of any two such votes, $(x_1,...,x_{100})$ and $(y_1,...,y_{100})$, wouldn't be an allowed vote. Then $f(V)=V$ and $O=E=<V>$. $\square$

The Uniqueness Theorem implies the following.

Corollary. Suppose we are given two sets $V$ and $O$. Suppose also that a function $f:<V>\to O$ satisfies Fungibility. If, moreover, $V$ generates $O$ and $f$ satisfies DSV, then the matrix of $f$ is the identity, $\operatorname{Id}$: for all $u_i,x_i\in V$, we have $$f\left(\sum_i u_i\right)=\sum_iu_i.$$

Since $V$ generates $O$ too, function $f$ is defined on the generators $V$ of $O$, and we can extend $f$ -- as a homomorphism -- to the whole $O$. Then, our tally can be seen as $$f:O\to O.$$

At the other end of the spectrum, there can be no outcome without a possibility of voting for it.

• Completeness -- Surjectivity: For any $v\in O$, there is $u\in V$ such that $f(u)=v$, or

$$f(V)=O.$$