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 $\mu \neq \{-\pm 1, \pm 0.5, 0\}$; see 75.

Here are some additional examples,

•

A similar argument to the theorem shows that if $\rho > 0$, then $\langle f, f \rangle _\rho \geq \rho ^n$ for $f : \{-1,1\}^n \to \{-1,1\}$. The parity function $x_{[n]}$ achieves equality.

•

The asymptotic noise stability of Majority is given by the Sheppard formula (see 72), i.e., $\mathbb{E}[\operatorname {sgn}(N) \operatorname {sgn}(M)]$, where $(N,M)$ are $\rho$-correlated Gaussian random variables,$$\begin{equation*} \mathbb{E}[\operatorname {sgn}(M)\operatorname {sgn}(N)] = 2\mathbb{P}[\operatorname {sgn}(M)=\operatorname {sgn}(N)]-1 = 1-\frac{2\arccos (\rho )}{\pi } \coloneq \kappa (\rho ). \end{equation*}$$

In particular if $\rho = 1-\varepsilon$, then $\mathbb{P}[f(x) \neq f(y)]$ is of order $\sqrt {\varepsilon }$. Compare this to a dictator where it is of order $\varepsilon$.

•

If we consider $n = r^2$ where $r$ is odd and the function $f$ implements electoral college, i.e.,$$\begin{equation*} f(x_1,\ldots ,x_n) = m \Big (m(x_1,\ldots ,x_r),\ldots ,m(x_{n-r+1},x_n) \Big ), \end{equation*}$$

then it is easy to see that asymptotically the noise stability is given by $\kappa (\kappa (\rho ))$. In particular if $\rho = 1-\varepsilon$ for small $\varepsilon$, then $\mathbb{P}[f(x) \neq f(y)]$ is of order $\varepsilon ^{1/4}$.

•

Let $m_r$ be the Majority function on $r$ voters, define $m_r^{(1)} = m_r$, and by induction,$$\begin{equation*} m_r^{(h)}(x_1,\ldots ,x_{r^h}) = m_r^{(h-1)} \left( m_r(x_1,\ldots ,x_r),\ldots ,m_r(x_{r^h-r+1},\ldots ,x_{r^h}) \right). \end{equation*}$$

This function is called the recursive majority function. The paper 56 shows that for every $\varepsilon < 0.5$, if $r$ is large enough and $n_h = r^h$ and if $\rho = 1-n_h^{-\varepsilon }$, then$$\begin{equation*} \lim _{h \to \infty } \mathbb{E}[m_r^{(h)}(x) m_r^{(h)}(y)] = 0, \end{equation*}$$

where $(x,y)$ are $\rho$-correlated. In other words, this function is very far from being noise stable.

2.2. Gaussian noise stability

We will now take a detour and consider analogous quantities defined in Gaussian space. We will later see that this is quite useful in the Boolean setting.

Definition 2.7.

In Gaussian space, the ($\rho$-)noisy inner product of $\phi : \mathbb{R}^n \to \mathbb{R}$ and $\psi : \mathbb{R}^n \to \mathbb{R}$ denoted by $\langle \phi , \psi \rangle _{\rho }$ is defined as

$$\begin{equation*} \mathbb{E}[\phi (M) \psi (N)], \end{equation*}$$

where $((M_i,N_i))_{i=1}^n$ are i.i.d. two-dimensional Gaussian vectors, such that $N_i,M_i$ are standard (mean $0$, variance $1$) Gaussian random variables and $\mathbb{E}[N_i M_i] = \rho$. The noise stability of $\phi$ is its noisy inner product with itself: $\langle \phi , \phi \rangle _{\rho }$.

We will generally use $f$, $g$, etc., to denote functions over the Boolean cube and $\phi$, $\psi$, etc., for functions in $L_2(\mathbb{R}^n,\gamma )$. In particular, for $\mu \in [0,1]$ we write $\chi _{\mu }$ for the indicator of the interval $(-\infty ,\Phi ^{-1}(\mu ))$ whose Gaussian measure is $\mu$.

We can now state Borell’s 12 noise stability result.

Theorem 2.8.

For all $n \geq 1$, $\rho > 0$, and $\phi ,\psi : \mathbb{R}^n \to [0,1]$, it holds that

$$\begin{gather*} \langle 1-\chi _{1-\mathbb{E} \phi }, \chi _{\mathbb{E} \psi } \rangle _{\rho } \leq \langle \phi , \psi \rangle _{\rho } \leq \langle \chi _{\mathbb{E} \phi }, \chi _{\mathbb{E} \psi } \rangle _{\rho },\\ \langle 1-\chi _{1-\mathbb{E} \phi }, \chi _{\mathbb{E} \psi } \rangle _{-\rho } \geq \langle \phi , \psi \rangle _{-\rho } \geq \langle \chi _{\mathbb{E} \phi }, \chi _{\mathbb{E} \psi } \rangle _{-\rho }. \end{gather*}$$

Borell 12 was interested in more general functionals of the heat equations, and he showed that these functionals increase with respect to nonincreasing spherical rearrangement. The fact that half-spaces are the unique optimizers of $\rho$-noisy inner products was proven in 55, where a robust version of the theorem is also proven. Tighter robust versions were later proven by Eldan 21. Other alternative proofs and generalizations of Borell’s result include 3342.

2.3. Gaussian and Boolean noise stability

By applying the CLT, it is easy to check that Gaussian noise stability provides bounds on Boolean noise stability.

Proposition 2.9.

For every $\rho \in [-1,1]$, $\mu ,\nu \in [0,1]$, and for every

$$\begin{equation*} s \in \Big [ \langle 1-\chi _{1-\mu }, \chi _{\nu } \rangle _{\rho } , \langle \chi _{\mu }, \chi _{\nu } \rangle _{\rho } \Big ], \end{equation*}$$

there exists sequence of Boolean functions $f_n,g_n :\{-1,1\}^n \to \{0,1\}$ such that $\mathbb{E}[f_n] \to \mu , \mathbb{E}[g_n] \to \nu$ and

$$\begin{equation*} \langle f_n, g_n \rangle _{\rho } \to s. \end{equation*}$$

Moreover, by Theorem 2.8 and Theorem 2.4 it follows that the extreme Gaussian noise stability is bounded away from the extreme Boolean noise stability at $\mu = 1/2$ and $0 < |\rho | < 1$; see Figure 1.

The proof of the proposition is standard using approximation of Gaussian random variables in terms of sums of independent Bernoullis:

Proof.

To show that we can obtain the right endpoint of the interval, let

$$\begin{gather*} f_n =\chi _{\mu }(\frac{1}{\sqrt {n}} \sum _{i=1}^n x_i) = 1(\frac{1}{\sqrt {n}} \sum _{i=1}^n x_i \leq \Phi ^{-1}(\mu )), \\ g_n = \chi _{\nu }(\frac{1}{\sqrt {n}} \sum _{i=1}^n x_i) = 1(\frac{1}{\sqrt {n}} \sum _{i=1}^n x_i \leq \Phi ^{-1}(\nu )), \end{gather*}$$

denote the indicator that the normalized sums of the $x_i$ lie in the intervals $\chi _{\mu }$ and $\chi _{\nu }$, and apply the CLT. The proof of achievability of the left endpoint is similar where now we take the intervals $\chi _{\nu }$ and $1-\chi _{1-\mu }$.

To obtain an intermediate point $s$, take the inputs of $f_n$ and $g_n$ to be defined on overlapping blocks of bits, e.g, by varying $\alpha$ from $1$ to $0$ in

$$\begin{equation*} f_n =\chi _{\mu }(\frac{1}{\sqrt {n}} \sum _{i=\alpha n}^{(1+\alpha )n} x_i), \qquad g_n = \chi _{\nu }(\frac{1}{\sqrt {n}} \sum _{i=1}^n x_i), \end{equation*}$$

we get all values in $[\mu \nu , \langle \chi _{\mu }, \chi _{\nu } \rangle _{\rho }]$. Taking overlapping intervals for $\chi _{\nu }$ and $1-\chi _{1-\mu }$ gives all the values in $[\mu \nu , \langle 1-\chi _{1-\mu }, \chi _{\nu } \rangle _{\rho }]$.

■

2.4. Smooth Boolean functions

To better understand the connection between Boolean and Gaussian stability, we define two notions of smoothness, termed low influences and resilience for Boolean functions. We begin with the notion of influence. This notion measures the power of a voter 20. It plays a crucial role in the analysis of Boolean functions 6 and 36. When it comes to general probability spaces, there are several possible definitions; see, e.g., 1340. We choose the $L^2$ definition, which is closely related to the notion of local variance in statistics. To simplify notation, we will often omit the sigma algebra and probability measure defined over a probability space $\Omega$.

Definition 2.10.

Consider a probability space $\Omega$. For a function $f : \Omega ^n \to \mathbb{R}$, we define the $i$th influence of $f$ as

$$\begin{equation*} I_i(f) = \mathbb{E} \big [\operatorname *{Var}[f | x_1,\ldots ,x_{i-1},x_{i+1},\ldots ,x_n] \big ], \end{equation*}$$

where the expected value is with respect to the product measure on $\Omega ^n$. In the Boolean case with the uniform measure $f : \{-1,1\}^n \to \mathbb{R}$, the influence is equivalently defined as

$$\begin{equation*} I_i(f) = \mathbb{E} \big [\operatorname *{Var}[f | x_1,\ldots ,x_{i-1},x_{i+1},\ldots ,x_n] \big ] = \sum _{S : i \in S} \hat{f}^2(S), \end{equation*}$$

or as

$$\begin{equation*} I_i(f) = \mathbb{E}[ |\partial _i f|^2], \end{equation*}$$

where

$$\begin{equation*} \begin{split} &(\partial _i f)(x_1,\ldots ,x_n) \\ &\qquad = 0.5(f(x_1,\ldots ,x_{i-1},+,x_{i+1},\ldots ,x_n) - f(x_1,\ldots ,x_{i-1},-,x_{i+1},\ldots ,x_n)) \end{split} \end{equation*}$$

is the discrete $i$th directional derivative.

An easy corollary of the definition is that for $|\rho | < 1$, it holds that $T_{\rho } f$ is small in the sense that the sum of its influences is bounded as a function of $\rho$ only.

Lemma 2.11.

Let $f : \{-1,1\}^n \to [-1,1]$ and $|\rho | < 1$. Then

$$\begin{equation*} \sum _{i=1}^n I_i(T_{\rho }f) \leq \frac{1}{1-|\rho |}. \end{equation*}$$

Proof.

$$\begin{eqnarray*} \sum _{i=1}^n I_i(T_{\rho }f) &=& \sum _{i=1}^n \sum _{S : i \in S} \widehat{T_{\rho }f}^2(S) \\ &=& \sum _S |S| \widehat{T_{\rho }f}^2(S) = \sum _{S} |S| \rho ^{2 |S|} \hat{f}^2(S) \\ &\leq & \max _k |\rho |^{2k} k \sum _S \hat{f}^2(S) \leq \max _k |\rho |^{2k} k \leq 1/(1-|\rho |). \end{eqnarray*}$$ The proof follows.

■

Hypercontractivity is a key feature of many of the proofs in the analysis of Boolean functions starting with the Kahn–Kalai–Linial paper 36. Many of the results in analysis of Boolean functions in general and in the study of quantitative social choice in particular, use the famous hypercontractive theorem:

Theorem 2.12 (10).

Let $f : \{-1,1\}^n \rightarrow \mathbb{R}$ and $1 \le q \le p$. Then if $\rho ^2 \le \frac{q-1}{p-1}$, then

$$\begin{equation*} \| T_{\rho } f \|_p \le \| f \|_q. \end{equation*}$$

Theorem 2.12 has a long history. First, Gaussian versions of it were proven by Nelson 6566 and in the Boolean setting by Bonami 910 and by Gross 29; see, e.g., 69 for more detailed discussion.

The easy Lemma 2.11 states that $T_{\rho } f$ is smooth in a local sense—as on average, it bounds the sum of its discrete derivatives. Theorem 2.12 proves global smoothness, as it shows that higher norms of $T_{\rho } f$ are bounded by lower norms of $f$.

Interestingly, in quantitative social choice, a reverse inequality proved by Borell 11 also plays an important role.

Theorem 2.13 (11).

Let $f,g : \{-1,1\}^n \rightarrow \mathbb{R}_+$ and $1 > p > q$. Then, for any $0 \leq \rho ^2 \le \frac{1-p}{1-q}$,

$$\begin{equation*} \| T_{\rho } f \|_q \ge \| f \|_p, \end{equation*}$$

and for any $0 \leq \rho ^2 \le (1-p)(1-q)$,

$$\begin{equation*} \langle f, g \rangle _{\rho } \geq \| f \|_p \| \| g \|_q. \end{equation*}$$

Recall that for $f : \{-1,1\}^n \rightarrow \mathbb{R}_+$, and we write

$$\begin{equation*} \| f \|_p = \mathbb{E}[f^p]^{1/p}, p \neq 0, \quad \| f \|_0 = \exp (\mathbb{E}[\ln f]). \end{equation*}$$

While the inequalities may seem like a curiosity, as $p$ and $q$ “norms” for $p,q < 1$ are rarely used in analysis (nor are they norms), the second inequality is quite helpful in some social choice proofs. In more general settings, reverse hypercontraction is implied by standard hypercontraction and in fact by a weaker inequality, called the modified log-Sobolev inequality. For a more general discussion of reverse hypercontraction and its applications, see 5960.

For a voting function $f : \{-1,1\}^n \to \{-1,1\}$, $I_i(f)$ is the probability that voter $i$ is the deciding voter, given all other votes. A stronger notion of the power of a voter or a small set of voters is that their vote affects the expected outcome on average. A function whose expectation is not affected by any small set of voters is called resilient. More formally,

Definition 2.14.

We say that a function $f : \Omega ^n \to \mathbb{R}$ is $(r,\alpha )$-resilient if

$$\begin{align} \Big | \mathbb{E} \left[f | X_S = z \right] - \mathbb{E}[f] \Big | \leq \alpha , {\tag{3}} \end{align}$$

for all sets $S$ with $|S| \leq r$ and all $z\in \Omega ^S$.

Proposition 2.15.

If $f : \{-1,1\}^n \to \mathbb{R}$ satisfies

$$\begin{equation} \max (|\hat{f}(S)| : 0 < |S| \leq r) \leq 2^{-r} \alpha , {\tag{4}} \end{equation}$$

then $f$ is $(r,\alpha )$-resilient. In particular if $f$ has all influences bounded by $4^{-r} \alpha ^2$, then $f$ is $(r,\alpha )$-resilient.

Proof.

The second statement follows from the first one immediately as for every nonempty $S$, we may choose $i \in S$, and then

$$\begin{equation*} \hat{f}^2(S) \leq I_i(f) \leq 4^{-r} \alpha ^2, \end{equation*}$$

as needed. For the first statement, assume 4. Then

$$\begin{equation*} \begin{split} &\Big | \mathbb{E} \left[f | X_S= z \right] - \mathbb{E}[f] \Big | \\ &\qquad = \Big | \mathbb{E}[ \sum _{T\neq \emptyset } \hat{f}(T) z_{S \cap T} x_{T \setminus S}] \Big | = \Big | \sum _{\emptyset \neq T \subset S} \hat{f}(T) z_T \Big | \leq 2^{|S|} 2^{-r} \alpha \leq \alpha . \end{split} \end{equation*}$$■

Resilient functions have long been studied in the context of pseudo-randomness; see, e.g., 15.

Thus, the statement that a function has a high-influence variable means that there exists a voter $i$ that can have a noticeable effect on the outcome if voter $i$ has access to all other votes cast. The statement that a function is not resilient implies that there is a bounded set of voters who have noticeable effect on the outcome on average, i.e., with no access to other votes cast. Consider the following examples:

•

Dictator has maximal influence of $1$ (and all other $0$). It is also not resilient for $r \geq 1, \alpha < 1$.

•

Majority has all influences of order $n^{-1/2}$ and is also $(r,O(r/\sqrt {n}))$-resilient.

•

An example of a resilient function with a high-influence variable is the function$$\begin{equation*} f(x) = x_1 \operatorname {sgn}(\sum _{i=2}^n x_i). \end{equation*}$$

Here coordinate $1$ has influence $1$ but the function is resilient. In terms of voting, voter $1$ has a lot of power if she has access to all other votes cast (or the majority of the votes), but without access to this information, she is powerless. Moreover, every small set of $k$ voters can change the expected value of $f$ (by conditioning on their vote) by $O(k n^{-1/2})$. Another simple example is the parity function $\prod _{i=1}^n x_i$, which is $(r,0)$-resilient for every $r < n$, but where all influences are $1$.

The Majority Is Stablest theorem states that the extremal noise stability of low-influence/resilient functions on the discrete cube is captured by Gaussian noise stability. Here are three increasingly stronger statements along this line.

Theorem 2.16 (5758).

For every $\varepsilon > 0, 0 \leq \rho < 1$, there exists a $\tau > 0$ for which the following holds. Let $f,g : \{-1,1\}^n \to [0,1]$ satisfy $\max (I_i(f),I_i(g)) < \tau$ for all $i$. Then

$$\begin{equation*} \langle f, g \rangle _{\rho } \leq \langle \chi _{\mathbb{E} f}, \chi _{\mathbb{E} g} \rangle _{\rho }+ \varepsilon . \end{equation*}$$

This theorem is called “Majority Is Stablest” ,since $\langle \chi _{\mathbb{E} f}, \chi _{\mathbb{E} g} \rangle _{\rho }=\lim _{n \to \infty } \langle f_n , g_n \rangle _{\rho },$ where $f_n(x) = \chi _{\mathbb{E} f}(n^{-1/2} \sum _{i=1}^n x_i)$ and $g_n(x) = \chi _{\mathbb{E} g}(n^{-1/2} \sum _{i=1}^n x_i)$.

It turns out that for two functions, it is in fact enough that one of them is low influence to obtain the same results, i.e.:

Theorem 2.17 (51, Prop. 1.15).

For every $\varepsilon > 0$ and $0 \leq \rho < 1$, there exists a $\tau (\rho ,\varepsilon ) > 0$ for which the following holds. Let $f,g : \{-1,1\}^n \to [0,1]$ be such that $\min (I_i(f),I_i(g)) < \tau$ for all $i$. Then

$$\begin{equation} \langle f, g \rangle _{\rho } \leq \langle \chi _{\mathbb{E} f}, \chi _{\mathbb{E} g} \rangle _{\rho } + \varepsilon , {\tag{5}} \end{equation}$$

where one can take

$$\begin{equation} \tau = \varepsilon ^{O\left( \frac{\log (1/\varepsilon ) \log (1/(1-\rho ))}{(1-\rho ) \varepsilon } \right)}. {\tag{6}} \end{equation}$$

In particular the statement above holds when $\max _i I_i(f) < \tau$ and $g$ is any Boolean function bounded between $0$ and $1$.

Moreover, one can replace the low-influence condition by the condition that the function is resilient:

Theorem 2.18 (53).

For every $\varepsilon > 0, 0 \leq \rho < 1$, there exist $r,\alpha > 0$ for which the following holds. Let $f : \{-1,1\}^n \to [0,1]$ be $(r,\alpha )$-resilient, and let $g : \{-1,1\}^n \to [0,1]$ be an arbitrary function. Then

$$\begin{equation*} \langle f, g \rangle _{\rho } \leq \langle \chi _{\mathbb{E} f}, \chi _{\mathbb{E} g} \rangle _{\rho }+ \varepsilon . \end{equation*}$$

One can take

$$\begin{equation} r = O \left(\frac{1}{\varepsilon ^2(1-\rho )\tau } \right), \alpha = O\left(\varepsilon 2^{-r} \right), {\tag{7}} \end{equation}$$

where $\tau$ is given by 6.

Note in particular that for our current bounds for $\tau$ and for fixed $\rho$, $r$ is exponential in a polynomial in $1/\varepsilon$ and $\alpha$ is doubly exponential in a polynomial in $1/\varepsilon$. Similar statements for one function were proven before by 70 and appeared in 35.

There are two known proof strategies for Theorem 2.16. In 5758, the authors applied a nonlinear invariance principle, which states that the distribution of low-degree polynomials with low influences is nearly identical when the variables are independent Bernoulli and when they are independent Gaussians. Thus, it is possible to apply Theorem 2.8 (12) with error that diminishes with the influences.

A second approach 1819 does not use Borell’s result and is based on induction on dimension in the discrete cube. It is inspired by Bobkov’s inductive proof of the Gaussian isoperimetric inequality 8.

Obtaining the stronger Theorems 2.17 and 2.18 from the weaker statements is more straightforward using simple averaging arguments 51 and applying Boolean regularity lemmas 355370.

2.5. Are pluralities stablest?

Given the asymptotic optimality of the stability of Majority, it is natural to ask if a similar statement holds for low-influence or resilient functions $f : [q]^n \to [q]$ for $q \geq 3$, where the conjectured most-stable functions are now plurality functions. This was first asked in 41. Similar to the case of $q=2$, there is an equivalent Gaussian question 33, which was conjectured to be true in 33. The shape of the conjectured optimal partition of $\mathbb{R}^n$ to $q$ pasts has a number of names, including the “Gaussian double-bubble”, the “standard $Y$”, and the “peace-sign”.

For the isoperimetric problem, corresponding to $\rho \to 1$, the optimality of such a partition for $q=3$ was obtained in 17, under mild conditions and for all $q$ and no additional conditions, in recent work 4748.

The case of noise stability (i.e., constant $\rho$) turned out to be much more subtle. Recall that in the binary case, low-influence functions $f : \{0,1\}^n \to \{0,1\}$ cannot be asymptotically more stable than majorities with the same expectation. In 30 the authors showed that for any probability measure $\mu = (\mu _1,\ldots ,\mu _q) \neq (1/q,\ldots ,1/q)$ that has full support there exists low-influence functions that are more stable than all plurality functions with the same expected values. Thus low influence functions $f : [q]^n \to [q]$ that are not balanced can be asymptotically more stable in all pluralities with the same expectation. On the other hand, in the balanced case, for $q=3$, and for small positive values of $\rho$, the conjectured Gaussian double-bubble was very recently shown to be optimal 31.

3. Paradoxes, noise stability, and reverse hypercontraction

3.1. Probability of paradox

Our next goal is to prove a quantitative version of Arrow’s theorem following 52. We will only discuss the case of three alternatives but will allow different functions to determine different pairwise selections. Recall that we 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 voter ranks $b$ above/below $c$, $z$ is $+1/-1$ if voter ranks $c$ above/below $a$. We will assume further that $f,g,h : \{-1,1\}^n \to \{-1,1\}$ are the aggregation functions for the $a$ vs. $b$, $b$ vs. $c$, and $c$ vs. $a$ preferences. We will again use the following observation used in 37: Since the binary predicate $\psi (a,b,c) = 1(a=b=c)$ for $a,b,c \in \{-1,1\}$ can be expressed as

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

we can write

$$\begin{eqnarray*} \mathbb{P}[f(x) = g(y) = h(z)] &=& \frac{1}{4} \Big (1 + \mathbb{E}[f(x) g(y)] + \mathbb{E}[g(y) h(z)] + \mathbb{E}[h(z) f(x)] \Big ) \\ &=& \frac{1}{4}\Big (1+ \langle f, g \rangle _{-1/3} + \langle g, h \rangle _{-1/3} + \langle h, f \rangle _{-1/3} \Big ), \end{eqnarray*}$$

where the last equality follows from the fact that the uniform distribution over $\{\pm 1\}^3 \setminus \{ \pm (1,1,1) \}$ satisfies $E[x_i y_i] = -1/3$ and similarly for other pairs of coordinates.

To state a quantitive version, we will say that a function $f$ is $\varepsilon$-close to a function $g$ if $\mathbb{P}[f \neq g] \leq \varepsilon$. The quantitative version we we wish to prove is the following.

Theorem 3.1.

For every $\varepsilon > 0$, there exists $\delta (\varepsilon ) > 0$ such that the following holds for every $n$. If

$$\begin{equation*} \mathbb{P}[f(x) = g(y) = h(z)] < \delta , \end{equation*}$$

then either two of the functions $f,g,h$ are $\varepsilon$-close to constant functions of the opposite sign, or there exists a variable $i$ such that $f$, $g$, and $h$ are all $\varepsilon$-close to the same dictator on voter $i$.

The main significance of Theorem 3.1 is that it is dimension independent. We get the same bound no matter what the dimension $=$ number of voters $n$ is. This shows that one cannot avoid the curse of paradoxes in voting by assuming the probability of a paradox vanishes as the number of voters grows. The dependence of $\delta (\varepsilon )$ on $\varepsilon$ proven in 52 is worse than exponential, i.e., $\delta (\varepsilon ) = \exp (-C/\varepsilon ^{21})$. Using the results of 52, hypercontractivity and reverse-hypercontractivity, Keller 39 obtained the optimal dependency, $\delta (\varepsilon ) = C \varepsilon ^3$.

Before discussing how to prove Theorem 3.1, we give a direct implication of the Majority Is Stablest theorem in the case where the functions $f=g=h$ are all balanced so $\mathbb{E}[f] = \mathbb{E}[g] = \mathbb{E}[h] = 0$. Using the Majority Is Stablest theorem, we obtain the following.

Theorem 3.2 (3758).

For every $\varepsilon > 0$, there exists a $\tau > 0$ such that if $f,g,h : \{-1,1\}^n \to \{-1,1\}$ satisfy $\mathbb{E}[f] = \mathbb{E}[g] = \mathbb{E}[h] = 0$ and have all influences bounded above by $\tau$, then

$$\begin{equation} \mathbb{P}[f(x) = g(y) = h(z)] \geq \frac{1}{4} + \frac{3}{4} \langle 2 \chi _{{\frac{1}{2}}} - 1, 2\chi _{{\frac{1}{2}}} -1 \rangle _{-{\frac{1}{3}}} - \varepsilon . {\tag{8}} \end{equation}$$

Again, the right hand side of equation 8 is the asymptotic probability that $\mathbb{P}[f(x) = g(y) = h(z)]$ when $f = g = h = 2 \chi _{{\frac{1}{2}}}(n^{-{\frac{1}{2}}} \sum _{i=1}^n x_i) - 1$ are all given by the same Majority function. Theorem 3.2 provides a surprising counter argument to Condorcet’s arguments. Condorcet argued that pairwise ranking by Majority is problematic as it results in a paradox and Theorem 3.2 shows that in fact Majority asymptotically minimizes the probability of a paradox among low-influence functions.

We also have the following strengthening of Theorem 3.2.

Theorem 3.3.

For every $\varepsilon >0$, there exist $m, \beta >0$ such that if $f,g,h : \{-1,1\}^n\to \{-1,1\}$ satisfy $\mathbb{E}[f] = \mathbb{E}[g] = \mathbb{E}[h] = 1/2$ and $f$, $g$, and $h$ are all $(m,\beta )$-resilient, then

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

3.2. Kalai’s proof for the balanced case

The special case of Arrow’s theorem, where all the functions are balanced, was the first where a quantitative Arrow’s theorem was proved by Kalai 37. The function $f : \{-1,1\}^n \to \{-1,1\}$ is balanced if $\mathbb{P}[f = 1] = \mathbb{P}[f = -1] = 1/2$ which is equivalent to $\mathbb{E}[f] = 0$. In terms of voting this means that a priori both outcomes of $f$ are equally likely.

In this short section we provide the statement and the proof of this special case.

Theorem 3.4 (37).

There exists a constant $C$ such that if $f,g,h : \{-1,1\}^n \to \{-1,1\}$ satisfy $\mathbb{E}[f] = \mathbb{E}[g] = \mathbb{E}[h] = 0$ and

$$\begin{equation*} \mathbb{P}[f(x) = g(y) = h(z)] \leq \varepsilon , \end{equation*}$$

then there exists a dictator function $d$, such that

$$\begin{equation*} \mathbb{P}[f(x) \neq d(x)] \leq C \varepsilon , \quad \mathbb{P}[g(y) \neq d(y)] \leq C \varepsilon , \quad \mathbb{P}[h(z) \neq d(z)] \leq C \varepsilon . \end{equation*}$$

The proof of the theorem will use the Friedgut–Kalai–Naor theorem 25, which will be proved at the end of the section.

Theorem 3.5 (25).

There exists a constant $C$ such that if $f : \{-1,1\}^n \to \{-1,1\}$ satisfies $\mathbb{E}[f] = 0$ and

$$\begin{equation} \sum _{S : |S| = 1} \hat{f}^2(S) = 1-\varepsilon , {\tag{9}} \end{equation}$$

Then there exists a dictator $d$ such that $\mathbb{P}[f(x) \neq d(x)] \leq C \varepsilon$.

We now prove Theorem 3.4.

Proof.

Recalling

$$\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*}$$

and Theorem 2.4, it is clear that to prove Theorem 3.4 it suffices to prove the following. There exists a constant $C$ such that if $f,g : \{-1,1\}^n \to \{-1,1\}$ satisfy $\mathbb{E}[f] = \mathbb{E}[g] = 0$ and

$$\begin{equation} \langle f,g \rangle _{-1/3} \leq -\frac{1}{3}+\varepsilon , {\tag{10}} \end{equation}$$

then there exists a dictator $d$, such that

$$\begin{equation} \mathbb{P}[f(x) \neq d(x)] \leq C \varepsilon , \quad \mathbb{P}[g(y) \neq d(y)] \leq C \varepsilon . {\tag{11}} \end{equation}$$

Note that

$$\begin{equation*} \langle f,g \rangle _{-1/3} \geq (-1/3) \sum _{S : |S| = 1} \hat{f}(S) \hat{g}(S) + (-1/9) \sum _{S : |S| > 1} |\hat{f}(S) \hat{g}(S)| \geq -\frac{1}{3} \gamma -\frac{1}{9}(1-\gamma ), \end{equation*}$$

where $\gamma = \sum _{S : |S| = 1}| \hat{f}(S) \hat{g}(S)|$. Thus if 10 holds, then

$$\begin{equation} \sum _{S : |S| = 1} |\hat{f}(S) \hat{g}(S)| \geq 1-\varepsilon . {\tag{12}} \end{equation}$$

It therefore suffices to show that if 12 holds, then 11 holds. By the Cauchy–Schwarz inequality,

$$\begin{equation*} \sum _{S : |S| = 1} \hat{f}^2(S) \geq (1-\varepsilon )^2 \geq 1-2\varepsilon . \end{equation*}$$

Therefore, by the Friedgut–Kalai–Naor theorem, Theorem 3.5, $f$ is $C_{FKN} \varepsilon$-close to a dictator $d_1$. Similarly, $g$ is $C_{FKN} \varepsilon$-close to a dictator $d_2$. Note that the statement of the theorem is trivial if $C \geq 8$ and $\varepsilon \leq 1/8$, so assume $\varepsilon \leq 1/8$. It remains to show that $d_1 = d_2$. Note that if $d_1 \neq d_2$, then

$$\begin{equation*} \begin{split} &\mathbb{P}[f(x) \neq g(x)]\\ &\qquad \geq \mathbb{P}[d_1(x) \neq d_2(x)] - \mathbb{P}[d_1(x) \neq f(x)] - \mathbb{P}[d_2(x) \neq g(x)] \geq \frac{1}{2} - 2 \frac{1}{8} = 1/4. \end{split} \end{equation*}$$

However, by 12 and using the fact that $\sum _{S} |\hat{f}(S) \hat{g}(S)| \leq 1$,

$$\begin{equation*} \mathbb{E}[f(x)g(x)] = \sum _{S} \hat{f}(S) \hat{g}(S) \geq 1-2\varepsilon , \end{equation*}$$

and therefore $\mathbb{P}[f(x) \neq g(x)] \leq \varepsilon$. The assertion follows.

■

We will now prove the Friedgut–Kalai–Naor theorem, Theorem 3.5, so that the results of this section are self-contained. The proof gives a flavor of some of the reasoning applied in analysis of Boolean function but is not needed for any of the material in the following sections. The proof is similar to the proof in 69. For an alternative proof see 34. We will use the following corollary of hypercontraction.

Lemma 3.6.

Let $q(x) = \sum _{i < j} q_{i,j} x_i x_j$. Then

$$\begin{equation*} \mathbb{E}[q^4] \leq 81 \mathbb{E}[q^2]^2. \end{equation*}$$

Proof.

By hypercontraction if $\eta ^2 \leq 1/3$, then

$$\begin{equation*} \| T_{\eta } q \|_4 \leq \| q \|_2 \implies \mathbb{E}[(T_{\eta } q)^4] \leq \mathbb{E}[q^2]^2. \end{equation*}$$

On the other hand,

$$\begin{equation*} \mathbb{E}[(T_{\eta } q)^4] = \mathbb{E}[(\sum _{i < j} \eta ^2 q_{i,j} x_i x_j)^4] = \eta ^8 \mathbb{E}[q^4], \end{equation*}$$

so by choosing $\eta = 1/\sqrt {3}$, we get

$$\begin{equation*} \mathbb{E}[q^4] \leq \eta ^{-8} \mathbb{E}[q^2]^2. \end{equation*}$$■

The proof will also use the Paley–Zygmund inequality stating that for a positive random variable $Z$ and for $0 \leq \theta \leq 1$ it holds that

$$\begin{equation*} \mathbb{P}[Z \geq \theta \mathbb{E}[Z]] \geq (1-\theta )^2 \frac{\mathbb{E}[Z]^2}{\mathbb{E}[Z^2]}. \end{equation*}$$

Applying this inequality for $Z = q^2$ and using Lemma 3.6 implies the following.

Corollary 3.7.

For $0 \leq \theta \leq 1$,

$$\begin{equation} \mathbb{P}[q^2 \geq \theta \mathbb{E}[q^2]] \geq \frac{(1-\theta )^2}{81}. {\tag{13}} \end{equation}$$

We now prove Theorem 3.5.

Proof.

Let

$$\begin{equation*} \ell (x) = \sum _{|S| \leq 1} \hat{f}(S)x_S, \quad h(x) = \sum _{|S| > 1} \hat{f}(S) x_S, \quad q(x) = 2 \sum _{i < j} \hat{f}(\{i\}) \hat{f}(\{j\}) x_i x_j. \end{equation*}$$

Note that $f = \ell + h$ and that

$$\begin{equation*} \ell ^2(x) = \sum _{i} \hat{f}^2(i) + q(x) = 1-\varepsilon +q(x). \end{equation*}$$

Note that $f^2 = 1$ implies that $\ell ^2 + h(2f-h) = 1$. Moreover using the fact that $|f| = 1$, for all $c \geq 1$ and sufficiently small $\varepsilon$,

$$\begin{equation*} \mathbb{P}[h(2f-h) \geq 3 c \sqrt {\varepsilon }] \leq \mathbb{P}[|h|(|h|+2) \geq 3 c \sqrt {\varepsilon }] \leq \mathbb{P}[|h(x)| \geq c \sqrt {\varepsilon }] \leq \frac{\mathbb{E}[h^2]}{c^2 \varepsilon } \leq \frac{1}{c^2}. \end{equation*}$$

Therefore,

$$\begin{equation*} \begin{split} &\mathbb{P}[|q(x)| \geq (3 c + 1) \sqrt {\varepsilon }]\\ &\qquad = \mathbb{P}[|\ell ^2-1+\varepsilon | \geq (3 c+1) \sqrt {\varepsilon }] \leq \mathbb{P}[|h(2f-h)| + \varepsilon \geq (3 c+1) \sqrt {\varepsilon }] \leq \frac{1}{c^2}. \end{split} \end{equation*}$$

In particular for $c=10$, we obtain

$$\begin{equation*} \mathbb{P}[q^2(x) \geq 1000 \varepsilon ] \leq \frac{1}{100}. \end{equation*}$$

On the other hand, applying 13 with $\theta = 1/20$, implies that

$$\begin{equation*} \mathbb{P}[q^2 \geq \mathbb{E}[q^2]/20] > \frac{1}{100}, \end{equation*}$$

and therefore $\mathbb{E}[q^2] \leq C \varepsilon$, with $C = 20000$. Now

$$\begin{equation*} C \varepsilon \geq \mathbb{E}[q^2] = 4 \sum _{i < j} \hat{f}^2(i) \hat{f}^2(j)=2 \left( \sum _i \hat{f}^2(i) \right)^2 - 2 \sum _i \hat{f}^4(i)=2(1-\varepsilon )^2 - 2 \sum _i \hat{f}^4(i), \end{equation*}$$

so we obtain that

$$\begin{equation*} \max _i \hat{f}^2(i) \geq \sum _i \hat{f}^4(i) \geq (1-\varepsilon )^2 - C \varepsilon = 1 - O(\varepsilon ), \end{equation*}$$

as needed.

■

3.3. Sketch of proof of the general case

The case where the functions are not balanced goes through a longer route 52. We will sketch the proof of Theorem 3.1, which we restate here.

Theorem 3.8.

For every $\varepsilon > 0$, there exists $\delta (\varepsilon ) > 0$ such that the following holds for every $n$. If

$$\begin{equation*} \mathbb{P}[f(x) = g(y) = h(z)] < \delta , \end{equation*}$$

then either two of the functions $f,g,h$ are $\varepsilon$-close to constant functions of the opposite sign, or there exists a variable $i$ such that $f$, $g$, and $h$ are all $\varepsilon$-close to the same dictator on voter $i$.

The main steps of the proof are the following.

I.

First a Gaussian version of the theorem is formulated and proved. One advantage of Gaussian space is that it has no dictators, and therefore, the statement is simpler: that unless some choices are almost fixed, there is a good probability of paradox.

II.

Once a Gaussian version is proven and using the Majority Is Stablest theorem, one can deduce the same statement as long as all of the influences are small. In fact, due to Theorem 2.17, it is sufficient that each variable is influential for at most one of the functions $f,g,h$.

III.

Using the reverse hypercontractivity inequality by Borell 11, Theorem 2.13, it is easy to show that if two voters $i,j$ have high influence for two different functions $f,g$, then the probability of paradox is high.

IV.

The remaining case is where there is only one voter who is influential. In this case, by conditioning on the vote of this voter and applying the low-influence result in II, it is possible to conclude that the function is either close to a dictator or has a high probability of paradox.

To provide more of a taste of the proof, we state the Gaussian version of Arrow’s theorem in I and give more details on the application of the reverse hypercontractivity inequality in III.

The Gaussian version corresponds to a situation where the functions $f,g,h$ can only “see” averages of large subsets of the voters. We thus define a three-dimensional normal vector $N$. The first coordinate of $N$ is supposed to represent the deviation of the number of voters where $a$ ranks above $b$ from the mean. The second coordinate is for $b$ ranking above $c$, and the last coordinate for $c$ ranking above $a$.

Since averaging maintains the expected value and covariances, we define

$$\begin{equation*} \mathbb{E}[N_1^2] = \mathbb{E}[N_2^2] = \mathbb{E}[N_3^2] = 1,\qquad \mathbb{E}[N_1 N_2] = \mathbb{E}[N_2 N_3] = \mathbb{E}[N_3 N_1] = -1/3. \end{equation*}$$

We let $N(1)$, …, $N(n)$ be independent copies of $N$. We write ${\mathcal{N}}=(N(1),\ldots ,N(n))$, and for $1 \leq i \leq 3$ we write ${\mathcal{N}}_i = (N(1)_i,\ldots ,N(n)_i)$. The Gaussian version of Arrow’s theorem states the following.

Theorem 3.9.

For every $\varepsilon > 0$ there exists a $\delta = \delta (\varepsilon ) > 0$ such that the following hold. Let $\phi _1,\phi _2,\phi _3 : \mathbb{R}^n \to \{-1,1\}$. Assume that for all $1 \leq i \neq j \leq 3$ and all $u \in \{-1,1\}$ it holds that

$$\begin{equation} \mathbb{P}[\phi _i({\mathcal{N}}_i) = u] + \mathbb{P}[\phi _j({\mathcal{N}}_j) = -u] \geq 2 \varepsilon . {\tag{14}} \end{equation}$$

Then

$$\begin{equation*} \mathbb{P}[\phi _1({\mathcal{N}}_1) = \phi _2({\mathcal{N}}_2) = \phi _3({\mathcal{N}}_3)] \geq \delta . \end{equation*}$$

Moreover, one may take $\delta = (\varepsilon /2)^{18}$.

Interestingly it is not hard to prove Theorem 3.9 either by Borell’s half-space result, Theorem 2.8, or using a Gaussian variant of his reverse hypercontraction result, Theorem 2.13.

We next apply reverse hypercontraction in the setting of III. We say that coordinate $1$ is pivotal for $f$ at $(x_3,\ldots ,x_n)$ if there exists a value of $x_2$ such that $f(-x_1,x_2,\ldots ,x_n) \neq f(x_1,x_2,\ldots ,x_n)$. We first prove the following.

Lemma 3.10.

Suppose that $I_1(f) > \varepsilon$ and $I_2(g) > \varepsilon$. Let

$$\begin{multline*} B = \{((x_i,y_i,z_i))_{i=3}^n : 1 \text{ is pivotal for } f(\cdot ,\cdot ,x_3,\ldots ,x_n)\\ \text{ and } 2 \text{ is pivotal for } g(\cdot ,\cdot ,y_3,\ldots ,y_n) ) \}. \end{multline*}$$

Then

$$\begin{equation*} \mathbb{P}[B] \geq \varepsilon ^3. \end{equation*}$$

Proof.

Let

$$\begin{equation*} B_1 = \{((x,y,z))_{i=3}^n : 1 \text{ is pivotal for } f(\cdot ,\cdot ,x_3,\ldots ,x_n) \}, \end{equation*}$$

$$\begin{equation*} B_2 = \{((x,y,z))_{i=3}^n : 2 \text{ is pivotal for } g(\cdot ,\cdot ,y_3,\ldots ,y_n)\}. \end{equation*}$$ Then $\mathbb{P}[B_1] \geq I_1(f) > \varepsilon$ and $\mathbb{P}[B_2] \geq I_2(g) > \varepsilon$, and our goal is to obtain a bound on $\mathbb{P}[B_1 \cap B_2]$. Note that the event $B_1$ is determined by $x$ and the event $B_2$ is determined by $y$. So the proof follows reverse hypercontraction with $\rho = -1/3$.

■

We can therefore conclude that:

Theorem 3.11.

Suppose that there exist voters $i$ and $j$ such that

$$\begin{equation*} I_i(f) > \varepsilon , \quad I_j(g) > \varepsilon . \end{equation*}$$

Then $\mathbb{P}[f(x) = g(y) = h(z)] > \frac{1}{36} \varepsilon ^3$.

Proof.

Without loss of generality assume that $i=1$ and $j=2$. Let $B = B_1 \cap B_2$, where $B_1$ and $B_2$ are the events from Lemma 3.10. By the lemma we have $\mathbb{P}[B] \geq \varepsilon ^3$. Note that conditioned on any $((x,y,z)_{i=3}^n) \in B$, the functions $f$, $g$, and $h$ on coordinates $1$ and $2$ satisfy the condition of Arrow’s theorem, Theorem 1.3. Thus with probability at least $1/36$, the outcome is not transitive. Therefore,

$$\begin{equation*} \mathbb{P}[f(x) = g(y) = h(z)] \geq \frac{1}{36} \mathbb{P}[B] \geq \frac{1}{36} \varepsilon ^3. \end{equation*}$$■

3.4. More general statements

In this subsection we discuss a more general statement of Arrow’s theorem which is closer to its original formulation and its quantitative counterpart. This requires that we introduce a number of additional definitions. The reduction from the more general statements of Arrow’s theorem to the three candidate case discussed above will be carried out in this subsection.

3.4.1. General setup

Consider $A = \{a,b,\ldots \}$, a set of $k \geq 3$ alternatives. A transitive preference over $A$ is a ranking of the alternatives from top to bottom where ties are not allowed. Such a ranking corresponds to a permutation $\sigma$ of the elements of $A$ where $\sigma _i$ is the rank of alternative $i$. The set of all rankings will be denoted by $S_k$.

A constitution is a function $F$ that associates to every $n$-tuple $\sigma =(\sigma (1),\ldots ,\sigma (n))$ of transitive preferences (also called a profile), and every pair of alternatives $a,b$ a preference between $a$ and $b$. Some key properties of constitutions include the following.

•

Transitivity. The constitution $F$ is transitive if $F(\sigma )$ is transitive for all $\sigma$. In other words, for all $\sigma$ and for all three alternatives $a$, $b$, and $c$, if $F(\sigma )$ prefers $a$ to $b$, and prefers $b$ to $c$, it also prefers $a$ to $c$. Thus $F$ is transitive if and only if its image is a subset of the permutations on $k$ elements.

•

Independence of irrelevant alternatives (IIA). The constitution $F$ satisfies the IIA property if for every pair of alternatives $a$ and $b$, the social ranking of $a$ vs. $b$ (higher or lower) depends only on their relative rankings by all voters. The IIA condition implies that the pairwise preference between any pair of outcomes depends only on the individual pairwise preferences. Thus, if $F$ satisfies the IIA property, then there exists functions $f^{a>b}$ for every pair of candidates $a$ and $b$ such that$$\begin{equation*} F(\sigma ) = ((f^{a>b}(x^{a>b}) : \{a,b\} \in {k \choose 2}). \end{equation*}$$

•

Unanimity. The constitution $F$ satisfies unanimity if the social outcome ranks $a$ above $b$ whenever all individuals rank $a$ above $b$.

•

The constitution $F$ is a dictator on voter $i$ if $F(\sigma ) = \sigma (i)$ for all $\sigma$ or if $F(\sigma ) = -\sigma$ for all $\sigma$, where $-\sigma (i)$ is the ranking $\sigma _k(i) > \sigma _{k-1}(i) \cdots \sigma _2(i) > \sigma _1(i)$ by reversing the ranking $\sigma (i)$.

Arrow’s theorem states 12 the following.

Theorem 3.12.

Any constitution on three or more alternatives which satisfies transitivity, IIA, and unanimity is a dictatorship.

It is possible to give a characterization of all constitutions satisfying IIA and transitivity. Results of Wilson 74 provide a partial characterization for the case where voters are allowed to rank some alternatives as equal. In order to obtain a quantitative version of Arrow’s theorem, we give an explicit and complete characterization of all constitutions satisfying IIA and transitivity in the case where all voters vote using a strict preference order. Write ${\mathcal{F}}_k(n)$ for the set of all constitutions on $k$ alternatives and $n$ voters satisfying IIA and transitivity. For the characterization it is useful write $A >_F B$ for the statement that for all $\sigma$ it holds that $F(\sigma )$ ranks all alternatives in $A$ above all alternatives in $B$. We will further write $F_{A}$ for the constitution $F$ restricted to the alternatives in $A$. The IIA condition implies that $F_A$ depends only on the individual rankings of the alternatives in the set $A$. The characterization of ${\mathcal{F}}_k(n)$ we prove is the following.

Theorem 3.13.

The class ${\mathcal{F}}_k(n)$ consist exactly of all constitutions $F$ satisfying the following. There exists a partition of the set of alternatives into disjoint sets $A_1$, …, $A_r$ such that the following hold.

•

$A_1 >_F A_2 >_F \cdots >_F A_r$.

•

For all $A_s$ such that $|A_s| \geq 3$, there exists a voter $j$ such that $F_{A_s}$ is a dictator on voter $j$.

•

For all $A_s$ such that $|A_s| = 2$, the constitution $F_{A_s}$ is a nonconstant function of the preferences on the alternatives in $A_s$.

We note that for all $k \geq 3$ all elements of ${\mathcal{F}}_k(n)$ are not desirable as constitutions. Indeed elements of $F_k(n)$ either have dictators whose vote is followed with respect to some of the alternatives or they always rank some alternatives on top some other. For a related discussion see 74. The statement above follows easily from 74, Theorem 3. The exact formulation is taken from 50.

The main goal of the current section is to provide a quantitative version of Theorem 3.13 assuming voters vote independently and uniformly at random. Note that Theorem 3.13 above implies that if $F \not \in {\mathcal{F}}_k(n)$, then the probability of a paradox, $P(F)$, satisfies $P(F) \geq (k!)^{-n}$. However if $n$ is large and the probability of a nontransitive outcome is indeed as small as $(k!)^{-n}$, one may argue that a nontransitive outcome is so unlikely that in practice Arrow’s theorem is irrelevant.

Theorem 3.14.

For every number of alternatives $k \geq 1$ and $0.01 > \varepsilon > 0$, there exists a $\delta = \delta (\varepsilon )$, such that for every $n \geq 1$, if $F$ is a constitution on $n$ voters and $k$ alternatives satisfying

•

IIA and

•

$P(F) < \delta$,

then there exists $G \in {\mathcal{F}}_k(n)$ satisfying $D(F,G) < k^2 \varepsilon$.

We therefore obtain the following.

Corollary 3.15.

For any number of alternatives $k \geq 3$ and $\varepsilon > 0$, there exists a $\delta = \delta (\varepsilon )$, such that for every $n$, if $F$ is a constitution on $n$ voters and $k$ alternatives satisfying

•

IIA, and

•

$F$ is $k^2 \varepsilon$-far from any dictator, so $D(F,G) > k^2 \varepsilon$ for any dictator $G$,

•

for every pair of alternatives $a$ and $b$, the probability that $F$ ranks $a$ above $b$ is at least $k^2 \varepsilon$,

then the probability of a nontransitive outcome, $P(F)$, is at least $\delta$.

Proof.

Assume by contradiction that $P(F) < \delta$. Then by Theorem 3.14 there exists a function $G \in {\mathcal{F}}_{n,k}$ satisfying $D(F,G) < k^2 \varepsilon$. Note that for every pair of alternatives $a$ and $b$ it holds that

$$\begin{equation*} \mathbb{P}[G \text{ ranks } a \text{ above } b] \geq \mathbb{P}[F \text{ ranks } a \text{ above } b] - D(F,G) > 0. \end{equation*}$$

Therefore for every pair of alternatives there is a positive probability that $G$ ranks $a$ above $b$. Thus by Theorem 3.14 it follows that $G$ is a dictator which is a contradiction.

■

Remark 3.16.

Note that if $G \in {\mathcal{F}}_k(n)$ and $F$ is any constitution satisfying $D(F,G) < k^2 \varepsilon$, then $P(F) < k^2 \varepsilon$.

Remark 3.17.

The bounds stated in Theorem 3.14 and Corollary 3.15 in terms of $k$ and $\varepsilon$ are not optimal. We expect that the true dependency has $\delta$ which is some fixed power of $\varepsilon$. Moreover, we expect that the bound $D(F,G) < k^2 \varepsilon$ should be improved to $D(F,G) < \varepsilon$.

3.4.2. Nisan’s argument

Noam Nisan argued in his blog 68 that the natural way to study quantitative versions of Arrow’s theorem is to look at functions from $S_k^n$ to $S_k$ and check to what extent they satisfy the IIA property. That is, while so far we insisted on the IIA condition and checked how far we are from transitivity, Nisan’s suggested that it is more natural to insist on transitivity and ask how far we are from IIA. The $S^n$ point of view of quantitative versions of Arrow’s theorem was also taken in 22.

To formalize his approach, Nisan defines a function to be $\eta$-IIA if for every two alternatives $a$ and $b$, it holds that $\mathbb{P}[F(\sigma ) \neq {\mathcal{F}}(\tau )] \leq \eta$, where $\sigma$ is uniformly chosen and $\tau$ is uniformly chosen conditioned on the $a,b$ ranking at $\tau$ being identical to that of $\sigma$ for all voters. In his blog Nisan sketches how a quantitative Arrow’s theorem proven for the definition used here implies a quantitative Arrow’s theorem for his definition. We briefly repeat the argument with some minor modifications and corrections.

Fix alternatives $a,b$ and write $p_{a,b} : \{0,1\}^n \to [0,1]$ for the probability that, given a vector of $n$ binary preferences between $a$ and $b$, $F$ ranks $a$ above $b$. If $F$ satisfies the IIA property, then $p_{a,b} \in \{0,1\}$ almost surely. If $F$ is $\eta$-IIA, then $\mathbb{E}[2 p_{a,b}(1-p_{a,b})] \leq \eta$, and therefore $\mathbb{E}[\min (p_{a,b},1-p_{a,b})] \leq \eta$.

Assume a quantitative Arrow’s theorem such as the one proven here with parameters $\varepsilon ,\delta$, and suppose by contradiction that $F : S_k^n \to S_k$ is $\eta$-IIA and $\varepsilon$-far from ${\mathcal{F}}_k(n)$ for some small $\eta$ to be determined later. Define a function $G$ as follows. Let $G(\sigma )$ rank $a$ above $b$ if for the majority of $\tau$ which agree with $\sigma$ in the $a,b$ orderings it holds that $F(\tau )$ ranks $a$ above $b$. We note that for every pair of alternatives $a,b$ it holds that

$$\begin{equation*} \mathbb{P}[F(\sigma ), G(\sigma ) \text{ have different order on } a,b] = \mathbb{E}[\min (p_{a,b},1-p_{a,b})] \leq \eta . \end{equation*}$$

By taking a union bound on all pairs of alternatives, this implies that $D(F,G) \leq {k \choose 2} \eta \leq k^2 \eta /2$. Note further that $G$ satisfies the IIA property by definition. Since $F$ is transitive and from the quantitative Arrow’s theorem proven here we conclude that

$$\begin{equation*} D(F,G) \geq \mathbb{P}[P(G)] \geq \delta , \end{equation*}$$

and a contradiction is implied unless $k^2 \eta / 2 \geq \delta$. Thus the Arrow’s theorem for the $\eta$-IIA definition holds with $\eta (\varepsilon ) = 2 \delta /k^2$. (We briefly note that moving from $F$ to $G$ does not preserve the property of the function being balanced so in the setting of Kalai’s theorem an additional argument is needed.)

3.4.3. Proof of Theorem 3.14

Proof.

The proof follows by applying Theorem 3.1 to triplets of alternatives. Assume $P(F) < \delta (\varepsilon )$.

Note that if $g_1,g_2 : \{-1,1\}^n \to \{-1,1\}$ are two different functions, each of which is either a dictator or a constant function, then $D(g_1,g_2) \geq 1/2$. Therefore, for all $a,b$ it holds that $D(f^{a>b},g) < \varepsilon /10$ for at most one function $g$ which is either a dictator or a constant function. In case there exists such function, we let $g^{a>b} = g$; otherwise, we let $g^{a>b} = f^{a>b}$.

Let $G$ be the social choice function defined by the functions $g^{a>b}$. Clearly,

$$\begin{equation*} D(F,G) < {k \choose 2} \varepsilon < k^2 \varepsilon . \end{equation*}$$

The proof would follow if we could show $P(G) = 0$ and, therefore, $G \in {\mathcal{F}}_k(n)$.

To prove that $G \in {\mathcal{F}}_k(n)$ it suffices to show that for every set $A$ of three alternatives, it holds that $G_A \in {\mathcal{F}}_3(n)$. Since $P(F) < \delta$ implies $P(F_A) < \delta$, Theorem 3.1 implies that there exists a function $H_A \in {\mathcal{F}}_3(n)$ such that $D(H_A,F_A) < \varepsilon$. There are two cases to consider:

•

$H_A$ is a dictator. This implies that $f^{a>b}$ is $\varepsilon$-close to a dictator for each $a,b$ and therefore $f^{a>b} = g^{a>b}$ for all pairs $a,b$, so $G_A = H_A \in {\mathcal{F}}_3(n)$.

•

There exists an alternative (say $a$) that $H_A$ always ranks at the top/bottom. In this case we have that $f^{a>b}$ and $f^{c>a}$ are at most $\varepsilon$-far from the constant functions $1$ and $-1$ (or $-1$ and $1$). The functions $g^{a>b}$ and $g^{c>a}$ have to take the same constant values, and therefore again we have that $G_A \in {\mathcal{F}}_3(n)$.

The proof follows.

■

Remark 3.18.

Note that this proof is generic in the sense that it takes the quantitative Arrow’s result for three alternatives as a black box and produces a quantitative Arrow’s result for any $k \geq 3$ alternatives.

3.4.4. Other probability measures

Given the right analytic tools, it is not hard to generalize the proof of Theorems 3.1 and 3.14 to other product distributions. This is done in 60 where some of the tools related to reverse hypercontractivity are developed. In 60 the authors obtain the following extension.

Theorem 3.19 (Quantitative Arrow’s theorem for general distribution).

Let $\varrho$ be general distribution on $S_k$ with $\varrho$ assigning positive probability to each element of $S_k$. Let $\mathbb{P}$ denote the distribution $\varrho ^{\otimes n}$ on $S_k^n$. Then for any number of alternatives $k \geq 3$ and $\varepsilon > 0$, there exists $\delta = \delta (\varepsilon , \rho )>0$, such that for every $n$, if $F : S_k^n \to \{-1,1\}^{k \choose 2}$ satisfies

•

IIA and

•

$\mathbb{P} \{F(\sigma ) \text{ is transitive}\} \geq 1-\delta$.

Then there exists a function $G$ which is transitive and satisfies the IIA property and $\mathbb{P}\{F(\sigma ) \neq G(\sigma )\} \leq \varepsilon$.

3.5. Other variants

In concluding this section, we discuss the optimal low-influence function for voting in the case of $k>3$ alternatives. When we are considering $k \geq 3$ alternatives, we want to define more formally the possible outcome in Arrow’s voting. Since for every two alternatives a winner is decided, the aggregation results in a tournament $G_k$ on the set $[k]$. Recall that $G_k$ is a tournament on $[k]$ if it is a directed graph on the vertex set $[k]$ such that for all $a,b \in [k]$ either $(a > b) \in G_k$ or $(b > a) \in G_k$. Given individual rankings $(\sigma _i)_{i=1}^n$ the tournament $G_k$ is defined as follows.

Let $x^{a > b}(i) = 1$ if $\sigma _i(a) > \sigma _i(b)$, and let $x^{a > b}(i) = -1$ if $\sigma _i(a) < \sigma _i(b)$. Note that $x^{b > a } = -x^{a > b}$.

The binary decision between each pair of candidates is performed via an antisymmetric function $f : \{-1,1\}^n \to \{-1,1\}$ so that $f(-x) = -f(x)$ for all $x \in \{-1,1\}$. Here we assume that each two candidates are compared using the same function $f$. Moreover, since we require that the comparison between $a$ and $b$ and $b$ and $a$ will be the same, we require that $f$ is antisymmetric. The tournament $G_k = G_k(\sigma ; f)$ is then defined by letting $(a > b) \in G_k$ if and only if $f(x^{a > b}) = 1$.

Note that there are $2^{k \choose 2}$ tournaments while there are only $k! = 2^{\Theta (k \log k)}$ linear rankings. For the purposes of social choice, some tournaments make more sense than others.

Definition 3.20.

We say that a tournament $G_k$ is linear if it is acyclic. We will write $\mathrm{Acyc}(G_k)$ for the logical statement that $G_k$ is acyclic. Nonlinear tournaments are often referred to as nonrational in economics as they represent an order where there are three candidates $a$, $b$, and $c$ such that $a$ is preferred to $b$, $b$ is preferred to $c$, and $c$ is preferred to $a$.

We say that the tournament $G_k$ is a unique max tournament if there is a candidate $a \in [k]$ such that for all $b \neq a$ it holds that $(a > b) \in G_k$. We write $\mathrm{UniqueBest}(G_k)$ for the logical statement that $G_k$ has a unique max. Note that the unique max property is weaker than linearity. It corresponds to the fact that there is a candidate that dominates all other candidates.

A generalization of Borell’s result along with a general invariance principle 4951 allows us to prove the following 33.

Theorem 3.21.

For any $k \ge 1$ and $\epsilon >0$ there exists a $\tau (\epsilon , k)>0$ such that for any antisymmetric $f:\{-1,1\}^n \rightarrow \{-1,1\}$ satisfying $\max _i \operatorname {Inf}_i f \le \tau$,

$$\begin{equation} \mathbb{P}[\mathrm{UniqueBest}_k(f)] \le \lim _{n \rightarrow \infty } \mathbb{P}[\mathrm{UniqueBest}_k(\operatorname {Maj}_n)] + \epsilon . \tag{15} \end{equation}$$

An alternative proof can be derived via multidimensional generalization of the inductive Majority Is Stablest theorem using a general notion of $\rho$-concavity 4463.

It is not hard to show that

$$\begin{equation} \mathbb{P}[\mathrm{UniqueBest}_k(\operatorname {Maj}_n)] = k^{-1+o(1)}. {\tag{16}} \end{equation}$$

To prove 16 one can use a multidimensional CLT to represent the advantage of candidate $1$ over candidate $i$ as

$$\begin{equation*} \sqrt {\frac{1}{3}} X + \sqrt {\frac{2}{3}} Z_i, \end{equation*}$$

where $X$, $Z_2$, …, $Z_k$ are i.i.d. $N(0,1)$ random variables.

Other than the case $k=3$, where the notions of unique-max and linear tournaments coincide, very little is known about which function maximizes the probability of a linear order. Even computing this probability for Majority provides a surprising result 51:

Proposition 3.22.

We have

$$\begin{equation} \lim _{n \to \infty } \mathbb{P}[\mathrm{Acyc}(G_k(\sigma ; \operatorname {Maj}_n))] = \exp (-\Theta (k^{5/3})). {\tag{17}} \end{equation}$$

We find this asymptotic behavior quite surprising. Indeed, given the previous results that the probability that there is a unique max is $k^{-1+o(1)}$, one may expect that the probability that the order is linear would be

$$\begin{equation*} k^{-1+o(1)} (k-1)^{-1+o(1)} \cdots = (k!)^{-1+o(1)}. \end{equation*}$$

However, it turns out that there is a strong negative correlation between the event that there is a unique maximum among the $k$ candidates and that among the other candidates there is a unique max.

Proof.

We use the multidimensional CLT. Let

$$\begin{equation*} X_{a > b} = \frac{1}{\sqrt {n}} \left( |\{\sigma : \sigma (a) > \sigma (b)\}| - |\{\sigma : \sigma (b) > \sigma (a) \}| \right). \end{equation*}$$

By the CLT the collection of variables $(X_{a > b})_{a \neq b}$ converges to a joint Gaussian vector $(N_{a > b})_{a \neq b}$ satisfying for all distinct $a,b,c,d$,

$$\begin{equation*} N_{a > b} = - N_{b > a}, \quad \operatorname *{Cov}[N_{a > b}, N_{a > c}] = \frac{1}{3}, \quad \operatorname *{Cov}[N_{a > b}, N_{c > d}] = 0, \end{equation*}$$

and $N_{a > b} \sim N(0,1)$ for all $a$ and $b$.

We are interested in providing bounds on

$$\begin{equation*} P[\forall a > b: N_{a > b} > 0] \end{equation*}$$

as the probability that the resulting tournament is an order is obtained by multiplying this quantity by a $k! = \exp (\Theta (k \log k))$ factor.

We claim that there exist independent $N(0,1)$ random variables $X_a$ for $1 \leq a \leq k$ and $Z_{a > b}$ for $1 \leq a \neq b \leq k$ such that

$$\begin{equation*} N_{a > b} = \frac{1}{\sqrt {3}} (X_a - X_b + Z_{a > b}), \end{equation*}$$

where $Z_{a > b} = - Z_{b > a}$. This follows from the fact that the joint distribution of Gaussian random variables is determined by the covariance matrix (this is noted in the literature in 67).

We now prove the upper bound. Let $\alpha$ be a constant to be chosen later. Note that for all $\alpha$ and large enough $k$ it holds that

$$\begin{equation*} P[|X_a| > k^{\alpha }] \leq \exp (-\Omega (k^{2 \alpha })). \end{equation*}$$

Therefore the probability that for at least half of the $a$’s in the interval $[k/2,k]$ it holds that $|X_a| > k^{\alpha }$ is at most

$$\begin{equation*} \exp (-\Theta (k^{1 + 2 \alpha })). \end{equation*}$$

Let’s assume that at least half of the $a$’s in the interval $[k/2,k]$ satisfy that $|X_a| < k^{\alpha }$. We claim that in this case the number of pairs $a > b$ such that $X_a, X_b \in [-k^{\alpha },k^{\alpha }]$ and $X_a - X_b < 1$ is $\Omega (k^{2-\alpha })$.

For the last claim, partition the interval $[-k^{\alpha },k^{\alpha }]$ into subintervals of length $1$ and note that at least $\Omega (k)$ of the points belong to subintervals which contain at least $\Omega (k^{1-\alpha })$ points. This implies that the number of pairs $a > b$ satisfying $|X_a - X_b| < 1$ is $\Omega (k^{2-\alpha })$.

Note that, for such pair $a > b$ in order that $N_{a > b} > 0$, we need that $Z_{a>b} > -1$ which happens with constant probability.

We conclude that, given that half of the $X$’s fall in $[-k^{\alpha },k^{\alpha }]$, the probability of a linear order is bounded by

$$\begin{equation*} \exp (-\Omega (k^{2-\alpha })). \end{equation*}$$

Thus overall we have bounded the probability by

$$\begin{equation*} \exp (-\Omega (k^{1 + 2 \alpha })) + \exp (-\Omega (k^{2-\alpha })). \end{equation*}$$

The optimal exponent is $\alpha =1/3$ giving the desired upper bound.

For the lower bound we condition on $X_a$ taking value in $(a,a+1) k^{-2/3}$. Each probability is at least $\exp (-O(k^{2/3}))$ and therefore the probability that all $X_a$ take such values is

$$\begin{equation*} \exp (-O(k^{5/3})). \end{equation*}$$

Moreover, conditioned on $X_a$ taking such values, the probability that

$$\begin{equation*} Z_{a > b} > X_b - X_a, \end{equation*}$$

for all $a > b$ is at least

$$\begin{equation*} \left( \prod _{i=0}^{k-1} \Phi (i)^{k^{2/3}} \right)^k \geq \left( \prod _{i=0}^{\infty } \Phi (i) \right)^{k^{5/3}} = \exp (-O(k^{5/3})). \end{equation*}$$

This proves the required result.

■

4. Manipulation and isoperimetry

4.1. Quantitive manipulation

The Gibbard–Satterthwaite theorem, Theorem 1.4, states that under natural conditions, there exist profiles of voters such that at least one voter can manipulate the vote. We are interested in quantitative versions of the statement. A natural approach is to view quantitative statements as isoperimetric results. In classical isoperimetric theory, the goal is to find conditions that establish a large boundary between sets. In the context of manipulation we can consider a voter who can manipulate as a special boundary point, and our goal is to prove that there are many boundary points.

It is natural to consider the following graph where the vertex set is $S_k^n$—the set of all voting profiles and there are edges between voting profiles that differ at a single voter. The statement of the Gibbard–Satterthwaite theorem can be interpreted in terms of this graph: for certain natural partitions of $S_k^n$ into $k$ parts, there is an edge of the graph between two different parts that corresponds to a manipulation. It is not hard to see that the existence of many edges between different parts of the graph follows from classical isoperimetric theory.

Thus one may consider quantitative statements of the Gibbard–Satterthwaite theorem as isoperimetric statements: It is not only the case that there are many edges between different parts of the partition, but it is also the case that many of these edges correspond to manipulation by one of the voters.

In the classical setup, isoperimetry and concentration of measure are closely related. In particular, standard concentration of measure results imply that for any set of fractional size at least $\varepsilon$ in $S_k^n$, the set of profiles at graph distance at most $C(\varepsilon ) \sqrt {n}$ contains almost the whole graph. However, it is not known under what conditions typically a small coalition can manipulate.

It may be useful to consider the following examples:

•

Consider the plurality function with $q \geq 3$ alternatives and $n$ voters. For a voter to be able to manipulate, it must hold that the difference between the top candidate and the second to top is at most $1$. This implies that the probability that there exists a voter who can manipulate is $O(1/\sqrt {n})$.

A second question we can ask is what is the minimal size $s$ of a coalition $S \subset [n]$ that can manipulate with probability close to $1$. Since the difference between the top candidate and the second candidate is typically of order $\sqrt {n}$, it is clear that the size has to be at least order $\sqrt {n}$, and in fact it is easy to see that if $s/\sqrt {n} \to \infty$ that for every fixed set $S$ of size $s$, with probability $1-o(1)$ there exists a subset $T \subset S$ that can change the outcome of the elections by manipulating. Indeed if $a$ is the top candidate, $b$ is the second from the top, and $c$ is a candidate different than $a$ and $b$, we may take $T$ to be all the voters in $S$ that rank $c$ above $b$ above $a$. If these voters would rank $b$ as their top candidate, the outcome will be $b$ which is more favorable to them.

•

Consider the case $q=2$ and the function $g(x) = -f(x)$ where $f$ is the tribes function. The tribes function 6 is a balanced monotone function, where all influences are $O(\log n / n)$. In this case a voter can manipulate if and only if they are influential. Therefore, in general, we cannot expect that the probability that an individual voter can manipulate is higher than $O(\log n /n)$.

4.1.1. A quantitive Gibbard–Satterthwaite theorem

Our goal in this section is to sketch the proof of a quantitative version of the manipulation theorem. We will mostly follow 6162 who proved a pretty general average manipulation theorem for a single voter. Some special cases of the theorem were known before: in particular in the case of three alternatives, this was proved by Friedgut, Kalai, Keller, and Nisan 2426. The original proofs of Gibbard–Satterthwaite theorem were carried out by reduction to Arrow’s theorem. The arguments of 2426 succeed in providing a quantitive reduction to the quantitive Arrow’s theorem, but only in the case of $k = 3$ alternatives.

Here our goal is to sketch the following result: if $k \geq 3$ and the SCF $f$ is $\varepsilon$-far from the family of nonmanipulable functions, then the probability of a ranking profile being manipulable is bounded from below by a polynomial in $1/n$, $1/k$, and $\varepsilon$. We continue by stating the results and their implications, and sketching the main steps of the proof.

4.1.2. Definitions and formal statements

Recall that our basic setup consists of $n$ voters electing a winner among $k$ alternatives via an SCF $f : S_k^n \to \left[k\right]$. We now define manipulability in more detail.

Definition 4.1 (Manipulation points).

Let $\sigma \in S_k^n$ be a ranking profile. Write $a \stackrel{\sigma _i}{>} b$ to denote that alternative $a$ is preferred over $b$ by voter $i$. An SCF $f \colon S_k^n \to [k]$ is manipulable at the ranking profile $\sigma \in S_k^n$ if there exists a $\sigma ' \in S_k^n$ and an $i\in \left[n\right]$ such that $\sigma$ and $\sigma '$ only differ in the $i$th coordinate and

$$\begin{equation*} f(\sigma ') \stackrel{\sigma _i}{>} f(\sigma ). \end{equation*}$$

In this case we also say that $\sigma$ is a manipulation point of $f$, and that $(\sigma ,\sigma ')$ is a manipulation pair for $f$. We say that $f$ is manipulable if it is manipulable at some point $\sigma$. We also say that $\sigma$ is an $r$-manipulation point of $f$ if $f$ has a manipulation pair $(\sigma ,\sigma ')$ such that $\sigma '$ is obtained from $\sigma$ by permuting (at most) $r$ adjacent alternatives in one of the coordinates of $\sigma$. (We allow $r > k$—any manipulation point is an $r$-manipulation point for $r > k$.)

Let $M \left( f \right)$ denote the set of manipulation points of the SCF $f$, and for a given $r$ let $M_r \left( f \right)$ denote the set of $r$-manipulation points of $f$. When the SCF is obvious from the context, we write simply $M$ and $M_r$.

We first recall the Gibbard–Satterthwaite theorem (stated as Theorem 1.4 in the Introduction).

Theorem 4.2 (Gibbard and Satterthwaite 2871).

Any SCF $f \colon S_k^n \to \left[k\right]$ which takes at least three values and is not a dictator (i.e., not a function of only one voter) is manipulable.

This theorem is tight in the sense that monotone SCFs, which are dictators or only have two possible outcomes, are indeed nonmanipulable (a function is nonmonotone, and clearly manipulable, if for some ranking profile a voter can change the outcome from, say, $a$ to $b$ by moving $a$ ahead of $b$ in her preference). It is useful to introduce a refined notion of a dictator before defining the set of nonmanipulable SCFs.

Definition 4.3 (Dictator on a subset).

For a subset of alternatives $H \subseteq \left[k\right]$, let $\operatorname {top}_H$ be the SCF on one voter whose output is always the top-ranked alternative among those in $H$.

Definition 4.4 (Nonmanipulable SCFs).

We denote by

$$\begin{equation*} \operatorname {NONMANIP}\equiv \operatorname {NONMANIP}\left( n, k \right) \end{equation*}$$

the set of nonmanipulable SCFs, which is the following:

$$\begin{align*} \operatorname {NONMANIP}\left( n, k\right) &= \big \{ f : S_k^n \to \left[k\right] \mid f \left( \sigma \right) = \operatorname {top}_H \left( \sigma _i \right)\\ &\qquad \quad \text{ for some } i \in \left[n\right], H \subseteq \left[k\right], H \neq \emptyset \big \} \\ &\quad \cup \big \{ f : S_k^n \to \left[k\right] \mid f\\ &\qquad \quad \text{ is a monotone function taking on exactly two values} \big \}. \end{align*}$$

When the parameters $n$ and $k$ are obvious from the context, we omit them.

Another useful class of functions, which is larger than $\operatorname {NONMANIP}$ but which has a simpler description, is the following.

Definition 4.5.

Define, for parameters $n$ and $k$ that remain implicit,

$$\begin{multline*} \overline{\operatorname {NONMANIP}}=\big \{f \colon S_k^n \to [k] \mid f\\ \text{ only depends on one coordinate or takes at most two values}\big \}. \end{multline*}$$

The notation should be thought of as “closure” rather than “complement”.

As discussed previously, our goal is to study manipulability from a quantitative viewpoint, and in order to do so we need to define the distance between SCFs.

Definition 4.6 (Distance between SCFs).

The distance $\operatorname {{\mathbf{D}}}(f,g)$ between two SCFs $f,g \colon S_k^n \to \left[ k \right]$ is defined as the fraction of inputs on which they differ: $\operatorname {{\mathbf{D}}}\left(f,g\right) = \mathbb{P}\left(f\left(\sigma \right) \neq g\left(\sigma \right)\right)$, where $\sigma \in S_k^n$ is uniformly selected. For a class $G$ of SCFs, we write $\operatorname {{\mathbf{D}}}\left(f,G\right) = \min _{g \in G} \operatorname {{\mathbf{D}}}\left(f,g\right)$.

The concepts of anonymity and neutrality of SCFs will be important to us, so we define them here.

Definition 4.7 (Anonymity).

An SCF is anonymous if it is invariant under changes made to the names of the voters. More precisely, an SCF $f : S_k^n \to \left[k\right]$ is anonymous if for every $\sigma = \left( \sigma _1, \dots , \sigma _n \right) \in S_k^n$ and every $\pi \in S_n$,

$$\begin{equation*} f\left( \sigma _1, \dots , \sigma _n \right) = f\left( \sigma _{\pi \left( 1 \right)}, \dots , \sigma _{\pi \left( n \right)} \right). \end{equation*}$$

Definition 4.8 (Neutrality).

An SCF is neutral if it commutes with changes made to the names of the alternatives. More precisely, an SCF $f : S_k^n \to \left[k\right]$ is neutral if for every $\sigma = \left( \sigma _1, \dots , \sigma _n \right) \in S_k^n$ and every $\pi \in S_k$,

$$\begin{equation*} f \left( \pi \circ \sigma _1, \dots , \pi \circ \sigma _n \right) = \pi \left( f \left( \sigma \right) \right). \end{equation*}$$

Our goal is to sketch the proof of the following theorem.

Theorem 4.9.

Suppose we have $n \geq 1$ voters, $k \geq 3$ alternatives, and an SCF $f : S_k^n \to \left[k\right]$ satisfying $\operatorname {{\mathbf{D}}}\left( f, \operatorname {NONMANIP}\right) \geq \varepsilon$. Then

$$\begin{equation} \mathbb{P}\left( \sigma \in M \left( f \right) \right) \geq \mathbb{P} \left( \sigma \in M_4 \left( f \right) \right)\geq p \left( \varepsilon , \frac{1}{n}, \frac{1}{k} \right) {\tag{18}} \end{equation}$$

for some polynomial $p$, where $\sigma \in S_k^n$ is selected uniformly.

An immediate consequence is that

$$\begin{equation*} \mathbb{P} \left( \left( \sigma , \sigma ' \right) \text{ is a manipulation pair for } f \right) \geq q \left( \varepsilon , \frac{1}{n}, \frac{1}{k} \right) \end{equation*}$$

for some polynomial $q$, where $\sigma \in S_k^n$ is uniformly selected, and $\sigma '$ is obtained from $\sigma$ by uniformly selecting a coordinate $i \in \left\{1, \dots , n \right\}$, uniformly selecting $j \in \left\{1, \dots , k-3 \right\}$, and then uniformly randomly permuting the following four adjacent alternatives in $\sigma _i:$ $\sigma _i \left( j \right), \sigma _i \left( j + 1 \right), \sigma _i \left( j + 2 \right)$, and $\sigma _i \left( j + 3 \right)$.

4.1.3. Proof ideas

We first present our techniques that achieve a lower bound for the probability of manipulation that involves factors of $\frac{1}{k!}$ and then describe how a refined approach leads to a lower bound which has inverse polynomial dependence on $k$.

Rankings graph and applying the original Gibbard–Satterthwaite theorem

Consider the graph $G = \left( V, E \right)$ having vertex set $V = S_k^n$, the set of all ranking profiles, and let $\left( \sigma , \sigma ' \right) \in E$ if and only if $\sigma$ and $\sigma '$ differ in exactly one coordinate. The SCF $f : S_k^n \to \left[k \right]$ naturally partitions $V$ into $k$ subsets. Since every manipulation point must be on the boundary between two such subsets, we are interested in the size of such boundaries.

For two alternatives $a$ and $b$ and for voter $i$, denote by $B_i^{a,b}$ the boundary between $f^{-1} \left( a \right)$ and $f^{-1}\left( b \right)$ in voter $i$. A simple lemma tells us that at least two of the boundaries are large. In the following assume that these are $B_1^{a,b}$ and $B_2^{a,c}$. The case where the boundaries are $B_1^{a,b}$ and $B_2^{c,d}$, where $a,b,c,d$ are distinct, is easier due to the independence between the relative ranking of $a$ vs. $b$ and $c$ vs. $d$.

Now if a ranking profile $\sigma$ lies on both of these boundaries, then applying the original Gibbard–Satterthwaite theorem to the restricted SCF on two voters where we fix all coordinates of $\sigma$ except the first two, we get that there must exist a manipulation point which agrees with $\sigma$ in all but the first two coordinates. Consequently, if we can show that the intersection of the boundaries $B_1^{a,b}$ and $B_2^{a,c}$ is large, then we have many manipulation points.

Fibers and reverse hypercontractivity

In order to have more “control” over what is happening at the boundaries, we partition the graph further—this idea is due to Friedgut et al. 2426. Given a ranking profile $\sigma$ and two alternatives $a$ and $b$, $\sigma$ induces a vector of preferences $x^{a,b}\left( \sigma \right) \in \left\{-1,1\right\}^{n}$ between $a$ and $b$. For a vector $z^{a,b} \in \left\{-1,1\right\}^n$, we define the fiber with respect to preferences between $a$ and $b$, denoted by $F\left( z^{a,b} \right)$, to be the set of ranking profiles for which the vector of preferences between $a$ and $b$ is $z^{a,b}$. We can then partition the vertex set $V$ into such fibers, and work inside each fiber separately. Working inside a specific fiber is advantageous, because it gives us the extra knowledge of the vector of preferences between $a$ and $b$.

We distinguish two types of fibers: large and small. We say that a fiber with respect to preferences between $a$ and $b$ is large if almost all of the ranking profiles in this fiber lie on the boundary $B_1^{a,b}$, and is small otherwise. Now since the boundary $B_1^{a,b}$ is large, either there is big mass on the large fibers with respect to preferences between $a$ and $b$ or big mass on the small fibers. This holds analogously for the boundary $B_2^{a,c}$ and fibers with respect to preferences between $a$ and $c$.

Consider the case when there is big mass on the large fibers of both $B_1^{a,b}$ and $B_2^{a,c}$. Notice that for a ranking profile $\sigma$, being in a fiber with respect to preferences between $a$ and $b$ only depends on the vector of preferences between $a$ and $b$, $x^{a,b}\left( \sigma \right)$, which is a uniform bit vector. Similarly, being in a fiber with respect to preferences between $a$ and $c$ only depends on $x^{a,c}\left( \sigma \right)$. Moreover, we know the exact correlation between the coordinates of $x^{a,b} \left( \sigma \right)$ and $x^{a,c} \left( \sigma \right)$, and it is in exactly this setting where reverse hypercontractivity applies and shows that the intersection of the large fibers of $B_1^{a,b}$ and $B_2^{a,c}$ is also large. Finally, by the definition of a large fiber it follows that the intersection of the boundaries $B_1^{a,b}$ and $B_2^{a,c}$ is large as well, and we can finish the argument using the Gibbard–Satterthwaite theorem as above.

To deal with the case when there is big mass on the small fibers of $B_1^{a,b}$, we use various isoperimetric techniques, including the canonical path method. In particular, we use the fact that for a small fiber for $B_1^{a,b}$, the relative size of the boundary of $B_1^{a,b}$ in the small fiber is comparable to the size of $B_1^{a,b}$ in the small fiber itself, up to polynomial factors.

A refined geometry

Using this approach with the rankings graph above, our bound includes $\frac{1}{k!}$ factors. In order to obtain inverse polynomial dependence on $k$, we use a refined approach. Instead of the rankings graph outlined above, we use an underlying graph with a different edge structure: $\left( \sigma , \sigma ' \right) \in E$ if and only if $\sigma$ and $\sigma '$ differ in exactly one coordinate, and in this coordinate they differ by a single adjacent transposition. In order to prove the refined result, we need to show that the geometric and combinatorial quantities, such as boundaries and manipulation points, are roughly the same in the refined graph as in the original rankings graph.

Figure 1.

The noise stability of dictator and Gaussian half-space of measure $0.5$, i.e., functions $\rho$ and $1-\arccos {\rho }/2\pi$. Note that for every $0 < \rho < 1$, the dictator is more stable than the corresponding half-spaces, and for every $-1 < \rho < 0$ it is less stable than the corresponding half-space.