$\mathbb{P}\left(f\left(\sigma\right)\neq\operatorname{top}_{K}\left(\sigma\right),f\left(\sigma\right)\in
K\right)\geq\frac{{\varepsilon}}{2}.$

Let $\sigma$ be such that
$f\left(\sigma\right)\neq\operatorname{top}_{K}\left(\sigma\right)$ and
$f\left(\sigma\right)\in K$. Now bubble
$\operatorname{top}_{K}\left(\sigma\right)$ up to the top in $\sigma$, call
this ranking profile $\bar{\sigma}$. Clearly then
$\operatorname{top}_{K}\left(\bar{\sigma}\right)=\operatorname{top}_{K}\left(\sigma\right)$.

There are two cases to consider. If $f\left(\sigma\right)\neq
f\left(\bar{\sigma}\right)$, then there is a 2-manipulation point along the
way from $\sigma$ to $\bar{\sigma}$, i.e., a 2-manipulation point
$\hat{\sigma}$ such that $\hat{\sigma}$ agrees with $\sigma$ except perhaps
some alternative $c$ is arbitrarily shifted. Otherwise
$f\left(\sigma\right)=f\left(\bar{\sigma}\right)$, and so
$f\left(\bar{\sigma}\right)\neq\operatorname{top}_{K}\left(\bar{\sigma}\right)$.

Consequently we have that either (4.59) holds, or that

$\mathbb{P}\left(\sigma:f\left(\bar{\sigma}\right)\neq\operatorname{top}_{K}\left(\bar{\sigma}\right)\right)\geq\frac{{\varepsilon}}{4}.$
(4.60)

By the construction of $\bar{\sigma}$, we know that $\bar{\sigma}$ is
uniformly distributed conditional on $\bar{\sigma}\left(1\right)\in K$.
Consequently, by (4.58), we have that

$\mathbb{P}\left(\sigma:f\left(\bar{\sigma}\right)\neq\operatorname{top}_{K}\left(\bar{\sigma}\right)\right)\leq\frac{{\varepsilon}}{50k},$

which contradicts with (4.60) since
$\frac{{\varepsilon}}{50k}<\frac{{\varepsilon}}{4}$. ∎

This concludes the proof of the small fiber case.

####  4.6.5 Large fiber case

In this section we assume that (4.47) holds. We show that we either have a lot
2-manipulation points or we have a lot of local dictators on three
alternatives.

Our first step towards this is the following lemma.

######  Lemma 4.61.

Suppose (4.47) holds. Then

$\mathbb{P}^{\left(a,b\right)}\left(\sigma\in B\right)\geq
1-\frac{{\varepsilon}}{4}.$ (4.61)

###### Proof.

Let $B^{c}=\bar{F}\setminus B$. Our assumption (4.47) implies that
$\mathbb{P}\left(\sigma\in
B^{c}\,\middle|\,\sigma\in\bar{F}\right)\leq\frac{{\varepsilon}}{4k}$, which
means that $\left|B^{c}\right|\leq\frac{{\varepsilon}\left(k-1\right)!}{4k}$,
and so

$\mathbb{P}^{\left(a,b\right)}\left(\sigma\notin
B\right)\leq\frac{{\varepsilon}\left(k-1\right)!}{4k\left(k-2\right)!}<\frac{{\varepsilon}}{4},$

which is equivalent to (4.61). ∎

The next lemma (together with Section 4.6.4) concludes the proof in the large
fiber case.

######  Lemma 4.62.

Suppose (4.47) holds and recall that our SCF $f$ satisfies $\operatorname{{\bf
D}}\left(f,\operatorname{NONMANIP}\right)\geq{\varepsilon}$. Then either

$\mathbb{P}\left(\sigma\in M_{2}\right)\geq\frac{{\varepsilon}}{4k^{2}}$
(4.62)

or

$\mathbb{P}\left(\sigma\in\operatorname{LD}\left(a,b\right)\right)\geq\frac{{\varepsilon}}{4k^{2}}.$
(4.63)

###### Proof.

By Lemma 4.61 we know that (4.61) holds.

Let $\sigma\in S_{k}$ be uniform. Define $\sigma^{\prime}$ by being the same
as $\sigma$ except alternatives $a$ and $b$ are moved to the top of the
coordinate: $\sigma^{\prime}\left(1\right)=a$ and
$\sigma^{\prime}\left(2\right)=b$. Clearly $\sigma^{\prime}$ is distributed
according to $\mathbb{P}^{\left(a,b\right)}\left(\cdot\right)$. Also define
$\sigma^{\prime\prime}=\left[a:b\right]\sigma^{\prime}$.

We partition the set of ranking profiles $S_{k}$ into three parts:

$\displaystyle I_{1}$ $\displaystyle:=\left\\{\sigma\in
S_{k}:f\left(\sigma\right)=\operatorname{top}_{\left\\{a,b\right\\}}\left(\sigma\right),\left(f\left(\sigma^{\prime}\right),f\left(\sigma^{\prime\prime}\right)\right)=\left(a,b\right)\right\\}$
$\displaystyle I_{2}$ $\displaystyle:=\left\\{\sigma\in
S_{k}:f\left(\sigma\right)\neq\operatorname{top}_{\left\\{a,b\right\\}}\left(\sigma\right),\left(f\left(\sigma^{\prime}\right),f\left(\sigma^{\prime\prime}\right)\right)=\left(a,b\right)\right\\}$
$\displaystyle I_{3}$ $\displaystyle:=\left\\{\sigma\in
S_{k}:\left(f\left(\sigma^{\prime}\right),f\left(\sigma^{\prime\prime}\right)\right)\neq\left(a,b\right)\right\\}.$

By (4.61) we know that $\mathbb{P}\left(\sigma\in
I_{3}\right)\leq\frac{{\varepsilon}}{4}$. We also know that
$\mathbb{P}\left(\sigma\in I_{1}\right)\leq 1-{\varepsilon}$, since
$\operatorname{{\bf
D}}\left(f,\operatorname{NONMANIP}\right)\geq{\varepsilon}$. Therefore we must
have

$\mathbb{P}\left(\sigma\in
I_{2}\right)\geq\frac{3{\varepsilon}}{4}>\frac{{\varepsilon}}{2}.$

Let us partition $I_{2}$ further, and write it as
$I_{2}=I_{2}^{\prime}\cup\left(\cup_{c\notin\left\\{a,b\right\\}}I_{2,c}\right)$,
where

$I_{2}^{\prime}:=\left\\{\sigma\in
I_{2}:f\left(\sigma\right)\neq\operatorname{top}_{\left\\{a,b\right\\}}\left(\sigma\right),f\left(\sigma\right)\in\left\\{a,b\right\\}\right\\}$

and for any $c\notin\left\\{a,b\right\\}$,

$I_{2,c}:=\left\\{\sigma\in I_{2}:f\left(\sigma\right)=c\right\\}.$

Suppose $\sigma\in I_{2}^{\prime}$. W.l.o.g. let us assume that $a$ is ranked
higher than $b$ by $\sigma$, and therefore $f\left(\sigma\right)=b$, since
$\sigma\in I_{2}^{\prime}$. Then we can get from $\sigma$ to $\sigma^{\prime}$
by first bubbling up $a$ to the top, and then bubbling up $b$ to just below
$a$. Since $f\left(\sigma\right)=b$ and $f\left(\sigma^{\prime}\right)=a$,
there must be a 2-manipulation point $\hat{\sigma}$ along the way, which is
equal to $\sigma$ except perhaps the positions of $a$ and $b$ are arbitrarily
shifted.

Now suppose that $\sigma\in I_{2,c}$ for some $c\notin\left\\{a,b\right\\}$.
We distinguish two cases: either $c$ is ranked above both $a$ and $b$ in
$\sigma$, or it is not.

If not, then say $a$ is ranked above $c$ in $\sigma$. Bubble $a$ all the way
to the top, and then bubble $b$ as well, all the way to the top, just below
$a$. Since $f\left(\sigma\right)=c$ and $f\left(\sigma^{\prime}\right)=a$,
there must be a 2-manipulation point $\hat{\sigma}$ along the way, which is
equal to $\sigma$ except perhaps the positions of $a$ and $b$ are arbitrarily
shifted.

If $c$ is ranked above both $a$ and $b$ in $\sigma$, then the argument is
similar. First bubble up $a$ and $b$ to just below $c$, and denote this
ranking profile by $\tilde{\sigma}$, then permute these three alternatives
arbitrarily, and then bubble $a$ and $b$ to the top. It is not hard to think
through that either there is a 2-manipulation $\hat{\sigma}$ along the way,
which is then equal to $\sigma$ except perhaps the positions of $a$ and $b$
are arbitrarily shifted, or else
$\tilde{\sigma}\in\operatorname{LD}^{\left\\{a,b,c\right\\}}$.

Combining these cases we see that either (4.62) or (4.63) must hold. ∎

So if (4.62) holds then we are done, and if (4.63) holds, then we refer back
to Section 4.6.4, where we deal with the case of local dictators on three
alternatives.

####  4.6.6 Proof of Theorem 4.29 concluded

###### Proof of Theorem 4.29.

Our starting point is Lemma 4.48, which implies that (4.45) holds (unless we
already have many 2-manipulation points). We then consider two cases, as
indicated in Section 4.6.2.

We deal with the small fiber case—when (4.46) holds—in Section 4.6.3. First,
Lemma 4.49, Corollary 4.50, Lemma 4.51 and Corollary 4.52 show that either
there are many 3-manipulation points, or there are many local dictators on
three alternatives. We then deal with the case of many local dictators in
Section 4.6.4. Lemma 4.53, Corollary 4.54, Lemmas 4.55 and 4.56, Corollary
4.57, and Lemmas 4.58, 4.59 and 4.60 together show that there are many
3-manipulation points if there are many local dictators on three alternatives,
and the SCF is ${\varepsilon}$-far from the family of nonmanipulable
functions.

We deal with the large fiber case—when (4.47) holds—in Section 4.6.5. Here
Lemma 4.62 shows that either we have many 2-manipulation points, or we have
many local dictators on three alternatives. In this latter case we refer back
to Section 4.6.4 to conclude the proof. ∎

###  4.7 Proof for unbounded number of Alternatives

In this section we prove the theorem below, which is the same as our main
theorem, Theorem 4.9, except that the condition of $\operatorname{{\bf
D}}\left(f,\operatorname{NONMANIP}\right)\geq{\varepsilon}$ from Theorem 4.9
is replaced with the stronger condition $\operatorname{{\bf
D}}\left(f,\overline{\operatorname{NONMANIP}}\right)\geq{\varepsilon}$.

######  Theorem 4.63.

Suppose we have $n\geq 2$ voters, $k\geq 3$ alternatives, and a SCF
$f:S_{k}^{n}\to\left[k\right]$ satisfying $\operatorname{{\bf
D}}\left(f,\overline{\operatorname{NONMANIP}}\right)\geq{\varepsilon}$. Then

$\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),$ (4.64)

for some polynomial $p$, where $\sigma\in S_{k}^{n}$ is selected uniformly. In
particular, we show a lower bound of
$\frac{{\varepsilon}^{5}}{10^{9}n^{7}k^{46}}$.

An immediate consequence is that

$\mathbb{P}\left(\left(\sigma,\sigma^{\prime}\right)\text{ is a manipulation
pair for }f\right)\geq q\left({\varepsilon},\frac{1}{n},\frac{1}{k}\right),$

for some polynomial $q$, where $\sigma\in S_{k}^{n}$ is uniformly selected,
and $\sigma^{\prime}$ is obtained from $\sigma$ by uniformly selecting a
coordinate $i\in\left\\{1,\dots,n\right\\}$, uniformly selecting
$j\in\left\\{1,\dots,n-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)$. In particular, the specific lower bound for
$\mathbb{P}\left(\sigma\in M_{4}\left(f\right)\right)$ implies that we can
take
$q\left({\varepsilon},\frac{1}{n},\frac{1}{k}\right)=\frac{{\varepsilon}^{5}}{10^{11}n^{8}k^{47}}$.

For the remainder of the section, let us fix the number of voters $n\geq 2$,
the number of alternatives $k\geq 3$, and the SCF $f$, which satisfies
$\operatorname{{\bf
D}}\left(f,\overline{\operatorname{NONMANIP}}\right)\geq{\varepsilon}$.
Accordingly, we typically omit the dependence of various sets (e.g.,
boundaries between two alternatives) on $f$.

####  4.7.1 Division into cases

Our starting point in proving Theorem 4.63 is Lemma 4.41. Clearly if (4.34)
holds then we are done, so in the rest of Section 4.7 we assume that this is
not the case. Then Lemma 4.41 tells us that (4.35) holds, and w.l.o.g. we may
assume that the two boundaries that the lemma gives us have $i=1$ and $j=2$.
I.e., we have

$\mathbb{P}\left(\sigma\text{ on
}B_{1}^{a,b;\left[a:b\right]}\right)\geq\frac{4{\varepsilon}}{nk^{7}}\quad\text{and}\quad\mathbb{P}\left(\sigma\text{
on }B_{2}^{c,d;\left[c:d\right]}\right)\geq\frac{4{\varepsilon}}{nk^{7}},$

where recall that $\sigma$ is on $B_{1}^{a,b;\left[a:b\right]}$ if
$f\left(\sigma\right)=a$ and $f\left(\left[a:b\right]_{1}\sigma\right)=b$. If
$\sigma$ is on $B_{1}^{a,b;\left[a:b\right]}$ and
$b\stackrel{{\scriptstyle\sigma_{1}}}{{>}}a$, then $\sigma$ is a
2-manipulation point, so if this happens in more than half of the cases when
$\sigma$ is on $B_{1}^{a,b;\left[a:b\right]}$, then we have

$\mathbb{P}\left(\sigma\in M_{2}\right)\geq\frac{2{\varepsilon}}{nk^{7}},$

and we are done. Similarly in the case of the boundary between $c$ and $d$ in
coordinate 2. So we may assume from now on that

$\mathbb{P}\left(\sigma\in\cup_{z_{-1}^{a,b}}B_{1}\left(z_{-1}^{a,b}\right)\right)\geq\frac{2{\varepsilon}}{nk^{7}}\quad\text{and}\quad\mathbb{P}\left(\sigma\in\cup_{z_{-2}^{c,d}}B_{2}\left(z_{-2}^{c,d}\right)\right)\geq\frac{2{\varepsilon}}{nk^{7}}.$

The following lemma is an immediate corollary.

######  Lemma 4.64.

Either

$\mathbb{P}\left(\sigma\in\operatorname{Sm}\left(B_{1}^{a,b;\left[a:b\right]}\right)\right)\geq\frac{{\varepsilon}}{nk^{7}}$
(4.65)

or

$\mathbb{P}\left(\sigma\in\operatorname{Lg}\left(B_{1}^{a,b;\left[a:b\right]}\right)\right)\geq\frac{{\varepsilon}}{nk^{7}},$
(4.66)

and the same can be said for the boundary $B_{2}^{c,d;\left[c:d\right]}$.

We distinguish cases based upon this: either (4.65) holds, or (4.65) holds for
the boundary $B_{2}^{c,d;\left[c:d\right]}$, or (4.66) holds for both
boundaries. We only need one boundary for the small fiber case, and we need
both boundaries only in the large fiber case. So in the large fiber case we
must differentiate between two cases: whether $d\in\left\\{a,b\right\\}$ or
$d\notin\left\\{a,b\right\\}$. We will see that our method of proof works in
both cases.

In the rest of the section we first deal with the small fiber case, and then
with the large fiber case.

####  4.7.2 Small fiber case

We now deal with the case when (4.65) holds. We formalize the ideas of the
outline in a series of statements.

First, we want to formalize that the boundaries of the boundaries are big in
this refined graph setting as well, when we are on a small fiber. The proof
uses the canonical path method, as successfully adapted to this setting by
Isaksson, Kindler and Mossel [41], and is very similar to the proof of Lemma
4.49, with some necessary modifications due to the fact that we now have $n$
coordinates.

######  Lemma 4.65.

Fix a coordinate and a pair of alternatives—for simplicity we choose
coordinate 1 and alternatives $a$ and $b$, but we note that this lemma holds
in general, we do not assume anything special about these choices. Let
$z_{-1}^{a,b}$ be such that $B_{1}\left(z_{-1}^{a,b}\right)$ is a small fiber
for $B_{1}^{a,b;\left[a:b\right]}$. Then, writing $B\equiv
B_{1}\left(z_{-1}^{a,b}\right)$ for simplicity, we have

$\mathbb{P}\left(\sigma\in\partial\left(B\right)\right)\geq\frac{\gamma}{2nk^{5}}\mathbb{P}\left(\sigma\in
B\right).$ (4.67)

###### Proof.

Let $B^{c}=\bar{F}\left(z_{-1}^{a,b}\right)\setminus B$. For every
$\left(\sigma,\sigma^{\prime}\right)\in B\times B^{c}$, we define a canonical
path from $\sigma$ to $\sigma^{\prime}$, which has to pass through at least
one edge in $\partial_{e}\left(B\right)$. Then if we show that every edge in
$\partial_{e}\left(B\right)$ lies on at most $r$ canonical paths, then it
follows that
$\left|\partial_{e}\left(B\right)\right|\geq\left|B\right|\left|B^{c}\right|/r$.

So let $\left(\sigma,\sigma^{\prime}\right)\in B\times B^{c}$. We define a
path from $\sigma$ to $\sigma^{\prime}$ by applying a path construction in
each coordinate one by one, and then concatenating these paths: first in the
first coordinate we get from $\sigma_{1}$ to $\sigma^{\prime}_{1}$, while
leaving all other coordinates unchanged, then in the second coordinate we get
from $\sigma_{2}$ to $\sigma^{\prime}_{2}$, while leaving all other
coordinates unchanged, and so on, finally in the last coordinate we get from
$\sigma_{n}$ to $\sigma^{\prime}_{n}$. In the first coordinate we apply the
path construction of Proposition 4.36, but considering the block formed by $a$
and $b$ as a single element; in all other coordinates we apply the path
construction of Proposition 4.38. Since this path goes from $\sigma$ (which is
in $B$) to $\sigma^{\prime}$ (which is in $B^{c}$), it must pass through at
least one edge in $\partial_{e}\left(B\right)$.

For a given edge $\left(\pi,\pi^{\prime}\right)\in\partial_{e}\left(B\right)$,
at most how many possible $\left(\sigma,\sigma^{\prime}\right)\in B\times
B^{c}$ pairs are there such that the canonical path between $\sigma$ and
$\sigma^{\prime}$ defined above passes through
$\left(\pi,\pi^{\prime}\right)$? Let us differentiate two cases.

Suppose $\pi$ and $\pi^{\prime}$ differ in the first coordinate. Then
coordinates 2 through $n$ of $\sigma$ must agree with the respective
coordinates of $\pi$, while coordinates 2 through $n$ of $\sigma^{\prime}$ can
be anything (up to the restriction given by $\sigma^{\prime}\in
B^{c}\subseteq\bar{F}\left(z_{-1}^{a,b}\right)$), giving
$\left(\frac{k!}{2}\right)^{n-1}$ possibilities. Now fixing all coordinates
except the first,Proposition 4.36 tells us that there are at most
$\left(k-1\right)^{2}\left(k-1\right)!/2<k^{2}\left(k-1\right)!$ possibilities
for the pair $\left(\sigma_{1},\sigma^{\prime}_{1}\right)$. So altogether
there are at most $k^{2}\left(k-1\right)!\left(\frac{k!}{2}\right)^{n-1}$
paths that pass through a given edge in $\partial_{e}\left(B\right)$ in this
case.

Suppose now that $\pi$ and $\pi^{\prime}$ differ in the $i^{\text{th}}$
coordinate, $i\neq 1$. Then the first $i-1$ coordinates of $\sigma^{\prime}$
must agree with the first $i-1$ coordinates of $\pi$, while coordinates
$i+1,\dots,n$ of $\sigma$ must agree with the respective coordinates of $\pi$.
The first $i-1$ coordinates of $\sigma$, and coordinates $i+1,\dots,n$ of
$\sigma^{\prime}$ can be anything (up to the restriction given by
$\sigma,\sigma^{\prime}\in\bar{F}\left(z_{-1}^{a,b}\right)$), giving
$\left(k-1\right)!\left(\frac{k!}{2}\right)^{n-2}$ possibilities. Now fixing
all coordinates except the $i^{\text{th}}$ coordinate, [41, Proposition 6.6.]
tells us that there are at most $k^{4}k!$ possibilities for the pair
$\left(\sigma_{i},\sigma^{\prime}_{i}\right)$. So altogether there are at most
$2k^{4}\left(k-1\right)!\left(\frac{k!}{2}\right)^{n-1}$ paths that pass
through a given edge in $\partial_{e}\left(B\right)$ in this case.

So in any case, there are at most
$2k^{4}\left(k-1\right)!\left(\frac{k!}{2}\right)^{n-1}$ paths that pass
through a given edge in $\partial_{e}\left(B\right)$.

Recall that
$\left|\bar{F}\left(z_{-1}^{a,b}\right)\right|=\left(k-1\right)!\left(\frac{k!}{2}\right)^{n-1}$,
and also
$\left|B^{c}\right|\geq\gamma\left(k-1\right)!\left(\frac{k!}{2}\right)^{n-1}$
since $B$ is a small fiber. Therefore

$\left|\partial_{e}\left(B\right)\right|\geq\frac{\left|B\right|\left|B^{c}\right|}{2k^{4}\left(k-1\right)!\left(\frac{k!}{2}\right)^{n-1}}\geq\frac{\gamma}{2k^{4}}\left|B\right|.$

Now in $G\left(z_{-1}^{a,b}\right)$ every ranking profile has no more than
$nk$ neighbors, which implies (4.67). ∎

######  Corollary 4.66.

If (4.65) holds, then

$\mathbb{P}\left(\sigma\in\bigcup_{z_{-1}^{a,b}}\partial\left(B_{1}\left(z_{-1}^{a,b}\right)\right)\right)\geq\frac{\gamma{\varepsilon}}{2n^{2}k^{12}}.$

###### Proof.

Using the previous lemma and (4.65) we have

$\displaystyle\mathbb{P}\left(\sigma\in\bigcup_{z_{-1}^{a,b}}\partial\left(B_{1}\left(z_{-1}^{a,b}\right)\right)\right)$
$\displaystyle=\sum_{z_{-1}^{a,b}}\mathbb{P}\left(\sigma\in\partial\left(B_{1}\left(z_{-1}^{a,b}\right)\right)\right)$
$\displaystyle\geq\sum_{z_{-1}^{a,b}:B_{1}\left(z_{-1}^{a,b}\right)\subseteq\operatorname{Sm}\left(B_{1}^{a,b;\left[a:b\right]}\right)}\mathbb{P}\left(\sigma\in\partial\left(B_{1}\left(z_{-1}^{a,b}\right)\right)\right)$
$\displaystyle\geq\sum_{z_{-1}^{a,b}:B_{1}\left(z_{-1}^{a,b}\right)\subseteq\operatorname{Sm}\left(B_{1}^{a,b;\left[a:b\right]}\right)}\frac{\gamma}{2nk^{5}}\mathbb{P}\left(\sigma\in
B_{1}\left(z^{a,b}\right)\right)$
$\displaystyle=\frac{\gamma}{2nk^{5}}\mathbb{P}\left(\sigma\in\operatorname{Sm}\left(B_{1}^{a,b}\right)\right)\geq\frac{\gamma{\varepsilon}}{2n^{2}k^{12}}.\qed$

Next, we want to find manipulation points on the boundaries of boundaries.

Before we do this, let us divide the boundaries of the boundaries according to
which direction they are in. If
$\sigma\in\partial\left(B_{1}\left(z_{-1}^{a,b}\right)\right)$ for some
$z_{-1}^{a,b}$, then we know that there exists a ranking profile $\pi$ such
that
$\left(\sigma,\pi\right)\in\partial_{e}\left(B_{1}\left(z_{-1}^{a,b}\right)\right)$.
We know that $\sigma$ and $\pi$ differ in exactly one coordinate, say
coordinate $j$; in this case we say that $\sigma$ is on the boundary of
$B_{1}\left(z_{-1}^{a,b}\right)$ in direction $j$, and we write
$\sigma\in\partial_{j}\left(B_{1}\left(z_{-1}^{a,b}\right)\right)$. (This
notation should not be confused with that of the edge boundary.)

We can write the boundary of $B_{1}\left(z_{-1}^{a,b}\right)$ as a union of
boundaries in the different directions:

$\partial\left(B_{1}\left(z_{-1}^{a,b}\right)\right)=\cup_{j=1}^{n}\partial_{j}\left(B_{1}\left(z_{-1}^{a,b}\right)\right),$

but note that this is not (necessarily) a disjoint union, as a ranking profile
$\sigma$ for which
$\sigma\in\partial\left(B_{1}\left(z_{-1}^{a,b}\right)\right)$ might lie on
the boundary in multiple directions.

In particular, we differentiate between the boundary in direction 1 and the
boundary in all other directions. To this end we introduce the notation

$\partial_{-1}\left(B_{1}\left(x_{-1}^{a,b}\right)\right):=\cup_{j=2}^{n}\partial_{j}\left(B_{1}\left(x_{-1}^{a,b}\right)\right).$

With this notation we have the following corollary of Corollary 4.66.

######  Corollary 4.67.

If (4.65) holds, then either

$\mathbb{P}\left(\sigma\in\cup_{z_{-1}^{a,b}}\partial_{-1}\left(B_{1}\left(z_{-1}^{a,b}\right)\right)\right)\geq\frac{\gamma{\varepsilon}}{4n^{2}k^{12}}$
(4.68)

or

$\mathbb{P}\left(\sigma\in\cup_{z_{-1}^{a,b}}\partial_{1}\left(B_{1}\left(z_{-1}^{a,b}\right)\right)\right)\geq\frac{\gamma{\varepsilon}}{4n^{2}k^{12}}.$
(4.69)

######  Lemma 4.68.

Suppose the ranking profile $\sigma$ is on the boundary of a fiber for
$B_{1}^{a,b;\left[a:b\right]}$ in direction $j\neq 1$, i.e.,

$\sigma\in\cup_{z_{-1}^{a,b}}\partial_{-1}\left(B_{1}\left(z_{-1}^{a,b}\right)\right).$

Then there exists a 3-manipulation point $\hat{\sigma}$ which agrees with
$\sigma$ in all coordinates except perhaps coordinate 1 and some coordinate
$j\neq 1$; furthermore $\hat{\sigma}_{1}$ is equal to $\sigma_{1}$ or
$\left[a:b\right]\sigma_{1}$, except that the position of a third alternative
$c$ might be shifted arbitrarily, and $\hat{\sigma}_{j}$ is equal to
$\sigma_{j}$ or $z\sigma_{j}$ for some adjacent transposition $z\in T$, except
the position of $b$ might be shifted arbitrarily.

###### Proof.

Suppose $x_{-1}^{a,b}\left(\sigma\right)=z_{-1}^{a,b}$. Since
$\sigma\in\partial\left(B_{1}\left(z_{-1}^{a,b}\right)\right)\subseteq
B_{1}\left(z_{-1}^{a,b}\right)$, we know that $f\left(\sigma\right)=a$, and if
$\sigma^{\prime}=\left[a:b\right]_{1}\sigma$, then
$f\left(\sigma^{\prime}\right)=b$.

Let $\pi=\left(\pi_{j},\sigma_{-j}\right)$ denote the ranking profile such
that
$\left(\sigma,\pi\right)\in\partial_{e}\left(B_{1}\left(z_{-1}^{a,b}\right)\right)$.
Let $\pi^{\prime}:=\left[a:b\right]_{1}\pi$. Since $\pi\notin
B_{1}\left(z_{-1}^{a,b}\right)$,
$\left(f\left(\pi\right),f\left(\pi^{\prime}\right)\right)\neq\left(a,b\right)$.
Then, by Lemma 4.39, if $f\left(\pi\right)\neq f\left(\pi^{\prime}\right)$,
then one of $\pi$ and $\pi^{\prime}$ is a 2-manipulation point.

So let us suppose that $f\left(\pi\right)=f\left(\pi^{\prime}\right)$. If
$f\left(\pi^{\prime}\right)=a$, then one of $\sigma^{\prime}$ and
$\pi^{\prime}$ is a 2-manipulation point by Lemma 4.39, since
$\pi^{\prime}=z_{j}\sigma^{\prime}$ for some adjacent transposition
$z\neq\left[a:b\right]$. If $f\left(\pi\right)=b$, then similarly one of
$\sigma$ and $\pi$ is a 2-manipulation point.

Finally let us suppose that $f\left(\pi\right)=c$ for some
$c\notin\left\\{a,b\right\\}$. In this case Lemma 4.40 tells us that there
exists an appropriate 3-manipulation point $\hat{\sigma}$. ∎

######  Corollary 4.69.

If (4.68) holds, then

$\mathbb{P}\left(\sigma\in
M_{3}\right)\geq\frac{\gamma{\varepsilon}}{8n^{3}k^{16}}.$ (4.70)

###### Proof.

Lemma 4.68 tells us that for every ranking profile $\sigma$ which is on the
boundary of a fiber for $B_{1}^{a,b;\left[a:b\right]}$ in some direction
$j\neq 1$, there is a 3-manipulation point $\hat{\sigma}$ ’’nearby‘‘; the
lemma specifies what ’’nearby‘‘ means.

How many ranking profiles $\sigma$ may give the same $\hat{\sigma}$? At most
$2nk^{4}$, which comes from the following: $\sigma$ and $\hat{\sigma}$ agree
in all coordinates except maybe two, one of which is the first coordinate;
there are $n-1<n$ possibilities for the other coordinate; in the first
coordinate, $\hat{\sigma}_{1}$ is either $\sigma_{1}$ or
$\left[a:b\right]\sigma_{1}$ (giving 2 possibilities), while some alternative
$c$ ($k-2<k$ possibilities) might be shifted arbitrarily (at most $k$
possibilities); in the other coordinate $j\neq 1$, $\hat{\sigma}_{j}$ is equal
to $\sigma_{j}$ or $z\sigma_{j}$ for some adjacent transposition $z\in T$ (at
most $k$ possibilities), except $b$ might be shifted arbitrarily ($k$
possibilities).

So putting this result from Lemma 4.68 together with (4.68) yields (4.70). ∎

The remaining case we have to deal with is when (4.69) holds.

######  Lemma 4.70.

Suppose the ranking profile $\sigma$ is on the boundary of a fiber for
$B_{1}^{a,b;\left[a:b\right]}$ in direction 1, i.e.,

$\sigma\in\cup_{z_{-1}^{a,b}}\partial_{1}\left(B_{1}\left(z_{-1}^{a,b}\right)\right).$

Then either $\sigma\in\operatorname{LD}_{1}\left(a,b\right)$, or there exists
a 3-manipulation point $\hat{\sigma}$ which agrees with $\sigma$ in all
coordinates except perhaps in coordinate 1; furthermore $\hat{\sigma}_{1}$ is
equal to $\sigma_{1}$, or $\left[a:b\right]\sigma_{1}$ except that the
position of a third alternative $c$ might be shifted arbitrarily.

###### Proof.

Just like the proof of Lemma 4.51. ∎

The following corollary then tells us that either we have found many
3-manipulation points, or we have many local dictators on three alternatives
in coordinate 1.

######  Corollary 4.71.

Suppose (4.69) holds. Then either

$\sum_{c\notin\left\\{a,b\right\\}}\mathbb{P}\left(\sigma\in\operatorname{LD}_{1}^{\left\\{a,b,c\right\\}}\right)=\mathbb{P}\left(\sigma\in\operatorname{LD}_{1}\left(a,b\right)\right)\geq\frac{\gamma{\varepsilon}}{8n^{2}k^{12}}$
(4.71)

or

$\mathbb{P}\left(\sigma\in
M_{3}\right)\geq\frac{\gamma{\varepsilon}}{16n^{2}k^{14}}.$

####  4.7.3 Dealing with local dictators

So the remaining case we have to deal with in this small fiber case is when
(4.71) holds, i.e., we have many local dictators in coordinate 1.

######  Lemma 4.72.

Suppose $\sigma\in\operatorname{LD}_{1}^{\left\\{a,b,c\right\\}}$ for some
alternative $c\notin\left\\{a,b\right\\}$. Define
$\sigma^{\prime}:=\left(\sigma^{\prime}_{1},\sigma_{-1}\right)$ by letting
$\sigma^{\prime}_{1}$ be equal to $\sigma_{1}$ except that the block of $a$,
$b$ and $c$ is moved to the top of the coordinate. Then

  * •

either $\sigma^{\prime}\in\operatorname{LD}_{1}^{\left\\{a,b,c\right\\}}$,

  * •

or there exists a 3-manipulation point $\hat{\sigma}$ which agrees with
$\sigma$ in all coordinates except perhaps in coordinate 1; furthermore
$\hat{\sigma}_{1}$ is equal to $\sigma_{1}$ except that the position of $a$,
$b$ and $c$ might be shifted arbitrarily.

###### Proof.

Just like the proof of Lemma 4.53. ∎

######  Corollary 4.73.

If (4.71) holds, then either

$\sum_{c\notin\left\\{a,b\right\\}}\mathbb{P}\left(\sigma\in
LD_{1}^{\left\\{a,b,c\right\\}},\left\\{\sigma_{1}\left(1\right),\sigma_{1}\left(2\right),\sigma_{1}\left(3\right)\right\\}=\left\\{a,b,c\right\\}\right)\geq\frac{\gamma{\varepsilon}}{16n^{2}k^{13}}$
(4.72)

or

$\mathbb{P}\left(\sigma\in
M_{3}\right)\geq\frac{\gamma{\varepsilon}}{16n^{2}k^{15}}.$

###### Proof.

Just like the proof of Corollary 4.54. ∎

Now (4.72) is equivalent to

$\sum_{c\notin\left\\{a,b\right\\}}\mathbb{P}\left(\sigma\in
LD_{1}^{\left\\{a,b,c\right\\}},\left(\sigma_{1}\left(1\right),\sigma_{1}\left(2\right),\sigma_{1}\left(3\right)\right)=\left(a,b,c\right)\right)\geq\frac{\gamma{\varepsilon}}{96n^{2}k^{13}}.$
(4.73)

We know that

$\mathbb{P}\left(\left(\sigma_{1}\left(1\right),\sigma_{1}\left(2\right),\sigma_{1}\left(3\right)\right)=\left(a,b,c\right)\right)=\frac{1}{k\left(k-1\right)\left(k-2\right)}\leq\frac{6}{k^{3}},$

and so (4.73) implies (recall Definition 4.45)

$\sum_{c\notin\left\\{a,b\right\\}}\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in
LD_{1}^{\left\\{a,b,c\right\\}}\right)\geq\frac{\gamma{\varepsilon}}{576n^{2}k^{10}}.$
(4.74)

Now fix an alternative $c\notin\left\\{a,b\right\\}$ and define the graph
$G_{\left(a,b,c\right)}=\left(V_{\left(a,b,c\right)},E_{\left(a,b,c\right)}\right)$
to have vertex set

$V_{\left(a,b,c\right)}:=\left\\{\sigma\in
S_{k}^{n}:\left(\sigma_{1}\left(1\right),\sigma_{1}\left(2\right),\sigma_{1}\left(3\right)\right)=\left(a,b,c\right)\right\\}$

and for $\sigma,\pi\in V_{\left(a,b,c\right)}$ let $\left(\sigma,\pi\right)\in
E_{\left(a,b,c\right)}$ if and only if $\sigma$ and $\pi$ differ in exactly
one coordinate, and by an adjacent transposition in this coordinate. So
$G_{\left(a,b,c\right)}$ is the subgraph of the refined rankings graph induced
by the vertex set $V_{\left(a,b,c\right)}$.

Let

$T_{1}\left(a,b,c\right):=V_{\left(a,b,c\right)}\cap
LD_{1}^{\left\\{a,b,c\right\\}},$

and let $\partial_{e}\left(T_{1}\left(a,b,c\right)\right)$ and
$\partial\left(T_{1}\left(a,b,c\right)\right)$ denote the edge and vertex
boundary of $T_{1}\left(a,b,c\right)$ in $G_{\left(a,b,c\right)}$,
respectively.

The next lemma shows that unless $T_{1}\left(a,b,c\right)$ is almost all of
$V_{\left(a,b,c\right)}$, the size of the boundary
$\partial\left(T_{1}\left(a,b,c\right)\right)$ is comparable to the size of
$T_{1}\left(a,b,c\right)$.

######  Lemma 4.74.

Let $c\notin\left\\{a,b\right\\}$ be arbitrary. Write $T\equiv
T_{1}\left(a,b,c\right)$ for simplicity. If
$\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in T\right)\leq 1-\delta$,
then

$\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in\partial\left(T\right)\right)\geq\frac{\delta}{nk^{3}}\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in
T\right).$ (4.75)

###### Proof.

The proof is essentially the same as the proof of Lemma 4.55, with a slight
modification to deal with $n$ coordinates. Let
$T^{c}=V_{\left(a,b,c\right)}\setminus T\left(a,b,c\right)$. For every
$\left(\sigma,\sigma^{\prime}\right)\in T\times T^{c}$ we define a canonical
path from $\sigma$ to $\sigma^{\prime}$ by applying a path construction in
each coordinate one by one, and then concatenating these paths. In all
coordinates we apply the path construction of [41, Proposition 6.4.], but in
the first coordinate we only apply it to alternatives
$\left[k\right]\setminus\left\\{a,b,c\right\\}$.

The analysis of this construction is done in exactly the same way as in Lemma
4.65; in the end we get that
$\left|\partial_{e}\left(T\right)\right|\geq\frac{\delta}{k^{2}}\left|T\right|$.
Now every vertex in $V_{\left(a,b,c\right)}$ has no more than $nk$ neighbors,
which implies (4.75). ∎

The next lemma tells us that if $\sigma$ is on the boundary of a set of local
dictators on $\left\\{a,b,c\right\\}$ for some alternative
$c\notin\left\\{a,b\right\\}$ in coordinate 1, then there is a 4-manipulation
point $\hat{\sigma}$ which is close to $\sigma$. The proof is similar to that
of Lemma 4.56, but we have to take care of all $n$ coordinates.

######  Lemma 4.75.

Suppose $\sigma\in\partial\left(T_{1}\left(a,b,c\right)\right)$ for some
$c\notin\left\\{a,b\right\\}$. We distinguish two cases, based on the number
of alternatives.

If $k=3$, then there exists a (3-)manipulation point $\hat{\sigma}$ which
differs from $\sigma$ in at most two coordinates, one of them being the first
coordinate.

If $k\geq 4$, then there exists a 4-manipulation point $\hat{\sigma}$ which
differs from $\sigma$ in at most two coordinates, one of them being the first
coordinate; furthermore, $\hat{\sigma}_{1}$ is equal to $\sigma_{1}$ except
that the order of the block of $a$, $b$ and $c$ might be rearranged and an
additional alternative $d$ might be shifted arbitrarily; and in the other
coordinate, call it $j$, $\hat{\sigma}_{j}$ is equal to $\sigma_{j}$ except
perhaps $a$, $b$ and $c$ are shifted arbitrarily.

###### Proof.

Let $\pi$ be the ranking profile such that
$\left(\sigma,\pi\right)\in\partial_{e}\left(T_{1}\left(a,b,c\right)\right)$,
let $j$ be the coordinate in which they differ, and let $z$ be the adjacent
transposition in which they differ, i.e., $\pi=z_{j}\sigma$. Since $\pi\notin
T_{1}\left(a,b,c\right)$, there exists a reordering of the block of $a$, $b$,
and $c$ at the top of $\pi_{1}$ such that the outcome of $f$ is not the top
ranked alternative in coordinate 1. Call the resulting vector
$\pi^{\prime}_{1}$, and let
$\pi^{\prime}:=\left(\pi^{\prime}_{1},\pi_{-1}\right)$. W.l.o.g. let us assume
that $\pi^{\prime}_{1}\left(1\right)=a$. Let us also define
$\sigma^{\prime}:=z_{j}\pi^{\prime}$. We distinguish two cases: $j=1$ and
$j\neq 1$.

If $j=1$ (in which case we must have $k\geq 5$), $\pi^{\prime}$ is a
2-manipulation point, since $f\left(\sigma^{\prime}\right)=a$.

If $j\neq 1$, then there are various cases to consider. If the adjacent
transposition $z$ does not move $a$, then either $\pi^{\prime}$ or
$\sigma^{\prime}$ is a 2-manipulation point. So let us suppose that
$z=\left[a:d\right]$ for some $d\neq a$.

Clearly we must have $f\left(\pi^{\prime}\right)=d$, or else $\pi^{\prime}$ or
$\sigma^{\prime}$ is a 2-manipulation point. Suppose first that
$d\in\left\\{b,c\right\\}$. W.l.o.g. suppose that $d=b$.

Then take alternative $c$ in coordinate $j$ of both $\sigma^{\prime}$ and
$\pi^{\prime}$, and bubble it to the block of $a$ and $b$ simultaneously in
the two ranking profiles. If along the way the value of the outcome of the SCF
$f$ changes from $a$ or $b$, respectively, then we have a 2-manipulation point
by Lemma 4.39. Otherwise, we now have $a$, $b$, and $c$ adjacent in both
coordinates 1 and $j$. Now rearranging the order of the blocks of $a$, $b$,
and $c$ in these two coordinates (which can be done using adjacent
transpositions), we either get a 2-manipulation point by Lemma 4.39, or we can
define a new SCF on two voters and three alternatives, $a$, $b$, and $c$. This
SCF takes on three values and it is also not hard to see that the outcome is
not only a function of the first coordinate, so by the Gibbard-Satterthwaite
theorem we know that this SCF has a manipulation point, which is a
3-manipulation point of the original SCF $f$.

Now let us look at the case when $d\notin\left\\{b,c\right\\}$. In this case
we do something similar to what we just did in the previous paragraph. In both
$\sigma^{\prime}$ and $\pi^{\prime}$, first bubble up alternative $d$ in
coordinate 1 up to the block of $a$, $b$, and $c$, and then bubble $b$ and $c$
in coordinate $j$ to the block of $a$ and $d$. All of this using adjacent
transpositions. If the value of the outcome of the SCF $f$ changes from $a$ or
$d$, respectively, at any time along the way, then we have a 2-manipulation
point by Lemma 4.39. Otherwise, we now have $a$, $b$, $c$ and $d$ adjacent in
both coordinates 1 and $j$, and we can apply the same trick to find a
4-manipulation point, using the Gibbard-Satterthwaite theorem. ∎

The next corollary puts together Corollary 4.73 and Lemmas 4.74 and 4.75.

######  Corollary 4.76.

Suppose (4.72) holds. Then if for every $c\notin\left\\{a,b\right\\}$ we have
$\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in
T_{1}\left(a,b,c\right)\right)\leq 1-\frac{{\varepsilon}}{100k}$, then

$\mathbb{P}\left(\sigma\in
M_{4}\right)\geq\frac{\gamma{\varepsilon}^{2}}{345600n^{4}k^{22}}.$

###### Proof.

We know that (4.72) implies

$\sum_{c\notin\left\\{a,b\right\\}}\mathbb{P}_{1}^{a,b,c}\left(\sigma\in
T_{1}\left(a,b,c\right)\right)\geq\frac{\gamma{\varepsilon}}{576n^{2}k^{10}}.$

Now then using the assumptions, Lemma 4.74 with
$\delta=\frac{{\varepsilon}}{100k}$ and Lemma 4.75, we have

$\displaystyle\mathbb{P}\left(\sigma\in M_{4}\right)$
$\displaystyle\geq\sum_{c\neq\left\\{a,b\right\\}}\frac{1}{k^{3}}\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in
M_{4}\right)\geq\sum_{c\notin\left\\{a,b\right\\}}\frac{1}{6nk^{8}}\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in\partial\left(T_{1}\left(a,b,c\right)\right)\right)$
$\displaystyle\geq\sum_{c\notin\left\\{a,b\right\\}}\frac{{\varepsilon}}{600n^{2}k^{12}}\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in
T_{1}\left(a,b,c\right)\right)\geq\frac{\gamma{\varepsilon}^{2}}{345600n^{4}k^{22}}.\qed$

So again we are left with one case to deal with: if there exists an
alternative $c\notin\left\\{a,b\right\\}$ such that
$\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in
T_{1}\left(a,b,c\right)\right)>1-\frac{{\varepsilon}}{100k}$. Define a subset
of alternatives $K\subseteq\left[k\right]$ in the following way:

$K:=\left\\{a,b\right\\}\cup\left\\{c\in\left[k\right]\setminus\left\\{a,b\right\\}:\mathbb{P}_{1}^{\left(a,b,c\right)}\left(\sigma\in
T_{1}\left(a,b,c\right)\right)>1-\frac{{\varepsilon}}{100k}\right\\}.$

In addition to $a$ and $b$, $K$ contains those alternatives that whenever they
are at the top of coordinate 1 with $a$ and $b$, they form a local dictator
with high probability.

So our assumption now is that $\left|K\right|\geq 3$.

Our next step is to show that unless we have many manipulation points, for any
alternative $c\in K$, conditioned on $c$ being at the top of the first
coordinate, the outcome of $f$ is $c$ with probability close to 1.

######  Lemma 4.77.

Let $c\in K$. Then either

$\mathbb{P}_{1}^{\left(c\right)}\left(f\left(\sigma\right)=c\right)\geq
1-\frac{{\varepsilon}}{50k},$ (4.76)

or

$\mathbb{P}\left(\sigma\in M_{2}\right)\geq\frac{{\varepsilon}}{100k^{4}}.$
(4.77)

###### Proof.

Just like the proof of Lemma 4.58. ∎

We now deal with alternatives that are not in $K$: either we have many
manipulation points, or for any alternative $d\notin K$, the outcome of $f$ is
_not_ $d$ with probability close to 1.

######  Lemma 4.78.

Let $d\notin K$. If
$\mathbb{P}\left(f\left(\sigma\right)=d\right)\geq\frac{{\varepsilon}}{4k}$,
then

$\mathbb{P}\left(\sigma\in
M_{4}\right)\geq\frac{{\varepsilon}^{2}}{10^{6}n^{2}k^{13}}.$

###### Proof.

The proof is very similar to that of Lemma 4.59: we do the same steps in the
first coordinate as done in the proof of Lemma 4.59, and the fact that we have
$n$ coordinates only matters at the very end.

Let $\sigma$ be such that $f\left(\sigma\right)=d$. We will keep coordinates 2
through $n$ to be fixed as $\sigma_{-1}$ throughout the proof. By bubbling
alternatives $d$, $a$, and $b$ in the first coordinate, we can define
$\sigma^{\prime}$, $\sigma^{\left(d,b,a\right)}$,
$\sigma^{\left(d,a,b\right)}$, $\sigma^{\left(a,b,d\right)}$,
$\sigma^{\left(a,d,b\right)}$, $\sigma^{\left(b,a,d\right)}$, and
$\sigma^{\left(b,d,a\right)}$ just as in the proof of Lemma 4.59. Again, we
can show that either

$\mathbb{P}\left(\sigma\in M_{2}\right)\geq\frac{{\varepsilon}}{1600k^{3}},$

in which case we are done, or

$\mathbb{P}_{1}^{\left(a,b,d\right)}\left(\sigma^{\left(a,b,d\right)}\in
LD_{1}^{\left\\{a,b,d\right\\}}\right)=\mathbb{P}\left(\sigma:\sigma^{\left(a,b,d\right)}\in
LD_{1}^{\left\\{a,b,d\right\\}}\right)\geq\frac{{\varepsilon}}{1600k}.$ (4.78)

Define $G_{\left(a,b,d\right)}$ and $T_{\left(a,b,d\right)}$ analogously to
$G_{\left(a,b,c\right)}$ and $T_{\left(a,b,c\right)}$, respectively.

Suppose that (4.78) holds. We also know that $d\notin K$, so Lemma 4.74
applies, and then Lemma 4.75 shows us how to find manipulation points. We can
put these arguments together, just like in the proof of Corollary 4.76, to
show what we need:

$\displaystyle\mathbb{P}\left(\sigma\in M_{4}\right)$
$\displaystyle\geq\frac{1}{k^{3}}\mathbb{P}_{1}^{\left(a,b,d\right)}\left(\sigma\in
M_{4}\right)\geq\frac{1}{6nk^{8}}\mathbb{P}_{1}^{\left(a,b,d\right)}\left(\sigma\in\partial\left(T_{1}\left(a,b,d\right)\right)\right)$
$\displaystyle\geq\frac{{\varepsilon}}{600n^{2}k^{12}}\mathbb{P}_{1}^{\left(a,b,d\right)}\left(\sigma\in
T_{1}\left(a,b,d\right)\right)\geq\frac{{\varepsilon}^{2}}{10^{6}n^{2}k^{13}}.\qed$

Putting together the results of the previous lemmas, there is only one case to
be covered, which is covered by the following final lemma. Basically, this
lemma says that unless there are enough manipulation points, our function is
close to a dictator in the first coordinate, on the subset of alternatives
$K$.

######  Lemma 4.79.

Recall that we assume that $\operatorname{{\bf
D}}\left(f,\overline{\operatorname{NONMANIP}}\right)\geq{\varepsilon}$.
Furthermore assume that $\left|K\right|\geq 3$, for every $c\in K$ we have

$\mathbb{P}_{1}^{\left(c\right)}\left(f\left(\sigma\right)=c\right)\geq
1-\frac{{\varepsilon}}{50k},$ (4.79)

and for every $d\notin K$ we have

$\mathbb{P}\left(f\left(\sigma\right)=d\right)\leq\frac{{\varepsilon}}{4k}.$

Then

$\mathbb{P}\left(\sigma\in M_{2}\right)\geq\frac{{\varepsilon}}{4k^{2}}.$
(4.80)

###### Proof.

Just like the proof of Lemma 4.79. ∎

To conclude the proof in the small fiber case, inspect all the lower bounds
for $\mathbb{P}\left(\sigma\in M_{4}\right)$ obtained in Section 4.7.2, and
recall that $\gamma=\frac{{\varepsilon}^{3}}{10^{3}n^{3}k^{24}}$.

####  4.7.4 Large fiber case

We now deal with the large fiber case, when (4.66) holds for both boundaries,
i.e., when

$\mathbb{P}\left(\sigma\in\operatorname{Lg}\left(B_{1}^{a,b;\left[a:b\right]}\right)\right)\geq\frac{{\varepsilon}}{nk^{7}}$

and

$\mathbb{P}\left(\sigma\in\operatorname{Lg}\left(B_{2}^{c,d;\left[c:d\right]}\right)\right)\geq\frac{{\varepsilon}}{nk^{7}}.$

We differentiate between two cases: whether $d\in\left\\{a,b\right\\}$ or
$d\notin\left\\{a,b\right\\}$.

##### Case 1

Suppose $d\in\left\\{a,b\right\\}$, in which case w.l.o.g. we may assume that
$d=a$. That is, in the rest of this case we may assume that

$\mathbb{P}\left(\sigma\in\operatorname{Lg}\left(B_{1}^{a,b;\left[a:b\right]}\right)\right)\geq\frac{{\varepsilon}}{nk^{7}}$
(4.81)

and

$\mathbb{P}\left(\sigma\in\operatorname{Lg}\left(B_{2}^{a,c;\left[a:c\right]}\right)\right)\geq\frac{{\varepsilon}}{nk^{7}}.$
(4.82)

First, let us look at only the boundary between $a$ and $b$ in direction 1.
Let us fix a vector $z_{-1}^{a,b}$ which gives a large fiber
$B_{1}\left(z_{-1}^{a,b}\right)$ for the boundary
$B_{1}^{a,b;\left[a:b\right]}$, i.e., we know that

$\mathbb{P}\left(\sigma\in
B_{1}\left(z_{-1}^{a,b}\right)\,\middle|\,\sigma\in\bar{F}\left(z_{-1}^{a,b}\right)\right)\geq
1-\gamma.$ (4.83)

Our basic goal in the following will be to show that conditional on the
ranking profile $\sigma$ being in the fiber $F\left(z_{-1}^{a,b}\right)$ (but
not necessarily in $\bar{F}\left(z_{-1}^{a,b}\right)$), with high probability
the outcome of the vote is
$\operatorname{top}_{\left\\{a,b\right\\}}\left(\sigma_{1}\right)$, or else we
have a lot of 2-manipulation points or local dictators on three alternatives
in coordinate 1.

Our first step towards this is the following.

######  Lemma 4.80.

Suppose $z_{-1}^{a,b}$ gives a large fiber $B_{1}\left(z_{-1}^{a,b}\right)$
for the boundary $B_{1}^{a,b;\left[a:b\right]}$. Then

$\mathbb{P}_{1}^{\left(a,b\right)}\left(\sigma\in
B_{1}\left(z_{-1}^{a,b}\right)\,\middle|\,\sigma\in
F\left(z_{-1}^{a,b}\right)\right)\geq 1-k\gamma.$ (4.84)

###### Proof.

We know that

$\mathbb{P}\left(\left(\sigma_{1}\left(1\right),\sigma_{1}\left(2\right)\right)=\left(a,b\right)\,\middle|\,\sigma\in\bar{F}\left(z_{-1}^{a,b}\right)\right)=\frac{1}{k-1},$

and so

$\displaystyle\mathbb{P}_{1}^{\left(a,b\right)}$
$\displaystyle\left(\sigma\notin
B_{1}\left(z_{-1}^{a,b}\right)\,\middle|\,\sigma\in
F\left(z_{-1}^{a,b}\right)\right)=\mathbb{P}_{1}^{\left(a,b\right)}\left(\sigma\notin
B_{1}\left(z_{-1}^{a,b}\right)\,\middle|\,\sigma\in\bar{F}\left(z_{-1}^{a,b}\right)\right)$
$\displaystyle=\left(k-1\right)\mathbb{P}\left(\sigma\notin
B_{1}\left(z_{-1}^{a,b}\right),\left(\sigma_{1}\left(1\right),\sigma_{1}\left(2\right)\right)=\left(a,b\right)\,\middle|\,\sigma\in\bar{F}\left(z_{-1}^{a,b}\right)\right)\leq\left(k-1\right)\gamma<k\gamma.\qed$

The next lemma formalizes our goal mentioned above.

######  Lemma 4.81.

Suppose $z_{-1}^{a,b}$ gives a large fiber $B_{1}\left(z_{-1}^{a,b}\right)$
for the boundary $B_{1}^{a,b;\left[a:b\right]}$. Then either

$\mathbb{P}\left(f\left(\sigma\right)=\operatorname{top}_{\left\\{a,b\right\\}}\left(\sigma_{1}\right)\,\middle|\,\sigma\in
F\left(z_{-1}^{a,b}\right)\right)\geq 1-2k\gamma$ (4.85)

or

$\mathbb{P}\left(\sigma\in M_{2}\,\middle|\,\sigma\in
F\left(z_{-1}^{a,b}\right)\right)\geq\frac{\gamma}{2k}$ (4.86)

or

$\mathbb{P}\left(\sigma\in LD_{1}\left(a,b\right)\,\middle|\,\sigma\in
F\left(z_{-1}^{a,b}\right)\right)\geq\frac{\gamma}{2k}.$ (4.87)

###### Proof.

The proof of this lemma is essentially the same as that of Lemma 4.62, there
are only two slight differences. First, we use Lemma 4.80 to know that (4.84)
holds. Second, we take $\sigma\in F\left(z_{-1}^{a,b}\right)$ to be uniform,
and we stay on the fiber $F\left(z_{-1}^{a,b}\right)$ throughout the proof: we
modify only the first coordinate throughout the proof, in the same way as we
did for Lemma 4.62. We omit the details. ∎

Now this lemma holds for all vectors $z_{-1}^{a,b}$ which give a large fiber
$B_{1}\left(z_{-1}^{a,b}\right)$ for the boundary
$B_{1}^{a,b;\left[a:b\right]}$. By (4.81) we know that

$\mathbb{P}\left(\sigma:B_{1}\left(x_{-1}^{a,b}\left(\sigma\right)\right)\text{
is a large fiber}\right)\geq\frac{{\varepsilon}}{nk^{7}}.$

Now if (4.86) holds for at least a third of the vectors $z_{-1}^{a,b}$ that
give a large fiber $B_{1}\left(z_{-1}^{a,b}\right)$, then it follows that

$\mathbb{P}\left(\sigma\in
M_{2}\right)\geq\frac{\gamma{\varepsilon}}{6nk^{8}}$

and we are done. If (4.87) holds for at least a third of the vectors
$z_{-1}^{a,b}$ that give a large fiber $B_{1}\left(z_{-1}^{a,b}\right)$, then
similarly we have

$\mathbb{P}\left(\sigma\in
LD_{1}\left(a,b\right)\right)\geq\frac{\gamma{\varepsilon}}{6nk^{8}},$

which means that (4.71) also holds, and so we are done by the argument in
Section 4.7.3.

So the remaining case to consider is when (4.85) holds for at least a third of
the vectors $z_{-1}^{a,b}$ that give a large fiber
$B_{1}\left(z_{-1}^{a,b}\right)$.

We can go through this same argument for the boundary between $a$ and $c$ in
direction 2 as well, and either we are done because

$\mathbb{P}\left(\sigma\in
M_{2}\right)\geq\frac{\gamma{\varepsilon}}{6nk^{8}}$

or

$\mathbb{P}\left(\sigma\in
LD_{2}\left(a,c\right)\right)\geq\frac{\gamma{\varepsilon}}{6nk^{8}},$

or for at least a third of the vectors $z_{-2}^{a,c}$ that give a large fiber
$B_{2}\left(z_{-2}^{a,c}\right)$ we have

$\mathbb{P}\left(f\left(\sigma\right)=\operatorname{top}_{\left\\{a,c\right\\}}\left(\sigma_{2}\right)\,\middle|\,\sigma\in
F\left(z_{-2}^{a,c}\right)\right)\geq 1-2k\gamma.$

So basically our final case is if

$\mathbb{P}\left(\sigma\in
F_{1}^{a,b}\right)\geq\frac{{\varepsilon}}{3nk^{7}}$ (4.88)

and also

$\mathbb{P}\left(\sigma\in
F_{2}^{a,c}\right)\geq\frac{{\varepsilon}}{3nk^{7}}.$ (4.89)

Notice that being in the set $F_{1}^{a,b}$ only depends on the vector
$x^{a,b}\left(\sigma\right)$ of preferences between $a$ and $b$, and similarly
being in the set $F_{2}^{a,c}$ only depends on the vector
$x^{a,c}\left(\sigma\right)$ of preferences between $a$ and $c$. We know that
$\left\\{\left(x_{i}^{a,b}\left(\sigma\right),x_{i}^{a,c}\left(\sigma\right)\right)\right\\}_{i=1}^{n}$
are independent, and for any given $i$ we know that
$\left|\mathbb{E}\left(x_{i}^{a,b}\left(\sigma\right)x_{i}^{a,c}\left(\sigma\right)\right)\right|=\frac{1}{3}$.
Hence we can apply reverse hypercontractivity (Lemma LABEL:lem:invhypcontr),
to get the following result.

######  Lemma 4.82.

If (4.88) and (4.89) hold, then also

$\mathbb{P}\left(\sigma\in F_{1}^{a,b}\cap
F_{2}^{a,c}\right)\geq\frac{{\varepsilon}^{3}}{27n^{3}k^{21}}.$ (4.90)

###### Proof.

See above. ∎

The next and final lemma then concludes that we have lots of manipulation
points.

######  Lemma 4.83.

Suppose (4.90) holds. Then

$\mathbb{P}\left(\sigma\in
M_{3}\right)\geq\frac{{\varepsilon}^{3}}{54n^{3}k^{27}}-\frac{9\gamma}{k^{3}}.$
(4.91)

###### Proof.

First let us define two events:

$\displaystyle I_{1}$
$\displaystyle:=\left\\{\sigma:f\left(\sigma\right)=\operatorname{top}_{\left\\{a,b\right\\}}\left(\sigma_{1}\right)\right\\}$
$\displaystyle I_{2}$
$\displaystyle:=\left\\{\sigma:f\left(\sigma\right)=\operatorname{top}_{\left\\{a,c\right\\}}\left(\sigma_{2}\right)\right\\}.$

Using similar estimates as previously in Lemma 4.23, we have

$\mathbb{P}\left(\sigma\in I_{1}\cap I_{2}\cap F_{1}^{a,b}\cap
F_{2}^{a,c}\right)\geq\mathbb{P}\left(\sigma\in F_{1}^{a,b}\cap
F_{2}^{a,c}\right)\\\ -\mathbb{P}\left(\sigma\notin I_{1},\sigma\in
F_{1}^{a,b}\cap F_{2}^{a,c}\right)-\mathbb{P}\left(\sigma\notin
I_{2},\sigma\in F_{1}^{a,b}\cap F_{2}^{a,c}\right).$

The first term is bounded below via (4.90), while the other two terms can be
bounded using the definition of $F_{1}^{a,b}$ and $F_{2}^{a,c}$, respectively:

$\mathbb{P}\left(\sigma\notin I_{1},\sigma\in F_{1}^{a,b}\cap
F_{2}^{a,c}\right)\leq\mathbb{P}\left(\sigma\notin I_{1},\sigma\in
F_{1}^{a,b}\right)\leq\mathbb{P}\left(\sigma\notin I_{1}\,\middle|\,\sigma\in
F_{1}^{a,b}\right)\leq 2k\gamma,$

and similarly for the other term. Putting everything together gives us

$\mathbb{P}\left(\sigma\in I_{1}\cap I_{2}\cap F_{1}^{a,b}\cap
F_{2}^{a,c}\right)\geq\frac{{\varepsilon}^{3}}{27n^{3}k^{21}}-4k\gamma.$

If $\sigma\in I_{1}\cap I_{2}\cap F_{1}^{a,b}\cap F_{2}^{a,c}$, then clearly
we must have $f\left(\sigma\right)=a$, and therefore
$x_{1}^{a,b}\left(\sigma\right)=1$ and $x_{2}^{a,c}\left(\sigma\right)=1$. Now
define $\sigma^{\prime}$ from $\sigma$ by bubbling up $b$ in coordinate 1 to
just below $a$, and bubbling up $c$ in coordinate 2 to just below $a$. Either
we encounter a 2-manipulation point along the way, or the outcome is still
$a$: $f\left(\sigma^{\prime}\right)=a$. If we encounter a 2-manipulation point
along the way for at least half of such ranking profiles, then we are done:

$\mathbb{P}\left(\sigma\in
M_{2}\right)\geq\frac{1}{k^{2}}\left(\frac{{\varepsilon}^{3}}{54n^{3}k^{21}}-2k\gamma\right)=\frac{{\varepsilon}^{3}}{54n^{3}k^{23}}-\frac{2\gamma}{k}.$

Otherwise, we may assume that

$\mathbb{P}\left(\sigma\in I_{1}\cap I_{2}\cap F_{1}^{a,b}\cap
F_{2}^{a,c},f\left(\sigma^{\prime}\right)=a\right)\geq\frac{{\varepsilon}^{3}}{54n^{3}k^{21}}-2k\gamma.$

In this case define
$\tilde{\sigma}^{\prime}:=\left[a:b\right]_{1}\sigma^{\prime}$ and
$\tilde{\sigma}^{\prime\prime}:=\left[a:c\right]_{2}\sigma^{\prime}$. If
$f\left(\tilde{\sigma}^{\prime}\right)\notin\left\\{a,b\right\\}$ or
$f\left(\tilde{\sigma}^{\prime\prime}\right)\notin\left\\{a,c\right\\}$, then
we automatically have that one of
$\sigma^{\prime},\tilde{\sigma}^{\prime},\tilde{\sigma}^{\prime\prime}$ is a
2-manipulation point. If $f\left(\tilde{\sigma}^{\prime}\right)=b$ and
$f\left(\tilde{\sigma}^{\prime\prime}\right)=c$, then by Lemma 4.40 we know
that there exists a 3-manipulation point $\hat{\sigma}$ which agrees with
$\sigma$ except perhaps $a$, $b$, and $c$ could be arbitrarily shifted in the
first two coordinates. The final case is when
$a\in\left\\{f\left(\tilde{\sigma}^{\prime}\right),f\left(\tilde{\sigma}^{\prime\prime}\right)\right\\}$.
But we now show that this has small probability, and therefore (4.91) follows.

First let us look at the case of $f\left(\tilde{\sigma}^{\prime}\right)=a$. We
have

$\mathbb{P}\left(\sigma\in I_{1}\cap I_{2}\cap F_{1}^{a,b}\cap
F_{2}^{a,c},f\left(\sigma^{\prime}\right)=a,f\left(\tilde{\sigma}^{\prime}\right)=a\right)\\\
\begin{aligned} &=\sum_{z_{-1}^{a,b}:F\left(z_{-1}^{a,b}\right)\subseteq
F_{1}^{a,b}}\mathbb{P}\left(\sigma\in I_{1}\cap I_{2}\cap
F\left(\left(1,z_{-1}^{a,b}\right)\right)\cap
F_{2}^{a,c},f\left(\sigma^{\prime}\right)=a,f\left(\tilde{\sigma}^{\prime}\right)=a\right)\\\
&=\sum_{z_{-1}^{a,b}:F\left(z_{-1}^{a,b}\right)\subseteq
F_{1}^{a,b}}\mathbb{P}\left(\sigma\in I_{1}\cap I_{2}\cap
F_{2}^{a,c},f\left(\sigma^{\prime}\right)=a,f\left(\tilde{\sigma}^{\prime}\right)=a\,\middle|\,\sigma\in
F\left(\left(1,z_{-1}^{a,b}\right)\right)\right)\mathbb{P}\left(\sigma\in
F\left(\left(1,z_{-1}^{a,b}\right)\right)\right)\\\
&\leq\sum_{z_{-1}^{a,b}:F\left(z_{-1}^{a,b}\right)\subseteq
F_{1}^{a,b}}\mathbb{P}\left(\sigma:f\left(\tilde{\sigma}^{\prime}\right)=a\,\middle|\,\sigma\in
F\left(\left(1,z_{-1}^{a,b}\right)\right)\right)\mathbb{P}\left(\sigma\in
F\left(\left(1,z_{-1}^{a,b}\right)\right)\right).\end{aligned}$

Now we know that $\tilde{\sigma}^{\prime}\in
F\left(\left(-1,z_{-1}^{a,b}\right)\right)\subseteq F_{1}^{a,b}$, and we also
know that

$\mathbb{P}\left(f\left(\sigma\right)\neq b\,\middle|\,\sigma\in
F\left(\left(-1,z_{-1}^{a,b}\right)\right)\right)\leq 4k\gamma.$

The number of $\sigma$‘s that give the same $\tilde{\sigma}^{\prime}$ is at
most $k^{2}$, and so we can conclude that

$\mathbb{P}\left(\sigma\in I_{1}\cap I_{2}\cap F_{1}^{a,b}\cap
F_{2}^{a,c},f\left(\sigma^{\prime}\right)=a,f\left(\tilde{\sigma}^{\prime}\right)=a\right)\leq
4k^{3}\gamma,$

and similarly

$\mathbb{P}\left(\sigma\in I_{1}\cap I_{2}\cap F_{1}^{a,b}\cap
F_{2}^{a,c},f\left(\sigma^{\prime}\right)=a,f\left(\tilde{\sigma}^{\prime\prime}\right)=a\right)\leq
4k^{3}\gamma,$

which shows that

$\mathbb{P}\left(\sigma\in
M_{3}\right)\geq\frac{1}{k^{6}}\left(\frac{{\varepsilon}^{3}}{54n^{3}k^{21}}-2k\gamma-8k^{3}\gamma\right)\geq\frac{{\varepsilon}^{3}}{54n^{3}k^{27}}-\frac{9\gamma}{k^{3}}.\qed$

To conclude the proof in this case, recall that we have chosen
$\gamma=\frac{{\varepsilon}^{3}}{10^{3}n^{3}k^{24}}$.

##### Case 2

First, as in the previous case, we can look at simply the boundary between $a$
and $b$ in direction 1, and conclude that either there are many manipulation
points, or there are many local dictators, or (4.88) holds. This holds
similarly for the boundary between $c$ and $d$ in direction 2. Finally, just
as in Section 4.2.3, we can show that (4.88) and (4.89) cannot hold at the
same time. We omit the details.

####  4.7.5 Proof of Theorem 4.63 concluded

###### Proof of Theorem 4.63.

Our starting point is Lemma 4.41, which directly implies Lemma 4.64 (unless
there are many 2-manipulation points, in which case we are done). We then
consider two cases, as indicated in Section 4.7.1.

We deal with the small fiber case in Section 4.7.2. First, Lemmas 4.65, 4.68,
and 4.70, and Corollaries 4.66, 4.67, 4.69, and 4.71 imply that either there
are many 3-manipulation points, or there are many local dictators on three
alternatives in coordinate 1. We then deal with the case of many local
dictators in Section 4.7.3. Lemma 4.72, Corollary 4.73, Lemmas 4.74, 4.75,
Corollary 4.76, and Lemmas 4.77, 4.78, and 4.79 together show that there are
many 4-manipulation points if there are many local dictators on three
alternatives, and the SCF is ${\varepsilon}$-far from the family of
nonmanipulable functions.

We deal with the large fiber case in Section 4.7.4. Here Lemmas 4.80, 4.81,
4.82, and 4.83 show that if there are not many local dictators on three
alternatives, then there are many 3-manipulation points. In the case when
there are many local dictators, we refer back to Section 4.7.3 to conclude the
proof. ∎

###  4.8 To truly nonmanipulable functions

###### Proof of Theorem 4.46.

Our assumption means that there exists a SCF
$g\in\overline{\operatorname{NONMANIP}}$ such that $\operatorname{{\bf
D}}\left(f,g\right)\leq\alpha$. We distinguish two cases: either $g$ is a
function of one coordinate, or $g$ takes on at most two values.

Case 1. $g$ is a function of one coordinate. In this case we can assume
w.l.o.g. that $g$ is a function of the first coordinate, i.e., there exists a
SCF $h:S_{k}\to\left[k\right]$ on one coordinate such that for every ranking
profile $\sigma$, we have $g\left(\sigma\right)=h\left(\sigma_{1}\right)$.

We know from the quantitative Gibbard-Satterthwaite theorem for one voter that
for any $\beta$ either $\operatorname{{\bf
D}}\left(h,\operatorname{NONMANIP}\left(1,k\right)\right)\leq\beta$, or
$\mathbb{P}\left(\sigma\in
M_{3}\left(h\right)\right)\geq\frac{\beta^{3}}{10^{5}k^{16}}$.

In the former case, we have that

$\operatorname{{\bf
D}}\left(g,\operatorname{NONMANIP}\left(n,k\right)\right)\leq\operatorname{{\bf
D}}\left(h,\operatorname{NONMANIP}\left(1,k\right)\right)\leq\beta,$

and so consequently

$\operatorname{{\bf
D}}\left(f,\operatorname{NONMANIP}\left(n,k\right)\right)\leq\alpha+\beta.$

In the latter case, we have that

$\mathbb{P}\left(\sigma\in
M_{3}\left(g\right)\right)=\mathbb{P}\left(\sigma\in
M_{3}\left(h\right)\right)\geq\frac{\beta^{3}}{10^{5}k^{16}},$

and so consequently

$\mathbb{P}\left(\sigma\in
M_{3}\left(f\right)\right)\geq\frac{\beta^{3}}{10^{5}k^{16}}-6nk\alpha,$

since changing the outcome of a SCF at one ranking profile can change the
number of 3-manipulation points by at most $6nk$. Now choosing
$\beta=100nk^{6}\alpha^{1/3}$ shows that either (4.41) or (4.42) holds.

Case 2. $g$ is a function which takes on at most two values. W.l.o.g. we may
assume that the range of $g$ is $\left\\{a,b\right\\}\subset\left[k\right]$,
i.e., for every ranking profile $\sigma\in S_{k}^{n}$ we have
$g\left(\sigma\right)\in\left\\{a,b\right\\}$.

There is one thing we have to be careful about: even though $g$ takes on at
most two values, it is not necessarily a Boolean function, since the value of
$g\left(\sigma\right)$ does not necessarily depend only on the Boolean vector
$x^{a,b}\left(\sigma\right)$.

We now define a function $h:S_{k}^{n}\to\left\\{a,b\right\\}$ that is close in
some sense to $g$ and which can be viewed as a Boolean function
$h:\left\\{a,b\right\\}^{n}\to\left\\{a,b\right\\}$ because
$h\left(\sigma\right)$ depends on $\sigma$ only through
$x^{a,b}\left(\sigma\right)$. (The vector
$x^{a,b}\left(\sigma\right)\in\left\\{-1,1\right\\}^{n}$ encodes which of $a$
and $b$ is preferred in each coordinate, and a vector in
$\left\\{a,b\right\\}^{n}$ can encode the same information.) For a given
ranking profile $\sigma$, let us consider the fiber on which it is on,
$F\left(x^{a,b}\left(\sigma\right)\right)$, and let us define
$g|_{F\left(x^{a,b}\left(\sigma\right)\right)}$ to be the restriction of $g$
to ranking profiles in the fiber $F\left(x^{a,b}\left(\sigma\right)\right)$.
Then define (see Definition 4.47)

$h\left(\sigma\right):=\operatorname{Maj}\left(g|_{F\left(x^{a,b}\left(\sigma\right)\right)}\right).$

By definition, $h\left(\sigma\right)$ depends on $\sigma$ only through
$x^{a,b}\left(\sigma\right)$, so we may also view $h$ as a Boolean function
$h:\left\\{a,b\right\\}^{n}\to\left\\{a,b\right\\}$.

For any given $0<\delta<1$, we either have $\operatorname{{\bf
D}}\left(g,h\right)\leq\delta$, in which case $\operatorname{{\bf
D}}\left(f,h\right)\leq\alpha+\delta$, or if $\operatorname{{\bf
D}}\left(g,h\right)>\delta$, then we show presently that

$\mathbb{P}\left(\sigma\in
M_{2}\left(f\right)\right)\geq\frac{\delta}{4nk^{5}}-nk\alpha.$ (4.92)

Choosing $\delta=8n^{2}k^{6}\alpha$ then shows that either (4.42) holds, or
$\operatorname{{\bf D}}\left(f,h\right)\leq 9n^{2}k^{6}\alpha$.

Let us now show (4.92). We use a canonical path argument again, but first we
divide the ranking profiles according to the fibers with respect to preference
between $a$ and $b$.

Let us consider an arbitrary fiber $F\left(z^{a,b}\right)$, and divide it into
two disjoint sets: into those ranking profiles for which the outcome of $g$
and $h$ agree, and those for which these outcomes are different. I.e.,

$F\left(z^{a,b}\right)=F^{\operatorname{maj}}\left(z^{a,b}\right)\cup
F^{\min}\left(z^{a,b}\right),$

where

$\displaystyle F^{\operatorname{maj}}\left(z^{a,b}\right)$
$\displaystyle=\left\\{\sigma\in
F\left(z^{a,b}\right):g\left(\sigma\right)=h\left(\sigma\right)\right\\},$
$\displaystyle F^{\min}\left(z^{a,b}\right)$ $\displaystyle=\left\\{\sigma\in
F\left(z^{a,b}\right):g\left(\sigma\right)\neq h\left(\sigma\right)\right\\}.$

By construction, we know that

$\left|F^{\min}\left(z^{a,b}\right)\right|\leq\frac{1}{2}\left|F\left(z^{a,b}\right)\right|=\frac{1}{2}\left(\frac{k!}{2}\right)^{n}.$

Now for every pair of profiles $\left(\sigma,\sigma^{\prime}\right)\in
F^{\min}\left(z^{a,b}\right)\times F^{\operatorname{maj}}\left(z^{a,b}\right)$
define a canonical path from $\sigma$ to $\sigma^{\prime}$ by applying a path
construction in each coordinate one by one, and then concatenating these
paths. In each coordinate we apply the path construction of [41, Proposition
6.6.]: we bubble up everything except $a$ and $b$, and then finally bubble up
the last two alternatives as well.

For a given edge $\left(\pi,\pi^{\prime}\right)\in
F^{\min}\left(z^{a,b}\right)\times F^{\operatorname{maj}}\left(z^{a,b}\right)$
there are at most $2k^{4}\left(\frac{k!}{2}\right)^{n}$ possible pairs
$\left(\sigma,\sigma^{\prime}\right)\in F^{\min}\left(z^{a,b}\right)\times
F^{\operatorname{maj}}\left(z^{a,b}\right)$ such that the canonical path
between $\sigma$ and $\sigma^{\prime}$ defined above passes through
$\left(\pi,\pi^{\prime}\right)$. (This can be shown just like in the previous
lemmas, e.g., Lemma 4.65.) Consequently we have

$\left|\partial_{e}\left(F^{\min}\left(z^{a,b}\right)\right)\right|\geq\frac{\left|F^{\min}\left(z^{a,b}\right)\right|\left|F^{\operatorname{maj}}\left(z^{a,b}\right)\right|}{2k^{4}\left(\frac{k!}{2}\right)^{n}}\geq\frac{\left|F^{\min}\left(z^{a,b}\right)\right|}{4k^{4}},$

where the edge boundary
$\partial_{e}\left(F^{\min}\left(z^{a,b}\right)\right)$ is defined via the
refined rankings graph restricted to the fiber $F\left(z^{a,b}\right)$.
Summing this over all fibers we have that

$\sum_{z^{a,b}}\left|\partial_{e}\left(F^{\min}\left(z^{a,b}\right)\right)\right|\geq\sum_{z^{a,b}}\frac{\left|F^{\min}\left(z^{a,b}\right)\right|}{4k^{4}}\geq\frac{\delta}{4k^{4}}\left(k!\right)^{n},$
(4.93)

using the fact that $\operatorname{{\bf D}}\left(g,h\right)>\delta$.

Now it is easy to see that if
$\left(\sigma,\sigma^{\prime}\right)\in\partial_{e}\left(F^{\min}\left(z^{a,b}\right)\right)$
for some $z^{a,b}$, then either $\sigma$ or $\sigma^{\prime}$ is a
2-manipulation point for $g$. In the refined rankings graph every vertex
(ranking profile) has $n\left(k-1\right)<nk$ neighbors, so each 2-manipulation
point can be counted at most $nk$ times in the sum on the left hand side of
(4.93), showing that

$\mathbb{P}\left(\sigma\in
M_{2}\left(g\right)\right)\geq\frac{\delta}{4nk^{5}},$

from which (4.92) follows immediately, since changing the outcome of a SCF at
one ranking profile can change the number of 2-manipulation points by at most
$nk$.

So either we are done because (4.42) holds, or $\operatorname{{\bf
D}}\left(f,h\right)\leq 9n^{2}k^{6}\alpha$; suppose the latter case. Our final
step is to look at $h$ as a Boolean function, and use a result on testing
monotonicity [34].

Denote by $\tilde{\operatorname{{\bf D}}}$ the distance of $h$ when viewed as
a Boolean function from the set of monotone Boolean functions. Let
$0<{\varepsilon}<1$ be arbitrary. Then either $\tilde{\operatorname{{\bf
D}}}\leq{\varepsilon}$, in which case $\operatorname{{\bf
D}}\left(h,\operatorname{NONMANIP}\right)\leq\tilde{\operatorname{{\bf
D}}}\leq{\varepsilon}$ and therefore $\operatorname{{\bf
D}}\left(f,\operatorname{NONMANIP}\right)\leq
9n^{2}k^{6}\alpha+{\varepsilon}$, or $\tilde{\operatorname{{\bf
D}}}>{\varepsilon}$. In the latter case we show that then

$\mathbb{P}\left(\sigma\in
M_{2}\left(f\right)\right)\geq\frac{2{\varepsilon}}{nk}-9n^{3}k^{7}\alpha.$
(4.94)

Choosing ${\varepsilon}=5n^{4}k^{8}\alpha$ then shows that either (4.41) or
(4.42) holds.

Let us now show (4.94). Let us view $h$ as a Boolean function, and denote by
$p\left(h\right)$ the fraction of pairs of strings, differing on one
coordinate, that violate the monotonicity condition. Goldreich, Goldwasser,
Lehman, Ron, and Samorodnitsky showed in [34, Theorem 2] that
$p\left(h\right)\geq\frac{\tilde{\operatorname{{\bf D}}}}{n}$.

Now going back to viewing $h$ as a SCF on $k$ alternatives, this tells us that
there are at least $\frac{{\varepsilon}}{2}2^{n}$ pairs of fibers, which
differ on one coordinate, that violate monotonicity. For each such pair of
fibers, whenever $a$ and $b$ are adjacent in the coordinate where the two
fibers differ, we get a 2-manipulation point. Such a 2-manipulation point can
be counted at most $n$ times in this way (since there are $n$ coordinates
where $a$ and $b$ can be adjacent). Consequently, we have

$\left|M_{2}\left(h\right)\right|\geq\frac{{\varepsilon}}{2}\cdot 2^{n}\cdot
2\left(k-1\right)!\left(\frac{k!}{2}\right)^{n-1}\cdot\frac{1}{n}=\frac{2{\varepsilon}}{nk}\left(k!\right)^{n},$

i.e.,

$\mathbb{P}\left(\sigma\in
M_{2}\left(h\right)\right)\geq\frac{2{\varepsilon}}{nk},$

from which (4.94) follows immediately, since changing the outcome of a SCF at
one ranking profile can change the number of 2-manipulation points by at most
$nk$. ∎

###### Proof of Theorem 4.9.

First we argue without specific bounds. Suppose on the contrary that our SCF
$f$ does not have many 4-manipulation points. Then $f$ is close to
$\overline{\operatorname{NONMANIP}}$ by Theorem 4.63. Consequently, by Theorem
4.46, $f$ is close to $\operatorname{NONMANIP}$, which is a contradiction.

Now we argue with specific bounds. Assume on the contrary that

$\mathbb{P}\left(\sigma\in
M_{4}\left(f\right)\right)<\frac{{\varepsilon}^{15}}{10^{39}n^{67}k^{166}}.$

Then by Theorem 4.63 we have that $\operatorname{{\bf
D}}\left(f,\overline{\operatorname{NONMANIP}}\right)<\frac{{\varepsilon}^{3}}{10^{6}n^{12}k^{24}}$,
and consequently by Theorem 4.46 we have $\operatorname{{\bf
D}}\left(f,\operatorname{NONMANIP}\right)<{\varepsilon}$, which is a
contradiction. ∎

##  Chapter 5 Aggregation power of Boolean Functions

In this chapter we will review some of the theory of Boolean functions from
the perspective of Condorcet Jury Theorem.

###  5.1 Influences and Aggregation

We now take a modern view of Condorcet Jury Theorem. First, recall the
setting. There are two alternatives denoted $+$ and $-$, which are apiori
equally likely to be the preferable alternative, and that each voter
independently receives the correct information with probability $p>1/2$ and
incorrect information with probability $1-p$. We now denote the $n$ signals by
$x_{1},\ldots,x_{n}$ and aggregate them via a boolean function
$f:\\{-1,1\\}^{n}\to\\{-1,1\\}$. The following fact is a generalization of the
second part of the Jury Theorem.

######  Theorem 5.1.

Let $0.5<p\leq 1$. Then $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ maximizes $P[f(x)=s]$
if and only if $f(x)=+$ for all $x$ such that $\sum_{i=1}^{n}x_{i}>0$ and
$f(x)=-$ for all $x$ such that $\sum x_{i}<0$.

In particular when $n$ is odd Majority is the only function that maximizes
$P[f(x)=s]$.

This is a special case of the Neyman-Pearson lemma for hypothesis testing in
statistics [83]. In our case, the proof immediately follows from the fact that

$\frac{P[s=+|x_{1},\ldots,x_{n}]}{P[s=-|x_{1},\ldots,x_{n}]}=\frac{P[x_{1},\ldots,x_{n}|s=+]}{P[x_{1},\ldots,x_{n}|s=-]}=\left(\frac{p}{1-p}\right)^{n_{+}(x)-n_{-}(x)}$

where $n_{+}(x)$ is the number of $+$s in $x$ and similarly $n_{-}$.

Assume for a moment that $s=+$. Therefore, our interest is in the quantity
$\mathbb{P}[f=+]$. If $f$ is a monotone function, we have the following
Russo‘s formula [59, 90], where $\mathbb{P}_{p}$ denotes the product measure
with marginals $\mathbb{P}_{p}[x_{i}=+]=p$:

######  Proposition 5.2.

Let $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ be monotone then

$\frac{d}{dp}\bigg{\rvert}_{p=1/2}\mathbb{P}_{p}[f=1]=\sum_{i=1}^{n}I_{i}(f).$

One short proof of Proposition 5.2 is to consider an $n$ variable function
$P_{(p_{1},\ldots,p_{n})}[f=1]$ and applying the chain rule. In fact, if we
define for Boolean functions

$J_{p,i}(f)=\mathbb{E}_{p}[\mathbb{P}_{p}[f(x_{-i},+)\neq f(x_{-i},-)]],$

then the same proof yields more generally that for monotone
$f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ it holds that

$\frac{d}{dp}\bigg{\rvert}_{p}\mathbb{P}_{p}[f=1]=\sum_{i=1}^{n}J_{p,i}(f)=\frac{1}{4p(1-p)}\sum_{i=1}^{n}I_{p,i}(f),$
(5.1)

where

$I_{p,i}(f)=\mathbb{E}[Var[f(x)|x_{-i}]],$

######  Lemma 5.3.

In the setting of Condorcet voting with uniform prior on $s$, among all
monotone functions majority maximizes

$\frac{d}{dp}\bigg{\rvert}_{p=1/2}\mathbb{P}_{p}[f=s]=\sum_{i=1}^{n}I_{i}(f)$

###### Proof.

Consider jurors who receive the correct signal with probability $p$. Then for
any monotone function $f$ we have that

$\mathbb{P}_{p}[f=s]=0.5(\mathbb{P}_{p}[f=+]+\mathbb{P}_{1-p}[f=-])=0.5+0.5(\mathbb{P}_{p}[f=+]-\mathbb{P}_{1-p}[f=+]).$

We know that for every $p$, among all monotone functions, the pan-ultimae
expression above is maximized for the Majority function. Taking the derivative
of the ultimate expression with respect to $p$ concludes the proof. ∎

By examining the proof of Theorem 5.1 more carefully, we see that the
Majorities are the only maximizers of the influence sum.

Interestingly, dictators are the minimizers in their aggregation power. In
particular we have:

######  Proposition 5.4.

For any Boolean function with $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ it holds that
$\sum I_{i}(f)\geq Var[f]$. Equality holds if and only if $f$ is a dictator or
a constant.

###### Proof.

This follows from the fact that

$\sum_{i}I_{i}(f)=\sum_{S}|S|\hat{f}^{2}(S),\quad
Var[f]=\sum_{S\neq\emptyset}\hat{f}^{2}(S).$

∎

Again, in fact the claim is true for every $0<p<1$:

######  Proposition 5.5.

For any Boolean function $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ it holds that

$\sum I_{p,i}(f)\geq Var_{p}[f]$

Equality holds if and only if $f$ is a dictator.

######  Exercise 5.6.

Prove it.

In fact more is true:

######  Proposition 5.7.

Among all $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ which are monotone and satisfy
$\mathbb{E}_{1/2}[f]=0$, dictators are the only minimizers of
$\mathbb{E}_{p}[f]$ for all $0.5<p<1$.

###### Proof.

Assume by contradiction the statement is false. Then there exists a non-
dictator function $f$ and $1>r>1/2$ such that $\mathbb{P}_{r}[f=1]=r$. Let
$q=\inf(r>1/2:\mathbb{P}_{r}[f=1]=r)$. Since $\mathbb{P}_{r}[f=1]$ is a
polynomial in $r$, it follows that $\mathbb{P}_{q}[f=1]=q$. Moreover, by
Poincare‘s inequality at $1/2$, it follows that $q>1/2$. Since
$\mathbb{P}_{r}[f=1]\geq r$ for $1/2\leq r\leq q$ it follows that
$d/dr_{|r=q}\mathbb{P}_{r}[f=1]\leq 1$. However, by Poincare‘s inequality at
$q$ it is strictly greater than $1$. The proof follows. ∎

###  5.2 The minimal Influence Problem and Coalitions

Assume that in a binary vote $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ it is possible to
buy a certain number of the votes. How much can this influence the outcome of
the election. This question and related questions were studied in [7] which is
one of the foundational papers of analysis of Boolean functions.

Poincare‘s inequality:

$\sum_{i=1}^{n}I_{i}(f)=\sum_{S}|S|\hat{f}^{2}(S)\geq\operatorname*{Var}[f]$

implies that any function $f:\\{-1,1\\}^{n}\to\mathbb{R}$ has a variable $i$
with $I_{i}(f)\geq\operatorname*{Var}[f]/n$. This in turn implies the
following:

######  Lemma 5.8.

If $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ is a monotone function with
$\mathbb{E}[f]=0$, then for any $1>{\varepsilon}>0$, there exists a set
$|S|\leq{\varepsilon}n$ such that $\mathbb{E}[f|\forall i\in
S,x_{i}=1]\geq{\varepsilon}/4$.

That is, a small linear fraction of the voters can change the expected value
of the function noticeably. For the proof the following lemma is useful to
note that if $f:\\{-1,+1\\}^{n}\to\\{-1,+1\\}$ is monotone then:

$\hat{f}(i)=\mathbb{E}[fx_{i}]=\mathbb{E}[\mathbb{E}[fx_{i}|x_{-i}]]=\mathbb{E}_{x_{-i}}[Var[f|x_{-i}]]=I_{i}(f),$

since conditioned on $x_{-i}$, either $f$ is a constant or $f$ is the identity
and in both cases, $\mathbb{E}[fx_{i}|x_{-i}]=Var[f|x_{-i}]$.

###### Proof.

Construct $S$ iteratively. Let $f_{1}=f$ and let $S_{0}=\emptyset$. At stage
$i$ of the construction, let $j$ be the variable with most influence of the
function $f_{i}$ and let $S_{i}=S_{i-1}\cup\\{j\\}$. Let $f_{i+1}$ be defined
as $f_{i}$ conditioned on $x_{j}=1$. If $\mathbb{E}[f_{i+1}]\geq{\varepsilon}$
we stop. Otherwise, we continue. Note that at each step we have
$\mathbb{E}[f_{i+1}-f_{i}]\geq I_{j}(f_{i})\geq 0.25/n$. The proof follows. ∎

It is natural to ask if the claim and proof are tight. We first ask if one can
improve the bound $I_{i}(f)\geq\operatorname*{Var}[f]/n$. For general
functions the answer to the later question is no, as the function
$f=n^{-1/2}\sum x_{i}$ shows. For Boolean functions, Ben-Or and Linial [7]
found an example that is almost tight i.e., the tribes function.

######  Example 5.9.

Let $m=2^{r}$ and let $n=m\log_{2}m=mr$ and define the tribes function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ by

$f(x)=(x_{1}\wedge\ldots\wedge x_{r})\vee(x_{r+1}\wedge\ldots\wedge
x_{2r})\vee\cdots\vee(x_{n-r+1}\wedge\ldots\wedge x_{n})$

This can be described in words as follows. The function is $1$ if there is a
decision to go to war and $0$ otherwise. In order to go to war there has to be
at least one tribe where all members decide to go to war, i.e, there has to
exist a $k$ so that $x_{kr+1}=\ldots=x_{(k+1)r}=1$. It is easy to see that the
number of tribes that go to war is $\mathrm{Bin}(m,1/m)$ which is
approximately Poisson. In particular,

$\mathbb{E}[f]=\mathbb{P}[\mathrm{Bin}(m,1/m)\geq 1]\in[0.1,0.9],$

for $r\geq 1$. For $\partial_{1}f=1$, i.e., that the first coordinate is
influential, we need that none of the tribes but the first tribe wants to go
to war and that in tribe $1$, everyone but the first voter wants to go to war.
Thus

$I_{i}(f)=\mathbb{P}[\partial_{1}f=1]=2^{-r+1}\mathbb{P}[\mathrm{Bin}(m-1,1/m)=0]\leq
2^{-r+1}=\frac{2}{m}\leq\frac{2\log_{2}(n)}{n}.$

It is also easy to see from the equation above that in fact $I_{i}(f)$ is of
order $\frac{\log_{2}(n)}{n}$.

Thus, we already know that the minimal influence is of order at least
$\operatorname*{Var}[f]/n$ and we have an example where it is of order
$\operatorname*{Var}[f]\log n/n$. The KKL Theorem [45] by Kahn, Kalai and
Linial which will be proved in the next section shows that the $\log n$ factor
is in fact necessary.

######  Theorem 5.10.

There exists a constant $c$ such that for all $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$
it holds that

$\min_{i}I_{i}(f)\geq c\frac{\log n}{n}\operatorname*{Var}[f]$

Repeating the proof of Lemma 5.8 we obtain the following:

######  Lemma 5.11.

Let $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ be a monotone function with
$\mathbb{E}[f]=0$, then for any ${\varepsilon}>0$, there exists a set $|S|\leq
c({\varepsilon})n/\log n$ such that $\mathbb{E}[f|\forall i\in S,x_{i}=1]\geq
1-{\varepsilon}$.

Interestingly, the tribes example is far from tight for Lemma 5.11 as it
suffices to take $S$ of size $\log n$ (e.g., a tribe) to fix the value of the
function to $1$. There is a famous example by Ajtai and Linial where a
coalition of size of order $n/\log^{2}n$ is needed to shift the expected value
of $f$ [1] by a constant.

###  5.3 Semi-Group proof of the KKL Theorem

In this section we will write $P_{t}=T_{e^{-t}}$ so that $P_{t}$ is a semi-
group, so $P_{s+t}=P_{s}P_{t}$.

######  Lemma 5.12.

$P_{t}f=\sum_{S}\hat{f}(S)e^{-t|S|}x_{S},\quad(\nabla_{i}f)(x)=\frac{1}{2}(f(x_{-i},1)-f(x_{-i},-1))=\sum_{S:i\in
S}\hat{f}(S)x_{S\setminus\\{i\\}}$

Note that

$\nabla_{i}(P_{t}f)=\sum_{S:i\in
S}\hat{f}(S)e^{-t|S|}x_{S\setminus\\{i\\}}=e^{-t}P_{t}\nabla f_{i}.$

and that

$\frac{d}{dt}P_{t}f=-\sum_{S}|S|\hat{f}(S)e^{-t|S|}x_{S}=-\sum_{i=1}^{n}x_{i}\nabla_{i}(P_{t}f)=-e^{-t}\sum_{i=1}^{n}x_{i}P_{t}\nabla_{i}f$

so

$\frac{d}{dt}\mathbb{E}[fP_{t}g]=-e^{-t}\sum_{i=1}^{n}\mathbb{E}[fx_{i}P_{t}\nabla_{i}g]=-e^{-t}\sum_{i=1}^{n}\mathbb{E}[\nabla_{i}fP_{t}\nabla_{i}g]$

The computation above allows to prove the following [48]:

######  Claim 5.13.

If $f$ and $g$ are monotone functions then $\mathbb{E}[fP_{t}g]$ is
monotonically decreasing in $t$.

###### Proof.

Assume $f$ and $g$ are increasing then the proof follows since $\nabla_{i}f$
and $\nabla_{i}g$ are always non-negative. ∎

######  Claim 5.14.

Let $f_{1},\ldots,f_{k}$ be positive and monotone increasing then
$\mathbb{E}[P_{t}f_{1}P_{t}f_{2}\ldots P_{t}f_{k}]$ is monotone decreasing.

###### Proof.

Write the derivative as a sum of partial derivatives. ∎

######  Remark 5.15.

The proofs are so easy that the claims can be generalized to a more general
Markov chain setting.

We now turn to applications a la Cordero-Ersquin and Ledoux [18] of the
derivative formula which can be thought of as an integration by parts formula.

######  Claim 5.16.

$Cov(f,g)=\int_{0}^{\infty}e^{-t}\sum_{i=1}^{n}\mathbb{E}[\nabla_{i}fP_{t}\nabla_{i}g]dt$

###### Proof.

$Cov(f,g)=\mathbb{E}[fP_{0}g]-\mathbb{E}[fP_{\infty}g]=-\int_{0}^{\infty}\frac{d}{dt}\mathbb{E}[fP_{t}g]dt=\int_{0}^{\infty}e^{-t}\sum_{i=1}^{n}\mathbb{E}[\nabla_{i}fP_{t}\nabla_{i}g]dt$

as needed. ∎

We can now prove some useful corollaries.

######  Claim 5.17.

$|Cov(f,g)|\leq\sum_{i=1}^{n}\sqrt{I_{i}(f)I_{i}(g)}$

###### Proof.

Note that

$|\mathbb{E}[\nabla_{i}fP_{t}\nabla_{i}g]|\leq\|\nabla_{i}f\|_{2}\|P_{t}\nabla_{i}g\|_{2}\leq\|\nabla_{i}f\|_{2}\|\nabla_{i}g\|_{2}=\sqrt{I_{i}(f)I_{i}(g)}.$

The proof follows by integration. ∎

######  Exercise 5.18.

Provide an alternative proof using directly the Fourier expansion. Show
moreover that if $\hat{f}(S)\hat{g}(S)\neq 0$ if and only if $S=\emptyset$ of
$|S|\geq k$, then the results can be improved to:

$|Cov(f,g)|\leq\frac{1}{k}\sum_{i=1}^{n}\sqrt{I_{i}(f)I_{i}(g)}$

If instead of the contractive estimate above we use the hyper-contractive
inequality:

$\|E[\nabla_{i}fP_{t}\nabla_{i}g]|\leq\|\nabla_{i}f\|_{1+e^{-t}}\|\nabla_{i}g\|_{1+e^{-t}}$

We get the following bound:

$|Cov(f,g)|\leq\int_{0}^{\infty}e^{-t}\sum_{i=1}^{n}\|\nabla_{i}f\|_{1+e^{-t}}\|\nabla_{i}g\|_{1+e^{-t}}dt=\int_{1}^{2}\sum_{i=1}^{n}\|\nabla_{i}f\|_{v}\|\nabla_{i}g\|_{v}dv$

Now By Holder inequality

$\|f\|_{v}\leq\|f\|_{2}^{1-\theta(v)}\|f\|_{1}^{\theta(v)}=\|f\|_{2}\left(\frac{\|f\|_{1}}{\|f\|_{2}}\right)^{\theta(v)},$

where $v\theta+0.5(1-\theta)v=1$ so $0.5\theta v=1-0.5v$ so $\theta=2/v-1$.
Writing

$r_{i}=\frac{\|\nabla_{i}f\|_{1}\|\|\nabla_{i}g\|_{1}}{\|\nabla_{i}f\|_{2}\|\nabla_{i}g\|_{2}},$

we see that

$|Cov(f,g)|\leq\sum_{i=1}^{n}\|\nabla_{i}f\|_{2}\|\nabla_{i}g\|_{2}\int_{1}^{2}r_{i}^{\theta(v)}dv$

Note that $\theta(v)=2/v-1\geq 1-v/2$ so

$\int_{1}^{2}r_{i}^{\theta(v)}dv\leq\int_{1}^{2}r_{i}^{1-v/2}dv=2\int_{0}^{1/2}r_{i}^{v}dv=\frac{1}{\ln
r_{i}}(r_{i}-1)\leq\frac{5}{1+\ln(1/r_{i})}$

We thus obtain

######  Claim 5.19.

$|Cov(f,g)|\leq
5\sum_{i=1}^{n}\frac{\sqrt{I_{i}(f)I_{i}(g)}}{1+\ln\left(\|\nabla_{i}f\|_{2}\|\nabla_{i}g\|_{2}/(\|\nabla_{i}f\|_{1}\nabla\|_{i}g\|_{2})\right)}$

######  Remark 5.20.

This statement is a slight generalization of the proof by [18] of Talagrands‘s
result [93].

$Var[f]\leq
5\sum_{i=1}^{n}\frac{I_{i}(f)}{1+2\ln\left(\|\nabla_{i}f\|_{2}/(\|\nabla_{i}f\|_{1})\right)}$

We claim that furthermore the last inequality implies the KKL Theorem that for
Boolean functions $f:\\{-1,1\\}^{n}\to\\{0,1\\}$ there exists an $i$ such that
$I_{i}(f)\geq cVar[f]\log n/n$. This is true since for Boolean functions
$\nabla_{i}f\in\\{1,0,-1\\}$ and therefore

$\|\nabla_{i}f\|_{2}=\sqrt{I_{i}(f)},\quad\|\nabla_{i}f\|_{1}=I_{i}(f).$

So for such function we get that

$Var[f]\leq 10\sum_{i=1}^{n}\frac{I_{i}(f)}{1-\ln I_{i}(f)}$

So the there exist an $i$ such that

$\frac{I_{i}(f)}{1-\ln I_{i}(f)}\geq cVar[f]/n$

and therefore $I_{i}(f)\geq cVar[f]\log n/n$.

###  5.4 Larger Domains

######  Remark 5.21.

The KKL Theorem and its proof immediately extend from the measure
$2^{-n}(\delta_{-1}+\delta_{1})^{\otimes n}$ to any measure of the form
$(p\delta_{-1}+(1-p)\delta_{1})^{\otimes n}$ for any fixed $p$, since hyper-
contractive estimates are known for such measures.

Allowing varying values of $p$ in the KKL Theorem has interesting implications
for aggregation of information.

We call a function $f:\\{-1,1\\}^{n}\to\\{-1,1\\}^{n}$ symmetric, if there
exists a group $\Pi$ who acts transitively on $[n]$ such that $f(\pi(x))=f(x)$
for all $\pi\in\Pi$, where $\pi(x)=(x_{\pi(1)},\ldots,x_{\pi(n)})$. Recall
that $\Pi$ acts transitively on $[n]$ if for all $i,j\in[n]$, there exists
$\pi\in\Pi$ with $\pi(i)=j$.

######  Corollary 5.22.

Let $f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ be monotone and symmetric and assume
$f(-x)=-f(x)$ for all $x$. Then for any ${\varepsilon}>0$, there exists a
$c({\varepsilon})>0$ such that if

$\mathbb{E}_{1/2+c/\log n}[f]\geq 1-{\varepsilon}.$

###### Proof.

Use Russo‘s formula and the KKL Theorem. ∎

Of course there are examples, where the theorem is far from tight. For example
for the majority function, we know that the statement of the theorem holds
when $p=1/2+c/\sqrt{n}$.

######  Exercise 5.23.

Consider the tribes functions and show that the statement of the theorem
cannot be improved.

######  Exercise 5.24.

Show that for the recursive Majority of threes functions, the statement of the
theorem holds for $p=1/2+n^{-\delta}$ for some $\delta>0$.

These results can be further generalized to scenarios involving multiple
candidates following [49].

####  5.4.1 Monotonicity and Aggregation for multiple alternatives

Let $A$ be a finite set. Let $X=A^{n}$. For $\sigma\in S(n)$, a permutation on
$n$ elements and $x\in A^{n}$ we denote by $y=x_{\sigma}$ the vector
satisfying $y_{i}=x_{\sigma(i)}$ for all $i$. For $\sigma\in S(A)$ we write
$y=\sigma(x)$ for the vector satisfying $y_{i}=\sigma(x_{i})$ for all $i$. For
$a\in A$ and $x,y\in X$ we write $x\leq_{a}y$ if
$\\{i:x_{i}=a\\}\subset\\{i:y_{i}=a\\}$ and for all $i$ such that $y_{i}\neq
a$ it holds that $x_{i}=y_{i}$. In other words if $x\leq_{a}y$ then for all
$i$ if $x_{i}\neq y_{i}$ then $y_{i}=a$. It is easy to see that $\leq_{a}$
defines a partial order on $X$.

######  Definition 5.25.

We say that $f:X=A^{n}\to A$ is monotone if for all $a\in A$ and $x,y\in X$
such that $x\leq_{a}y$ it holds that $f(x)=a$ implies that $f(y)=a$. We say
that $f$ is symmetric if there exists a transitive group $\Sigma\subset S(n)$
such that $f(x_{\sigma})=f(x)$ for all $x\in X$ and $\sigma\in\Sigma$. We say
that $f$ is fair if for all $\sigma\in S(A)$ and all $x\in X$ it holds that
$f(\sigma(x))=\sigma(f(x))$.

Let $\Delta[A]$ denote the simplex of probability measures on $A$ and let
$\gamma$ denote the standard probability measure on $\Delta[A]$. For
$\mu\in\Delta[A]$ denote by $\mathbb{P}_{\mu}$ the measure $\mu^{\otimes n}$
on $X$. We denote by $\mathbb{E}_{\mu}$ the expected value according to the
measure $\mathbb{P}_{\mu}$. For any measure $\mu\in\Delta[A]$, we write
$\mu^{\ast}$ for the minimal probability $\mu$ assigns to any of the atoms in
$A$.

It is not too hard to generalize the proof of the KKL Theorem to obtain the
following theorems, see cite

######  Theorem 5.26.

There exists an absolute constant $C=C(|A|)$ such that if $f$ is symmetric and
monotone then for any $a\in A$ and $1/2>{\varepsilon}>0$ it holds that

$\gamma[\mu:{\varepsilon}\leq P_{\mu}[f=a]\leq 1-{\varepsilon}]\leq
C(\log(1-{\varepsilon})-\log({\varepsilon}))\frac{\log\log n}{\log n}.$

######  Theorem 5.27.

For every $q$ there exists a constant $C=C(q)$ for which the following holds
for every $0<{\varepsilon}<1/3$. Let $\mu\in\Delta(q)$ and $i\in[q]$ satisfy
that

$\mu(i)>\max_{j\neq i}\mu(j)+C(\log(1-{\varepsilon})-\log(1/q))\frac{\log\log
n}{\log n}.$

Then for every fair monotone symmetric function $f:[q]^{n}\to[q]$ it holds
that

$\mu[f=i]\geq 1-{\varepsilon}.$

The results above establishes sharp threshold for symmetric functions as it
shows that for almost all probability measures $f$ takes one specific value
with probability at least $1-{\varepsilon}$.

######  Remark 5.28.

It is interesting to compare the results established here to those of [27].
For $|A|=2$ our results give a threshold interval of length $O(\log\log n/\log
n)$ compared to the results of [27] which give threshold interval of length
$O(1/\log n)$. The example of the tribes function shows that a better bound is
impossible. It is natural to conjecture that the threshold is always of
measure $O(1/\log n)$.

####  5.4.2 Applications to Majority/Plurality Dynamics

An interesting application of the theorems above is to Majority and Plurality
dynamics [71]. We will concentrate on Majority dynamics.

Consider a graph $G$ where all the degree are odd and an assignment of
opinions $X_{v}(0)$ for nodes of the graph. Consider the following dynamics,
where $X_{v}(t+1)=maj(X_{w}(t):w\sim v)$.

It is natural to ask a few questions: Does this process converge? It is easy
to see that the answer to this question is no. This can be seen for example in
the case where $G$ is bi-partite graph where the initial opinions on one side
are $+$ and on the other $-$.

Interestingly a finer notion of convergence is known to hold [35]

######  Proposition 5.29.

For each $v$, the sequence $X_{v}(2t)$ converges.

###### Proof.

Let

$J_{v}(t)=(X_{v}(t+1)-X_{v}(t-1))\sum_{w\sim v}X_{w}(t),\quad
J(t)=\sum_{v}J_{t}(v)$

We first note that $J_{v}(t)\geq 0$ and $J_{v}(t)=0$ if and only if
$X_{v}(t+1)=X_{v}(t-1)$. From this we conclude that $J_{t}\geq 0$ and
$J_{t}=0$ if and only if $X_{v}(t+1)=X_{v}(t-1)$ for all $v$. Thus it suffices
to show that $J_{t}=0$ from some point on. Also note that if $J_{t}=0$ then
$X_{v}(t+2i-1)=X_{v}(t-1)$ for all $i$.

For this let $L_{t}=\sum_{u\sim v}(X_{v}(t+1)-X_{u}(t))^{2}$ be a measure of
disagreement. We claim that $L_{t}-L_{t-1}=-J_{t}$. Note that this implies
that $L_{t}$ is decreasing and therefore at some point we will have to have
$J_{t}=0$ as needed. It is straightforward to check that
$L_{t}-L_{t-1}=-J_{t}$. ∎

Let us write $X_{v}=\lim_{t\to\infty}X_{v}(2t)$. Given that this process
converges, it is natural to ask if it retains information in the following
sense: Suppose that $X_{v}(0)$ are chosen i.i.d.
$p\delta_{1}+(1-p)\delta_{-1}$ for $p>1/2$. What is the probability that the
information is retained, i.e., what is

$\mathbb{P}_{p}[maj(X_{v})=+]?$

KKL Theorem allows us to answer this question in the special case where the
graph is transitive.

###  5.5 Aggregation for non-product measures

In this section we ask the following question: can aggregation results such as
the Jury Theorem and the KKL theorem be extended to non-product measures. This
section provides some answers to this question. The section is based on [37]

To describe a more general settings consider the following framework. Let
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a Boolean function. We will assume that $f$
is

  * •

monotone non-decreasing, i.e.,

$\left(\forall i:\,\,x_{i}\geq y_{i}\right)\implies f(x_{1},\ldots,x_{n})\geq
f(y_{1},\ldots,y_{n}),$

  * •

and anti-symmetric, i.e.,

$f(1-x_{1},1-x_{2},\dots,1-x_{n})=1-f(x_{1},x_{2},\dots,x_{n}).$

The purpose of this section is to study extensions of the weak law of large
numbers in the context of general probability distributions. Let $\mu$ be a
probability distribution on $\\{0,1\\}^{n}$. When $\mu$ is not a product
measure the notion of influence can be extended in different way compared to
the above. Define the effect of the $k$‘th variable on the Boolean function
$f$ as the difference between the expected value of $f(x_{1},\dots,x_{n})$
conditioned on $x_{k}=1$ and the expected value of $f(x_{1},\dots,x_{n})$
conditioned on $x_{k}=0$, and denote by $e_{k}^{\mu}(f)$ the effect of the
$k$‘th variable for the Boolean function $f$, w.r.t. the distribution $\mu$.
More precisely,

$e_{k}^{\mu}(f)=\mu[f(X_{1},\ldots,X_{n})|X_{k}=1]-\mu[f(X_{1},\ldots,X_{n})|X_{k}=0].$
(5.2)

The effect is undefined if the probability for $X_{k}=1$ is $1$ or $0$.
Writing $\mu[X_{k}]=p$ and $Y_{k}=X_{k}-p$, we get

$\displaystyle\operatorname*{Cov}_{\mu}[f(X_{1},\ldots,X_{n}),X_{k}]$
$\displaystyle=$ $\displaystyle\mu[f(X_{1},\ldots,X_{n})Y_{k}]$
$\displaystyle=$ $\displaystyle p\mu[(1-p)f|X_{k}=1]+(1-p)\mu[-pf|X_{k}=0]$
$\displaystyle=$ $\displaystyle p(1-p)e_{k}^{\mu}(f)$

so that the effect may be interpreted as a normalized form of the correlation
between the individual vote and the election‘s outcome.

When $\mu$ represent a product probability measure, the effect (5.2) and the
influence coincide, but in general this is not the case. For instance, for
general $\mu$ the effect may be negative (an example will appear later) while
the influence is of course always non-negative.

It is not true that for general probability distributions and general $f$,
small influences implies aggregation of information. Our main result is that
small effects implies aggregation of information for the particular case of
weighted majority functions. Moreover, the bounds for weighted majorities are
rather realistic.

We call monotone antisymmetric function $f$ a weighted majority function if
there exists non-negative weights $w_{1},\dots,w_{n}$, not all zero such that
$f(x_{1},\dots,x_{n})=1$ if $\sum_{i=1}^{n}w_{i}(2x_{i}-1)>0$ and and
$f(x_{1},\dots,x_{n})=0$ if $\sum_{i=1}^{n}w_{i}(2x_{i}-1)<0$. If $n$ is odd
and $w_{i}=1$ for every $i$, $f$ is called the majority function (or simple
majority).

Note that in our definition of a weighted majority function, if $\sum
w_{i}(2x_{i}-1)=0$ then the value of $f(x)$ may be either $0$ or $1$ as long
as $f$ is monotone and anti-symmetric. This is different from the traditional
definition of a weighted majority (or threshold) function where $f(x)=1$ iff
$\sum w_{i}(2x_{i}-1)>0$ and $f(x)=0$ iff $\sum w_{i}(2x_{i}-1)<0$.

Thus for example, any monotone anti-symmetric function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ satisfying $f(x)=1$ when $x_{1}=x_{2}=1$ and
$f(x)=0$ when $x_{1}=x_{2}=0$ is a weighted majority function (taking
$w_{1}=w_{2}=1$ and $w_{3}=\cdots=w_{n}=0$) according to our definition.

The above example demonstrates that under our definition of weighted majority
functions, there are at least $2^{2^{n-2}}$ weighted majority functions. Under
the traditional definition the number of weighted majority functions is at
most $2^{n^{2}}$ [16, 89].

Of particular interest are voting schemes where all the voters have the same
power. One such case is when $f$ is invariant under a transitive group of
permutations. In other words there exists a group of permutation
$\Gamma\subset S_{n}$ such that
$f(x_{1},\ldots,x_{n})=f(x_{\sigma(1)},\ldots,x_{\sigma(n)})$ for all
$\sigma\in\Gamma$ and for all $1\leq i,j\leq n$ there exists $\sigma\in\Gamma$
such that $\sigma(i)=j$; here $S_{n}$ denotes the full permutation group on
$n$ elements. One instructive example is the simple majority function when $n$
is odd which is invariant under $S_{n}$; another is the recursive majority
function $RM_{k,\ell}$ which is defined for $n=k^{\ell}$ where $k$ is odd. The
definition is by induction. $RM_{k,1}$ is just the majority function on $k$
bits and

$RM_{k,\ell+1}(x_{1},\ldots,x_{k^{\ell+1}})=RM_{k,1}\left(RM_{k,\ell}(x_{1},\ldots,x_{k^{\ell}}),\ldots,RM_{k,\ell}(x_{k^{\ell}-k^{\ell-1}+1},\ldots,x_{k^{\ell}})\right).$

######  Theorem 5.30.

(a) For every $p>\frac{1}{2},\epsilon>0$ there is
$\delta=\delta(p,\epsilon)>0$ such that for every weighted majority function
$f$ and any distribution $\mu$ on $\\{0,1\\}^{n}$, if
$e_{k}^{\mu}[f]\leq\delta$ and $\mu[X_{k}=1]\geq p$ for all $k$ then
$\mu[f]\geq 1-{\varepsilon}$.

In other words, if the effect of each variable is at most $\delta$ and the
probability that each variable is $1$ is at least $p$, then $f=1$ with
$\mu$-probability at least $1-{\varepsilon}$.

(b) If $f$ is a monotone anti-symmetric function but not a weighted majority
function, then there exists a probability distribution $\mu$ such that
$\mu[X_{k}=1]>1/2$ for all $k$, yet $\mu[f]=0$ and $e_{k}^{\mu}(f)=0$ for all
$k$.

In other words, if $f$ is not a weighted majority function, then there is a
probability measure $\mu$ for which $f=0$ with $\mu$-probability $1$, yet
$\mu[X_{k}=1]>\frac{1}{2}$ for all $k$. (Since $f$ is constant according to
the measure $\mu$, all the effects are $0$ in this case.)

(c) If $f$ is monotone anti-symmetric and invariant under a transitive group,
but is not the (simple) majority function, then then there exists a
probability distribution $\mu$ such that $\mu[X_{k}=1]>1/2$ for all $k$, yet
$\mu[f]=0$ and $e_{k}^{\mu}(f)=0$ for all $k$.

The rest of this section is organized as follows. In subsection 5.5.1 we will
discuss the notions of aggregation of information, influences and effects for
general probability distributions on $\\{0,1\\}^{n}$. We will try to examine
what aggregation of information means when we do not suppose that the
probability distribution for the voter‘s behavior is a product distribution.
We also examine to what extent our technical notion of ’’effects‘‘ represent
real influence in the non-technical sense of the words. Subsection 5.5.2
contains the proof of our theorem and in subsection 5.5.3 we present several
natural problems as well as an example showing lack of aggregation for
monotone functions even for the restricted class of FKG-distributions.

####  5.5.1 Voting games, information aggregation and notions of influence

Consider the following scenario. Every agent $k$ receives a single bit of
information $s_{i}$ which is either ’Vote for Alice‘ or ’Vote for Bob‘ and
these signals are independent. When Alice is the better candidate the
probability of receiving the signal ’Vote for Alice‘ is $p>1/2$. Condorcet‘s
Jury Theorem deals with the case that the voters vote precisely as the signal
dictates and the decision is made according to the simple majority rule. It
asserts that for every $p>1/2$ the better candidate will be elected with
probability tending to one. Thus the majority rule allows to reveal the actual
state of the world from rather weak individual signals.

A major problem in the economic and political interpretation of Condorcet‘s
Jury Theorem and its extensions arises from the fact that the basic assumption
of probability independence among voters is quite unrealistic. Without the
assumption of independence, Condorcet‘s Jury Theorem as stated is no longer
true, and it will no longer be the case that when each individual votes for
Alice with probability $p>1/2$, Alice will win with a high probability.

To see this, consider the following example. As before, we have an election
between Alice and Bob and Alice is the superior candidate. The distribution of
signals $s_{1},s_{2},\dots,s_{n}$ will be biased towards Alice as follows: Let
$p=1/2+\epsilon/2$, where $\epsilon$ is small. First choose at random a number
$t$ uniformly in the interval $[\epsilon,1]$. Then, independently for each
$i$, choose the $i$‘th voter signal $s_{i}$ to be ’1‘ with probability $t$ and
’0‘ with probability $1-t$. Voters with $s_{i}=1$ will vote for Alice. In this
case, the probability for each individual signal $s_{i}$ being ’1‘ is $p$ but
the individual signals are not independent. The probability that Alice will
win is below $\frac{1}{2(1-{\varepsilon})}$ for any number of voters. This is
because we can think of $t$ being chosen in two stages. First we toss a coin
which is ‘H‘ with probability $\epsilon/(1-\epsilon)$. If the coin is ‘H‘,
then $t$ is chosen uniformly in the interval $[1-\epsilon,1]$. This
contributes to the probability that Alice wins at most
$\epsilon/(1-\epsilon)$. If the coin is ‘T‘ then $t$ is chosen uniformly in
the interval $[\epsilon,1-\epsilon]$. Here by symmetry, Alice and Bob have the
same chance of winning. Thus the contribution to the probability that Alice
will win from this case is $\frac{1-2\epsilon}{2(1-\epsilon)}$. Thus the
overall probability that Alice will win is at most
$\frac{1-2\epsilon}{2(1-\epsilon)}+\frac{\epsilon}{1-\epsilon}=\frac{1}{2(1-{\varepsilon})}$.

An even more extreme example is the case in which all voters vote in the same
way: With probability $p$ they all vote for Alice and with probability $1-p$
they all vote for Bob. Alice will be elected with probability $p$ regardless
of the number of voters when the election is based on simple majority and for
every other simple game.

These simple examples will help us to examine the notions of information
aggregation and influence in the case when the assumption of probability
independence is dropped. The problem in these examples is not in the way
information aggregates but in the quality of the information to start with.
This assertion can be formalized as follows. Suppose that Alice and Bob are
given an a-priori probability $1/2$ of being the superior candidate. We assume
that the distribution of voters for Bob given Bob is the superior candidate is
the same as the distribution of voters for Alice given that Alice is the
superior candidate. Thus in the first example above if Bob is superior then we
choose $t$ uniformly in $[{\varepsilon},1]$ and then each voter votes for Bob
independently with probability $t$. In the second example if Bob is superior,
then all voters will vote for Bob with probability $p$.

We now wish to decide between the hypothesis that Alice is the superior and
the hypothesis that Bob is the superior candidate given the entire vector of
individual signals. It is intuitively clear and easy to prove using the
Neyman-Pearson Lemma that in both cases described above one should guess that
Alice is superior to Bob exactly when the majority of voters voted for Alice.
However, in both examples above the probability that the majority will vote
Alice when Alice is superior is bounded away from $1$ and tends to $1/2$ as
$p$ does.

When we consider general distributions, the issue is to understand what
information we can derive on the superior alternative from knowing the signals
of all individuals and how the voting mechanism extracts this information.
Note that in the examples we considered above the individual effects are large
while the individual influences are small. This is most transparent in the
second example where if $f$ is the majority function and $n\geq 3$, then all
of the influences are $0$, while the effect of all voters are $1$. Theorem
5.30 asserts that for the weighted majority voting rule (and only for these
rules) for every probability measure on $\\{0,1\\}^{n}$, small individual
effects implies asymptotically complete aggregation of information.

Let us next consider the notion of influence without probability independence.
The notion of pivotal variables (or players) and influence is of important
technical importance in various areas of mathematics, computer science and
economics. This notion is also of a considerable conceptual importance. The
voting power index of Banzhaf is based on measuring the influence with respect
to the uniform distribution. The Shapley–Shubik power index can also be based
on the influence with respect to another distribution. Conceptual
understanding of voting power in situations where the voters‘ behavior is not
independent is of great interest. In [31] the authors propose to define the
voting power as the probability to be pivotal based on realistic assumptions
on individual voting distributions. We make the following remarks on the
notion of individual effects which is quite a different extension of influence
and voting power measures to arbitrary probability distributions.

(i) For general distributions, the effect of an agent can be negative. This
will be the case for a voter who always votes for the candidate who is the
underdog in the election polls and also for a committee member who antagonizes
the other members of the committee. (On the other hand, the influence of an
agent is always nonegative, because it is defined as a represents a
probability.)

(ii) A dummy (a voter $k$ which is never pivotal) has zero influence (with
respect to every probability distribution). He may nevertheless have a large
effect, such as if he always votes for the candidate who is expected to win
according to election polls. In real life, this will also be the case for an
observer on a committee without the right to vote but who is likely to
convince the committee of his opinion. Note that in the first case we do not
attribute to that player real ’’influence‘‘ in the (non-technical) English
sense of the word, while in the second case we would consider him
’’influential‘‘. The uncertainty in interpreting effects as real
’’influences‘‘ is genuine.

(iii) What is the motivation for a voter to vote, given the small probability
for him to be pivotal? This is a social dilemma, related to, e.g., the so-
called tragedy of the commons, and has been extensively discussed in the
political science and philosophy literature. (Sometimes the term voting
paradox has been used for this dilemma, but may cause some confusion as the
same term is used also for Condorcet‘s famous observation that when three or
more choices are available, the majority preference between them need not be
transitive.) A possible solution to the dilemma may lie in the fact that in
real-life elections, individual effects tend to be large, namely bounded away
from zero regardless of the size of the society. The uncertainty in regarding
effects as real ’’influence‘‘ may suggest that it is the effect of an agent
rather than his influence which is related to his ’’satisfaction‘‘ with the
social decision process and his ability to identify with the collective
choice.

####  5.5.2 Proof of Theorem 5.30

##### Part (a) of the theorem

We begin this section by providing a probabilistic proof of the following
result, which clearly implies Theorem 5.30 (a).

######  Lemma 5.31.

Let $(w_{i})_{i=1}^{n}$ be non-negative weights which are not all $0$, let
$0<q<1$, and let $f:\\{0,1\\}^{n}\to\\{-1,1\\}$ be a function which satisfies

$f=\left\\{\begin{array}[]{ll}1&\mbox{if }\sum_{i=1}^{n}(2x_{i}-2q)w_{i}>0\\\
0&\mbox{if }\sum_{i=1}^{n}(2x_{i}-2q)w_{i}<0.\end{array}\right.$

Write $W=\sum_{i=1}^{n}w_{i}$. Suppose furthermore that $p>q$ and that $\mu$
is a probability measure satisfying $\mu[X_{i}]=p_{i}$ and

$\sum_{i=1}^{n}w_{i}p_{i}=pW$ (5.3)

as well as

$\sum_{i=1}^{n}w_{i}p_{i}(1-p_{i})e_{i}^{\mu}[f]\leq p(1-p)\delta W.$ (5.4)

Then

$\mu[f]\geq 1-\frac{\delta p(1-p)}{p-q}.$

(Note that (5.3) holds if $\mu[X_{i}]=p$ for all $i$, and that (5.4) holds if
$\mu[X_{i}]=p$ and $e_{i}^{\mu}[f]\leq\delta$ for all $i$, so that indeed
Theorem 5.30 (a) follows.)

###### Proof.

Let $X=\sum_{i=1}^{n}(2X_{i}-2q)w_{i}$. We start by noting that
$\mu[X]=(2p-2q)W$.

We let $g=1-f$ and $Y_{i}=p_{i}-X_{i}$, so that

$\mu[Y_{i}g]=\operatorname*{Cov}_{\mu}[f,X_{i}]=p_{i}(1-p_{i})e_{k}^{\mu}[f].$

Note that conditioned on $g=1$, $\sum_{i=1}^{n}(2X_{i}-2q)w_{i}\leq 0$ and
therefore $\sum_{i=1}^{n}w_{i}Y_{i}\geq(p-q)W$. It follows that

$\displaystyle\mu\left[\left(\sum_{i=1}^{n}w_{i}Y_{i}\right)g(X_{1},\ldots,X_{n})\right]$
$\displaystyle\geq$ $\displaystyle(p-q)W\mu[g]$ (5.5) $\displaystyle=$
$\displaystyle(p-q)W(1-\mu[f]).$

On the other hand,

$\displaystyle\mu\left[\left(\sum_{i=1}^{n}w_{i}Y_{i}\right)g(X_{1},\ldots,X_{n})\right]$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}w_{i}\mu[Y_{i}g(X_{1},\ldots,X_{n})]$ (5.6)
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}w_{i}p_{i}(1-p_{i})e_{i}^{\mu}[f]$
$\displaystyle\leq$ $\displaystyle p(1-p)\delta W.$

Combining (5.5) and (5.6), we get that

$\displaystyle\mu[f]$ $\displaystyle\geq$ $\displaystyle
1-\frac{\sum_{i=1}^{n}w_{i}p_{i}(1-p_{i})e_{i}^{\mu}[f]}{(p-q)W}$
$\displaystyle\geq$ $\displaystyle 1-\frac{\delta p(1-p)}{p-q}.$

∎

##### Parts (b) and (c) of the theorem

We note that part (c) of Theorem 5.30 follows immediately from part (b),
because the only weighted majority function that is invariant under a
transitive group, is simple majority. Let us nevertheless begin by giving an
independent and simple proof of part (c). Note that if $f$ is not the majority
function then there is a vector $(x_{1},x_{2},\dots,x_{n})\in\\{0,1\\}^{n}$
such that $f(x)=0$ and $x_{1}+x_{2}+\dots+x_{n}>n/2$. Then we can simply take
$\mu$ to be uniform probability distribution on the orbit of $x$ under
$\Gamma$. It is then easy to see that $\mu[X_{k}]>1/2$ for all $k$ and that
$\mu[f=0]=1$.

We now turn to the proof of Theorem 5.30 (b). We will show that if $f$ is not
a weighted majority function, then there exists a measure $\mu$ satisfying
$\mu[X_{k}]>1/2$ for all $k$ and $\mu[f=0]=1$.

Define $[n]=\\{1,2,\dots,n\\}$. For $S\subset[n]$ put
$x_{S}=(x_{1},x_{2}\dots,x_{n})$ where $x_{i}=1$ if and only if $i\in S$. Let
$H$ be a hypergraph whose set of vertices is $[n]$ and whose edges are subsets
$S$ of $[n]$ such that $f(x_{S})=0$. Let $\tau^{*}=\tau^{*}(H)$ be the
fractional cover number of $H$, i.e., the infimum over all
$\nu:\\{0,1\\}^{n}\to\mathbb{R}$ of $\sum_{S\in H}\nu[x_{S}]$, under the
condition that $\nu(x_{S})\geq 0$ for every $S\in H$ and $\sum_{S\in H,k\in
S}\nu[x_{S}]\geq 1$ for all $k$. We get $\tau^{\ast}=\infty$ if there are no
$\nu$ satisfying the two conditions above (note that this is the case if
$f(x)=x_{1}$, say).

If $\tau^{*}<2$, then we can define $\mu(S)=0$ if $f(S)=1$ and
$\mu(S)=\nu(S)/\tau^{*}$ when $f(S)=0$. The probability measure $\mu$
satisfies that

$\sum_{S:k\in S,f(S)=0}\mu(x_{S})\geq 1/\tau^{*}>1/2$

for every $k$ and $\mu[f=0]=1$ as stated in the theorem. Therefore, in order
to prove part (b) of the theorem, it only remains to analyze the case
$\tau^{*}\geq 2$.

A well known equivalent (by linear programming duality) definition of of
$\tau^{*}$ is as the supremum of $\sum_{i=1}^{n}w_{i}$ under the condition
that $w_{k}\geq 0$ for $k=1,2,\dots,n$ and $\sum\\{w_{i}:i\in S\\}\leq 1$ for
every $S\in H$.

Assume first that $\tau^{\ast}>2$. In this case we can find $w_{i}$‘s such
that $\sum_{i}w_{i}>2$ and $f(x_{1},\dots,x_{n})=1$ if $\sum w_{i}x_{i}>1$. By
slightly perturbing the $w_{i}$ we may assume that for all $x\in\\{0,1\\}^{n}$
it holds that $\sum_{i}w_{i}x_{i}\neq\frac{1}{2}\sum_{i}w_{i}$ in addition to
the properties that $\sum_{i}w_{i}>2$ and $f(x_{1},\dots,x_{n})=1$ if $\sum
w_{i}x_{i}>1$. Let $g(x)=1$ if $\sum_{i}w_{i}x_{i}>\frac{1}{2}\sum_{i}w_{i}$
and $g(x)=0$ if $\sum_{i}w_{i}x_{i}<\frac{1}{2}\sum_{i}w_{i}$. Then $g$ is
anti-symmetric and $f=0\implies g=0$. It follows that $f=g$ so that $f$ is a
weighted majority function as needed.

The remaining case is where $\tau^{\ast}=\sum w_{i}=2$. We obtain that
$f(x_{1},\dots,x_{n})=1$ if $\sum w_{i}x_{i}>1$. Since $f$ is anti-symmetric
it follows that $f(x_{1},\dots,x_{n})=0$ if $\sum w_{i}x_{i}<1$. The result
follows. $\square$

####  5.5.3 Problems and an additional example

The following problems naturally suggest themselves at this point:

(1) For which class of distributions is it the case that for simple majority
small voting power implies asymptotically complete aggregation of information?

(2) For which class of distributions is it the case that for every monotone
Boolean function small voting power implies asymptotically complete
aggregation of information?

(3) For which class of distributions is it the case that for every monotone
Boolean function small individual effects implies asymptotically complete
aggregation of information?

A natural condition to impose on the distribution $\mu$ which is realistic in
various economic situations is the FKG condition (see [55]). For
$x=(x_{1},\dots,x_{n})$ and $y=(y_{1},\dots,y_{n})$, define

$\max(x,y)=(\max(x_{1},y_{1}),\dots,\max(x_{n},y_{n}))$

and

$\min(x,y)=(\min(x_{1},y_{1}),\dots,\min(x_{n},y_{n})).$

One definition of FKG measure on $\\{0,1\\}^{n}$ goes as follows: A
distribution $\mu$ on $\\{0,1\\}^{n}$ (or on $\mathbb{R}^{n}$) is called an
FKG measure if for every $x,y\in\\{0,1\\}^{n}$ we have

$\mu(x)\mu(y)\leq\mu(\max(x,y))\mu(\min(x,y)).$

The FKG property is a profound notion of non-negative correlations between
agents‘ signals. It implies (but is strictly stronger than) the following
condition (known as non-negative association, see [60]): For all increasing
real functions $f$ and $g$, it is the case that $E[fg]\geq E[f]E[g]$. This is
equivalent to the condition that for all increasing events $A$ and $B$ we have
that $P[AB]\geq P[A]P[B]$. Under the FKG property if the simple game is
monotone, all effects are non-negative. This form of non-negative correlation
is a plausible assumption to make in various contexts of collective choice. It
is easy to see that under the condition of non-negative association all
individual effects are non-negative.

(4) For which class of monotone Boolean functions does small individual
effects imply asymptotically complete aggregation of information?

In the following subsection, we present an example of an FKG measure and a
monotone Boolean function such that the individual effects are small and yet
there is no asymptotically complete aggregation of information. In this
example both the voting scheme and the measure $\mu$ are invariant under a
transitive group of permutations.

####  5.5.4 Example: FKG without aggregation

The measure $\mu$. We start by describing the measure $\mu$. The measure is
given by a Gibbs measure for the Ising model on the $3$-regular tree. See e.g.
[32]. The measure is defined as follows. Let $T_{r}=(V_{r},E_{r})$ be the
$r$-level $3$-regular tree. This is a rooted tree where each internal nodes
has exactly $3$ children and all the leaves are at distance exactly $r$ from
the root $\rho$. Let $L_{r}$ be the set of leaves of that tree. Note that
$|L_{r}|=3^{r}$.

We first define a measure $\nu$ on the tree $\\{0,1\\}^{V_{r}}$. In this
measure the probability of $x$ is given by

$\nu[x]=\frac{1}{2}\prod_{(u,v)\in
E_{r}}\left((1-\epsilon)1_{\\{x_{u}=x_{v}\\}}+\epsilon 1_{\\{x_{u}\neq
x_{v}\\}}\right).$

In words, this means that in the measure $\nu$ the sign of the root $x_{\rho}$
is chosen to be $0$ or $1$ with probability $1/2$. Then each vertex inherits
its parents label with probability $\theta=1-2{\varepsilon}$ and is chosen
independently otherwise.

Our measure $\mu$ is defined on $\\{0,1\\}^{L_{r}}$ (so that the voters are
the leaves of the tree) as follows.

$\mu[x]=\sum_{y:y|L_{r}\leq x}\nu[y]\delta^{|\\{i:x_{i}=1,y_{i}=0\\}|}.$

In other words, a configuration of votes according to $\mu$ may be obtained by
drawing a configuration $x$ according to $\nu$ and looking at $x|L_{r}$. Then
for each of the coordinates of $i\in L_{r}$ independently, the vote at $x$ re-
sampled to have the value $1$ with probability $\delta$. Below we will
sometime abuse notation and write $\mu$ for the joint probability distribution
of $x$ and $y$.

Standard results for the Ising model (see, e.g., [32]) imply that $\mu$ is an
FKG measure. Moreover it is easy to see that the measure is invariant under a
transitive group and that $\mu[x_{i}]=(1+\delta)/2$ for all $i$.

The function $m$. The function $m$ is given by the recursive majority function
$m=RM_{3,r}$. Clearly, $m$ is monotone, anti-symmetric and invariant under a
transitive group.

######  Claim 5.32.

If ${\varepsilon}=\delta\leq 0.01$ then $\mu[m]\leq 1/2+\delta/2$ for
$m=RM_{3,r}$ and all $r$.

###### Proof.

The proof below is similar to arguments in [63, 64]. Let $(y_{v}:v\in V_{r})$
be chosen according to the measure $\nu$. Let $(x_{v}:v\in L_{r})$ be obtained
from $y_{v}$ by re-sampling each of the coordinates of $(y_{v}:v\in L_{r})$ to
$1$ with probability $\delta$. Let $(m_{v}:v\in V_{r})$ denote the value of
the recursive majority of all $(x_{w}:w\in L_{r}(v))$, where $L_{r}(v)$ are
all the leaves of $T$ below $v$. We will show that
$\mu[m=m_{\rho}=0|y_{\rho}=0]\geq 1-\delta$. Since $\mu[y_{\rho}=0]=1/2$, we
conclude that $\mu[m]\leq 1/2+\mu[m|x_{\rho}=0]/2\leq(1+\delta)/2$, as needed.

We are interested in the probability that $m_{v}=0$ conditioned on $y_{v}=0$.
It is easy to see that this probability only depends on the height of $v$,
i.e., on the distance between $v$ and the set of leaves. We let $p(k)$ denote
the probability that $m_{v}=0$ conditioned on $y_{v}=0$ for a vertex $v$ of
height $k$.

Clearly, $p(0)=1-\delta$. We want to prove by induction that $p(k)\geq
1-\delta$ for all $k$. Let $v$ be a node of height $k+1$ and $w$ a child of
$v$. Note that conditioned on $x_{v}=0$ the probability that $m_{w}=0$ is at
least $(1-{\varepsilon})p(k)$ which is at least
$t=(1-{\varepsilon})(1-\delta)$ by the induction hypothesis. Moreover, noting
that the values of the majorities of the children of the node $v$ are
conditionally independent given that $m_{v}=0$, we conclude that

$p(k)\geq t^{3}+3t^{2}(1-t)=3t^{2}-2t^{3}=t^{2}(3-2t).$

We need that $t^{2}(3-2t)\geq 1-\delta$ or recalling that
${\varepsilon}=\delta$:
$(1-{\varepsilon})^{4}(3-2(1-{\varepsilon})^{2})\geq(1-{\varepsilon})$. This
in turn is equivalent to $(1-{\varepsilon})^{3}(3-2(1-{\varepsilon})^{2})\geq
1$. The function
$h({\varepsilon})=(1-{\varepsilon})^{3}(3-2(1-{\varepsilon})^{2})$ has
$h^{\prime}({\varepsilon})=10(1-{\varepsilon})^{4}-9(1-{\varepsilon})^{2}=(1-{\varepsilon})^{2}(10(1-{\varepsilon})^{2}-9)$.
Therefore $h$ is increasing in the interval $[0,0.01]$. Since $h(0)=1$ it
follows that $h({\varepsilon})\geq 1$ for all ${\varepsilon}\leq 0.01$ as
needed. ∎

Our next objective is to bound the effect of a voter at level $r$. We will
prove the following:

######  Claim 5.33.

The measure $\mu$ on $T_{r}$ and the function $m=RM_{3,r}$ satisfy that the
effect of each voter is at most $(1-{\varepsilon}/2)^{(r-1)/2}+2^{-(r-1)/2}$.

###### Proof.

The argument here is similar in spirit to an argument in [9]. Let $t+s=r$
where $t\geq(r-1)/2$ and $s\geq(r-1)/2$. Fix a leaf voter $i$. We want to
estimate $\mu[m=1|y_{i}=1]-\mu[m=1|y_{i}=0]$. Let‘s denote by $\mu_{0}$ the
measure $\mu$ conditioned on $y_{i}=0$ and by $\mu_{1}$ the measure $\mu$
conditioned on $y_{i}=1$.

Let $i=v_{0},v_{1},\ldots,v_{r}=\rho$ denote the path from $i$ to the root. We
first claim that the measures $\mu_{0},\mu_{1}$ and $\mu$ may be coupled in
such a way that except with probability $(1-2{\varepsilon})^{t}$ the only
disagreements between $\mu_{0},\mu_{1}$ and $\mu$ are on vertices below
$v_{t}$.

The follows immediately from the random cluster representation of the model.
In this representation we declare and edge $(u,v)$ open with probability
$(1-2{\varepsilon})$ and closed with probability $2{\varepsilon}$. If the edge
$(u,v)$ is open then $y_{u}=y_{v}$, otherwise, the two labels are independent.
It is then clear that we may couple the two measure $\mu_{0},\mu_{1}$ and
$\mu$ below $v_{t}$ as long as the path from $i$ to $v_{t}$ contains at least
one closed edge. The probability that such an edge does not exist is at most
$(1-2{\varepsilon})^{t}$. The proof of the first claim follows.

For each $j$ denote by $u_{j}$ and $w_{j}$ the siblings of $v_{j}$. We assume
that the measures $\mu_{0},\mu_{1}$ and $\mu$ are coupled in such a way that
the only disagreements between them are on vertices below $v_{t}$. Note that
if this is the case, then if the values of $m$ under $\mu_{0}$ and $\mu_{1}$
are different then for all $r\geq j\geq t$ it holds that $m_{u_{j}}\neq
m_{w_{j}}$. We wish to bound the $\mu$ probability that $m_{u_{j}}\neq
m_{w_{j}}$ for $r\geq j\geq t$. We will bounds this probability conditioned on
the values $(y_{v_{j}})_{j=t}^{r}$. Conditioned on $(y_{v_{j}})_{j=t}^{r}$ the
event $m_{u_{j}}\neq m_{w_{j}}$ are independent for different $j$‘s. Moreover,
by the Markov property, $\mu[m_{u_{j}}\neq
m_{w_{j}}|(y_{v_{h}})_{h=t}^{r}]=\mu[m_{u_{j}}\neq m_{w_{j}}|y_{v_{j-1}}]$.
Finally note that conditioned on $y_{v_{j-1}}$ the random variables
$m_{u_{j}},m_{w_{j}}$ are identically distributed and independent. Therefore

$\mu[m_{u_{j}}\neq m_{w_{j}}|y_{v_{j-1}}]\leq\max_{p\in[0,1]}2p(1-p)\leq 1/2.$

We thus obtain that the $\mu$ probability that $m_{u_{j}}\neq m_{w_{j}}$ for
$r\geq j\geq t$ is at most $2^{-s}$. ∎

##  Chapter 6 Recent Progress

Some exciting developments have taken place since the course these lecture
notes are based upon was taught. We briefly discuss some of these.

###  6.1 Plurality is Stablest

The Majority is Stablest Theorem played a major role in these lectures, see
theorems 2.15, 2.16, 2.17 etc. 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 function is now a plurality function.
This was first asked in [51]. Similarly to the case of $q=2$, there is an
equivalent Gaussian question [42], which was conjectured to be true in [42].
The shape of the conjectured optimal partition 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 partition for $q=3$ was obtained in [19] under mid conditions and for all
$q$ and no additional condition in recent work [61, 62].

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. [38] 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 the
pluralities functions with the same expected values. Thus low influence
functions $f:[q]^{n}\to[q]$ that are not balanced can be asymptotically more
stable 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 [39].

###  6.2 Judgment Aggregation

In the legal literature, Kornhauser and Sager [53] discusses 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

$f(x\land y)=f(x)\land f(y),$ (6.1)

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 [57, 58] showed that the only
non-constant aggregation functions that satisfy (6.1) 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\ldots\land x_{i_{r}}$ for some
$1=i_{1}<\ldots i_{r}\leq n$. Recent work [26] 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, improving on prior work by
Nehama [81] 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.

## Bibliography

  * [1] M. Ajtai and N. Linial.  The influence of large coalitions.  Combinatorica, 13(2):129–145, 1993.
  * [2] K. Arrow.  A difficulty in the theory of social welfare.  J. of Political Economy, 58:328–346, 1950.
  * [3] K. Arrow.  Social choice and individual values.  John Wiley and Sons, 1963.
  * [4] S. Barbera.  Pivotal voters: A new proof of arrow‘s theorem.  Economics Letter, 6:13–16, 1980.
  * [5] J. J. Bartholdi, C. A. Tovey, and M. A. Trick.  The computational difficulty of manipulating an election.  Social Choice and Welfare, 6(3):227–241, 1989.
  * [6] W. Beckner.  Inequalities in Fourier analysis.  Ann. of Math. (2), 102(1):159–182, 1975.
  * [7] M. Ben-Or and N. Linial.  Collective coin flipping.  In S. Micali, editor, Randomness and Computation. Academic Press, New York, 1990.
  * [8] I. Benjamini, G. Kalai, and O. Schramm.  Noise sensitivity of boolean functions and applications to percolation.  Inst. Hautes Études Sci. Publ. Math., 90:5–43, 1999.
  * [9] N. Berger, C. Kenyon, E. Mossel, and Y. Peres.  Glauber dynamics on prob and hyperbolic graphs.  Probab. Theory Related Fields, 131(3):311–340, 2005.
  * [10] S. G. Bobkov.  An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space.  Ann. Probab., 25(1):206–214, 1997.
  * [11] A. Bonami.  Étude des coefficients de Fourier des fonctions de $L^{p}(G)$.  Ann. Inst. Fourier (Grenoble), 20(fasc. 2):335–402 (1971), 1970\.
  * [12] C. Borell.  Positivity improving operators and hypercontractivity.  Math. Zeitschrift, 180(2):225–234, 1982.
  * [13] C. Borell.  Geometric bounds on the Ornstein-Uhlenbeck velocity process.  Z. Wahrsch. Verw. Gebiete, 70(1):1–13, 1985.
  * [14] C. D. Campbell and G. Tullock.  The paradox of voting?a possible method of calculation.  American Political Science Review, 60(3):684–685, 1966.
  * [15] B. Chor, O. Goldreich, J. Hasted, J. Freidmann, S. Rudich, and R. Smolensky.  The bit extraction problem or t-resilient functions.  In — 26th Annual Symposium on Foundations of Computer Science, pages 396–407. IEEE, 1985.
  * [16] C. L. Coates and P. Lewis.  Donut: A threshold gate computer.  IEEE Transactions on Electronic Computers, (3):240–247, 1964.
  * [17] J.-A.-N. Condorcet.  Essai sur l‘application de l‘analyse à la probabilité des décisions rendues à la pluralité des voix.  De l‘Imprimerie Royale, 1785.
  * [18] D. Cordero-Erausquin and M. Ledoux.  Hypercontractive measures, talagrand‘s inequality, and influences.  In Geometric Aspects of Functional Analysis, volume 2050 of Lecture Notes in Mathematics. 2012.
  * [19] J. Corneli, I. Corwin, S. Hurder, V. Sesum, Y. Xu, E. Adams, D. Davis, M. Lee, R. Visocchi, N. Hoffman, and R. Hardt.  Double bubbles in Gauss space and spheres.  Houston J. Math, 34(1):181–204, 2008.
  * [20] A. De, E. Mossel, and J. Neeman.  Majority is stablest : Discrete and sos.  In STOC (Symposium on Theory of Computing), pages 477–486, 2013\.
  * [21] A. De, E. Mossel, and J. Neeman.  Majority is stablest: Discrete and sos.  Theory of Computing, 12(4):1–50, 2016.
  * [22] I. Diakonikolas, D. M. Kane, and J. Nelson.  Bounded independence fools degree-2 threshold functions.  In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 11–20. IEEE, 2010.
  * [23] R. Eldan.  A two-sided estimate for the gaussian noise stability deficit.  Inventiones mathematicae, 201(2):561–624, 2015.
  * [24] P. Faliszewski and A. D. Procaccia.  Ai?s war on manipulation: Are we winning?  AI Magazine, 31(4):53–64, 2010.
  * [25] W. Feller.  An introduction to probability theory and its applications. Vol. I.  Third edition. John Wiley & Sons Inc., New York, 1968.
  * [26] Y. Filmus, N. Lifshitz, D. Minzer, and E. Mossel.  And testing and robust judgement aggregation.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 222–233, 2020.
  * [27] E. Friedgut and G. Kalai.  Every monotone graph property has a sharp threshold.  Proc. Amer. Math. Soc., 124:2993–3002, 1996.
  * [28] E. Friedgut, G. Kalai, N. Keller, and N. Nisan.  A quantitative version of the gibbard–satterthwaite theorem for three alternatives.  SIAM Journal on Computing, 40(3):934–952, 2011.
  * [29] E. Friedgut, G. Kalai, and A. Naor.  Boolean functions whose fourier transform is concentrated on the first two levels.  Advances in Applied Mathematics, 29(3):427–437, 2002.
  * [30] E. Friedgut, G. Kalai, and N. Nisan.  Elections can be manipulated often.  In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 243–249, 2009.
  * [31] A. Gelman, J. N. Katz, and F. Tuerlinckx.  The mathematics and statistics of voting power.  Statistical Science, pages 420–435, 2002.
  * [32] H. O. Georgii.  Gibbs measures and phase transitions, volume 9 of de Gruyter Studies in Mathematics.  Walter de Gruyter & Co., Berlin, 1988.
  * [33] A. Gibbard.  Manipulation of voting schemes: a general result.  Econometrica, 41(4):587—601, 1973.
  * [34] O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samorodnitsky.  Testing monotonicity.  Combinatorica, 20(3):301–337, 2000.
  * [35] E. Goles and J. Olivos.  Periodic behaviour of generalized threshold functions.  Discrete mathematics, 30(2):187–189, 1980.
  * [36] L. Gross.  Logarithmic Sobolev inequalities.  Amer. J. Math., 97(4):1061–1083, 1975.
  * [37] O. Häggström, G. Kalai, and E. Mossel.  A law of large numbers for weighted majority.  Advances in Applied Mathematics, 37(1):112–123, 2006.
  * [38] S. Heilman, E. Mossel, and J. Neeman.  Standard simplices and pluralities are not the most noise stable (abstract).  In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 255–255. ACM, 2015.
  * [39] S. Heilman and A. Tarter.  Three candidate plurality is stablest for small correlations.  arXiv preprint arXiv:2011.05583, 2020.
  * [40] M. Isaksson, G. Kindler, and E. Mossel.  The geometry of manipulation - a quantitative proof of the gibbard satterthwaite theorem.  In Foundations of Computer Science (FOCS), pages 319–328, 2010\.
  * [41] M. Isaksson, G. Kindler, and E. Mossel.  The geometry of manipulation - a quantitative proof of the gibbard satterthwaite theorem.  Combinatorica, 32(2):221–250, 2012.
  * [42] M. Isaksson and E. Mossel.  New maximally stable Gaussian partitions with discrete applications.  Israel Journal of Mathematics, 189:347–396, 2012.
  * [43] J. Jendrej, K. Oleszkiewicz, and J. O. Wojtaszczyk.  On some extensions of the fkn theorem.  Theory of Computing, 11(1):445–469, 2015.
  * [44] C. Jones.  A noisy-influence regularity lemma for boolean functions, 2016.  arXiv preprint arXiv:1610.06950.
  * [45] J. Kahn, G. Kalai, and N. Linial.  The influence of variables on boolean functions.  In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 68–80, 1988.
  * [46] G. Kalai.  A Fourier-theoretic perspective on the Condorcet paradox and Arrow‘s theorem.  Adv. in Appl. Math., 29(3):412–426, 2002.
  * [47] G. Kalai.  Social Indeterminacy.  Econometrica, 72:1565–1581, 2004.
  * [48] G. Kalai, N. Keller, and E. Mossel.  On the Correlation of Increasing Families.  Journal of Combinatorial Theory A, 144:250–276, 2016.
  * [49] G. Kalai and E. Mossel.  Sharp thresholds for monotone non boolean functions and social choice theory.  Mathematics of Operation Research, 40(4):915–925, 2015.
  * [50] N. Keller.  A tight quantitative version of arrow?s impossibility theorem.  2012\.
  * [51] S. Khot, G. Kindler, E. Mossel, and R. O‘Donnell.  Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?  SIAM J. Comput., 37:319–357, 2007.
  * [52] G. Kindler, N. Kirshner, and R. O?Donnell.  Gaussian noise sensitivity and fourier tails.  Israel Journal of Mathematics, 225(1):71–109, 2018.
  * [53] L. A. Kornhauser and L. G. Sager.  Unpacking the court.  Yale LJ, 96:82, 1986.
  * [54] M. Ledoux.  Remarks on gaussian noise stability, brascamp-lieb and slepian inequalities.  In Geometric aspects of functional analysis, pages 309–333. Springer, 2014.
  * [55] T. M. Liggett.  Interacting particle systems, volume 276 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, New York, 1985.
  * [56] J. H. Lindsey.  Assignment of numbers to vertices.  The American Mathematical Monthly, 71(5):508–516, 1964.
  * [57] C. List and P. Pettit.  Aggregating sets of judgments: An impossibility result.  Economics and Philosophy, 18(1):89–110, 2002.
  * [58] C. List and P. Pettit.  Aggregating sets of judgments: Two impossibility results compared.  Synthese, 140(1–2):207–235, 2004.
  * [59] G. A. Margulis.  Probabilistic characteristics of graphs with large connectivity.  Problemy Peredav ci Informacii, 10(2):101–108, 1974.
  * [60] P. R. Milgrom and R. J. Weber.  A theory of auctions and competitive bidding.  Econometrica: Journal of the Econometric Society, pages 1089–1122, 1982.
  * [61] E. Milman and J. Neeman.  The Gaussian double-bubble conjecture.  arXiv preprint arXiv:1801.09296, 2018.
  * [62] E. Milman and J. Neeman.  The Gaussian multi-bubble conjecture.  arXiv preprint arXiv:1805.10961, 2018.
  * [63] E. Mossel.  Recursive reconstruction on periodic trees.  Random Structures Algorithms, 13(1):81–97, 1998.