Probabilistic view of voting, paradoxes, and manipulation

Abstract

The Marquis de Condorcet, a French philosopher, mathematician, and political scientist, studied mathematical aspects of voting in the eighteenth century. Condorcet was interested in studying voting rules as procedures for aggregating noisy signals and in the paradoxical nature of ranking three or more alternatives. We survey some of the main mathematical models, tools, and results in a theory that studies probabilistic aspects of social choice. Our journey will take us through major results in mathematical economics from the second half of the twentieth century, through the theory of Boolean functions and their influences and through recent results in Gaussian geometry and functional inequalities.

1. Introduction

The Marquis de Condorcet, a French philosopher, mathematician, and political scientist, studied mathematical aspects of voting in the eighteenth century. It is remarkable that already in the eighteenth century Condorcet was an advocate of equal rights for women and people of all races and of free and equal public education 73. His applied interest in democratic processes led him to write an influential paper in 1785 16, where in particular he was interested in voting as an aggregation procedure and where he pointed out the paradoxical nature of voting in the presence of three or more alternatives.

1.1. The law of large numbers and Condorcet’s jury theorem

In what is known as Condorcet’s jury theorem, Condorcet considered the following setup. There are $n$ voters and two alternatives denoted $+$ (which stands for $+1$) and $-$ (which stands for $-1$). Each voter obtains a signal which indicates which of the alternatives is preferable. The assumption is that there is an a priori better alternative and that each voter independently obtains the correct information with probability $p > 1/2$ and incorrect information with probability $1-p$. The $n$ voters then take a majority vote to decide the winner. Without loss of generality, we may assume that the correct alternative is $+$ and therefore the individual signals are i.i.d. (independent and identically distributed) random variables $x_i$ where $\mathbb{P}[x_i = +] = p$ and $\mathbb{P}[x_i = -] = 1-p$. Let $m$ denote the Majority function, i.e., the function that returns the most popular values among its inputs. Condorcet’s jury theorem is the following.

Theorem 1.1.

For every $1>p > 1/2$:

•

$\lim _{n \text{ odd} \to \infty } \mathbb{P}[m(x_1,\ldots ,x_n) = +] = 1$.

•

If $n_1 < n_2$ are odd, then $\mathbb{P}[m(x_1,\ldots ,x_{n_1}) = +] < \mathbb{P}[m(x_1,\ldots ,x_{n_2}) = +]$.

The first part of the theorem is immediate from the law of large numbers (which was known at the time), so the novel contribution was the second part. In the early days of modern democracy, Condorcet used his model to argue that the more people participating in decision making, the more likely that the correct decision is arrived at. We leave the proof of the second part of the theorem as an exercise.

1.2. Condorcet’s paradox and Arrow’s theorem

As hinted earlier, things are more interesting when there are three or more alternatives. In the same 1785 paper, Condorcet proposed the following paradox. Consider three voters named $1$, $2$, and $3$, and three alternatives named $a$, $b$, and $c$. Each voter ranks the three alternatives in one of six linear orders. While it is tempting to represent the orders as elements of the permutation group $S_3$, it will be more useful for us to use the following representation. Voter $i$ preference is given by $(x_i,y_i,z_i)$, where $x_i = +$ if she prefers $a$ to $b$, and $-$ otherwise; $y_i = +$ if she prefers $b$ to $c$, and $-$ otherwise; and $z_i = +$ if she prefers $c$ to $a$, and $-$ otherwise. Each of the six rankings corresponds to one of the vectors in $\{-1,1\}^3 \setminus \{ \pm (1,1,1) \}$.

Condorcet considered three voters, with rankings given by $a>b>c$, $c>a>b$, $b>c>a$, or in our notation by the rows of the following matrix:

$$\begin{equation*} \left( \begin{matrix} x_1 & y_1 & z_1 \\ x_2 & y_2 & z_2 \\ x_3 & y_3 & z_3 \end{matrix}\right) = \left( \begin{matrix} + & + & - \\ + & - & + \\ - & + & + \end{matrix}\right). \end{equation*}$$

How should we decide how to aggregate the individual rankings? If we use the majority rule to decide between each pair of preferences, then we apply the majority rule on each of the columns of the matrix and conclude that overall preference is $(+,+,+)$. In other words, the overall preference is that $a>b$, the overall preference is that $b>c$, and the overall preference is that $c>a$. This does not correspond to an order! This is what is known as Condorcet’s paradox.

Almost two hundred years later, Ken Arrow asked if perhaps the paradox is the result of using the majority function to decide between every pair of alternatives? Can we avoid paradoxes if we aggregate pairwise preferences using a different function?

One function that never results in paradoxes is the dictator function $f(x) = x_1$ as the aggregate ranking is $(x_1,y_1,z_1) \neq \pm (1,1,1)$.

Arrow in his famous theorem 12 proved the following.

Theorem 1.2.

Let $f : \{-1,1\}^n\to \{-1,1\}$ and suppose that $f$ never results in a paradox, so for all $(x_i,y_i,z_i) \neq \pm (1,1,1)$ it holds that $(f(x),f(y),f(z)) \neq \pm (1,1,1)$. Then $f$ is a dictator: there exists an $i$ such that $f(x) = x_i$ for all $x$, or there exists an $i$ such that $f(x) = -x_i$ for all $x$.

With the right notation and formulation, the proof of Arrow’s theorem is very short (see 350).

Proof.

First note that if $f$ is a constant function, then the outcome is always $\pm (1,1,1)$. Suppose that $f$ is not a dictator and not a constant, then $f$ depends on at least two coordinates. Without loss of generality, let these coordinates be $1$ and $2$. Therefore,

$$\begin{align*} \exists x_2,x_3,\ldots ,x_n: \quad f(+,x_2,x_3,\ldots ,x_n) &\neq f(-,x_2,x_3,\ldots ,x_n), \\ \exists y_1,y_3,\ldots ,y_n: \quad f(y_1,+,y_3,\ldots ,y_n) &\neq f(y_1,-,y_3,\ldots ,y_n). \end{align*}$$

We now choose $z_1 = -y_1$ and $z_i = -x_i$ for $i \geq 2$. This guarantees that $(x_i,y_i,z_i) \neq \pm (1,1,1)$ for all $i$ no matter what the values of $x_1$ and $y_2$ are. This can be also verified from the matrix in 1. Now choose $x_1$ and $y_2$ so that $f(x) = f(y) = f(z)$ results in a paradox:

$$\begin{equation} \left( \begin{matrix} x_1 & y_1 & -y_1 \\ x_2 & y_2 & -x_2 \\ \vdots & \vdots & \vdots \\ x_n & y_n & -x_n \end{matrix}\right). {\tag{1}} \end{equation}$$■

Arrow also considered a more general setting where $f$, $g$, and $h$ are allowed to be different functions. In this case, there are other functions that never result in a paradox. For example if $f = 1$ and $g = -1$ for all inputs, then $h$ can be arbitrary. This corresponds to the case where the second alternative $b$ is ignored (always ranked last) and the choice between $a$ and $c$ is determined by $h$. Arrow’s theorem in this setting can be stated as follows:

Theorem 1.3.

Let $f,g,h : \{-1,1\}^n\to \{-1,1\}$ and suppose that $(f,g,h)$ never results in a paradox. So for all $(x_i,y_i,z_i) \neq \pm (1,1,1)$ it holds that $(f(x),g(y),h(z)) \neq \pm (1,1,1)$. Then either two of the functions are constants of opposite signs or there exists an $i$ such that $f$, $g$, and $h$ are dictators on voter $i$, so $f = g = h = x_i$ or $f = g = h = -x_i$.

Proof.

If two of the functions, say $f$ and $g$, take the same constant value and the third function $h$ is not constant, then clearly one can find $x,y,z$ such that $f(x) = g(y) = h(z)$ and $(x,y,z) \neq \pm (1,1,1)$. So without loss of generality we may assume at least two of the functions, say $f$ and $g$ are not constant. Let $A(f)$ denote the set of variables that may change the value of $f$ and similarly $A(g)$ and $A(h)$. Since $f$ and $g$ are not constant, it follows that $A(f)$ and $A(g)$ are not empty. If there exists a variable $i \in A(f)$ and a variable $i \neq j \in A(g)$, then by the same argument as in Theorem 1.2, there exist $(x,y,z)$ resulting in a paradox. Thus, the only case remaining is where $A(f) = A(g) = i$ and $A(h) = i$ or $A(h) = \emptyset$. In either case, the functions $f,g$ and $h$ are all functions of variable $i$ only. It is now easy to verify that it must be the case that $f=g=h$ is a dictator on voter $i$.

■

1.3. Manipulation and the Gibbard–Satterthwaite theorem

A naturally desirable property of a voting system is strategy-proofness (a.k.a. nonmanipulability): no voter should benefit from voting strategically, i.e., voting not according to her true preferences. However, Gibbard 28 and Satterthwaite 71 showed that no reasonable voting system can be strategy proof. Before stating the result, let us specify the model more formally.

The setting here is different than the setup of Arrow’s theorem: We consider $n$ voters electing a winner among $k$ alternatives. The voters specify their opinion by ranking the alternatives, and the winner is determined according to some predefined social choice function (SCF) $f : S_k^n \to \left[k\right]$ of all the voters’ rankings, where $S_k$ denotes the set of all possible total orderings of the $k$ alternatives. We call a collection of rankings by the voters a ranking profile. We say that an SCF is manipulable if there exists a ranking profile where a voter who knows how all other voters vote, can achieve a more desirable outcome of the election according to her true preferences by voting in a way that does not reflect her true preferences.

For example, consider Borda voting, where each candidate receives a score which is the sum of its ranks, and the candidate with the lowest score wins. If the individual rankings are $(a b c d), (c a d b)$, then $a$ is the winner, but if the second voter were to vote $(c d b a)$ instead, then $c$ will become the winner, so the second voter is incentivized to cast a vote that is different from her true ranking.

Theorem 1.4 (Gibbard and Satterthwaite).

Any SCF which is not a dictatorship (i.e., not a function of a single voter) and which allows at least three alternatives to be elected is manipulable.

This theorem has contributed to the realization that it is unlikely to expect truthfulness in voting. There are many proofs of the Gibbard–Satterthwaite theorem, but all are more complex than the proof of Arrow’s theorem given above. We will not provide proof of the theorem here.

1.4. Judgment aggregation

A recent line of work is devoted to the problem of judgment aggregation. In the legal literature, Kornhauser and Sager 43 discuss a situation where three cases $A,B,C$ are considered in court, and by law, one should rule against $C$ if and only if there is a ruling against both $A$ and $B$. When several judges are involved, their opinions should be aggregated using a function $f : \{0,1\}^n \to \{0,1\}$ that preserves this law, that is, satisfies

$$\begin{equation} f(x \land y) = f(x) \land f(y), {\tag{2}} \end{equation}$$

where $(x_1,\ldots ,x_n) \land (y_1,\ldots ,y_n) = (x_1 \land y_1,\ldots , x_n \land y_n)$. List and Pettit 4546 showed that the only nonconstant aggregation functions that satisfy 2 are the AND functions, known in the social choice literature as oligarchies, i.e., functions of the form $f(x_1,\ldots ,x_n) = x_{i_1} \land \cdots \land x_{i_r}$ for some $1 = i_1 < \cdots < i_r \leq n$.

1.5. Modern perspectives

Work since the 1980s addressed novel aspects of aggregation of votes. Condorcet’s jury theorem assumes a probability distribution over the voters but is restricted to a specific aggregation function (majority) while Arrow’s theorem considers general aggregation functions but involves no probability model. There are many interesting questions that can be asked by combining the two perspectives. First, it is natural to ask about the aggregation properties of Boolean functions. The study of aggregation properties of Boolean functions was fundamental to the development of the area of analysis of Boolean functions since the 1980s, starting with the work of Ben-Or and Linial 6 and of Kahn, Kalai, and Linial 36. Second, we can ask questions regarding the probability of manipulation and paradoxes, questions that were analyzed since the early 2000s, starting with the works by Kalai, Nisan, Friedgut, and collaborators 263738.

The theory that was developed is intimately connected to the area of property testing in theoretical computer science and to additive combinatorics. Moreover, we will see that some of the main results and techniques have a discrete isoperimetric flavor. We discuss some of these topics and their connections as follows.

In Section 2, we will start by studying the question of noise stability of Boolean functions that were originally studied by Benjamini, Kalai, and Schramm in the context of percolation 7 and which later played an important role in analyzing the probability of paradoxes, starting with the work of Kalai 37. This work as well as motivation from theoretical computer science 41, led to the proof of the Majority Is Stablest theorem by Mossel, O’Donnell, and Oleszkiewicz 5758. The proof of these results will require some of the main analytical tools in the area, including, notably, hypercontraction 4102966, the invariance principle 58, and Borell’s Gaussian noise-stability result 12.

In Section 3, we sketch proofs of quantitative versions of Arrow’s theorem. We will follow 52 by first proving a Gaussian version of Arrow’s theorem, as well as a quantitive version using reverse hypercontraction 11. Combining the two, we will prove a general quantitive Arrow’s theorem 52. We will also present Kalai’s original proof of a quantitative Arrow’s theorem 37, which is less general but uses only hypercontraction via 25.

Different tools were used in proving different quantitive versions of the manipulation theorem. The first proof, which applies only to three alternatives, uses a reduction to a quantitive Arrow’s theorem 2426. In Section 4 we discuss later approaches that apply for any number of candidates and use reverse hypercontraction as a major tool 3262. The classical proofs of manipulation theorems often use long paths of voting profiles. The most general proof in 62 will quantify such arguments using geometric tools from the theory of Markov chains.

Recent work 23 established quantitative versions of the result by List and Pettit by showing that if $f$ is $\varepsilon$-close to satisfying judgment aggregation, then it is $\delta (\varepsilon )$-close to an oligarchy; this improved upon prior work by Nehama 64 in which $\delta$ decays polynomially with $n$. These results are based on the analysis of a variant of the noise operator, named the one-sided noise operator.

1.6. Probability of paradox for the majority

As a preview of what’s to come, we will compute the asymptotic probability of a nontransitive outcome in the Condorcet setup with three alternatives and where voters vote uniformly at random. The first reference to this computation is by Guilbaud (1952); see 14 and 527.

Let us denote the Majority function by $m:\{-1,1\}^n\to \{-1,1\}$ and assume that the number of voters $n$ is odd. Paradoxes seem more likely when there is no bias towards a particular candidate, so we will consider voters who vote independently and where voter $i$ votes uniformly at random from the six possible rankings. Recall that we encode the six possible rankings by vectors $(x,y,z) \in \{-1,+1\}^3 \setminus \{ \pm (1,1,1) \}$. Here $x$ is $+1/-1$ if a voter ranks $a$ above/below $b$, $y$ is $+1/-1$ if a voter ranks $b$ above/below $c$, $z$ is $+1/-1$ if a voter ranks $c$ above/below $a$.

How do we analyze the probability of a paradox? The following simple fact was used in 37: Since the binary predicate $\psi :\{-1,1\}^3\to \{0,1\}$, $\psi (a,b,c) =1(a=b=c)$ can be expressed as

$$\begin{equation*} \psi (a,b,c) = \frac{1}{4} ( 1+ ab + ac + bc ), \end{equation*}$$

we can write

$$\begin{equation*} \mathbb{P}[m(x) = m(y) = m(z)] = \frac{1}{4} (1 + \mathbb{E}[m(x) m(y)] + \mathbb{E}[m(x) m(z)] + \mathbb{E}[m(y) m(z)] ), \end{equation*}$$

which due to symmetry can be written as

$$\begin{equation*} \mathbb{P}[m(x) = m(y) = m(z)] = \frac{1}{4} (1 + 3 \mathbb{E}[m(x) m(y)] ). \end{equation*}$$

Moreover, the uniform distribution over $\{\pm 1\}^3 \setminus \{ \pm (1,1,1) \}$ satisfies $\mathbb{E}[x_i y_i] = \mathbb{E}[y_iz_i] = \mathbb{E}[z_ix_i] = -1/3$ and the $n$ coordinates are independent. As we will see shortly, the quantity $\mathbb{E}[m(x) m(y)]$ is called the noise stability of $m$ with noise parameter $-1/3$. Its asymptotic value as $n \to \infty$ is easy to compute using a two-dimensional central limit theorem (CLT) to obtain

$$\begin{equation*} \lim _{n \to \infty } \mathbb{E}[m(x) m(y)] = \mathbb{E}[\operatorname {sgn}(X) \operatorname {sgn}(Y)], \end{equation*}$$

where $X,Y \sim N(0, \left( \begin{matrix} 1 & -\frac{1}{3} \\ -\frac{1}{3} & 1 \end{matrix} \right))$ and we can see that

$$\begin{equation*} \mathbb{E}[\operatorname {sgn}(X)\operatorname {sgn}(Y)] = 2\mathbb{P}[\operatorname {sgn}(X)=\operatorname {sgn}(Y)]-1 = 1-\frac{2\arccos (-1/3)}{\pi } \end{equation*}$$

and

$$\begin{equation*} \lim _{n\to \infty }\mathbb{P}[m(x) = m(y) = m(z)] = 1 - \frac{3\arccos (-1/3)}{2\pi } \approx 0.088. \end{equation*}$$

In particular, the probability of paradox does not vanish as $n \to \infty$.

2. Noise stability

2.1. Boolean noise stability

Consider the following thought experiment. Suppose the voters in binary voting obtain independent uniform signals: $x_i = +$ or $x_i = -$ with probability $1/2$. This is the same setting as in Condorcet’s jury theorem except the voters are completely uninformed.

Now consider the following process that produces a vector $y$ as a noisy version of $x$. For each $i$ independently, let $y_i = x_i$ with probability $(1+\theta )/2$, and let $y_i = -x_i$ with probability $(1-\theta )/2$, where $\theta \in [-1,1]$. We chose the parametrization so that $\mathbb{E}[x_i y_i] = \theta$.

How should we interpret $y$? A simple interpretation is as a noise process of voting machines. Suppose that when each voter votes, there is a small probability, say $0.01$, that the voting machine records the opposite vote (independently for all voters and independently of the intended vote). In this case $\theta = 0.98$. Given a voting aggregation function $f:\{-1,1\}^n\to \{-1,1\}$, ideally we would like the quantity

$$\begin{equation*} \mathbb{P}[f(x) = f(y)] = \frac{1}{2}(1+\mathbb{E}[f(x) f(y)]) \end{equation*}$$

to be as large as possible if $\theta > 0$ and as small as possible if $\theta < 0$. The quantity $\mathbb{E}[f(x) f(y)]$ is called the noise stability of $f$. More generally, following 7 we define the following.

Definition 2.1.

For two functions $f,g : \{-1,1\}^n \to \mathbb{R}$ the ($\rho$-)noisy inner product of $f$ and $g$ denoted by $\langle f, g \rangle _{\rho }$ is defined by $\mathbb{E}[f(x) g(y)]$, where $( (x_i,y_i) : 1 \leq i \leq n)$ are i.i.d. mean $0$ ($\mathbb{E}[x_i] = \mathbb{E}[y_i] = 0$) and $\rho$-correlated ($\mathbb{E}[x_i y_i] = \rho$). The noise stability of $f$ is its noisy inner product with itself: $\langle f, f \rangle _{\rho }$.

We can also write the noisy inner product in terms of the noise operator $T_{\rho }$:

Definition 2.2.

The Markov operator $T_{\rho }$ maps functions $f : \{-1,1\}^n \to \mathbb{R}$ to functions $T_\rho f : \{-1,1\}^n \to \mathbb{R}$. It is defined by

$$\begin{equation*} ( T_{\rho } f)(x) = \mathbb{E}[f(y) | x]. \end{equation*}$$

This section discusses noise stability of various families of functions and analytical properties of the operator $T_{\rho }$, which will be used later.

The noise operator plays a key role in the theory of hypercontraction 10. Note that

$$\begin{equation*} \langle f, g \rangle _{\rho } = \mathbb{E}[f(x) g(y)] = \mathbb{E}[ f T_{\rho } g] = \mathbb{E}[ g T_{\rho } f] = \langle T_{\rho } f, g \rangle = \langle f , T_{\rho } g \rangle \end{equation*}$$

and that

$$\begin{equation*} \langle f, g \rangle \coloneq \mathbb{E}[f(x) g(x)] = \langle f, g \rangle _{1}. \end{equation*}$$

Basic properties of this operator can be revealed using its eigenfunctions, i.e., the Fourier basis. The following proposition is straightforward to prove.

Proposition 2.3.

For $S \subset [n]$, write $x_S = \prod _{i \in S} x_i$, so $x_{\emptyset } \equiv 1$. Then:

•

$(x_S : S \subset [n])$ is an orthonormal basis for the space of all functions $f : \{-1,1\}^n \to \mathbb{R}$.

•

$x_S$ is an eigenfunction of $T_{\rho }$ which corresponds to the eigenvalue $\rho ^{|S|}$: $T_{\rho } x_S = \rho ^{|S|} x_S$.

The following folklore result is easily derived by explicitly writing the Fourier expression of $f$ in terms of the basis $(x_S : S \subset [n])$.

Theorem 2.4.

For every $\rho > 0$, for every $n$, and for every $f,g : \{-1,1\}^n \to \{-1,1\}$ with $\mathbb{E}[f] = \mathbb{E}[g] = 0$, it holds that

$$\begin{equation*} \langle f, g \rangle _{\rho } \leq \langle x_1, x_1 \rangle _{\rho } = \rho , \end{equation*}$$

$$\begin{equation*} \langle f, g \rangle _{-\rho } \geq \langle x_1, x_1 \rangle _{-\rho } = -\rho . \end{equation*}$$ Moreover, the only optimizers are dictator functions, i.e., functions of the form $f(x) = g(x) = x_i$ or $f(x) = g(x) = -x_i$.

Theorem 2.4 allows a quick proof of a version of Arrow’s theorem by Kalai 37:

Corollary 2.5.

In the context of Arrow’s theorem if $\mathbb{E}[f] = \mathbb{E}[g] =\mathbb{E}[h] = 0$ and $\mathbb{P}[f(x) = g(y) = h(z)] = 0$, then $f$, $g$, and $h$ are all the same dictator.

Proof.

Use the previous theorem and

$$\begin{equation*} \mathbb{P}[f(x) = g(y) = h(z)] = \frac{1}{4} \left(1+ \langle f,g \rangle _{-1/3} + \langle g,h \rangle _{-1/3} + \langle h,f \rangle _{-1/3} \right). \end{equation*}$$■

From the voting perspective, there is something a little disappointing about Theorem 2.4. It says that if we want to maximize robustness, then among all balanced functions dictator is optimal. However, in the theory of voting dictators are usually not considered good voting schemes. From a mathematical perspective, it is disappointing that there is something special about $\mathbb{E}[f] = 0$. In particular the following problem is open.

Problem 2.6.

For a generic $\rho > 0, 0 < \mu < 1$, what is the value of

$$\begin{equation*} \lim _{n \to \infty } \max \Big ( \langle f, f \rangle _{\rho } : f : \{-1,1\}^n \to \{-1,1\}, \mathbb{E}[f] = \mu \Big )? \end{equation*}$$

To the best of our knowledge, the value is not known for all