Voting Systems¶

Suppose that we have $n$ candidates, labeled $\{1,\dots,n\}$.

The following notations will make things easier:

Given a set $X$, let $M(X)$ denote the set of multisubsets of $X$. Recall that multisubsets are unordered and can contain duplicate elements; they are denoted with square brackets.
Let $P_n$ be the powerset of $\{1,\dots, n\}$; $P_n$ is the set of all subsets of $\{1,\dots, n\}$.
Given $v\in\mathbb{R}^n$, write $\tau(v)$ for the set of indices $(1,\dots, n)$ of $v$ with the largest entry.

If $X\subseteq\mathbb{R}^n$, and $T:M(X)\to P_n$ is a function, then $(X,T)$ is a voting system.

Intuitively, $X$ (the voting space) is the set of all possible ballots, and $T$ (the tally function) is a way to use a collection of ballots to determine a winner.

The "voting process" consists of the following:

in some way, select a multisubset $C\in M(X)$ of "ballots" from $X$;
apply $T$ to $C$;
the candidates whose labels are in $T(C)$ "win".

Standard, Approval, and Score Voting¶

These three voting systems are related because all of their tally functions are defined using the same formula. They differ, however, in ballot space. Given $n\in\mathbb{N}$, we'll define voting space for standard, approval, and score voting:

\begin{align*} X_\text{sd} & = \{v\in\{0,1\}^n\ :\ |v|=1\}; \\ X_\text{ap} & =\{0,1\}^n; \\ X_\text{sr} & =\{0,\dots,m\}^n. \end{align*}

For all three we can define the tally function $T:M(X)\to P_n$ as $$T(C)=\tau\left(\sum C\right).$$

Example 1. Suppose we have $n=3$ candidates and 5 people are voting. For the first two voting systems, we can write out the ballot spaces: $$X_\text{sd}=\{(1,0,0), (0,1,0), (0,0,1)\};$$ \begin{align*} X_\text{ap} = \{ & (0,0,0), \\ & (1,0,0), (0,1,0), (0,0,1),\\ & (1,1,0), (1,0,1), (0,1,1),\\ & (1,1,1)\}. \end{align*} The space $X_{ap}$ is too big to write out if we assume $m=4$ since $|X_\text{sr}|= 4^3 = 64$, but is the set of all 3-tuples of numbers in $\{1, 2, 3, 4\}$. Now suppose we have the same 5 people vote on thew three candidates using each of these voting systems, and the resulting collections of ballots are \begin{align*} C_\text{sd} & = [(1,0,0), (1,0,0), (0,1,0), (0,1,0), (0,0,1)];\\ C_\text{ap} & = [(1,1,1), (1,0,0), (1,1,0), (0,1,0), (0,1,1)];\\ C_\text{sr} & = [(4,3,2), (3,1,1), (3,4,1), (1,3,1), (1,2,3)]. \end{align*} Then \begin{align*} T(C_\text{sd}) & = \tau\left(\sum C_\text{sd}\right) = \tau(2, 2, 1) = \{1,2\};\\ T(C_\text{ap}) & = \tau\left(\sum C_\text{ap}\right) = \tau(3, 4, 2) = \{2\};\\ T(C_\text{sr}) & = \tau\left(\sum C_\text{sr}\right) = \tau(10, 11, 8) = \{2\}. \end{align*}

Assessing Fairness of Voting Systems¶

To assess the fairness of a voting system, we can only assess the fairness of the choice of $X$ and $T$. Not, for example, on how $C$ is chosen; we won't consider sociological factors such as who is allowed to vote, or how many times people can vote.

The only thing that we can mean by "fair" is that the candidates are not treated differently in the voting process; the arbitrary labeling of the candidates with the numbers $1,\dots, n$ should not affect the outcome. That is, $(X,T)$ is fair if and only if for any permutation $\phi\in S_n$ and $C\in M(X)$, $$\{\phi \cdot v \ :\ v\in X\} = X$$ and $$T(\{\phi\cdot b\ :\ b\in C\})=\phi(T(C)).$$ (Note we are using the notation $\phi\cdot v$ to denote the operation of permuting the coordinates of $v$ according to $\phi$).

This eliminates the possibility that the ballot space is not "symmetric".

For example, the voting space $X=\{(1,0,0), (0,1,0)\}$ is considered not to be fair because the pemutation $\phi = (1\ 3\ 2)$ maps $(0,1,0)$ to $(0,0,1)$, which is not in $X$.