Voting and social choice

Rankings and Arrow's Theorem

We consider a simple setting of ranking, i.e., ordering multiple alternatives. The alternatives may be candidates running for elections, movie recommendations, and other votes of personal preferences.

Suppose the number $n$ of alternatives/candidates is fixed: $$K:=\{A_1,A_2, ...,A_n\}.$$ If candidate $A$ is preferred by vote/voter $r$ over $B$, we write: $$r:\quad A>B.$$ Then a strict ranking vote $r$ is a complete strict ordering of the alternatives. It may look like this: $$r:\quad A_1 < A_2 < A_3 <... < A_n,$$ or $$r=(A_1,A_2 , ... ,A_n).$$

However, even when the voters are forced to pick a strict ordering, it is unreasonable to expect that the outcome of an election must also be strict. A simple example with two votes: $A<B$ and $B<A$, will have to result in a tie.

We will allow ties (not to be confused with non-strict orderings, $A\le B$), as follows. Every voter $x$ has a preference of alternative $j\in A$ over alternative $i\in A$: $$r:\quad A_i < A_j,$$ or he is indifferent: $$r:\quad A_i = A_j.$$ Then a ranking $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=\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,... , \begin{array}{cc}1\\2\\3\end{array} \right\}.$$

We denote the set of all such ranking votes by $$V=R(K):=\left\{\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\}.$$

First, the number of voters/votes is fixed at $m$.

A decision function with $m$ voters $$f: E=R(K)^m \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 state IIA as follows. For two candidates, if no voter has changed his relative ranking for them from the election to the next, then the relative positions of the candidates haven't changed in the election results either.

• Independence of Irrelevant Alternatives: Given $A,B \in K$ and $r_i,s_i \in R(K)$, suppose $r_i:A>B\ \Leftrightarrow\ s_i:A>B$ for all $i$, then $r:A>B\ \Leftrightarrow\ s:A>B$, where $r=f(r_1,..., r_m),\ s=f(s_1, ..., s_m)\in R(K)$.

If two candidates are ranked relative to each other the same way by all voters, then they are ranked this way by the election results as well:

• Unanimity: For any $r_i\in R(K)$, if $r_i:A>B$ for each $i$, then $r:A>B$, where $r=f(r_1, ..., r_m)\in R(K)$.

There is no voter whose preferences always prevail.

• Non-dictatorship: There is no $i \in \{1, ...,m\} $ such that $f(r_1,r_2, ..., r_m) = r_i$ for any $r_1, ..., r_m$.

Arrow’s Impossibility Theorem (AIT). The three conditions above are incompatible, i.e., such a function $f$ doesn't exist, if $n \geq 3$.

Below, we will speak of votes not voters and that is why there is no concern about strategic voting and there is no need for IIA.

Ratings and means

Averaging numbers and even locations is a familiar task. For example, the arithmetic mean of $m$ values is computed by this standard formula: $$\text{ the mean of } x_1,...,x_m :=\tfrac{1}{m}(x_1+...+x_m).$$

Since the arithmetic mean is not always appropriate for angles, the following method can be used to obtain both a mean value and measure for the variance of the angles:

• convert all angles to corresponding points on the unit circle;
• compute the mean of these points in ${\bf R}^2$;
• the resulting point will lie within the unit disk;
• convert that point back to the circle.

The angle is the mean of the input angles. The result may be $0$, which suggests that it is impossible to define a continuous mean on the circle.

Thus, the formula might not work in a more complex setting. If these are just elements of a group, the group may have no division. If these are points in a subset of a vector space, the set may be non-convex.

Generalized means were started in a paper by Kolmogorov in 1930 and continued by various authors. The axiomatic approach comes from the thesis of G. Aumann (1933, under Caratheodory). In his paper (1935) he formulated the following conditions, limited mainly for subsets of number spaces.

Definition. For a set $X$ and integer $m>1$, a function $f:X^m\to X$ is called a mean of degree $m$ on $X$ if $$f(s(u))=f(u),\ \forall u\in X^m,\ \forall s\in \mathcal{S}_m;$$ and $$f(x,x, ...,x)=x,\ \forall x \in X.$$

For $X$ a group, a mean is algebraic if it is a homomorphism. For $X$ a topological space, a mean is topological if it is a continuous map.

The following is given by Eckmann in his 2003 lecture.

Mean Theorem. There is an algebraic mean of degree $m$ on a group $G$ if and only if $G$ allows division by $m$. In that case, $G$ is Abelian, the mean is unique, and is given by the standard formula above.

Let $d:G\to G^m$ be the diagonal function: $$d(x):=(x, ...,x).$$ Then the theorem states that we can't complete this diagram with a homomorphism that is also symmetric: $$ \newcommand{\ra}[1]{\!\!\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{cccccccccccc} & G \ & \ra{d} & G^m \\ & _{\operatorname{Id}} & \searrow &\quad \da{g=?} \\ & & & G \end{array} $$

More generally, there are $n$ alternatives or candidates: $$A:=\{0,1,2, ...,n-1\}=\{A_0,A_1, A_2, ... ,A_{n-1}\}.$$

The main examples of choice-making and votes are:

• selections: $A$ is a winner, $B,C,...$ are losers;
• rankings: $A$ $\#1$, $B$ is $\#20$, $C$ is $\#2$, etc.;
• ratings: $A$ is rated $10$, $B$ is rated $4$, $C$ is rated $2$, etc.

The candidates are ordered. We also suppose that these candidates are the vertices of a path-connected simplicial complex $K$. All candidates are subject to evaluation but the presence of edge $AB$ in $K$ reflects the fact that $A$ and $B$ are comparable.

Votes and elections

There may be many types of elections -- based on the types of votes used.

We will see what we can say about an electoral system without actually considering the alternative to be voted for.

First, we are given a set of all possible (affirmative) votes $V$.

Now the potential elections $E$. Where do they come from?

An election is formed as if the voters come in and cast their votes consecutively. This is given by a formal sum of votes: $$u,v\in V \ \Rightarrow \ u+v\in E.$$ Furthermore, two elections are combined together in the same fashion to produce a new election. This is given by a formal sum of elections: $$u,v\in E \ \Rightarrow \ u+v\in E,$$

Then, the main property is that any election can be combined with any other to produce a new election. This requirement is satisfied by any binary relation.

• Unrestricted Elections -- Closedness:

$$u,v\in E \ \Longrightarrow \ u+v\in E.$$

What are elections? As we know, they include all single-vote elections, i.e., $V\subset E$. Note that we will not be considering the $n$-vote elections apart from the $(n+1)$-vote elections. In fact, if the $(n+1)$-st vote is neutral the two are the exact same election.

Definition. For a given set $V$ of votes, an election is a formal sum (with possible repetitions) of votes: $$v=v_1 + ... + v_m,\ v_1, ..., v_m \in V.$$ Alternatively, an election is a formal linear combination of distinct votes with non-negative integer coefficients: $$v=p_1 v_1 + ... + p_mv_m,\ v_1, ..., v_m \in V,\ v_i\ne v_j \text{ for } i\ne j,\ p_1, ..., p_m \in {\bf Z}^+.$$ Furthermore, the election set is the set of all such combinations: $$E:=<V>.$$

Let's examine its properties.

If three groups of voters arrive in the same order but are combined -- pairwise -- in two different ways, the result is the same election. This requirement is satisfied by any group.

• Consistency -- Associativity: For any $u,v,w\in E$, we have

$$(u+v)+w=u+(v+w).$$

Whether a group of voters comes to cast their votes earlier or later than another group of voters shouldn't matter. This requirement is satisfied by any Abelian group.

• Interchangeability -- Commutativity: For any $u,v\in E$, we have:

$$v+u=u+v.$$

A special, neutral vote is available, i.e., one that doesn't change the outcome of any election. Alone, it is simply a failed election. This requirement is satisfied in any monoid.

• Participation -- Zero Element: There is some element $0\in E$ such that for any $v\in E$, we have

$$v+0=v.$$

In some settings, $0$ is not allowed to be a vote. For example, an all-zero rating vote or an all-tied ranking may be or may not be allowed. We assume that an election when no voters have showed up is neutral/failed. Once again, $V$ is the set of affirmative votes: $$0\in E\setminus V.$$

These properties amount to the following.

Proposition. The election set $E=<V>$ is the free commutative monoid generated by $V$.

Outcomes of elections

Next, suppose we are supplied with the set of all possible outcomes $O$ and a decision function, tally, $$f:E\to O =\operatorname{Im}f.$$

But what makes a good tally? The main requirement is as follows.

Suppose after two elections the voters may have changed their minds but the outcomes of the two have remained the same, then so should the outcome of their combination. This requirement is satisfied for any homomorphism.

• Fungibility -- Additivity: For all $u,v,u',v'\in E$, we have

$$f(u)=f(u'),\ f(v)=f(v') \ \Longrightarrow\ f(u+v)=f(u'+v').$$

This is another take on Anonymity (Substitution): not only $u,v$ can be interchanged but also $u,u'$ and $v,v'$ -- as long as their votes/outcomes are the same: $$\begin{array}{rcl} \text{Outcomes:}& \text{Elections:} & \text{Outcomes:}\\ same&\leftarrow \begin{cases} change&\to\\ change&\to \end{cases}& \begin{array}{ll} same\\ same \end{array} \end{array}$$

We directly define the binary operation on the outcome set $O$.

Definition. For any two outcomes $X,Y\in O$, there are elections $u,v\in E$ producing these outcomes, i.e., $$X=f(u),\ Y=f(v).$$ Then we define the sum of the outcomes to be $$X+Y:=f(u+v).$$

Proposition. Under Fungibility, we have the following:

• the sum on $O$ is well-defined;
• $O$ is a commutative monoid;
• $f:E\to O$ is a monoid homomorphism, i.e., for any $u,v\in E$, we have

$$f(u+v)=f(u)+f(v).$$

In other words, we get the same result if we disassemble an election into pieces and then reassemble their outcomes. The votes in an election are split arbitrarily into several elections and the outcomes are computed separately, then, as the outcomes are combined, the result is the same as the original. Because these splits can be arbitrary, this property is also called Path-independence. In fact, one can think of each of these elections as simply our election restricted to a particular polling station.

Let's review what happens when we start from the beginning, with no algebra.

Theorem (Existence and Uniqueness of Tally). Suppose we are given two sets $V$ and $O$ and suppose also that a function $f:<V>\to O$ satisfies Fungibility. Then $f$ is uniquely determined by its values on $V$: $$f\left(\sum_i u_i\right)=\sum_if(u_i).$$

Thus, once the outcome of each individual vote is determined, there is only one reasonable way to assign an outcome to any election.

The neutral outcome (failure) is defined to be the outcome of the neutral election, $0:=f(0)$.

If we choose $x=u$ and $y=0$ in Fungibility, we have for all $u,x\in E$ with $f(v)=0$, $$f(u+v)=f(u).$$ In other words, combining an election with a neutral election doesn't change its outcome.

Observe that we have an equivalence relation: two elections are equivalent whenever their outcomes coincide, $$u\sim v \text{ if } f(u)=f(v).$$

Proposition. Under Fungibility, each set of elections with a given outcome form an equivalence class, the tally is the identification map of this equivalence relation, and $O$ is a monoid with $$O\cong <V>/_\sim.$$

Alternatively, we can start our construction with $O$ already equipped with an algebraic structure.

Theorem. Suppose we are given a set $V$ and a monoid $O$. Then, any homomorphism $f: E=<V> \to O$ satisfies Fungibility.

Next, what if we have a richer algebra?

We require that any vote can be cancelled by some other vote or an election. This requirement is satisfied in any group.

• Cancellation -- Negative Element: For any $v\in V$, there is some $-v\in E$ such that

$$f(v+(-v))=f(v)+f(-v)=0.$$

In some settings, it isn't possible to have a vote $-v$. For example, the negative of a rating or the “anyone but” selection may not be allowed as votes.

Proposition. Under Fungibility and Cancellation, $O$ is a group with $-X:=f(-v)$, where $f(v)=X$.

Then, each equivalence class is a coset with respect to $N=\ker f$, i.e., $$v=f(u) \ \Rightarrow\ f^{-1}(v)=u+N.$$

Proposition. The tally $f:E\to O$ is a homomorphism with respect to $$O\cong <V>/\ker f.$$

Finally, a condition that sets this apart from an arbitrary group and an arbitrary homomorphism. We may require that the outcome of a single vote coincides with the outcome of an election with this vote repeated.

• Unanimity -- Mean: For any $v\in V$,

$$f(v+v)=f(v).$$

But $f$ is a homomorphism! Then we cancel: $$f(v)=f(v+v)= f(v)+f(v) \ \Longrightarrow \ f(v)=0.$$

Thus, we have the main theorem below.

Theorem (Triviality of Tally). Suppose we are given two sets $V$ and $O$ and suppose also that a function $f:<V>\to O$ satisfies Fungibility, Cancellation, and Unanimity. Then $f$ is trivial, $f(x)=0 \forall x$.

Alternatively, we have this simple algebra in group $O$: $$x=x+x \ \Longrightarrow \ x=0.$$ Then the only group with this property is trivial.

Corollary. Suppose we are given a set $V$ and a group $O$ and suppose also that a homomorphism $f:<V>\to O$ satisfies Unanimity. Then $f$ is trivial, $f(x)=0 \forall x$.

An example of Unanimity without Cancellation is produced by $V$ consisting of the three projections of ${\bf R}^3$ onto the three coordinate planes.