Designing Stable Elections

1. Introduction

Suppose votes have been cast in an election between two candidates, and then an adversary can select a fixed number of votes to change. Which voting method best preserves the outcome of the election? A majority vote does, among all voting methods where both candidates have an equal chance of winning the election.

Now, suppose votes have been cast in an election between two candidates, and then each vote is randomly changed with a small probability, independently of the other votes. It is desirable to keep the outcome of the election the same, regardless of the changes to the votes. It is well known that the US Electoral College system is more than four times more likely to have a changed outcome due to vote corruption, when compared to a majority vote. In fact, Mossel, O’Donnell, and Oleszkiewicz proved in 2005 that the majority voting method is most stable to this random vote corruption, among voting methods where each person has a small influence on the election. Below, we survey the design of elections that are resilient to attempted interference by third parties. We discuss some recent progress on the analogous result for elections between more than two candidates. In this case, plurality should be most stable to corruption in votes. We briefly discuss ranked choice voting methods (where a vote is a ranked list of candidates).

1.1. Condorcet’s paradox

Applications of mathematics to the analysis of elections perhaps began with Marquis de Condorcet in the 1700s. Condorcet’s famous paradox demonstrates that an election method that uses ranked preferences of voters might not have a sensible winner. Consider the ranking of three candidates $a,b$, and $c$ between three voters $1,2$, and $3$ as shown in Table 1.

Table 1.

Three voters (one for each row of the table) provide rankings of three candidates $a,b$, and $c$. For example, voter $1$ most prefers candidate $a$.

Voter	Rank 1	Rank 2	Rank 3
1	$a$	$b$	$c$
2	$b$	$c$	$a$
3	$c$	$a$	$b$

If we ignore candidate $b$, then voters $2$ and $3$ prefer $c$ over $a$, while voter $1$ prefers $a$ over $c$ (see Table 2). So, using a majority rule for these preferences, the voters prefer $c$ over $a$.

Table 2.

If candidate $b$ is ignored in Table 1, the remaining rankings of candidates $a$ and $c$ indicate that $c$ is preferred by the majority of voters.

Voter	Rank 1	Rank 2
1	$a$	$c$
2	$c$	$a$
3	$c$	$a$

If we ignore candidate $c$ in Table 1, then voters $1$ and $3$ prefer $a$ over $b$, while voter $2$ prefers $b$ over $a$. So, using a majority rule again, the voters prefer $a$ over $b$.

Finally, if we ignore candidate $a$ in Table 1, then voters $1$ and $2$ prefer $b$ over $c$, while voter $3$ prefers $c$ over $b$. So, using a majority rule, the voters prefer $b$ over $c$.

In conclusion, the voters prefer $a$ over $b$, they prefer $b$ over $c$, and they prefer $c$ over $a$. So, no one has won the election! This observation is known as Condorcet’s paradox. The simplest way to use rankings of candidates might lead to no one winning the election.

In fact, if we compare pairs of candidates using something other than a majority rule, then some analogue of Condorcet’s paradox must still occur, unless we ignore all voters except for one (a dictatorship). This statement can be formalized as Arrow’s Impossibility Theorem.

1.2. Voting power

Game theorists such as Shapley, Shubik, and Banzhaf in the 1950s and 1960s further developed the mathematical and economical analysis of voting methods. As an illustrative example, we consider the 1965 restructuring of the UN Security Council.

Voting method 1 (Pre-1965 UN Security Council).

In pre-1965 rules, the UN Security Council had five permanent members and six nonpermanent members. A resolution passes in the Security Council only if:

•

all five permanent members want xit to pass, and

•

at least two nonpermanent members want it to pass.

In particular, a single permanent member can effectively veto a resolution by voting “no” on that resolution. This voting method was called unfair for the nonpermanent members, so it was restructured in 1965. After the restructuring, the council had the following form (still in use today).

Voting method 2 (Post-1965 UN Security Council).

The UN Security Council has five permanent members and now ten nonpermanent members. A resolution passes in the council only if:

•

all five permanent members want it to pass, and

•

at least four nonpermanent members want it to pass.

A rather vague question is then the following.

Question 1.1.

Are the post-1965 rules more equitable for nonpermanent members of the UN Security Council than pre-1965 rules?

There are various ways to answer this question. One answer, provided by Banzhaf, is to consider the power of a voter in each voting method, i.e., the relative ability of a voter to cause a resolution to pass by changing their vote. Suppose we label the post-1965 UN Security Council members by the integers $1$ through $15$, where the numbers $1,2,3,4,5$ represent the five permanent members of the council, and the numbers $6,7,\ldots ,15$ represent nonpermanent members. Then, for any integer $i$ between $1$ and $15$, let $b_{i}$ be the number of combinations of votes of members of the council (other than voter $i$), such that when voter $i$ changes their vote from “no” to “yes,” the resolution changes from not passing to passing. The Banzhaf power index of a voter $i$ is defined to be the following ratio:

$$\frac{b_{i}}{b_{1}+b_{2}+\cdots +b_{15}}.$$

For example, in the post-1965 rules, what would it take for a nonpermanent member to cause the resolution to pass? First, all permanent members would have to vote “yes.” Then, exactly three other nonpermanent members out of nine would vote yes. So, the number of combinations of votes other members would make is: the number of ways to select three members from a set of nine, i.e., $\binom{9}{3}=\frac{9\cdot 8\cdot 7}{3\cdot 2}=84$. So, $b_{6}=b_{7}=\cdots =b_{15}=84$.

In the post-1965 rules, what would it take for a permanent member to cause the resolution to pass? First, all other permanent members would have to vote “yes.” Then, at least four nonpermanent members out of 10 would vote yes. So, the number of combinations of votes other members would make is: the number of ways to select at least four members from a set of $10$. This number is $\binom{10}{4}+\binom{10}{5}+\cdots +\binom{10}{10}=848$. So, $b_{1}=b_{2}=\cdots =b_{5}=848$.

Similar considerations apply for pre-1965 rules. We summarize the Banzhaf power indices in Table 3.

Table 3.

Banzhaf power indices for UN Security Council voting methods.

Voting Method	Banzhaf Power Index for Non-Permanent Member	Banzhaf Power Index for Permanent Member
Pre-1965 Rules	$\frac{5}{6\cdot 5+5\cdot 57}\approx .0159$	$\frac{57}{6\cdot 5+5\cdot 57}\approx .181 \vphantom {\int ^{\int _{\int }}_{\int _{\int _\int }}}$
Post-1965 Rules	$\frac{84}{10\cdot 84+5\cdot 848}\approx .0165$	$\frac{848}{10\cdot 84+5\cdot 848}\approx .167\vphantom {\int ^{\int _{\int }}_{\int _{\int _\int }}}$

In summary, the post-1965 rules give more power to nonpermanent members, and less power to permanent members of the UN Security Council. So, according to Banzhaf’s definition of voting power, the answer to Question 1.1 is: yes.

1.3. Voting methods as functions

Suppose we run an election between two candidates with $n$ voters, where $n$ is a large integer. For convenience, we denote the two candidates as $+1$ and $-1$ rather than $a$ and $b$. If person $i$ votes for candidate $1$, we define $x_{i}=1$, and if person $i$ votes for candidate $-1$, we define $x_{i}=-1$. We can then make a list of votes as

$$\begin{equation*} x=(x_{1},x_{2},\ldots ,x_{n}). \end{equation*}$$

A voting method is a function $f$ whose input is the votes $x$ and whose output is the winner of election. That is, $f(x)=1$ denotes candidate $1$ winning the election when the votes are $x$, and $f(x)=-1$ denotes candidate $-1$ winning the election when the votes are $x$.

Some examples of voting methods appear below.

Example 1.2.

The majority function is the function

$$f(x)=\mathrm{sign}(x_{1}+x_{2}+\cdots +x_{n}).$$

If there are more $+1$ votes than $-1$ votes, then $f(x)=1$. And if there are more $-1$ votes than $+1$ votes, then $f(x)=-1$. That is, $f$ agrees with our usual notion of majority: the candidate receiving the most votes wins the election. (To guarantee that someone wins the election, we could just assume that $n$ is odd, so that $f$ never takes the value $0$.)

Figure 1.

An iterated majority function with $m=3$ “states.”

Example 1.3.

A dictator function is a function of the form

$$f(x)=x_{1}.$$

That is, the vote of the first person is the winner of the election. In this way, $f$ agrees with our usual notion of dictator: all votes are ignored, except for one. More generally, if $1\leq i\leq n$, a dictator is a function of the form

$$f(x)=x_{i}.$$

Example 1.4.

If $w_{1},\ldots ,w_{n}$ are fixed real numbers, a weighted majority function on $n$ voters is a function of the form

$$f(x)=\mathrm{sign}(w_{1}x_{1}+w_{2}x_{2}+\cdots +w_{n}x_{n}).$$

If $w_{i}$ is large for some $1\leq i\leq n$, this corresponds to assigning more “weight” (i.e., more voting power, or more “say”) to the $i$th voter. And if $w_{i}$ is small, this corresponds to assigning less “weight” (i.e., less voting power, or less “say”) to the $i$th voter.

Example 1.5.

A two-layer iterated majority function is a function of the form

$$f(x)=g(f_{1}(x),f_{2}(x),\ldots ,f_{m}(x)),$$

where $f_{1},f_{2},\ldots ,f_{m}$ are each weighted majority functions on $n$ voters, and $g$ is a weighted majority function on $m$ voters.

A two-layer iterated majority function is similar to an Electoral College system with $m$ states. The US Electoral College system then corresponds to $m=51$.

Remark 1.6.

In learning theory, the iterated majority function is sometimes called a two-layer neural network with boolean activation function. The lines and nodes in Figure 1 are then interpreted as axons and neurons, respectively.

In the ensuing discussion, it is more convenient to replace the Banzhaf power index of a voter with the (almost identical) notion of influence of a voter.

Definition 1.7 (Influences).

Let $f\colon \{-1,1\}^{n}\to \{-1,1\}$ be a voting method. Let $1\leq i\leq n$ be an integer. Define the influence of the $i$th voter on $f$, denoted $\mathrm{Inf}_{i}(f)$, as

$$\begin{align*} &\mathrm{Inf}_{i}(f)\\ &=\frac{\text{# of combinations of votes where the $i$th voter can change the election’s outcome}}{\text{# of combinations of votes of all voters}}\\ &=\frac{\#\{(x_{1},\ldots ,x_{n})\in \{-1,1\}^{n}\colon f(x_{1},\ldots ,x_{n})\neq f(x_{1},\ldots ,x_{i-1},-x_{i},x_{i+1},\ldots ,x_{n})\}}{\#\{(x_{1},\ldots ,x_{n})\in \{-1,1\}^{n}\}}. \end{align*}$$

That is, $\mathrm{Inf}_{i}(f)$ is the probability that the $i$th voter can change the outcome of the election, when other voters are equally likely to vote for either candidate.

Example 1.8.

The numbers $b_{1},\ldots ,b_{n}$ used to define the Banzhaf power indices are just the influences, multiplied by $2^{n}$. For example, in the post-1965 UN Security Council voting method $f\colon \{-1,1\}^{15}\to \{-1,1\}$ with $n=15$ voters,

$$\begin{align*} &\mathrm{Inf}_{1}(f)=\cdots =\mathrm{Inf}_{5}(f)=\frac{848}{2^{15}}\approx .0259,\\ &\mathrm{Inf}_{6}(f)=\cdots =\mathrm{Inf}_{15}(f)=\frac{84}{2^{15}}\approx .00256. \end{align*}$$

Put another way, the Banzhaf power indices are the influences, multiplied by a number causing them to sum to $1$.

Table 4.

Influences for UN Security Council voting methods.

Voting Method	Influence for Non-Permanent Member	Influence for Permanent Member
Pre-1965 Rules	$\frac{5}{2^{11}}\approx .00244$	$\frac{57}{2^{11}}\approx .0278 \vphantom {\int ^{\int _{\int }}_{\int _{\int _\int }}}$
Post-1965 Rules	$\frac{84}{2^{15}}\approx .00256$	$\frac{848}{2^{15}}\approx .0259\vphantom {\int ^{\int _{\int }}_{\int _{\int _\int }}}$

As above, we observe that a nonpermanent member has a higher probability of affecting the outcome of a resolution in post-1965 rules.

Example 1.9.

When $f$ is a dictator function of the form $f(x)=x_{1}$, then the first voter can always change the outcome of the election, and the other voters cannot, so

$$I_{1}(f)=1,\quad I_{2}(f)=\cdots =I_{n}(f)=0.$$

When $f$ is a majority function $f(x)=\mathrm{sign}(x_{1}+\cdots +x_{n})$, then an application of Stirling’s formula implies that for all $1\leq i\leq n$, $\lim _{n\to \infty }\sqrt {n}I_{i}(f)=\sqrt {\frac{2}{\pi }}$, i.e.,

$$I_{1}(f)= I_{2}(f)=\cdots =I_{n}(f)=(1+o(1))\sqrt {\frac{2}{\pi }}\frac{1}{\sqrt {n}}.$$

To see this, note that if $n$ is even, recall that Stirling’s formula implies that

$$\begin{align*} \binom{n}{n/2}&=\frac{n!}{[(n/2)]!}\\ &=(1+o(1))\frac{1}{\sqrt {2\pi }}\frac{\sqrt {n}}{n/2}2^{n}=(1+o(1))2^{n}\frac{1}{\sqrt {n}}\sqrt {\frac{2}{\pi }}. \end{align*}$$

Therefore, $\lim _{n\to \infty }\sqrt {n}I_{i}(f)=\lim _{n\to \infty }(1+o(1))\frac{1}{\sqrt {2\pi }}\frac{2^{n}}{2^{n}}=\frac{1}{\sqrt {2\pi }}$ for all $1\leq i\leq n$.

Perhaps it is a compelling reason to vote in a majority election with one hundred million voters when your probability of changing the election’s outcome is around $1$ in ten thousand.

2. Adversarial Corruption in Voting

2.1. Two candidates

Suppose $n$ people cast their votes in an election between two candidates. Then, suppose an adversary found a way to change several of the votes. By changing some votes, the adversary attempts to change the outcome of the election. Suppose also that the voting method $f\colon \{-1,1\}^{n}\to \{-1,1\}$ is balanced in the following sense.

Definition 2.1 (Balanced voting method).

Let $f\colon \{-1,1\}^{n}\to \{-1,1\}$ be a voting method. We say $f$ is balanced if each of the two candidates has an equal chance of winning the election. That is, the number of combinations of votes where candidate $1$ wins is equal to the number of combinations of votes where candidate $-1$ wins.

For example, dictator functions and the majority function are balanced.

Question 2.2.

What balanced voting method is most resilient to adversarial changes to votes?

That is, if $k\geq 1$ votes can be changed by the adversary, what is the least number of combinations of votes (of all voters) such that the adversary can change the election’s outcome?

In a dictatorship, e.g., $f(x_{1},\ldots ,x_{n})=x_{1}$, changing the first vote changes the outcome of the election, so this voting method is not at all resilient to adversarial changes. Similarly, a voting method that is only a function of a small set of voters (sometimes called a junta) will probably not be resilient to adversarial changes to votes. It turns out that the majority function is the balanced voting method most resilient to adversarial changes; we thank Daniel Kane for telling us the following argument.

Proposition 2.3 (Adversarial optimality of majority).

Let $n$ be an odd positive integer, and let $k$ be an integer satisfying $1\leq k\leq n$. After the votes have been cast, suppose an adversary can change $k$ votes in an election between two candidates with $n$ voters. Then among all balanced voting methods, the majority function has the least number of combinations of votes where the election’s outcome can be altered by the adversary.

Before beginning the proof, we introduce some notation. For any $x=(x_{1},\ldots ,x_{n})\in \mathbb{R}^{n}$, denote the $\ell _{0}$ “norm” of $x$ by $\left\|x\right\|_{0}=\#\{1\leq i\leq n\colon x_{i}\neq 0\}$. (This quantity is not a norm since $\left\|tx\right\|_{0}=\left\|x\right\|_{0}$ for any $t\neq 0$.) Let $S\subseteq \{-1,1\}^{n}$. For any integer $k\geq 1$, we denote the distance $k$ neighborhood of $S$ by

$$\begin{equation} \Gamma _{k}(S)=\{x\in \{-1,1\}^{n}\colon \exists \, y\in S\,\,\mathrm{such}\,\,\mathrm{that}\,\, \left\|x-y\right\|_{0}\leq k\}. \tag{1}{} \end{equation}$$

Then $\Gamma _{k}(S)$ is the set of possible votes that can be obtained by changing at most $k$ votes from a given $y\in S$. For any $k\geq 0$, let $B_{k}\subseteq \{-1,1\}^{n}$ be a distance $k$ neighborhood of one “half” of the hypercube:

$$\begin{equation} B_{k}=\Gamma _{k}\big (\{(y_{1},\ldots ,y_{n})\in \{-1,1\}^{n}\colon y_{1}+\cdots +y_{n}\geq 0\}\big ). \tag{2}{} \end{equation}$$

The key geometric fact used to prove Proposition 2.3 is the following theorem.

Theorem 2.4 (Harper’s inequality/hypercube vertex isoperimetric inequality).

Let $S\subseteq \{-1,1\}^{n}$. Let $k\geq 0$. Assume that

$$\left|S\right|\geq \left|B_{k}\right|.$$

Then

$$\begin{equation*} \left|\Gamma _{1}(S)\right|\geq \left|\Gamma _{1}(B_{k})\right|. \end{equation*}$$

Proof of Proposition 2.3.

We induct on $k$. Let $f\colon \{-1,1\}^{n}\to \{-1,1\}$ be the majority function, and let $g\colon \{-1,1\}^{n}\to \{-1,1\}$ be another balanced voting method. Let $S=\{x\in \{-1,1\}^{n}\colon g(x)=1\}$ be the set of votes where candidate $1$ wins the election, when $g$ is the voting method used to run the election. Note that $B_{0}=\{x\in \{-1,1\}^{n}\colon f(x)=1\}$. Since $f$ and $g$ are balanced, $\left|S\right|=\left|B_{0}\right|=2^{n-1}$. So, Harper’s inequality, Theorem 2.4, implies that

$$\begin{equation} \left|\Gamma _{1}(S)\right|\geq \left|\Gamma _{1}(B_{0})\right|, \tag{3}{} \end{equation}$$

$$\begin{equation} \left|\Gamma _{1}(S)\right|-\left|S\right|\geq \left|\Gamma _{1}(B_{0})\right|-\left|B_{0}\right|. \tag{4}{} \end{equation}$$ The same inequality holds also when $S=\{x\in \{-1,1\}^{n}\colon g(x)=-1\}$. Taken together, we conclude that the number of combinations of votes for which the outcome of the election can be altered with one adversarial vote change is smallest for the majority vote $f$ (since $f$ corresponds to the right side of 4). The case $k=1$ therefore follows by 4.

We now proceed with the inductive step. By the inductive hypothesis, if $S=\{x\in \{-1,1\}^{n}\colon g(x)=1\}$ or if $S=\{x\in \{-1,1\}^{n}\colon g(x)=-1\}$, we have

$$\left|\Gamma _{k}(S)\right|-\left|S\right|\geq \left|\Gamma _{k}(B_{0})\right|-\left|B_{0}\right|.$$

That is, $\left|\Gamma _{k}(S)\right|\geq \left|\Gamma _{k}(B_{0})\right|=\left|B_{k}\right|$. We need to prove the case $k+1$. This again follows by Harper’s inequality, Theorem 2.4, since

$$\left|\Gamma _{k+1}(S)\right|\stackrel{ \xhref[disp-formula]{#gammadef}{1}}{=}\left|\Gamma _{1}(\Gamma _{k}(S))\right|\geq \left|\Gamma _{1}(B_{k})\right|\stackrel{ \xhref[disp-formula]{#bkdef}{2}}{=}\left|B_{k+1}\right|.$$

Therefore, when $S=\{x\in \{-1,1\}^{n}\colon g(x)=1\}$ or $S=\{x\in \{-1,1\}^{n}\colon g(x)=-1\}$,

$$\begin{equation} \left|\Gamma _{k+1}(S)\right|-\left|S\right|\geq \left|B_{k+1}\right|-\left|B_{0}\right|. \tag{5}{} \end{equation}$$

That is, the number of votes for which the outcome of the election can be altered with $k+1$ adversarial vote changes is smallest for the voting method $f$ (since the majority vote $f$ corresponds to the right side of 5). The inductive step and the proof are complete.

For some related observations for ranked choice voting, see, e.g., MPR13, Lemma 3.3.

Proposition 2.3 can easily be extended to unbalanced voting methods. To state such a result, let $t$ be a real number and define a majority function with threshold $t$ to be a function of the form

$$\begin{multline} \mathrm{Maj}_{n,t}(x)=\mathrm{sign}(x_{1}+x_{2}+\cdots +x_{n}-t)\\ \forall \,x=(x_{1},\ldots ,x_{n})\in \{-1,1\}^{n}. \end{multline}$$

Also, we say that two voting methods $f,g\colon \{-1,1\}^{n}\to \{-1,1\}$ have the same balance if the number of combinations of votes resulting in candidate $1$ winning are the same for each voting method, i.e.,

$$\begin{multline} \#\{(x_{1},\ldots ,x_{n})\in \{-1,1\}^{n}\!\colon \! f(x)=1\}\\ =\#\{(x_{1},\ldots ,x_{n})\in \{-1,1\}^{n}\!\colon \! g(x)=1\}. \end{multline}$$

For example, the majority function with threshold $t=0$ and the majority function with threshold $t=1$ do not have the same balance.

Proposition 2.5 (Adversarial optimality of majority, unbalanced case).

Let $n$ be an odd positive integer, and let $k$ be an integer satisfying $1\leq k\leq n$. After the votes have been cast, suppose an adversary can change $k$ votes in an election between two candidates with $n$ voters. Let $f$ be a majority function with threshold $t$, where $t$ is an even integer. Let $g$ be another voting method such that $f$ and $g$ have the same balance. Then the number of combinations of votes where the election’s outcome can be altered by the adversary is lesser for $f$ than for $g$.

2.2. More than two candidates

It would be desirable to have an analogue of Proposition 2.3 for voting methods with more than two candidates. Such a result might require a version of Harper’s inequality, Theorem 2.4, for multiple sets. It is unclear if such an inequality can be proven.

2.3. Additional comments

Proposition 2.3 can be strengthened slightly, so that a voting method that is “close” to being as resilient as majority must itself be “close” to majority. Instead of applying Theorem 2.4, one instead uses a stronger version, such as KL20.

The majority function is known to be optimal in various senses. For example, the majority function maximizes the number of votes that agree with the outcome of the election O’D14, Theorem 2.33. Apparently Rousseau argued this was an ideal choice for a voting method in 1762 in “Du contrat social.” Theorem 3.6 below, the Majority is Stablest Theorem, also characterizes the majority function as being the most stable to random corruption in votes, among a reasonable class of voting methods.

For more background on social choice theory, see, e.g., O’D14, Chapter 2, O’D, Kal18, Section 3.

3. Independent Random Corruption of Votes

In Proposition 2.3, we showed that the majority function is the most stable voting method to adversarial corruption. The majority function is also most stable when votes are corrupted randomly, as shown below.

Theorem 3.1 (Majority is stablest, informal version, MOO10, Theorem 4.4).

Suppose we run an election with a large number $n$ of voters and two candidates. In this election, voters are modelled to have the following random behavior:

(i)

Voters cast their votes randomly, independently, with equal probability of voting for either candidate.

(ii)

Each voter has a small influence on the outcome of the election. (That is, all influences from Definition 1.7 are small.)

Then the majority function is the balanced voting method that best preserves the outcome of the election, when votes have been corrupted independently.

The definition of “best” here is intentionally vague. We will define “best” to mean: maximizing noise stability, as defined below in Definition 3.4. Also, the probability of each vote being changed (corrupted) should be less than $1/2$ in Theorem 3.1. Otherwise the majority preferences of the electorate are reversed upon corruption.

Some remarks concerning the sensibility of the assumptions of Theorem 3.1 now follow:

•

Suppose we completely ignore the votes, and just declare that the first candidate wins. This voting method is as stable to vote corruption as one can imagine, since any amount of corruption in votes cannot change the outcome of the election. Since this voting method is certainly undemocratic and uninteresting, some assumption in Theorem 3.1 must eliminate it. And indeed, this voting method is not balanced, so Theorem 3.1 ignores it. This voting method corresponds to a constant function $f$.

•

As we saw in Example 1.9, a dictator function has one large influence, and the remaining voters have no influence on the election’s outcome. Consequently, the dictator voting method is quite stable to independently random changes to votes, since changing the votes of the nondictators has no effect on the election’s outcome. So, as in the previous example, the dictator function is rather stable to vote corruption for a rather uninteresting reason. We therefore eliminate dictator functions from consideration by imposing the democratic assumption (ii) that each voter has a small influence on the outcome of the election.

3.1. Two candidates

In this section, we will formalize the assumptions in Theorem 3.1, resulting in the formal version of the Majority is Stablest Theorem 3.6.

Assumption 1 (Voter assumptions).

•

There are $n$ voters denoted $\{1,\ldots ,n\}$. There are two candidates denoted $-1$ and $1$.

•

For any $1\leq i\leq n$, the $i$th voter casts a single random vote $X_{i}$ taking the value $-1$ or $1$. (In particular, we are not dealing with ranked voting methods.)

•

The votes $(X_{1},\ldots ,X_{n})$ are independent, identically distributed (i.i.d.) random variables. That is, voters are modelled as independent decision makers with the same probabilities of voting for either candidate.

The voting method $f$ is a function $f\colon \{-1,1\}^{n}\to \{-1,1\}$. If the votes are $(X_{1},\ldots ,X_{n})$, then the winner of the election is $f(X_{1},\ldots ,X_{n})$.

Remark 3.2.

One could argue that the voter assumptions are not realistic, since, e.g., a small group of friends will most likely share similar views, read similar news items, etc., so that their decisions are not truly independent. On the other hand, modeling a large number of voters to be independent individuals is somewhat plausible, from an aggregate perspective.

Assumption 2 (Voter corruption assumptions).

Let $0\leq \rho \leq 1$. Suppose we are given the votes $X_{1},\ldots ,X_{n}$ of $n$ voters choosing between two candidates. The corrupted votes $Y_{1},\ldots ,Y_{n}$ are defined as follows:

•

The corrupted votes $Y_{1},\ldots ,Y_{n}$ are independent, identically distributed (i.i.d.) random variables.

•

For each $1\leq i\leq n$, if $X_{i}=x_{i}\in \{-1,1\}$, then with probability $1-\rho$, $Y{}\!_{i}$ is a uniformly random element of $\{-1,1\}$, and with probability $\rho$, $Y{}\!_{i}=x_{i}$.

Remark 3.3.

When $\rho =1$, $Y{}\!_{i}=X_{i}$ for all $1\leq i\leq n$, i.e., no vote corruption has occurred. When $\rho$ is close to $1$, $Y_{1}$ is almost the same as $X_{1}$, i.e., $X_{1}$ and $Y_{1}$ are strongly correlated, and a small amount of vote corruption has occurred.

When $\rho =0$, the votes $(X_{1},\ldots ,X_{n})$ and $(Y_{1},\ldots ,Y_{n})$ are independent of each other, i.e., the corrupted votes $(Y_{1},\ldots ,Y_{n})$ have been so scrambled that they have no dependence (or correlation) with the original votes $(X_{1},\ldots ,X_{n})$.

Notation. We denote the original (random) votes cast in the election as $X=(X_{1},\ldots ,X_{n})$, and we denote the corrupted votes as $Y=(Y_{1},\ldots ,Y_{n})$.

Recall that the voting method $f$ takes the value $1$ or $-1$, according to which candidate ($1$ or $-1$) won the election. So, if the winner of the election $f(X)$ is the same as the winner of the election with corrupted votes $f(Y)$, then

$$f(X)f(Y)=1.$$

On the other hand, if the winner of the election $f(X)$ is different than the winner of the election with corrupted votes $f(Y)$, then

$$f(X)f(Y)=-1.$$

So, the voting method that has the largest average value of

$$f(X)f(Y)$$

will be the most stable on average to random vote corruption. This observation motivates the following definition.

Definition 3.4 (Noise stability).

Let $f\colon \{-1,1\}^{n}\to \{-1,1\}$ be a voting method. The noise stability of $f$ with correlation parameter $0\leq \rho \leq 1$ is

$$S_{\rho }(f)=\mathbb{E}f(X)f(Y).$$

Here $\mathbb{E}$ denotes expected value, or average value, with respect to the random variables $X=(X_{1},\ldots ,X_{n}),Y=(Y_{1},\ldots ,Y_{n})$ defined in Assumptions 1 and 2.

Remark 3.5.

The probability that the election’s outcome stays the same after vote corruption has occurred is $\frac{1}{2}(1+S_{\rho }(f))$.

3.1.1 Unbiased case. Theorem 3.1 can be restated as: the majority function maximizes noise stability, among a reasonable class of voting methods.

In the theorem below, we denote the majority function as $\mathrm{Maj}_{n}\colon \{-1,1\}^{n}\to \{-1,1\}$, so that