NOISE STABILITY OF RANKED CHOICE VOTING

STEVEN HEILMAN

Abstract. We conjecture that Borda count is the ranked choice voting method that best preserves the outcome of an election with randomly corrupted votes, among all fair voting methods with small influences satisfying the Condorcet Loser Criterion. This conjecture is an adaptation of the Plurality is Stablest Conjecture to the setting of ranked choice voting. Since the plurality function does not satisfy the Condorcet Loser Criterion, our new conjecture is not directly related to the Plurality is Stablest Conjecture. Nevertheless, we show that the Plurality is Stablest Conjecture implies our new Borda count is Stablest conjecture. We therefore deduce that Borda count is stablest for elections with three candidates when the corrupted votes are nearly uncorrelated with the original votes. We also adapt a dimension reduction argument to this setting, showing that the optimal ranked choice voting method is “low-dimensional.”

The Condorcet Loser Criterion asserts that a candidate must lose an election if each other candidate is preferred in head-to-head comparisons. Lastly, we discuss a variant of our conjecture with the Condorcet Winner Criterion as a constraint instead of the Condorcet Loser Criterion. In this case, we have no guess for the most stable ranked choice voting method.

Contents

1. Introduction  1
2. Majority is Stablest  6
3. Plurality is Stablest Conjecture  8
4. Ranked Choice Voting  10
5. Plurality is Stablest Implies Borda count is Stablest  12
6. Other Variants of the Borda count is Stablest Conjecture  14
References  15

1. Introduction

A basic question in social choice theory is: what is the best voting method? In this paper, a voting method is a function f whose input is a set of n votes and whose output is the winner of the election. There are many possible descriptions of a “best” voting method. For example, Rousseau suggested in the 1700s that the best two-candidate voting method maximizes the number of votes that agree with the election’s outcome [Rou62]. In this sense, the majority function is the best voting method [O’D14, Theorem 2.33], at least for an add

Date: September 22, 2022. Key words and phrases. social choice theory, noise stability, Borda count, ranked choice voting. S. H. is Supported by NSF Grant CCF 1911216.

number of voters satisfying the impartial culture assumption (that voters’ preferences are independent and uniformly random).

Through the years, various other notions of “best” voting method have been studied, e.g. by game theorists such as Shapley, Shubik and Banzhaf in the 1950s and 1960s [SS54, Ban65]. Statements such as Arrow’s Impossibility Theorem [Arr50, ASS02, ASS11] imply there is no “best” voting method, since no voting method satisfies a short list of reasonable assumptions. In the last few decades, computational aspects of social choice theory have been investigated (such as the complexity of computing the winner of an election or of finding voting strategies) [BCE^{+}16]. However, this article does not consider that topic. Contemporaneously, discrete Fourier analysis methods have been incorporated into social choice theory, sometimes motivated by applications in computational complexity [KKL88, Kal02, MOO10, Mos12].

One recent highlight in the latter theory is the Majority is Stablest Theorem [MOO10].

Theorem 1.1 (Majority is Stablest, Informal Version, [MOO10, Theorem 4.4]). Suppose we run an election with a large number n of voters and two candidates. In this election, we make the following assumptions:

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

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

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

We say an election method is balanced if each candidate has an equal chance of winning the election.

We say that votes are corrupted independently with probability 0 < ε < 1 if, for any given vote, with probability 1 − ε that vote remains the same, and with probability ε that vote is set to be equally likely to be any of the candidates, independently of all other votes and all other corruptions.

Since the majority function is optimal in the sense of Theorem 1.1, we say the majority function is the most stable or the most noise stable balanced voting method, among low influence functions.

To see a more general version of Theorem 1.1 with the balanced assumption changed, see [MOO10, Theorem 4.4]. If the small influence assumption is removed in Theorem 1.1, then it is a standard exercise to show that dictator functions are the most stable voting methods. So, in order to have majority be the most stable voting method, Theorem 1.1 requires an assumption on small influences. Note also that anti-majority (where the majority preferred candidate loses) also has the same probability of preserving the outcome as the majority function itself, so the term “Majority is Stablest” is a bit deceiving.

The original motivation for Theorem 2.5 was proving sharp computational hardness for approximation algorithms for MAX-CUT. Theorem 2.5 implies that the Goemans-Williamson semidefinite program [GW95] has an optimal quality of approximation for the MAX-CUT problem among all polynomial time algorithms, assuming the Unique Games Conjecture is true [KKMO07, KMS18].

The analogue of Theorem 1.1 for 3 or more candidates is still an open problem, known as the Plurality is Stablest Conjecture, though some cases of the conjecture have been proven [HT21]. In the current setting, each voter votes for exactly one candidate.

Conjecture 1.2 (Plurality is Stablest, Informal, [KKMO07, IM12]). Suppose we run an election with a large number n of voters and k ≥ 3 candidates. In this election, we make the following assumptions:

(i) Voters cast their votes randomly, independently, with equal probability of voting for each candidate.

(ii) Each voter has a small influence on the outcome of the election. Then, among all balanced voting methods, the plurality function best preserves the outcome of the election when votes have been corrupted independently.

As before, we say an election method is balanced if each candidate has an equal chance of winning the election.

In fact, the main result of [HT21] shows that the balanced voting method that best preserves the outcome of an election between k ≥ 3 candidates is “low-dimensional,” in that it is a function of at most k − 1 linear functions of the votes.

Theorem 1.3 (Plurality is Stablest, Weak Form, Informal, [HT21]). Let k ≥ 2. Under the assumptions of Conjecture 1.2, if we denote the votes of the candidates as x = (x_{1}, …, x_{n}) ∈ {1, …, k}^{n}, then the most stable balanced voting method g: {1, …, k}^{n} → {1, …, k} satisfies: ∀ 1 ≤ i ≤ k, ∃ w^{(i,1)}, …, w^{(i,k−1)} ∈ ℝ^{n} and ∃ h_{i}: ℝ^{k−1} → ℝ such that

1_{{g(x)=i}} = h_{i}(⟨x, w^{(i,1)}⟩, …, ⟨x, w^{(i,k−1)}⟩), ∀ x ∈ {1, …, k}^{n}.

In fact, the conclusion of Theorem 1.3 also holds with an unbalanced assumption on the voting method.

In particular, when k = 2, Theorem 1.3 gives a weakened form of the Majority is Stablest Theorem, stating that the most stable balanced voting method is a function of the form

h(⟨x, y^{(1)}⟩), ∀ x ∈ {−1, 1}^{n}.

The Majority is Stablest Theorem [MOO10] says we can choose h := sign and y^{(1)} := (1, …, 1) when k = 2. On the other hand, Theorem 1.3 applies for all k ≥ 2, whereas the original proof of the Majority is Stablest Theorem [MOO10] does not seem to apply except when k = 2.

Theorem 1.3 stated here is a discretization of Theorem 3.6 below from [HT21]. Note also that, without the balanced assumption, the Plurality is Stablest Conjecture is false [HMN16]. However, an optimal unbalanced voting method is still low-dimensional [HT21]. For a more thorough survey of these and related topics, see e.g. [Hei21].

As in Theorem 1.1, the Plurality is Stablest Conjecture asserts that the plurality voting method is the voting method that best preserves an election’s outcome among all “democratic” voting methods. This conjecture for k ≥ 3 candidates is closely related to sharp computational hardness results for the MAX-k-CUT problem [IM12]. So, from the perspective of computational complexity, plurality voting is well motivated.

However, from the perspective of social choice theory, the plurality voting method has many undesirable properties. It would be better to adapt Theorem 1.1 to the setting of ranked choice voting. Ranked choice voting allows voters a list of preferences rather than a single vote. Yet, even formulating a conjectural version of Theorem 1.1 for three or more candidates seemed difficult, since certain natural generalizations will just reduce to the Plurality is Stablest Conjecture itself. (A priori, it is possible that the most stable ranked-choice voting method simply ignores rankings other than the most preferred candidate.) So, it is natural to impose an additional constraint on the voting methods to ensure they “actually incorporate” all rankings of voters. We find the most natural such constraint is the Condorcet Loser Criterion. Here a technical difficulty arises since some constraints are not as natural when voters act independently and uniformly at random. (For example, with a large number n of voters, some imposed constraint might occur with probability tending to zero as n → ∞. In such a case, that constraint does not really affect the optimal voting methods under consideration, as n → ∞.)

With these issues in mind, our first result is a formulation of a ranked choice analogue of the Plurality is Stablest Conjecture.

Conjecture 1.4 (Borda count is Stablest, Informal Version). Suppose we run a ranked choice election with a large number n of voters and k ≥ 3 candidates. In this election, we make the following assumptions:

(i) Voters cast their ranked votes randomly, independently, with equal probability of providing any given ranking of candidates.

(ii) Each voter has a small influence on the outcome of the election.

We also assume that the voting method is balanced (each candidate has an equal chance of winning the election) and satisfies the Condorcet Loser Criterion (CLC), so that a Condorcet loser can never win the election (see Definition 4.1).

Then the Borda count voting method is the balanced voting method satisfying CLC that best preserves the outcome of the election, when votes have been corrupted independently.

We say that votes are corrupted independently with probability 0 < ε < 1 if, for any given person’s vote, with probability 1 − ε that vote remains the same, and with probability ε that vote is set to be uniformly random among all possible rankings of candidates, independently of all other votes and all other corruptions.

In the ranked choice setting, there are a few different natural ways to corrupt votes. In our formulation, we consider a corruption as a resampling among all possible rankings of voters. Another natural alternative involves swapping the rankings of two uniformly chosen (distinct) candidates. The invariance principle [MOO10] implies that these notions of vote corruption lead to equivalent versions of Conjecture 1.4, up to changing the corruption probability ε.

As mentioned above, Conjecture 1.4 is an adaptation of the Plurality is Stablest Conjecture to the setting of ranked choice voting. An exercise shows: if we remove the CLC constraint in Conjecture 1.4, then the optimal voting method becomes the plurality function itself. So, some extra constraint is needed in order to get a “truly” ranked choice voting analogue of the Plurality is Stablest Conjecture.

Although Conjecture 1.4 is not directly related to Conjecture 1.2, our first result shows that Conjecture 1.2 implies Conjecture 1.4.

Theorem 1.5 (Plurality is Stablest Implies Borda count is Stablest). Assume that Conjecture 1.2 holds for some probability of corruption 0 < ε < 1. Then Conjecture 1.4 holds with a probability of corruption ε.

By identifying the set of k! rankings of k candidates with the set {1, …, k!}, we can adapt the main dimension reduction result of [HT21] to Conjecture 1.4. That is, we can show the most stable ranked choice voting method between k ≥ 3 candidates in Conjecture 1.4 is “low-dimensional,” in that it is a function of at most k! + k − 1 linear functions of the votes.

Theorem 1.6 (Borda count is Stablest, Weak Form, Informal). Let k ≥ 3. Under the assumptions of Conjecture 1.4, if we denote the votes of the candidates as x = (x_{1}, …, x_{n}) ∈ {1, …, k!}^{n}, then the most stable balanced voting method g: {1, …, k!}^{n} → {1, …, k} that satisfies CLC must satisfy: ∀ 1 ≤ i ≤ k, ∃ w^{(i,1)}, …, w^{(i,k!+k−1)} ∈ ℝ^{n} and ∃ h_{i}: ℝ^{k!+k−1} → ℝ such that

1_{{g(x)=i}} = h_{i}(⟨x, w^{(i,1)}⟩, …, ⟨x, y^{(i,k!+k−1)}⟩), ∀ x ∈ {1, …, k!}^{n}.

Theorem 1.6 is a discretized version of a more formal statement, presented in Theorem 4.6 below. That is, Theorem 1.6 follows by applying the invariance principle [MOO10] to Theorem 4.6.

In some sense, the majority function is the simplest voting method for two candidates where each voter has a small influence on the election’s outcome. The Majority if Stablest Theorem reinforces this fact: if a voting method has a complicated description, corresponding e.g. to various inequalities holding or not holding, then there are more opportunities for random vote corruption to change the election’s outcome. Likewise, the plurality function is arguably one of the simplest voting methods for three or more candidates, and the Plurality is Stablest Conjecture reflects this fact. So, using a posteriori reasoning, it is perhaps unsurprising that the Borda count method could be the most stable ranked choice voting method among voting functions satisfying the Condorcet Loser Criterion. Complicated voting methods depending on various conditions or inequalities holding lead to more opportunities for random vote corruptions to change an election’s outcome.

In summary, it is perhaps not surprising that finding the most stable voting method should correspond to finding voting methods with very simple descriptions.

Before formulating Conjecture 1.4, it seemed reasonable that Instant Runoff Voting should be the stablest ranked choice voting method satisfying CLC. Computer simulations suggest otherwise. Using again our a posteriori reasoning, the Borda count method has an arguably simpler description than Instant Runoff Voting, so perhaps Borda’s superior stability is then less surprising. After all, Borda count can be viewed as taking the plurality of pairwise comparisons. Then Conjecture 1.4 might even be loosely equivalent to the original Plurality is Stablest Conjecture.

Vote Corruption Probability .01 .02 .03 .05 .1

Majority  .045 .064 .078 .101 .144
Plurality  .066 .095 .118 .149 .209
Borda  .066 .096 .119 .150 .214

Kemeny Young .071 .098 .121 .154 .215

IRV  .078 .106 .127 .162 .225
Ranked Pairs  .096 .126 .151 .185 .243
Copeland  .117 .139 .158 .188 .243

Estimated Probabilities that an Election’s Outcome is Changed for Various Voting Methods, 3 Candidates (Majority Provided for Reference)

Vote Corruption Probability .01 .02 .03 .05 .1

Majority  .045 .064 .078 .101 .144
Plurality  .078 .115 .135 .177 .251
Borda  .084 .111 .137 .177 .255

Kemeny Young .091 .126 .145 .193 .273

IRV  .103 .144 .173 .220 .295
Copeland  .159 .185 .205 .240 .312

Estimated Probabilities that an Election’s Outcome is Changed for Various Voting Methods, 4 Candidates (Majority Provided for Reference)

1.1. Related Work. This work concerns the probability of an election method preserving its outcome, subject to corruption, as in [KKMO07, MOO10, IM12]. Some related but different works address the probabilities of violating voting axioms such as [Mos12, MR15] or [Xia20, FHP22].

2. Majority is Stablest

A function f: {−1, 1}^{n} → {−1, 1} is a voting method with n voters and two candidates. For any x = (x_{1}, …, x_{n}) ∈ {−1, 1}^{n}, we think of x_{i} as the vote of person 1 ≤ i ≤ n for candidate x_{i} ∈ {−1, 1}. Given the votes x, the winner of the election is f(x).

Definition 2.1 (Majority Function). Let n > 1 be an integer. Define the majority function Maj_{n}: {−1, 1}^{n} → {−1, 1} to be

Maj_{n}(x) := sign(x_{1} + ⋯ + x_{n}), ∀ x = (x_{1}, …, x_{n}) ∈ {−1, 1}^{n}.

(We define the sign of 0 to be 1, though this definition will not matter in the statements below such as Theorem 2.5.)

Definition 2.2 (Noise Stability). Let 0 ≤ ρ ≤ 1. Let X = (X_{1}, …, X_{n}) ∈ {−1, 1}^{n} be a uniformly distributed random variable in {−1, 1}^{n}. Let Y = (Y_{1}, …, Y_{n}) ∈ {−1, 1}^{n} be a random variable such that Y_{1}, …, Y_{n} are independent, and for each 1 ≤ i ≤ n, Y_{i} = X_{i} with probability ρ, and with probability 1−ρ, Y_{i} ∈ {−1, 1} is uniformly random and independent of X_{1}, …, X_{n}. We define the noise stability of f: {−1, 1} → ℝ with correlation ρ to be

S_{ρ}(f) := 𝔼_{ρ}f(X)f(Y).

Note that 𝔼_{ρ}X_{i}Y_{i} = ρ and Y_{i} = X_{i} with probability (1 + ρ)/2 for each 1 ≤ i ≤ n. Also, in the case that f: {−1, 1}^{n} → {−1, 1}, we have

(1 + S_{ρ}f)/2 = ℙ_{ρ}(f(X) = f(Y)).

It is a standard exercise to deduce from the Central Limit Theorem that

lim_{n→∞} S_{ρ}(Maj_{n}) = \frac{2}{π} sin^{−1}(ρ), ∀ ρ ∈ [0, 1].

Definition 2.3 (Influence). Let f: {−1, 1}^{n} → ℝ. Fix 1 ≤ i ≤ n. Denote D_{i}f(x) := [f(x) − f(x_{1}, …, x_{i−1}, −x_{i}, x_{i+1}, …, x_{n})]/2 for all x ∈ {−1, 1}^{n}. Define the influence of the i^{th} variable on f to be

Inf_{i}(f) = ⟨D_{i}f, D_{i}f⟩ = 2^{−n} ∑_{x∈{−1,1}^{n}}(D_{i}f(x))^{2}.

That is, Inf_{i}(f) is the squared L_{2} norm of the i^{th} partial derivative of f.

In the case f: {−1, 1}^{n} → {−1, 1}, note that D_{i}f ∈ {−1, 0, 1}. So, if X_{1}, …, X_{n} are i.i.d. uniform in {−1, 1}, we have

Inf_{i}(f) = ℙ(f(X) ≠ f(X_{1}, …, X_{i−1}, −X_{i}, X_{i+1}, …, X_{n})), ∀ 1 ≤ i ≤ n.

Remark 2.4. For any 1 ≤ i ≤ n, we have Var_{X_{i}}f := 𝔼_{X_{i}}(f − 𝔼_{X_{i}}f)^{2}, so since f = ∑_{S⊆{1,...,n}}⟨f, W_{S}⟩W_{S}, where W_{S}(x) := ∏_{i∈S} x_{i} for all S ⊆ {1, …, n}, and D_{i}W_{S} = 0 if i ∉ S and D_{i}W_{S} = W_{S} if i ∈ S, we get

Inf_{i}(f) = 𝔼Var_{X_{i}}f, ∀ 1 ≤ i ≤ n.

The following Theorem was conjectured in [KKMO07] and proven in [MOO10].

Theorem 2.5 (Majority is Stablest, [MOO10]). Let 0 ≤ ρ ≤ 1 and let 0 < ε < 1. Then there exists a τ > 0 such that the following holds, for all integers n ≥ 1. If f: {−1, 1}^{n} → [−1, 1] satisfies 𝔼f = 0 and max_{1≤i≤n} Inf_{i}(f) ≤ τ, then

S_{ρ}(f) ≤ lim_{n→∞} S_{ρ}(Maj_{n}) + ε = \frac{2}{π} sin^{−1}(ρ) + ε.

Theorem 2.5 was deduced in [MOO10] as a corollary of an invariance principle [MOO10, Theorem 2.1], which can be understood as a nonlinear generalization of the Central Limit Theorem.

The invariance principle of [MOO10, Theorem 2.1] shows that the distribution of a multilinear polynomial Q with small influences is almost the same when Q has {−1 − 1} inputs or Gaussian inputs. A similar statement holds for the noise stability of a function itself, rather than its distribution [MOO10, Theorem 3.20].

Then maximizing the noise stability of functions f: {−1, 1}^{n} → [−1, 1] in Theorem 2.5 reduces to maximizing the noise stability of multilinear polynomials that are functions of i.i.d. Gaussian random variables. That is, [MOO10, Theorem 3.20] implies the equivalence between an optimization over discrete functions, versus an optimization over functions on a continuous (real) domain.

Fortunately, the corresponding continuous problem was solved decades earlier, Theorem 2.7 below.

2.1. Borell’s Inequality. We define the Gaussian density as

\begin{aligned}γ_{n}(x) & := (2π)^{−n/2}e^{−∥x∥^{2}/2},  ⟨x, y⟩ := ∑_{i=1}^{n} x_{i}y_{i},  ∥x∥^{2} := ⟨x, x⟩, \\ & ∀ x = (x_{1}, …, x_{n}), y = (y_{1}, …, y_{n}) ∈ ℝ^{n}. \end{aligned}  (1)

Let f: ℝ^{n} → [0, 1] be measurable and let ρ ∈ (−1, 1). Define the Ornstein-Uhlenbeck operator with correlation ρ applied to f by

\begin{aligned}T_{ρ}f(x) & := ∫_{ℝ^{n}} f(xρ + y\sqrt{1 − ρ^{2}})γ_{n}(y) dy \\ & = (1 − ρ^{2})^{−n/2}(2π)^{−(n)/2} ∫_{ℝ^{n}} f(y)e^{− \frac{∥y−ρx∥^{2}}{2(1−ρ^{2})}} dy,  ∀x ∈ ℝ^{n}. \end{aligned}  (2)

Definition 2.6 (Noise Stability). Let Ω ⊆ ℝ^{n} be measurable. Let ρ ∈ (−1, 1). We define the noise stability of the set Ω with correlation ρ to be

S_{ρ}(Ω) := ∫_{ℝ^{n}} 1_{Ω}(x)T_{ρ}1_{Ω}(x)γ_{n}(x) dx =^{(2)} (2π)^{−n}(1 − ρ^{2})^{−n/2} ∫_{Ω} ∫_{Ω} e^{\frac{−∥x∥^{2}−∥y∥^{2}+2ρ⟨x,y⟩}{2(1−ρ^{2})}} dxdy.

Equivalently, if X = (X_{1}, …, X_{n}), Y = (Y_{1}, …, Y_{n}) ∈ ℝ^{n} are n-dimensional jointly Gaussian distributed random vectors with 𝔼X_{i}Y_{j} = ρ · 1_{(i=j)} for all i, j ∈ {1, …, n}, then

S_{ρ}(Ω) = ℙ((X, Y) ∈ Ω × Ω).

The following theorem is the continuous version of the Majority is Stablest Theorem 2.5.

Theorem 2.7 (Borell’s Inequality, [Bor75]). Let Ω ⊆ ℝ^{n} be measurable. Let H ⊆ ℝ^{n} be a half space (a set of points on one side of a hyperplane) such that γ_{n}(Ω) = γ_{n}(H). Then

S_{ρ}(Ω) ≤ S_{ρ}(H).

2.2. Sketch of the Proof of Majority is Stablest. It is more convenient to consider functions taking values in [0, 1]. Fix μ ∈ (0, 1). To obtain an analogous statement for functions f: {−1, 1}^{n} → [−1, 1] with 𝔼f = 0, just consider (1+f)/2 and apply the argument below with μ = 1/2.

The invariance principle [MOO10, Theorem 3.20] implies that the f: {−1, 1}^{n} → [0, 1] with 𝔼f = μ with largest noise stability S_{ρ}f is approximately the same as taking Ω ⊆ ℝ^{n} with γ_{n}(Ω) = μ with the largest noise stability S_{ρ}(Ω). By Theorem 2.7, the largest such set is a half space H. Using [MOO10, Theorem 3.20] again, S_{ρ}(H) is approximately the same as S_{ρ}g where g is a (discrete) half space of the form g(x) = 1_{x_{1}+···+x_{n}>t}, for some t ∈ ℝ, for all x = (x_{1}, …, x_{n}) ∈ {−1, 1}^{n}.

To recover Theorem 2.5, note that 2 · 1_{x_{1}+···+x_{n}>0} − 1 = sign(x_{1} + ⋯ + x_{n}). For a full proof of a more general statement, see [MOO10, Theorem 4.4]. See also Chapter 11 of [O’D14].

3. Plurality is Stablest Conjecture

We now generalize our discussion from voting methods with two candidates to voting methods with three or more candidates.

Let k ≥ 2 be an integer and define the k-simplex to be

Δ_{k} := {(y_{1}, …, y_{k}) ∈ ℝ^{k}: y_{1} + ⋯ + y_{k} = 1, y_{i} ≥ 0, ∀ 1 ≤ i ≤ k}.

For any 1 ≤ i ≤ k, let e_{i} ∈ ℝ^{k} be the vector with a 1 in its i^{th} entry and zeros in the other entries.

A function f: {1, …, k}^{n} → {e_{1}, …, e_{k}} is a voting method with n voters and k candidates. (We associate e_{i} to candidate i, for each 1 ≤ i ≤ k.) For any x = (x_{1}, …, x_{n}) ∈ {1, …, k}^{n}, we think of x_{i} as the vote of person 1 ≤ i ≤ n for candidate x_{i} ∈ {1, …, k}. Given the votes x, the winner of the election is f(x).

In this section, we denote ⟨·, ·⟩ as the standard inner product on ℝ^{k}. We denote f_{i} := ⟨f, e_{i}⟩. A function f: {1, …, k}^{n} → Δ_{k} can be also be considered a (random) voting method, so that f_{i}(x) is the probability that e_{i} is elected, for each 1 ≤ i ≤ k, given votes x.

Definition 3.1. For any x ∈ ℤ^{n}, we denote ∥x∥_{0} as the number of nonzero coordinates of x. The noise stability of g: {1, …, k}^{n} → ℝ with parameter ρ ∈ (−1, 1) is

S_{ρ}g := k^{−n} ∑_{x∈{1,...,k}^{n}} g(x)𝔼_{ρ}g(Y)

= k^{−n} ∑_{x∈\{1,...,k\}^{n}} g(x) ∑_{y∈\{1,...,k\}^{n}} (\frac{1 − (k − 1)ρ}{m})^{n−∥y−x∥_{0}} (\frac{1 − ρ}{m})^{∥y−x∥^{0}} g(y).

Equivalently, conditional on X, 𝔼_{ρ}g(Y) is defined so that for all 1 ≤ i ≤ n, Y_{i} = X_{i} with probability \frac{1+(k−1)ρ}{k}, and Y_{i} is equal to any of the other (k − 1) elements of \{1, …, k\} each with probability \frac{1−ρ}{k}, and so that Y_{1}, …, Y_{n} are independent.

The noise stability of f: {1, …, k}^{n} → Δ_{k} with parameter ρ ∈ (−1, 1) is

S_{ρ}f := ∑_{i=1}^{k} S_{ρ}f_{i} = 𝔼_{ρ}⟨f(X), f(Y)⟩.

When f: {1, …, k}^{n} → {e_{1}, …, e_{k}}, we have

S_{ρ}f = ℙ_{ρ}(f(X) = f(Y)).

Define the plurality function Plur_{k,n}: {1, …, k}^{n} → Δ_{k} for k candidates and n voters such that for all x ∈ {1, …, k}^{n}.

Plur_{k,n}(x) := \begin{cases}e_{j} & , if |\{i ∈ \{1, …, k\}: x_{i} = j\}| > |\{i ∈ \{1, …, k\}: x_{i} = r\}| , \\ & ∀ r ∈ \{1, …, k\} \ \{j\} \\ \frac{1}{k} ∑_{i=1}^{k} e_{i} & , otherwise. \end{cases}

Example 3.2. When k = 2, the Definition 3.1 says Y_{i} = X_{i} with probability (1 + ρ)/2, and Y_{i} ≠ X_{i} with probability (1 − ρ)/2, agreeing with Definition 2.2 (though the values that X_{i}, Y_{i} take are different in these two definitions). Also, under our new definition of noise stability we have S_{ρ}f = ℙ_{ρ}(f(X) = f(Y)), so that lim_{n→∞} S_{ρ}Maj_{n} = [1 + (2/π) sin^{−1} ρ]/2.

Let X_{1}, …, X_{n} be i.i.d. uniform in {1, …, k}. Recalling Remark 2.4, we define the influence of voter 1 ≤ i ≤ n on g: {1, …, k}^{n} → ℝ to be

Inf_{i}(g) = 𝔼Var_{X_{i}}g.  (3)

Conjecture 3.3 (Plurality is Stablest Conjecture). For any k ≥ 2, ρ ∈ [0, 1], ε > 0, there exists τ > 0 such that, for all n ≥ 1, if f: {1, …, k}^{n} → Δ_{k} satisfies Inf_{i}(f_{j}) ≤ τ for all 1 ≤ i ≤ n and for all 1 ≤ j ≤ k, and if 𝔼f = \frac{1}{k} ∑_{i=1}^{k} e_{i}, then

S_{ρ}f ≤ lim_{n→∞} S_{ρ}Plur_{k,n} + ε.

Analogues of the invariance principles [MOO10, Theorem 2.1,Theorem 3.20] apply in this more general setting. See [IM12, Theorem 3.3, 3.4,3.6]. These invariance principles imply that Conjecture 3.3 is equivalent to Conjecture 3.5 stated below.

Problem 3.4 (Standard Simplex Problem, [IM12]). Let k ≥ 3. Fix ρ ∈ (0, 1). Find measurable sets Ω_{1}, … Ω_{k} ⊆ ℝ^{n} with ∪_{i=1}^{k}Ω_{i} = ℝ^{n} and γ_{n}(Ω_{i}) = 1/k for all 1 ≤ i ≤ k that maximize

∑_{i=1}^{k} ∫_{ℝ^{n}} 1_{Ω_{i}}(x)T_{ρ}1_{Ω_{i}}(x)γ_{n}(x) dx,

subject to the above constraints.

Conjecture 3.5 (Standard Simplex Conjecture [IM12]). Let Ω_{1}, … Ω_{k} ⊆ ℝ^{n} maximize Problem 3.4. Assume that k − 1 ≤ n. Fix ρ ∈ (0, 1). Let z^{(1)}, …, z^{(k)} ∈ ℝ^{n} be the vertices of a regular simplex in ℝ^{n} centered at the origin. Then for all 1 ≤ i ≤ m,

Ω_{i} = {x ∈ ℝ^{n}: ⟨x, z^{(i)}⟩ = max_{1≤j≤k}⟨x, z^{(j)}⟩}.  (4)

At present, the only general result for Conjecture 3.5 is that the optimal sets Ω_{1}, …, Ω_{k} are low-dimensional, in the following sense.

Theorem 3.6 (Dimension Reduction, [HT21]). Let Ω_{1}, … Ω_{k} ⊆ ℝ^{n} maximize Problem 3.4. Assume that k − 1 ≤ n. Fix ρ ∈ (0, 1). Then, after rotating Ω_{1}, …, Ω_{k} if necessary, there exist measurable sets Ω′_{1}, …, Ω′_{k} ⊆ ℝ^{k−1} such that

Ω_{i} = Ω′_{i} × ℝ^{n−k+1}, ∀ 1 ≤ i ≤ k.

Corollary 3.7 ([HT21]). Let k = 3. Then there exists ρ_{0} > 0 such that Conjecture 3.5 is true for all 0 < ρ < ρ_{0}.

4. Ranked Choice Voting

Let k be a positive integer. Let {e_{1}, …, e_{k}} denote the standard basis of ℝ^{k} so that e_{i} has a 1 in the i^{th} entry and zeros in other entries, for all 1 ≤ i ≤ k. Let S_{k} denote the set of permutations on k elements. That is, S_{k} is an ordered list of the integers {1, …, k}. For example,

S_{3} = {(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)}.

A ranked choice voting method with n voters and k candidates is a function

f: S_{k}^{n} → {e_{1}, …, e_{k}} ⊆ ℝ^{k}.

Let x = (x_{1}, …, x_{n}) ∈ S_{k}^{n}. We think of x_{i} ∈ S_{n} as the vote of person 1 ≤ i ≤ n.

More generally, f: S_{k}^{n} → Δ_{k} is a (randomized) voting method where we interpret f(x) as a probability distribution on the winning candidates, given the votes x.

Identifying S_{k} with {1, …, k!} via any particular bijection, for any 1 ≤ i ≤ n we can define an influence Inf_{i}(f) as in (3).

The noise stability can also be defined as in the previous section, as

S_{ρ}f := ∑_{i=1}^{k} S_{ρ}f_{i} = 𝔼⟨f(X), f(Y)⟩.

Here X, Y are defined as in Definition 3.1.

When f: S_{k}^{n} → {e_{1}, …, e_{k}}, we have

S_{ρ}f = ℙ(f(X) = f(Y)).

Definition 4.1. A permutation π ∈ S_{k} is a function π: {1, …, k} → {1, …, k}. We interpret the permutation π as a vote, so that π(1) is the rank of candidate 1, π(2) is the rank of candidate 2, and so on. A candidate j ∈ {1, …, k} is a Condorcet loser for a set of votes x ∈ S_{k}^{n} if, for each ℓ ∈ {1, …, k} \ {j},

\frac{1}{n} |i ∈ \{1, …, n\}: x_{i}(ℓ) ≥ x_{i}(j)| > 1/2.

A function f: S_{k}^{n} → Δ_{k} satisfies the Condorcet Loser Criterion (CLC) if, for each x ∈ S_{k}^{n}, if j is a Condorcet loser for x, then f(x) ≠ j.

There is an analogous condition for functions g: ℝ^{n} → Δ_{k} with n ≥ k!. Suppose we have a bijection B: {1, …, k!} → S_{k}. For any 1 ≤ i < j ≤ k, let y^{(i,j)} ∈ ℝ^{n} be such that y_{ℓ}^{(i,j)} = 1 when B(ℓ)(i) > B(ℓ)(j) and y_{ℓ}^{(i,j)} = −1 when B(ℓ)(i) < B(ℓ)(j), for all 1 ≤ ℓ ≤ k!, and y_{ℓ}^{(i,j)} = 0 if ℓ > k!. (We also define y^{(i,j)} := −y^{(j,i)} if 1 ≤ j < i ≤ k.) Then g: ℝ^{n} → Δ_{k} satisfies the Condorcet Loser Criterion (CLC) if, for all 1 ≤ j ≤ k

{x ∈ ℝ^{n}: ⟨x, y^{(ℓ,j)}⟩ ≥ 0, ∀ ℓ ∈ {1, …, k} \ {j}} ∩ {x ∈ ℝ^{n}: g(x) = j} = ∅.

Similarly, a partition of ℝ^{n} into measurable subsets Ω_{1}, …, Ω_{k} satisfies the Condorcet Loser Criterion (CLC) if, for all 1 ≤ j ≤ k,

{x ∈ ℝ^{n}: ⟨x, y^{(ℓ,j)}⟩ ≥ 0, ∀ ℓ ∈ {1, …, k} \ {j}} ∩ Ω_{j} = ∅.

Definition 4.2. Define the Borda Count function Bor_{k,n}: S_{k}^{n} → Δ_{k} so that, for any x ∈ S_{k}^{n},

Bor_{k,n}(x) := \begin{cases}e_{j} & , if ∑_{i=1}^{n} x_{i}(j) > ∑_{i=1}^{n} x_{i}(r), ∀ r ∈ \{1, …, k\} \ \{j\} \\ \frac{1}{k} ∑_{i=1}^{k} e_{i} & , otherwise. \end{cases}

Observe that the Borda Count function is the plurality function applied to a vector of pairwise comparisons, i.e. if x ∈ S_{k}^{n}, we have a vector of pairwise comparisons (ω^{(1)}, …, ω^{(n)}) where ω^{ℓ} ∈ \{1, …, k\}^{\binom{k}{2}}, if for any 1 ≤ ℓ ≤ n, define ω_{\{i,j\}}^{(ℓ)} := j if x_{ℓ}(j) > x_{ℓ}(i) and ω_{\{i,j\}}^{(ℓ)} := i

if x_{ℓ}(j) < x_{ℓ}(i). Then ω := (ω^{(1)}, …, ω^{(n)}) ∈ (\{1, …, k\}^{\binom{k}{2}})^{n} = \{1, …, k\}^{n\binom{k}{2}}. Then

Bor_{k,n}(x) = Plur_{k,n\binom{k}{2}}(ω).

We then have the following adaptation of Conjecture 3.3 to the ranked-choice setting

Conjecture 4.3 (Borda Count is Stablest Conjecture). For any k ≥ 2, ρ ∈ [0, 1], ε > 0, there exists τ > 0 such that, for all n ≥ 1, if f: S_{k}^{n} → Δ_{k} satisfies Inf_{i}(f_{j}) ≤ τ for all 1 ≤ i ≤ n and for all 1 ≤ j ≤ k, if 𝔼f = \frac{1}{k} ∑_{i=1}^{k} e_{i}, and if f satisfies the Condorcet Loser Criterion, then

S_{ρ}f ≤ lim_{n→∞} S_{ρ}Bor_{k,n} + ε.

As shown below in (6) and (8), the noise stability of the Borda count function as the number of voters n goes to infinity is the same as the noise stability of the Plurality function as n → ∞. So, the continuous version of Conjecture 4.3 can be stated as follows.

Problem 4.4. Let ρ ∈ (0, 1). Let n ≥ k! + k − 1. Find a partition Ω_{1}, …, Ω_{n} ⊆ ℝ^{n} be a partition satisfying γ_{n}(Ω_{i}) = 1/k for all 1 ≤ i ≤ k that maximizes

∑_{i=1}^{k} S_{ρ}(Ω_{i})

subject to these constraints.

Conjecture 4.5 (Standard Simplex Conjecture for Ranked Choice Voting). Let ρ ∈ (0, 1). Let n ≥ k! + k − 1. Then the sets Ω_{1}, …, Ω_{n} ⊆ ℝ^{n} maximizing problem 4.4 are those defined in (4).

The main result of [HT21] can be adapted to Conjecture (4.5) as follows.

Theorem 4.6 (Dimension Reduction). Let ρ ∈ (0, 1). Let n ≥ k!+k−1. Let Ω_{1}, …, Ω_{k} ⊆ ℝ^{n} satisfy CLC and maximize Problem 4.4. Then, after rotating Ω_{1}, …, Ω_{k}, there exists Θ_{1}, …, Θ_{n} ⊆ ℝ^{k!+k−1} such that

Ω_{i} = Θ_{i} × ℝ^{n−[k!+k−1]}, ∀ 1 ≤ i ≤ k.

Proof. The argument is the same as that of [HT21], with the additional observation that, if v ∈ ℝ^{n} is perpendicular to the vectors y^{(i,j)} for all 1 ≤ i < j ≤ n, then the sets Ω_{1} + v, … Ω_{n} + v also satisfy CLC. □

5. Plurality is Stablest Implies Borda count is Stablest

Proof of Theorem 1.5. Let z^{(1)}, …, z^{(k)} be the vertices of a regular simplex centered at the origin of ℝ^{k−1} with ∥z^{(i)}∥ = 1 for all 1 ≤ i ≤ k and ⟨z^{(i)}, z^{(j)}⟩ = −1/(k − 1) for all 1 ≤ i < j ≤ k. Recall the elementary identities 1^{2} + ⋯ + k^{2} = k(k + 1)(2k + 1)/6, (1+⋯+k)^{2} = (k(k +1)/2)^{2}, and (1+⋯+k)^{2} −(1^{2} +⋯+k^{2}) = k(k +1)(k −1)(3k +2)/12. So, if π ∈ S_{k} is uniformly random, we have

𝔼[π(1)]^{2} = (k + 1)(2k + 1)/6, 𝔼π(1)π(2) = (k + 1)(3k + 2)/12.
𝔼[π(1)]^{2} − 𝔼π(1)π(2) = k(k + 1)/12.  (5)

So, using these identities and ∑_{i=1}^{k} z^{(i)} = 0, for any 1 ≤ ℓ ≤ k we have

𝔼( ∑_{i=1}^{k} π(i)z^{(i)})( ∑_{j=1}^{k} π(j)z^{(j)})^{T} z^{(ℓ)}

= 𝔼 ∑_{i=1}^{k} π(i)z^{(i)}(π(ℓ) − \frac{1}{k − 1} ∑_{j: j≠ℓ} π(j))

= z^{(ℓ)}𝔼[π(1)]^{2} + 𝔼π(1)π(2) ∑_{i: i≠ℓ} z^{(i)}

− \frac{1}{k − 1} ∑_{j: j≠ℓ} (𝔼[π(1)]^{2}z^{(j)} + 𝔼π(1)π(2) ∑_{i: i≠j} z^{(i)})

= z^{(ℓ)}(𝔼[π(1)]^{2} − 𝔼π(1)π(2)) − \frac{1}{k − 1} ∑_{j: j≠ℓ} z^{(j)}(𝔼[π(1)]^{2} − 𝔼π(1)π(2))

=^{(5)} \frac{k(k + 1)}{12}(z^{(ℓ)} − \frac{1}{k − 1} ∑_{j: j≠ℓ} z^{(j)}) = \frac{k(k + 1)}{12}z^{(ℓ)}(1 + \frac{1}{k − 1}) = \frac{k^{2}(k + 1)}{12(k − 1)}z^{(ℓ)}.

Therefore, denoting the identity matrix as I,

\frac{12(k − 1)}{k^{2}(k + 1)}𝔼( ∑_{i=1}^{k} π(i)z^{(i)})( ∑_{j=1}^{k} π(j)z^{(j)})^{T} = I.

Also, 𝔼 ∑_{i=1}^{k} π(i)z^{(i)} = 0, and if σ ∈ S_{k} is such that σ = π with probability 1 − ε, and with probability 0 < ε < 1, σ is a uniformly random element of S_{k} independent of π, then

𝔼( ∑_{i=1}^{k} π(i)z^{(i)})( ∑_{j=1}^{k} σ(j)z^{(j)})^{T} = (1 − ε)𝔼( ∑_{i=1}^{k} π(i)z^{(i)})( ∑_{j=1}^{k} π(j)z^{(j)})^{T} z^{(ℓ)}

= (1 − ε)\frac{k^{2}(k + 1)}{12(k − 1)}I.

For any x ∈ S_{k}^{n}, define

V (x) := \frac{2\sqrt{3}\sqrt{k − 1}}{k\sqrt{k + 1}} \frac{1}{\sqrt{n}} ∑_{j=1}^{n} ∑_{i=1}^{k} x_{j}(i)z^{(i)}.

If X ∈ S_{k}^{n} is uniform, and Y ∈ S_{k}^{n} satisfies Y_{1}, …, Y_{n} are independent, Y_{i} = X_{i} with probability 1 − ε and with probability ε, Y_{i} ∈ S_{k} is independent of X_{i} and uniformly random in S_{k}, then as n → ∞,

(V (X), V (Y))

converges in distribution to a Gaussian random vector (W, Z) where W, Z ∈ ℝ^{k} are Gaussian random variables with mean, they each have identity covariance matrices, and 𝔼W_{i}Z_{j} = (1 − ε)1_{{i=j}} for all 1 ≤ i, j ≤ k. Since also Bor_{k,n}(x) = j if and only if ⟨V (x), z^{(j)}⟩ = max_{1≤i≤k}⟨V (x), z^{(i)}⟩ if and only if V (x) ∈ Ω_{j} where Ω_{1}, …, Ω_{k} are defined in (4),

lim_{n→∞} S_{(1−ε)}Bor_{k,n} = ∑_{i=1}^{k} S_{(1−ε)}(Ω_{i}).  (6)

Similarly, we have [IM12, Lemma 7.3]

lim_{n→∞} S_{(1−ε)}Plur_{k,n} = ∑_{i=1}^{k} S_{(1−ε)}(Ω_{i}).  (7)

Together, (6) and (7) imply that

lim_{n→∞} S_{(1−ε)}Bor_{k,n} = lim_{n→∞} S_{(1−ε)}Plur_{k,n}.  (8)

Equation 8 concludes the proof, since if the Plurality is Stablest Conjecture holds (for k candidates), the plurality function itself is an upper bound for the noise stability of a ranked choice voting method for k candidates.

For completeness, we review the proof of (7). Modifying the calculation above, we have 𝔼z^{(π(1))} = 0, 𝔼z^{(π(1))}[z^{(π(1))}]^{T} = \frac{k}{k−1}I, 𝔼z^{(π(1))}[z^{(σ(1))}]^{T} = (1 − ε)\frac{k}{k−1}I, so

W (x) := \sqrt{\frac{k − 1}{k}} \frac{1}{\sqrt{n}} ∑_{j=1}^{n} z^{(π(1))}

satisfies (W (X), W (Y)) also converges in distribution as n → ∞ to a Gaussian random vector (W, Z) where W, Z ∈ ℝ^{k} are Gaussian random variables with mean, they each have identity covariance matrices, and 𝔼W_{i}Z_{j} = (1 − ε)1_{{i=j}} for all 1 ≤ i, j ≤ k. Finally, Plur_{k,n}(x) = j if and only if ⟨W (x), z^{(j)}⟩ = max_{1≤i≤k}⟨W (x), z^{(i)}⟩ if and only if W (x) ∈ Ω_{j} where Ω_{1}, …, Ω_{k} are defined in (4), so (7) holds. □

6. Other Variants of the Borda count is Stablest Conjecture

Remark 6.1. Under the assumption that voters rank candidate independently and uniformly at random, there are at least three natural restrictions to impose on ranked choice voting methods:

• Condorcet Loser Criterion

• Condorcet (Winner) Criterion

• Smith Criterion

Above, we considered maximizing the noise stability of ranked choice voting methods that satisfy the Condorcet Loser Criterion, and we conjectured that Borda count is the most noise stable “democratic” voting method. Below, we present an analogue if this conjecture where we instead restrict to voting methods satisfying the Condorcet (Winner) Criterion. Borda count does not satisfy this condition, and we do not have a guess for which voting method satisfying this criterion is the most noise stable.

6.1. Condorcet (Winner) Criterion. A permutation π ∈ S_{k} is a function π: {1, …, k} → {1, …, k}. We interpret the permutation π as a vote, so that π(1) is the rank of candidate 1, π(2) is the rank of candidate 2, and so on. A candidate j ∈ {1, …, k} is a Condorcet winner for a set of votes x ∈ S_{k}^{n} if, for each ℓ ∈ {1, …, k} \ {j},

\frac{1}{n} |i ∈ \{1, …, n\}: x_{i}(ℓ) ≤ x_{i}(j)| > 1/2.

A function f: S_{k}^{n} → Δ_{k} satisfies the Condorcet Winner Criterion (CWC) or simply the Condorcet Criterion if, for each x ∈ S_{k}^{n}, if j is a Condorcet winner for x, then f(x) = j.

There is an analogous condition for functions g: ℝ^{n} → Δ_{k} with n ≥ k!. Suppose we have a bijection B: {1, …, k!} → S_{k}. For any 1 ≤ i < j ≤ k, let y^{(i,j)} ∈ ℝ^{n} be such that y_{ℓ}^{(i,j)} = 1 when B(ℓ)(i) > B(ℓ)(j) and y_{ℓ}^{(i,j)} = −1 when B(ℓ)(i) < B(ℓ)(j), for all 1 ≤ ℓ ≤ k!, and let y_{ℓ}^{(i,j)} = 0 if ℓ > k!. (We also define y^{(i,j)} := −y^{(j,i)} if 1 ≤ j < i ≤ k.) Then g: ℝ^{n} → Δ_{k} satisfies the Condorcet Winner Criterion (CWC) if, for all 1 ≤ j ≤ k

{x ∈ ℝ^{n}: ⟨x, y^{(ℓ,j)}⟩ ≤ 0, ∀ ℓ ∈ {1, …, k} \ {j}} ⊆ {x ∈ ℝ^{n}: g(x) = j}.

Similarly, a partition of ℝ^{n} into subsets Ω_{1}, …, Ω_{k} satisfies the Condorcet Winner Criterion (CWC) if, for all 1 ≤ j ≤ k,

{x ∈ ℝ^{n}: ⟨x, y^{(ℓ,j)}⟩ ≤ 0, ∀ ℓ ∈ {1, …, k} \ {j}} ⊆ Ω_{j}.

Problem 6.2 (Stablest Ranked Choice Voting for CWC). Find a sequence of functions g = g_{k,n}: S_{k}^{n} → Δ_{k} satisfying CWC such that the following holds, where 𝔼g = \frac{1}{k} ∑_{i=1}^{k} e_{i} and Inf_{i}(g_{j}) ≤ τ for all 1 ≤ i ≤ n and for all 1 ≤ j ≤ k.

For any k ≥ 2, ρ ∈ [0, 1], ε > 0, there exists τ > 0 such that, for all n ≥ 1, if f: S_{k}^{n} → Δ_{k} satisfies Inf_{i}(f_{j}) ≤ τ for all 1 ≤ i ≤ n and for all 1 ≤ j ≤ k, if 𝔼f = \frac{1}{k} ∑_{i=1}^{k} e_{i}, and if f satisfies the Condorcet Winner Criterion, then

S_{ρ}f ≤ lim_{n→∞} S_{ρ}g_{k,n} + ε.

Acknowledgement. Thanks to Jake Freeman, Elchanan Mossel and Alex Tarter for helpful discussions.

References

[Arr50] Kenneth J Arrow, A difficulty in the concept of social welfare, The Journal of Political Economy (1950), 328–346.

[ASS02] Kenneth J. Arrow, Amartya K. Sen, and Kotaro Suzumura (eds.), Handbook of social choice and welfare. Vol. 1, Handbooks in Economics, vol. 19, Elsevier/North-Holland, Amsterdam, 2002. MR 3183780

[ASS11] Kenneth J. Arrow, Amartya Sen, and Kotaro Suzumura (eds.), Handbook of social choice and welfare. Vol. 2, Handbooks in Economics, Elsevier/North-Holland, Amsterdam, 2011. MR 3183781

[Ban65] John F. Banzhaf, Weighted Voting Doesn’t Work: A Mathematical Analysis, Rutgers Law Rev. 19 (1965), 317–343.

[BCE^{+}16] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia (eds.), Hand-

book of computational social choice, Cambridge University Press, New York, 2016. MR 3587842

[Bor75] Christer Borell, The Brunn-Minkowski inequality in Gauss space, Invent. Math. 30 (1975), no. 2, 207–216. MR 0399402 (53 #3246)

[FHP22] Bailey Flanigan, Daniel Halpern, and Alexandros Psomas, Smoothed analysis of social choice revisited, Preprint, arXiv:2206.14684, 2022.

[GW95] Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228 (97g:90108)

[Hei21] Steven Heilman, Designing stable elections, Notices Amer. Math. Soc. 68 (2021), no. 4, 516–527. MR 4228125

[HMN16] Steven Heilman, Elchanan Mossel, and Joe Neeman, Standard simplices and pluralities are not the most noise stable, Israel Journal of Mathematics 213 (2016), no. 1, 33–53.

[HT21] Steven Heilman and Alex Tarter, Three candidate plurality is stablest for small correlations, Forum of Mathematics, Sigma 9 (2021), e65.

[IM12] Marcus Isaksson and Elchanan Mossel, Maximally stable Gaussian partitions with discrete applications, Israel J. Math. 189 (2012), 347–396. MR 2931402

[Kal02] Gil Kalai, A fourier-theoretic perspective on the condorcet paradox and arrow’s theorem, Advances in Applied Mathematics 29 (2002), no. 3, 412 – 426.

[KKL88] Jeff Kahn, Gil Kalai, and Nathan Linial, The influence of variables on boolean functions, Proc. of 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 68–80.

[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM J. Comput. 37 (2007), no. 1, 319–357. MR 2306295 (2008d:68035)

[KMS18] Subhash Khot, Dor Minzer, and Muli Safra, Pseudorandom sets in grassmann graph have nearperfect expansion, Electronic Colloquium on Computational Complexity (ECCC) 25 (2018), 6.

[MOO10] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Ann. of Math. (2) 171 (2010), no. 1, 295–341. MR 2630040 (2012a:60091)

[Mos12] Elchanan Mossel, A quantitative arrow theorem, Probability Theory and Related Fields 154 (2012), no. 1, 49–88.

[MR15] Elchanan Mossel and Miklós Z. Rácz, A quantitative Gibbard-Satterthwaite theorem without neutrality, Combinatorica 35 (2015), no. 3, 317–387. MR 3367129

[O’D14] Ryan O’Donnell, Analysis of Boolean functions, Cambridge University Press, 2014.

[Rou62] J.J. Rousseau, Du contrat social, Chez M.M. Rey, 1762.

[SS54] L. S. Shapley and Martin Shubik, A method for evaluating the distribution of power in a committee system., American Political Science Review 48 (1954), 787–792.

[Xia20] Lirong Xia, The smoothed possibility of social choice, Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, eds.), vol. 33, Curran Associates, Inc., 2020, pp. 11044–11055.

Department of Mathematics, University of Southern California, Los Angeles, CA 90089-2532

  E-mail address: stevenmheilman@gmail.com