Rating votes

Rating elections

This is how, typically, votes are used for evaluation. The customer/voter assigns a number to a product or service as a substitute of its perceived quality, such as:

• books,
• movies,
• hotels,
• various products,
• service providers,
• etc. $\\$

The choice is commonly visualized by $5$ stars: $$\star\quad \star\star\quad \star\star\star\quad \star\star\star\star\quad \star\star\star\star\star\ .$$ In political elections, it is simple: $$Yes: \underline{\checkmark} \quad No: \underline{\quad}$$

The set of alternatives is $$K:=\{A_0,...,A_n\},$$ and the set of possible ratings is the integers, $${\bf Z}:=\{...,-2,-1,0,1,2, ...\},$$

We now give a specific meaning to the general setting discussed previously.

• A vote is a rating on $K$ with values in ${\bf Z}$, i.e., an arbitrary integer-valued function on the alternatives, $p:K\to {\bf Z}$. We use this notation:

$$V:=C^0(K;{\bf Z})=\{p:K\to {\bf Z}\}.$$

• An election is a formal sum of votes, and we have

$$E:=<V>.$$

• An outcome is also a rating, i.e., an arbitrary function $p:K\to {\bf Z}$. Thus, we have

$$O:=C^0(K;{\bf Z})=\{p:K\to {\bf Z}\}.$$

• A rating tally gives an outcome of any election of this type; i.e., it is any function

$$f:E=<V>\to O.$$ Note that the obvious algebraic structure of $C^0(K;{\bf Z})$ -- point-by-point addition -- is ignored for now.

Written coordinate-wise, a tally is a function of matrices and the output a vector, over ${\bf Z}$. This matrix represents an election and its $(i,j)$-entry is the rating assigned by the $j$th voter to the $i$th candidate: $$\begin{array}{c|ccccccc} {\bf Election}&\text{votes}&&\text{outcome}\\ \hline &\begin{array}{ccc}\ \ V_1&...&V_j&...&V_m\end{array}&&X\\ \hline %\setlength\extrarowheight{3pt} \begin{array}{c|cccc} & A_1\\ &...\\ \text{candidates }& A_i\\ &...\\ & A_n \end{array} &f\left( \begin{array}{cccccc} a_{11}&...&a_{1j}&...&a_{1m}\\ ...&&...&&...\\ a_{i1}&...&a_{ij}&...&a_{im}\\ ...&&...&&...\\ a_{n1}&...&a_{nj}&...&a_{nm} \end{array} \right) &=& \left[ \begin{array}{ccc} c_1\\ ...\\ c_i\\ ...\\ c_n \end{array} \right] \end{array}$$ Here, we have $$f(V_1+...+V_m)=X,$$ and, coordinate-wise, these votes and this outcome are given by the following functions: $$V_j(A_i)=a_{ij} \text{ and } X(A_i)=c_{i}.$$ Note that adding a zero column won't change the outcome: $$f(V_1+...+V_m+0)=f(V_1+...+V_m)=X.$$

Interchangeability says that an election outcome is unaffected by permutations of the votes; i.e., $$sX=X\in E=<V>,\ \forall s\in \mathcal{S}_V,$$ where $\mathcal{S}_V$ is the permutation group on $V$. In other words, as the voters interchange their votes, the election outcome also remains unchanged. This requirement is meant to guarantee that there is no special voter, a dictator. But what about a special candidate?

We require that the outcome of an election is independent of the permutation of the candidates.

• Impartiality -- Symmetry: For all $X\in E=<C^0(K;{\bf Z})>$, for all $s\in \mathcal{S}_K$, and for all $P\in K$, we have

$$f(X)(sP)=s^{-1}f(X)(P).$$

So, renumbering the candidates, $A_1, ...,A_n$, in the ballots produces the same election outcome once we renumber them back.

To summarize, according to Interchangeability,

• interchanging the columns in the matrix doesn't affect the outcome; $\\$

while according to Impartiality,

• interchanging the rows in the matrix interchanges the entries in the outcome accordingly. $\\$

Election manipulation

Homomorphy and Identity combined imply the following: $$ f\left( \begin{array}{cccccc} a_{1}&b_{1}\\ ...&...\\ a_{i}&b_{i}\\ ...&....\\ a_{n}&b_{n} \end{array} \right) = \left[ \begin{array}{cccccc} a_{1}\\ ...\\ a_{i}\\ ...\\ a_{n} \end{array} \right]+ \left[ \begin{array}{cccccc} b_{1}\\ ...\\ b_{i}\\ ...\\ b_{n} \end{array} \right].$$ As stated, the addition on the right remains unspecified.

Now, we choose to utilize the algebra of $C^0(K;{\bf Z})$. The simple summation tally $\Sigma$ is a homomorphism and, therefore, satisfies these and the rest of the axioms: $$ \Sigma\left( \begin{array}{cccccc} a_{11}&...&a_{1j}&...&a_{1m}\\ ...&&...&&...\\ a_{i1}&...&a_{ij}&...&a_{im}\\ ...&&...&&...\\ a_{n1}&...&a_{nj}&...&a_{nm} \end{array} \right) = \left[ \begin{array}{cccccc} a_{11}+&...&+a_{1j}+&...&+a_{1m}\\ ...&&...&&...\\ a_{i1}+&...&+a_{ij}+&...&+a_{im}\\ ...&&...&&...\\ a_{n1}+&...&+a_{nj}+&...&+a_{nm} \end{array} \right]. $$ But, from the Uniqueness Theorem we already know is that there can be only one tally; it's the summation!

Unfortunately, this tally is known to be subject to manipulation.

Suppose we have $n:=4$ candidates: $A,B,C,D$; and $m:=3$ voters: $X,Y,Z$. The votes of the voters and the outcome is given by this table: $$\begin{array}{c|ccc|c} &X&Y&Z&U\\ \hline A&.&.&.&.\\ B&.&.&.&.\\ C&.&.&.&.\\ D&.&.&.&.\\ \hline \end{array}$$ Here each column is the voter's ballot and, at the right, $U$ is the outcome. One can also see the outcome as a vector valued function of matrices: $$U=\Sigma (M),$$ where $M$ is the $4\times 3$ matrix above.

We will apply the summation tally; i.e., each row is added up and the result is entered at the right column.

Let's consider a particular election: $$\begin{array}{c|ccc|c} &X&Y&Z&U\\ \hline A&4&3&3&10\\ B&3&4&4&11\\ C&2&2&2&6\\ D&1&1&1&3\\ \hline \end{array}$$ We have the election result: $$U:\ B > A.$$

Now suppose that in the next election, voter $X$, now $X'$, moves $B$ from second place to last on his list: $$\begin{array}{c|ccc|c} &X'&Y&Z&V\\ \hline A&4&3&3&10\\ B&1&4&4&9\\ C&3&2&2&7\\ D&2&1&1&4\\ \hline \end{array}$$ We have the election result: $$V:\ A > B.$$

As we can see, while each voter's ranking of $K$ with respect to $B$ is the same in the two elections, the final rankings are different.

What happened is that voter $X$ -- wishing victory for $A$ -- correctly predicted that $B$ was the most dangerous competition. He then pushed $B$ to the bottom of his list to reduce $B$'s rating as much as possible. This manipulative step alone lead to $A$'s victory.

The next axiom is meant to prevent a voter from manipulating the outcome by voting strategically. We require that if no voter has changed his preference for a given pair of candidates from the election to the next, then the preference of the election outcome for these candidates hasn't changed either.

• Independence of Irrelevant Alternatives -- Monotonicity: For all $A,B \in K$, and all $X=\Sigma_i X_i,\ Y=\Sigma_i Y_i\in E$, where $X_i,Y_i\in C^0(K;{\bf Z})$, we have

$$\begin{array}{llllll} \operatorname{sign}\Big(X_i(A) - X_i(B)\Big) = \operatorname{sign}\Big(Y_i(A) - Y_i(B)\Big) \quad \Longrightarrow\\ \operatorname{sign}\Big(f(X)(A) - f(X)(B)\Big) = \operatorname{sign}\Big(f(Y)(A) - f(Y)(B)\Big). \end{array}$$

The tally $f$ is a function of $X=\Sigma_iX_i,\ X_i\in C^0(K;{\bf Z})$. But with $A,B$ (two rows in our table) fixed, $X_i$ becomes an integer and so is $f(X)$, while $X$ is an element of $C^0(K;{\bf Z})$. Then we can restate the condition as follows: at two given locations, if the input of the function increases (or decreases), then the output simultaneously increases or decreases in both locations. Such a function can only be an increasing or decreasing one, i.e., monotonic.

Our example of election manipulation tells us that the summation tally $\Sigma$ does not satisfy Monotonicity. This fact gives us the following.

Theorem (Impossibility of a Rating Tally). There is no rating tally $f:<C^0(K;{\bf Z})>\to C^0(K;{\bf Z})$ that satisfies Fungibility, DSV, and IIA.

The theorem is an algebraic analog of the AIT.

However, when there are only two possible ratings to be given by a voter to each candidate, the above example of election manipulation is impossible!

Theorem (Possibility of a Rating Tally). The restriction of the summation rating tally $\Sigma:<C^0(K;\{0,1\})>\to C^0(K;{\bf Z})$ satisfies Fungibility, DSV, and IIA.

Proof. We only need to prove IIA. Suppose we have $A,B \in K,\ X=\Sigma_i X_i,Y=\Sigma_i Y_i\in E,$ for some $X_i,Y_i\in C^0(K;\{0,1\})$. First, $$\operatorname{sign}\Big(X_i(A) - X_i(B)\Big) = \operatorname{sign}\Big(Y_i(A) - Y_i(B)\Big)$$ becomes simply $$X_i(A) - X_i(B)=Y_i(A) - Y_i(B).$$ Now we compute the rest: $$\begin{array}{llll} \Sigma(X)(A)-\Sigma(X)(B)&=\sum_iX_i(A)-\sum_iX_i(B)\\ &=\sum_i(X_i(A)-X_i(B))\\ &=\sum_i(Y_i(A)-Y_i(B))\\ &=\sum_iY_i(A)-\sum_iY_i(B)\\ &=\Sigma(Y)(A)-\Sigma(Y)(B). \end{array}$$ $\blacksquare$

It is obvious that having more than two values available still leaves a possibility of election manipulation.

It appears that ratings alone aren't versatile enough to capture anything beyond a basic electoral system. This suggests that we should consider allowing comparison votes -- even at the risk of facing “inconsistent” votes: $A>B>C>A$.