# the_smoothed_possibility_of_social_choice__166c05c1.pdf

The Smoothed Possibility of Social Choice

Lirong Xia, RPI, xialirong@gmail.com

We develop a framework that leverages the smoothed complexity analysis by Spielman and Teng [60] to circumvent paradoxes and impossibility theorems in social choice, motivated by modern applications of social choice powered by AI and ML. For Condrocet s paradox, we prove that the smoothed likelihood of the paradox either vanishes at an exponential rate as the number of agents increases, or does not vanish at all. For the ANR impossibility on the non-existence of voting rules that simultaneously satisfy anonymity, neutrality, and resolvability, we characterize the rate for the impossibility to vanish, to be either polynomially fast or exponentially fast. We also propose a novel easy-to-compute tie-breaking mechanism that optimally preserves anonymity and neutrality for even number of alternatives in natural settings. Our results illustrate the smoothed possibility of social choice even though the paradox and the impossibility theorem hold in the worst case, they may not be a big concern in practice.

1 Introduction

Dealing with paradoxes and impossibility theorems is a major challenge in social choice theory, because the force and widespread presence of impossibility results generated a consolidated sense of pessimism, and this became a dominant theme in welfare economics and social choice theory in general , as the eminent economist Amartya Sen commented in his Nobel prize lecture [57].

Many paradoxes and impossibility theorems in social choice are based on worst-case analysis. Take perhaps the earliest one, namely Condorcet s (voting) paradox [15], for example. Condorcet s paradox states that, when there are at least three alternatives, it is impossible for pairwise majority aggregation to be transitive. The proof is done by explicitly constructing a worst-case scenario a proﬁle P that contains a Condorcet cycle. For example, in P = {a b c, b c a, c a b}, there is a cycle a b, b c, and c a of pairwise majority. Condorcet s paradox is closely related to the celebrated Arrow s impossibility theorem: if Condorcet s paradox can be avoided, then the pairwise majority rule can avoid Arrow s impossibility theorem.

As another example, the ANR impossibility theorem (e.g. [49, Problem 1] and [53, 22, 12]) states that no voting rule r can simultaneously satisfy anonymity (r is insensitive to the identities of agents) and neutrality (r is insensitive to the identities of alternatives), and resolvability (r always chooses a single winner). The proof is done by analyzing a worst-case scenario P = {a b, b a}. Suppose for the sake of contradiction that a resolvable r satisﬁes anonymity and neutrality, and without loss of generality let r(P) = a. After exchanging a and b, the winner ought to be b due to neutrality. But since the permuted proﬁle still contains one vote for a b and one vote for b a, the winner ought to be a due to anonymity, which is a contradiction.

There is an enormous literature in social choice on circumventing the impossibilities, most of which belongs to the following two approaches. (1) Domain restrictions, namely, agents reported preferences are assumed to come from a subset of all linear orders such as single-peaked preferences [6, 2, 58, 48, 16, 8, 24]; and (2) likelihood analysis, where impossibility theorems are evaluated by the likelihood of their occurrence in proﬁles randomly generated from a distribution such as the i.i.d. uniform distribution, a.k.a. Impartial Culture (IC) [28, 32]. Both approaches have been

34th Conference on Neural Information Processing Systems (Neur IPS 2020), Vancouver, Canada.

criticized for making strong and unrealistic assumptions on the domain and on the probability distributions, respectively. In particular, IC has received much criticism, see e.g. [19], yet no widelyaccepted probabilisitic model exists to the best of our knowledge.

The worst-case nature behind the impossibility theorems might be desirable for high-stakes, lessfrequent applications such as political elections, but it may not be appropriate for modern low-stakes, frequently-used applications of social choice, many of which are supported by AI systems that learn agents preferences to help them make group decisions [66]. While AI-powered social choice appears to be a promising solution to the long-standing turnout problem [57] and can therefore promote democracy to a larger scale and with a higher frequency, it questions the relevance of worst-case analysis in social choice theory. This motivates us to ask the following key question:

How serious are the impossibilities in frequently-used modern applications of social choice?

The frequently-used feature naturally leads to the analysis of average likelihood of the impossibility theorems. But in light of the criticism of the classical likelihood analysis approach discussed above, what is a realistic model to answer the key question?

Interestingly, computer science has encountered a similar challenge and has gone through a similar path in the analysis of practical performance of algorithms. Initially, the analysis mostly focused on the worst case, as in the spirit of big O notation and NP-hardness. Domain restrictions have been a popular approach beyond the worst-case analysis. For example, while SAT is NP-hard, its restriction 2-SAT is in P. Likelihood analysis, in particular average-case complexity analysis [7], has also been a popular approach, yet it suffers from the same criticism as its counterpart in social choice the distribution used in the analysis may well be unrealistic [61].

The challenge was addressed by the smoothed (complexity) analysis introduced by Spielman and Teng [60], which focuses on the worst average-case scenario that combines the worst-case analysis and the average-case analysis. The idea is based on the fact that the input x of an algorithm is often a noisy perception of the ground truth x . Therefore, the worst-case is analyzed by assuming that an adversary chooses a ground truth x and then Nature adds a noise ϵ (e.g. a Gaussian noise) to it, such that the algorithm s input becomes x = x + ϵ. The smoothed runtime of an algorithm is therefore sup x E ϵ Run Time( x + ϵ), in contrast to the worst-case runtime sup x Run Time( x ) and the average-case runtime E x πRun Time( x ), where π is a given distribution over data.

Our Contributions. We propose a framework that leverages the elegant smoothed complexity analysis to answer the key question above. In social choice, the data is a proﬁle, which consists of agents reported preferences that are often represented by linear orders over a set A of m alternatives. Like in the smoothed complexity analysis, in our framework there is an adversary who controls agents ground truth preferences, which may be ordinal (as rankings over alternatives) or cardinal (as utilities over alternatives). Then, Nature adds a noise to the ground truth preferences and outputs a preference proﬁle, which consists of linear orders over alternatives.

Following the convention in average-case complexity analysis [7], we use a statistical model to model Nature s noising procedure. As in many smoothed-analysis approaches, we assume that noises in agents preferences are independently generated, yet agents ground truth preferences can be arbitrarily correlated, which constitutes the basis for the worst-case analysis. Using our smoothed analysis framework, we obtain the following two dichotomy theorems on the asymptotic smoothed likelihood of Condorcet s paradox and the ANR impossibility under mild assumptions, when the number of alternatives m is ﬁxed and the number of agents n goes to inﬁnity.

THEOREM 1. (Smoothed Condorcet s paradox, informally put). The smoothed likelihood of Condorcet s Paradox either vanishes at an exponential rate, or does not vanish at all.

THEOREM 2. (Smoothed ANR (im)possibility theorem, informally put). The theorem has two parts. The smoothed possibility part states that there exist resolute voting rules under which the impossibility theorem either vanishes at an exponential rate or at a polynomial rate. The smoothed impossibility part states that there does not exists a resolute voting rule under which the impossibility theorem vanishes faster than under the rules in the smoothed possibility part.

Both theorems are quite general and their formal statements also characterize conditions for each case. Such conditions in Theorem 1 tell us when Condorcet s Paradox vanishes (at an exponential rate), which is positive. While the theorem may be expected at a high level and part of it is easy to

prove, for example the exponential-rate part can be proved by using a similar idea as in the proof of minimaxity/sample complexity of MLE under a large class of distance-based models [13], we are not aware of a previous work that provides a complete dichotomy that draws a clear line between paradoxes and non-paradoxes as Theorem 1 does. In addition, we view such expectedness positive news, because it provides a theoretical conﬁrmation of well-believed hypotheses under natural settings, as smoothed complexity analysis did for the runtime of a simplex algorithm.

The smoothed possibility part of Theorem 2 is also positive because it states that the ANR impossibility vanishes as the number of agents n increases. The smoothed impossibility part of Theorem 2 is mildly negative, because it states that no voting rule can do better, though the impossibility may still vanish as n increases. Together, Theorem 1 and 2 illustrate the smoothed possibility of social choice even though the paradox and the impossibility theorem hold in the worst case, they may not be a big concern in practice in some natural settings.

Our framework also allows us to develop a novel easy-to-compute tie-breaking mechanism called most popular singleton ranking (MPSR) tie-breaking, which tries to break ties using a linear order that uniquely occurs most often in the proﬁle (Deﬁnition 8). We prove that MPSR is better than the commonly-used lexicographic tie-breaking and ﬁxed-agent tie-breaking mechanisms w.r.t. the smoothed likelihood of the ANR impossibility MPSR reduces the smoothed likelihood from n 0.5

4 for many commonly-studied voting rules under natural assumptions (Proposition 1 and Theorem 3), and is optimal for even number of alternatives m (Theorem 2 and Lemma 2).

Proof Techniques. Standard approximation techniques such as Berry-Esseen theorem and its highdimensional counterparts, e.g. [64, 18, 21], due to their O(n 0.5) error terms, are too coarse for the (tight) bound in Theorem 2. To prove our theorems, we ﬁrst model various events of interest as systems of linear constraints. Then, we develop a technical tool (Lemma 1) to provide a dichotomy characterization for the Poisson Multinomial Variables (PMV) that corresponds to the histogram of a randomly generated proﬁle to satisfy the constraints. We further show in Appendix I that Lemma 1 is a general and useful tool for analyzing smoothed likelihood of many other commonly-studied events in social choice (Table 4), which are otherwise hard to analyze.

1.1 Related Work and Discussions

Smoothed analysis. Smoothed analysis has been applied to a wide range of problems in mathematical programming, machine learning, numerical analysis, discrete math, combinatorial optimization, and equilibrium analysis and price of anarchy [14], see [61] for a survey. In a recent position paper, Baumeister et al. [4] proposed to conduct smoothed analysis on computational aspects of social choice and mentioned that their model can be used to analyze voting paradoxes and ties, but the paper does not contain technical results. Without knowing their work, we independently proposed and formulated the smoothed analysis framework for social choice in this paper.

The worst average-case idea. While our framework is inspired by the smoothed complexity analysis, the worst average-case idea is deeply rooted in (frequentist) statistics and can be viewed as a measure of robustness. Taking a statistical decision theory [5] point of view, the frequentist s loss of a decision rule r : Data Decision under a statistical model M = (Θ, S, Π) is measured by

supθ Θ EP πθ(Loss(θ, r(P))),

where the expectation evaluates the average-case loss under the worst-case distribution πθ Π. There is a large literature in statistical aspects of social choice (e.g. [15, 13, 65]) and preference learning (e.g. [39, 59]) that study the frequentist loss w.r.t. classical loss functions in statistics that depend on both P and θ, leading to consistency and minimaxity results. The idea is also closely related to the min of means criteria in decision theory [31]. Our framework explicitly models smoothed likelihood of social choice events via loss functions that measure the dissatisfaction of axioms w.r.t. the data (proﬁle) and do not depend on the ground truth θ. This is similar to smoothed complexity analysis, where the loss function is the runtime of an algorithm, which also only depends on the input data P but not on θ.

Correlations among agents preferences. In our model, agents ground truth preferences can be arbitrarily correlated while the randomness comes from independent noises. This is a standard assumption in smoothed complexity analysis as well as in relevant literatures in psychology, economics, and behavioral science, as evident in random utility models, logistic regression, MLE inter-

pretation of the ordinary least squares method, etc. [62, 67]. As another justiﬁcation, the adversary can be seen as a manipulator who wants to control agents reported preferences, but is only able to do it in a probabilistic way.

Generality of results and techniques. Our technical results are quite general and can be immediately applied to classical likelihood analysis in social choice under i.i.d. distribution, to answer open questions, obtain new results, and provide new insights. For example, a straightforward application of Lemma 1 gives an asymptotic answer to an open question by Tsetlin et al. [63] (after Corollary 2 in Appendix I). As another example, we are not aware of a previous work on the asymptotic likelihood of the ANR impossibility even under IC, which is a special case of Theorem 2.

Other related work. As discussed above, there is a large literature on domain restrictions and the likelihood analysis toward circumventing impossibility theorems, see for example, the book by Gehrlein and Lepelley [30] for a recent survey. In particular, there is a large literature on the likelihood of Condorcet voting paradox and the likelihood of (non)-existence of Condorcet winner under i.i.d. distributions especially IC [20, 43, 29, 63, 35, 32, 10, 11]. The IC assumption has also been used to prove quantitative versions of other impossibility theorems in social choice such as Arrow s impossibility theorem [36, 37, 46] and Gibbard-Satterthwaite theorem [26, 47], as well as in judgement aggregation [51, 25]. Other works have studied social choice problems when each agent s preferences are represented by a probability distribution [3, 33, 55, 68, 52, 40]. These works focused on computing the outcome efﬁciently, which is quite different from our goal.

2 Preliminaries

Basic Setting. Let A = [m] = {1, . . . , m} denote the set of m 3 alternatives. Let L(A) denote the set of all linear orders (a.k.a. rankings) over A. Let n N denote the number of agents. Each agent uses a linear order to represent his or her preferences. The vector of n N agents votes P is called a (preference) proﬁle, or sometimes an n-proﬁle. For any proﬁle P, let Hist(P) Zm! 0 denote the anonymized proﬁle of P, also called the histogram of P, which counts the multiplicity of each linear order in P. A resolute voting rule r is a mapping from each proﬁle to a single winner in A. A voting correspondence c is a mapping from each proﬁle to a non-empty set of co-winners.

Tie-Breaking Mechanisms. Many commonly-studied voting rules are deﬁned as correspondences combined with a tie-breaking mechanism. For example, a positional scoring correspondence is characterized by a scoring vector s = (s1, . . . , sm) with s1 s2 sm and s1 > sm. For any alternative a and any linear order R L(A), we let s(R, a) = si, where i is the rank of a in R. Given a proﬁle P, the positional scoring correspondence c s chooses all alternatives a with maximum P

R P s(R, a). For example, Plurality uses the scoring vector (1, 0, . . . , 0) and Borda uses the scoring vector (m 1, m 2, . . . , 0). The positional scoring rule r s chooses a single alternative by further applying a tie-breaking mechanism. The lexicographic tie-breaking, denoted by LEX-R where R L(A), breaks ties in favor of alternatives ranked higher in R. The ﬁxed-agent tie-breaking, denoted by FA-j where 1 j n, uses agent j s preferences to break ties.

(Un)weighted Majority Graphs. For any proﬁle P and any pair of alternatives a, b, let P[a b] denote the number of rankings in P where a is preferred to b. Let WMG(P) denote the weighted majority graph of P, which is a complete graph where the vertices are A and the edge weights are w P (a, b) = P[a b] P[b a]. For any distribution π over L(A), let WMG(π) denote the weighted majority graph where π is treated as a fractional proﬁle, where for each R L(A) there are π(R) copies of R. The unweighted majority graph (UMG) of a proﬁle P, denoted by UMG(P), is the unweighted directed graph where the vertices are the alternatives and there is an edge a b if and only if P[a b] > P[b a]. If a and b are tied, then there is no edge between a and b. UMG(π) is deﬁned similarly. A Condorcet cycle of a proﬁle P is a cycle in UMG(P). A weak Condorcet cycle of a proﬁle P is a cycle in any supergraph of UMG(P).

Axiomatic Properties. A voting rule r satisﬁes anonymity, if the winner is insensitive to the identity of the voters. That is, for any pair of proﬁles P and P with Hist(P) = Hist(P ), we have r(P) = r(P ). r satisﬁes neutrality if the winner is insensitive to the identity of the alternatives. That is, for any permutation σ over A, we have r(σ(P)) = σ(r(P)), where σ(P) is the obtained from P by permuting alternatives according to σ.

Single-Agent Preference Models. A statistical model M = (Θ, S, Π) has three components: the parameter space Θ, which contains the ground truth ; the sample space S, which contains all possible data; and the set of probability distributions Π, which contains a distribution πθ over S for each θ Θ. In this paper we adopt single-agent preference models, where S = L(A). Deﬁnition 1. A single-agent preference model is denoted by M = (Θ, L(A), Π). M is strictly positive if there exists ϵ > 0 such that the probability of any ranking under any distribution in Π is at least ϵ. M is closed if Π is a closed set in Rm! 0, where each distribution in Π is viewed as a vector in m!-probability simplex. M is neutral if for any θ Θ and any permutation σ over A, there exists η Θ such that for all R L(A), we have πθ(R) = πη(σ(R)).

See Example 2 in Appendix A for two examples of single-agent preference models that correspond to the celebrated Mallows model and Plackett-Luce model, respectively.

3 Smoothed Analysis Framework and The Main Technical Lemma

Many commonly-studied axioms and events in social choice, denoted by X, are deﬁned based on per-proﬁle properties in the following way. Let r denote a voting rule or correspondence and let P denote a proﬁle. There is a function SX(r, P) {0, 1} that indicates whether X holds for r at P. Then, r satisﬁes X if P, SX(r, P) = 1, or equivalently, inf P SX(r, P) = 1. For example, for anonymity, let Sano(r, P) = 1 iff for all proﬁles P with Hist(P ) = Hist(P), r(P ) = r(P). For neutrality, let Sneu(r, P) = 1 iff for all permutation σ over A, σ(r(P)) = r(σ(P)). For nonexistence of Condorcet cycle, let SNCC(P) = 1 iff there is no Condorcet cycle in P.

Our smoothed analysis framework assumes that each of the n agents preferences are chosen from a single-agent preference model M = (Θ, L(A), Π) by the adversary. Deﬁnition 2 (Smoothed likelihood of events). Given a single-agent preference model M = (Θ, L(A), Π), n N agents, a function SX that characterizes an axiom or event X, and a voting rule (or correspondence) r, the smoothed likelihood of X is deﬁned as inf π Πn EP πSX(r, P).

For example, inf π Πn EP πSNCC(P) is the smoothed likelihood of non-existence of Condorcet cycle, which corresponds to the avoidance of Condorcet s paradox. inf π Πn Pr P π(Sano(P) + Sneu(P) = 2) is the smoothed likelihood of satisfaction of anonymity+neutrality, which corresponds to the avoidance of the ANR impossibility.

We use the following simple example to show how to model events of interest as a system of linear constraints. The ﬁrst event is closely related to the smoothed Condorcet s paradox (Theorem 1) and the second event is closely related to the smoothed ANR theorem (Theorem 2). Example 1. Let m = 3 and A = {1, 2, 3}. For any proﬁle P, let x123 denote the number of 1 2 3 in P. The event there is a Cordorcet cycle 1 2 3 1 can be represented by:

(x213 + x231 + x321) (x123 + x132 + x312) < 0 (1) (x312 + x321 + x132) (x231 + x213 + x123) < 0 (2) (x123 + x132 + x213) (x312 + x321 + x231) < 0 (3)

Equation (1) (respectively, (2) and (3)) states that UMG(P) has edge 1 2 (respectively, 2 3 and 3 1). As another example, the event Hist(P) is invariant to the permutation σ over A that exchanges 1 and 2 can be represented by {x123 x213 = 0, x132 x231 = 0, x312 x321 = 0}.

Notice that in this example each constraint has the form E x = 0 or S x < 0, where E 1 = 0 and S 1 = 0. More generally, our main technical lemma upper-bounds the smoothed likelihood for the Poisson multinomial variable Hist(P) to satisfy a similar system of linear inequalities below. Deﬁnition 3. Let q, n N. For any vector of n distributions π = (π1, . . . , πn), each of which is over [q], let Y = (Y1, . . . , Yn) denote the vector of n random variables distributed as π1, . . . , πn, respectively, and let X π = Hist( Y ), i.e. the Poisson multinomial variable that corresponds to Y .

Deﬁnition 4. Let CES( x) = {E ( x) = ( 0) and S ( x) < ( 0) }, where E is a K q integer matrix that represents the equations and S is an L q integer matrix with K +L 1 that represents the strict inequalities. Let CES 0( x) = {E ( x) = ( 0) and S ( x) ( 0) } denote the relaxation of CES( x). Let H and H 0 denote the solutions to CES( x) and CES 0( x), respectively.

Lemma 1 (Main technical lemma). Let q N and let Π be a closed set of strictly positive distributions over [q]. Let CH(Π) denote the convex hull of Π.

Upper bound. For any n N and any π Πn,

0 if H = exp( Ω(n)) if H = and H 0 CH(Π) = O(n Rank(E)

2 ) if H = and H 0 CH(Π) = Tightness of the upper bound. There exists a constant C such that for any n N, there exists n n Cn and π Πn such that

Pr X π H = exp( O(n)) if H = and H 0 CH(Π) = Ω(n Rank(E)

2 ) if H = and H 0 CH(Π) =

Lemma 1 is quite general because the assumptions on Π are mild and E and S are general enough to model a wide range of events in social choice as we will see later in the paper. It provides asymptotically tight upper bounds on the probability for the histogram of a randomly generated proﬁle from π Πn to satisfy all constraints in CES. The bounds provide a trichotomy: if no vector satisﬁes all constraints in CES, i.e. H = , then the upper bound is 0; otherwise if H = and its relaxation H 0 does not contain a vector in the convex hull of Π, then the upper bound is exponentially small; otherwise the upper bound is polynomially small in n, and the degree of polynomial is determined by the rank of E, speciﬁcally Rank(E)

2 . The tightness part of the lemma states that the upper bounds cannot be improved for all n.

At a high level the lemma is quite natural and follows the intuition of multivariate central limit theorem as follows. Roughly, X π is distributed like a multinomial Gaussian whose expectation is π 1 = Pn j=1 πj (which is a q-dimensional vector). Then, the zero part of Lemma 1 is trivial; the exponential part makes sense because the expectation π 1 is Θ(n) away from any vector in H; and the last part is expected to be O(n 0.5) because the center π 1 satisﬁes the E part of CES.

The surprising part of the lemma is the degree of polynomial Rank(E)

2 and its tightness. As discussed in the Introduction, all central limit theorems we are aware of are too coarse for proving the O(n Rank(E)

2 ) bound. To prove the polynomial upper bound, we introduce an alternative representation of X π to tackle the dependencies among its components, prove novel ﬁne-grained concentration and anti-concentration bounds, focus on the reduced row echelon form of E plus an additional constraint on the total number of agents to characterize H, and then do a weighted counting of vectors that satisfy CES. The full proof can be found in Appendix B.

4 Smoothed Condorcet s Paradox and ANR (Im)possibility Theorem

We ﬁrst apply the main technical lemma (Lemma 1) to characterize the smoothed likelihood of Condorcet s paradox in the following dichotomy theorem, which holds for any ﬁxed m 3.

Theorem 1 (Smoothed likelihood of Codorcet s paradox). Let M = (Θ, L(A), Π) be a strictly positive and closed single-agent preference model.

Smoothed avoidance of Condorcet s paradox. Suppose for all π CH(Π), UMG(π) does not contain a weak Condorcet cycle. Then, for any n N, we have:

inf π Πn EP πSNCC(P) = 1 exp( Ω(n))

Smoothed Condorcet s paradox. Suppose there exists π CH(Π) such that UMG(π) contains a weak Condorcet cycle. Then, there exist inﬁnitely many n N such that:

inf π Πn EP πSNCC(P) = 1 Ω(1)

The smoothed avoidance part of the theorem is positive news: if there is no weak Condorcet cycle in the UMG of any distribution in the convex hull of Π, then no matter how the adversary sets agents ground truth preferences, the probability for Condorcet s paradox to hold, which is 1 inf π Πn EP πSNCC(P) = sup π Πn Pr P π(SNCC(P) = 0), vanishes at an exponential rate as n . Consequently, in such cases Arrows impossibility theorem can be avoided because the pairwise

majority rule satisﬁes all desired properties mentioned in the theorem. The second part (smoothed paradox) states that otherwise the adversary can make Condorcet s paradox occur with constant probability. The proof is done by modeling SNCC(P) = 0 as systems of linear constraints as in Deﬁnition 4, each of which represents a target UMG with a weak Codorcet cycle as in Example 1, then applying Lemma 1. The full proof is in Appendix C.

We now turn to the smoothed ANR impossibility. We will reveal a relationship between all nproﬁles and all permutation groups over A after recalling some basic notions in group theory. The symmetric group over A = [m], denoted by SA, is the set of all permutations over A.

Deﬁnition 5. For any proﬁle P, let Perm(P) denote the set of all permutations σ over A that maps Hist(P) to itself. Formally, Perm(P) = {σ SA : Hist(P) = σ(Hist(P))}.

See Appendix D for additional notation and examples about group theory.1 It is not hard to see that Perm(P) is a permutation group. We now deﬁne a special type of permutation groups that cover all alternatives in A, which are closely related to the impossibility theorem.

Deﬁnition 6. For any permutation group U SA and any alternative a A, we say that U covers a if there exists σ U such that a = σ(a). We say that U covers A if it covers all alternatives in A. For any m, let Um denote the set of all permutation groups that cover A.

For example, when m = 3, U3 = {Id, (1, 2, 3), (1, 3, 2)}, where Id is the identity permutation and (1, 2, 3) is the circular permutation 1 2 3 1. See Example 5 in Appendix D for the list of all permutation groups for m = 3. In general |Um| > 1.

Theorem 2 (Smoothed ANR (im)possibility). Let M = (Θ, L(A), Π) be a strictly positive and closed single-agent preference model. Let UΠ m = {U Um : π CH(Π), σ U, σ(π) = π}, and when UΠ m = , let lmin = min U UΠ m |U| and lΠ = lmin 1

Smoothed possibility. There exist an anonymous voting rule rano and a neutral voting rule rneu such that for any r {rano, rneu}, any n, and any π Πn, we have:

Pr P π(Sano(r, P) + Sneu(r, P) < 2) = O(n lΠ

2 ) if UΠ m = exp( Ω(n)) otherwise

Smoothed impossibility. For any voting rule r, there exist inﬁnitely many n N such that:

sup π Πn Pr P π(Sano(r, P) + Sneu(r, P) < 2) = Ω(n lΠ

2 ) if UΠ m = exp( O(n)) otherwise

Again, Theorem 2 holds for ﬁxed m 3. We note that for any proﬁle P, Sano(r, P)+Sneu(r, P) < 2 if and only if at least one of anonymity or neutrality is violated at P. In other words, if Sano(r, P) + Sneu(r, P) = 2 then both anonymity and neutrality are satisﬁed at P. Therefore, the ﬁrst part of Theorem 2 is called smoothed possibility because it states that no matter how the adversary sets agents ground truth preferences, the probability for rano (respectively, rneu) to satisfy both anonymity and neutrality converges to 1. The second part (smoothed impossibility) shows that the rate of convergence in the ﬁrst part is asymptotically tight for all n. This is a mild impossibility theorem because violations of anonymity or neutrality may still vanish (at a slower rate) as n .

The proof proceeds in the following three steps. Step 1. For any m and n, we deﬁne a set of proﬁles, denoted by Tm,n, that represent the source of impossibility. In fact, Tm,n is the set of all n-proﬁles P such that Perm(P) covers A, i.e. Perm(P) Um. Step 2. To prove the smoothed possibility part, we deﬁne rano and rneu that satisfy both anonymity and neutrality for all proﬁles that are not in Tm,n. Then, we apply Lemma 1 to upper-bound the probability of Tm,n. Step 3. The smoothed impossibility part is proved by applying the tightness part of Lemma 1 to the probability of Tm,n. The full proof can be found in Appendix E.

In general lmin in Theorem 2 can be hard to characterize. The following lemma provides a lower bound on lmin by characterizing min U Um |U|, whose group-theoretic proof is in Appendix F.

Lemma 2. For any m 2, let l = min U Um |U|. We have l = 2 if m is even; l = 3 if m is odd and 3 | m; l = 5 if m is odd, 3 m, and 5 | m; and l = 6 for other m.

1Some group theoretic notation and ideas in this paper are similar to those in a 2015 working paper by Do gan and Giritligil [22] whose main results are different. See Appendix D for more details and discussions.

A notable special case of Theorem 2 is πuni CH(Π), where πuni is the uniform distribution over L(A). We note that for any permutation σ, πuni = σ(πuni), which means that UΠ m = Um. Therefore, only the polynomial bound in Theorem 2 remains, with lΠ = l 1

l m!. In particular, πuni CH(Π) for all neutral single-agent preference models under IC, which corresponds to Π = {πuni}. See Corollary 1 in Appendix F.1 for the formal statement.

5 Optimal Tie-Breaking for Anonymity + Neutrality

While rano and rneu in Theorem 2 are asymptotically optimal w.r.t. anonymity + neutrality, they may be hard to compute. The following proposition shows that the commonly-used LEX and FA mechanisms are far from being optimal for positional scoring rules. Proposition 1. Let r be a voting rule obtained from a positional scoring correspondence by applying LEX or FA. Let M = (Θ, L(A), Π) be a strictly positive and closed single-agent preference model with πuni CH(Π). There exist inﬁnitely many n N such that:

sup π Πn Pr P π (Sano(r, P) + Sneu(r, P) < 2) = Ω(n 0.5)

The proof is done by modeling ties under positional scoring correspondences as systems of linear constraints, then applying the tightness of the polynomial bound in Lemma 1. The full proof can be found in Appendix G. We now introduce a new class of easy-to-compute tie-breaking mechanisms that achieve the optimal upper bound O(n m!

4 ) in Theorem 2 when m is even. Deﬁnition 7 (Most popular singleton ranking). Given a proﬁle P, we deﬁne its most popular singleton ranking (MPSR) as MPSR(P) = arg max R(P[R] : W = R s.t. P[W] = P[R]).

Put differently, a ranking R is called a singleton in a proﬁle P, if there does not exist another linear order that occurs for the same number of times in P. MPSR(P) is the singleton that occurs most frequently in P. If no singleton exists, then we let MPSR(P) = . We now deﬁne tie-breaking mechanisms based on MPSR. Deﬁnition 8 (MPSR tie-breaking mechanism). For any voting correspondence c, any proﬁle P, and any backup tie-breaking mechanism TB, the MPSR-then-TB mechanism uses MPSR(P) to break ties whenever MPSR(P) = ; otherwise it uses TB to break ties. Theorem 3. Let M = (Θ, L(A), Π) be a strictly positive and closed single-agent preference model with πuni CH(Π). For any voting correspondence c that satisﬁes anonymity and neutrality, let r MPSR denote the voting rule obtained from c by MPSR-then-TB. For any n and any π Πn,

Pr P π(Sano(r MPSR, P) + Sneu(r MPSR, P) < 2) = O(n m!

Moreover, if TB satisﬁes anonymity (respectively, neutrality) then so does r MPSR.

The proof is done by showing that (1) anonymity and neutrality are preserved when MPSR(P) = , and (2) any proﬁle P with MPSR(P) = can be represented by a system of linear constraints, whose smoothed likelihood is upper-bounded by the polynomial upper bound in Lemma 1. The full proof can be found in Appendix H.

Note that when m is even, the O(n m!

4 ) upper bound in Theorem 3 matches the optimal upper bound in light of Theorem 2 and Lemma 2. This is good news because it implies that any anonymous and neutral correspondence can be made an asymptotically optimal voting rule w.r.t. anonymity+neutrality by MPSR tie-breaking. When m is odd, the O(n m!

4 ) upper bound in Theorem 3 is suboptimal but still signiﬁcantly better than that of the lexicographic or ﬁxed-agent tie-breaking mechanism, which is Ω(n 0.5) (Proposition 1).

6 Future work

We have only touched the tip of the iceberg of smoothed analysis in social choice. There are at least three major dimensions for future work: (1) other social choice axioms and impossibility theorems, for example Arrow s impossibility theorem [36, 37, 46] and the Gibbard-Satterthwaite theorem [26, 47], (2) computational aspects in social choice [9, 4] such as the smoothed complexity of winner determination and complexity of manipulation, and (3) other social choice problems such as judgement aggregation [51, 25], distortion [54, 1, 41, 38, 42], matching, resource allocation, etc.

7 Acknowledgements

We thank Elliot Anshelevich, Rupert Freeman, Herve Moulin, Marcus Pivato, Nisarg Shah, Rohit Vaish, Bill Zwicker, participants of the COMSOC video seminar, and anonymous reviewers for helpful discussions and comments. This work is supported by NSF #1453542, ONR #N00014-171-2621, and a gift fund from Google.

Broader Impact

In this paper we aim to provide smoothed possibilities of social choice, which is an important problem in the society. Therefore, success of the research will beneﬁt general public beyond the CS research community because better solutions are now available for a wide range of group decisionmaking scenarios.

[1] Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron. Approximating Optimal Social Choice under Metric Preferences. Artiﬁcial Intelligence, 264(27 51), 2018.

[2] Kenneth Arrow. Social choice and individual values. New Haven: Cowles Foundation, 2nd edition, 1963. 1st edition 1951.

[3] Yoram Bachrach, Nadja Betzler, and Piotr Faliszewski. Probabilistic possible winner determination. In Proceedings of the National Conference on Artiﬁcial Intelligence (AAAI), pages 697 702, Atlanta, GA, USA, 2010.

[4] Dorothea Baumeister, Tobias Hogrebe, and J org Rothe. Towards Reality: Smoothed Analysis in Computational Social Choice. In Proceedings of AAMAS, pages 1691 1695, 2020.

[5] James O. Berger. Statistical Decision Theory and Bayesian Analysis. Springer, 2nd edition, 1985.

[6] Duncan Black. The Theory of Committees and Elections. Cambridge University Press, 1958.

[7] Andrej Bogdanov and Luca Trevisan. Average-Case Complexity. Foundations and Trends in Theoretical Computer Science, 2(1):1 106, 2006.

[8] Felix Brandt, Markus Brill, Edith Hemaspaandra, and Lane A. Hemaspaandra. Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. In Proceedings of the National Conference on Artiﬁcial Intelligence (AAAI), pages 715 722, 2010.

[9] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jerome Lang, and Ariel D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.

[10] Felix Brandt, Christian Geist, and Martin Strobel. Analyzing the Practical Relevance of Voting Paradoxes via Ehrhart Theory, Computer Simulations, and Empirical Data. In Proceedings of AAMAS, pages 385 393, 2016.

[11] Felix Brandt, Johannes Hofbauer, and Martin Strobel. Exploring the No-Show Paradox for Condorcet Extensions Using Ehrhart Theory and Computer Simulations. In Proceedings of AAMAS, pages 520 528, 2019.

[12] Donald E. Campbell and Jerry S. Kelly. The ﬁner structure of resolute, neutral, and anonymous social choice correspondences. Economics Letters, pages 109 111, 2015.

[13] Ioannis Caragiannis, Ariel D. Procaccia, and Nisarg Shah. When Do Noisy Votes Reveal the Truth? ACM Transactions on Economics and Computation, 4(3):Article No. 15, 2016.

[14] Christine Chung, Katrina Ligett, Kirk Pruhs, and Aaron Roth. The Price of Stochastic Anarchy. In International Symposium on Algorithmic Game Theory, pages 303 314, 2008.

[15] Marquis de Condorcet. Essai sur l application de l analyse a la probabilit e des d ecisions rendues a la pluralit e des voix. Paris: L Imprimerie Royale, 1785.

[16] Vincent Conitzer. Eliciting single-peaked preferences using comparison queries. Journal of Artiﬁcial Intelligence Research, 35:161 191, 2009.

[17] William J. Cook, Albertus M. H. Gerards, Alexander Schrijver, and Eva Tardos. Sensitivity theorems in integer linear programming. Mathematical Programming, 34(3):251 264, 1986.

[18] Constantinos Daskalakis, Anindya De, Gautam Kamat, and Christos Tzamos. A Size-Free CLT for Poisson Multinomials and its Applications. In Proceedings of STOC, pages 1074 1086, 2016.

[19] Adrian Van Deemen. On the empirical relevance of condorcet s paradox. Public Choice, 158 (3 4):311 330, 2014.

[20] Frank De Meyer and Charles R. Plott. The Probability of a Cyclical Majority. Econometrica, 38(2):345 354, 1970.

[21] Ilias Diakonikolas, Daniel Mertz Kane, and Alistair Stewart. The fourier transform of poisson multinomial distributions and its algorithmic applications. In Proceedings of STOC, pages 1060 1073, 2016.

[22] Onur Do gan and Ayc a Ebru Giritligil. Anonymous and Neutral Social Choice: Existence Results on Resoluteness. Murat Sertel Center for Advanced Economic Studies Working Paper Series:2015-01, 2015.

[23] Richard Durrett. Probability: Theory and Examples. 1991.

[24] Edith Elkind, Martin Lackner, and Dominik Peters. Preference restrictions in computational social choice: recent progress. In Proceedings of the Twenty-Fifth International Joint Conference on Artiﬁcial Intelligence, pages 4062 4065, 2016.

[25] Yuval Filmus, Noam Lifshitz, Dor Minzer, and Elchanan Mossel. AND testing and robust judgement aggregation. Ar Xiv, 2019.

[26] Ehud Friedgut, Gil Kalai, Nathan Keller, and Noam Nisan. A quantitative version of the gibbard satterthwaite theorem for three alternatives. SIAM Journal on Computing, 40(3):934 952, 2011.

[27] Joseph Gallian. Contemporary Abstract Algebra. Cengage Learning, 8th edition, 2012.

[28] William V. Gehrlein. Condorcet s paradox and the likelihood of its occurrence: different perspectives on balanced preferences. Theory and Decision, 52(2):171 199, 2002.

[29] William V. Gehrlein and Peter C. Fishburn. The probability of the paradox of voting: A computable solution. Journal of Economic Theory, 13(1):14 25, 1976.

[30] William V. Gehrlein and Dominique Lepelley. Elections, Voting Rules and Paradoxical Outcomes. Springer, 2017.

[31] Itzhak Gilboa and David Schmeidler. Maxmin expected utility with non-unique prior. Journal of Mathematical Economics, 18(2):141 153, 1989.

[32] James Green-Armytage, T. Nicolaus Tideman, and Rafael Cosman. Statistical evaluation of voting rules. Social Choice and Welfare, 46(1):183 212, 2016.

[33] Noam Hazon, Yonatan Aumann, Sarit Kraus, and Michael Wooldridge. On the Evaluation of Election Outcomes under Uncertainty. Artiﬁcial Intelligence, 189:1 18, 2012.

[34] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13 30, 1963.

[35] Bradford Jones, Benjamin Radcliff, Charles Taber, and Richard Timpone. Condorcet Winners and the Paradox of Voting: Probability Calculations for Weak Preference Orders. The American Political Science Review, 89(1):137 144, 1995.

[36] Gil Kalai. A Fourier-theoretic perspective on the Condorcet paradox and Arrow s theorem. Advances in Applied Mathematics, 29(3):412 426, 2002.

[37] Nathan Keller. On the probability of a rational outcome for generalized social welfare functions on three alternatives. Journal of Combinatorial Theory, Series A, 117(4):389 410, 2010.

[38] David Kempe. Communication, Distortion, and Randomness in Metric Voting. In Proc. of AAAI, 2020.

[39] Ashish Khetan and Sewoong Oh. Data-driven Rank Breaking for Efﬁcient Rank Aggregation. Journal of Machine Learning Research, 17(193):1 54, 2016.

[40] Haoming Li, Sujoy Sikdar, Rohit Vaish, Junming Wang, Lirong Xia, and Chaonan Ye. Minimizing Time-to-Rank: A Learning and Recommendation Approach. In Proceedings of IJCAI, 2019.

[41] Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, and David P. Woodruff. Efﬁcient and Thrifty Voting by Any Means Necessary. In Proceedings of Neur IPS, 2019.

[42] Debmalya Mandal, Nisarg Shah, and David P. Woodruff. Optimal Communication-Distortion Tradeoff in Voting. In Proceedings of ACM EC, 2020.

[43] Robert M. May. Some mathematical remarks on the paradox of voting. Behavioral Science, 16(2), 1971.

[44] David C. Mc Garvey. A theorem on the construction of voting paradoxes. Econometrica, 21 (4):608 610, 1953.

[45] Carl D. Meyer. Matrix analysis and applied linear algebra. SIAM, 2000.

[46] Elchanan Mossel. A quantitative Arrow theorem. Probability Theory and Related Fields, 154: 49 88, 2012.

[47] Elchanan Mossel and Miklos Z Racz. A quantitative Gibbard-Satterthwaite theorem without neutrality. Combinatorica, 35(3):317 387, 2015.

[48] Herv e Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437 455, 1980.

[49] Herv e Moulin. The Strategy of Social Choice. Elsevier, 1983.

[50] Herv e Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1991.

[51] Ilan Nehama. Approximately classic judgement aggregation. Annals of Mathematics and Artiﬁcial Intelligence, 68:91 134, 2013.

[52] Ritesh Noothigattu, Snehalkumar Neil S. Gaikwad, Edmond Awad, Sohan Dsouza, Iyad Rahwan, Pradeep Ravikumar, and Ariel D. Procaccia. A Voting-Based System for Ethical Decision Making. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, 2018.

[53] Ali Ozkes and M. Remzi Sanver. Anonymous, Neutral, and Resolute Social Choice Revisited. http://dx.doi.org/10.2139/ssrn.3547394, 2020.

[54] Ariel D. Procaccia and Jeffrey S. Rosenschein. The Distortion of Cardinal Preferences in Voting. In Proceedings of the 10th International Workshop on Cooperative Information Agents, volume 4149 of LNAI, pages 317 331. 2006.

[55] Ariel D Procaccia and Nisarg Shah. Optimal aggregation of uncertain preferences. In AAAI, pages 608 614, 2016.

[56] Herbert Robbins. A Remark on Stirling s Formula. The American Mathematical Monthly, 62 (1):26 29, 1955.

[57] Amartya Sen. The Possibility of Social Choice. American Economic Review, 89(3):349 378, 1999.

[58] Amartya K. Sen. A Possibility Theorem on Majority Decisions. Econometrica, 32(2):491 499, 1966.

[59] Nihar B. Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramchandran, and Martin J. Wainwright. Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence. Journal of Machine Learning Research, 17(1 47), 2016.

[60] Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3), 2004.

[61] Daniel A. Spielman and Shang-Hua Teng. Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice. Communications of the ACM, 52(10):76 84, 2009.

[62] Kenneth E. Train. Discrete Choice Methods with Simulation. Cambridge University Press, 2nd edition, 2009.

[63] Ilia Tsetlin, Michel Regenwetter, and Bernard Grofman. The impartial culture maximizes the probability of majority cycles. Social Choice and Welfare, 21(3):387 398, 2003.

[64] Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. In Proceedings of STOC, pages 685 694, 2011.

[65] Lirong Xia. Bayesian estimators as voting rules. In Proceedings of the Thirty-Second Conference on Uncertainty in Artiﬁcial Intelligence, pages 785 794, 2016.

[66] Lirong Xia. Improving Group Decision-Making by Artiﬁcial Intelligence. In Proceedings of IJCAI-17, 2017.

[67] Lirong Xia. Learning and Decision-Making from Rank Data. Synthesis Lectures on Artiﬁcial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2019.

[68] Zhibing Zhao, Haoming Li, Junming Wang, Jeffrey Kephart, Nicholas Mattei, Hui Su, and Lirong Xia. A Cost-Effective Framework for Preference Elicitation and Aggregation. In Proceedings of Uncertainty in Artiﬁcial Intelligence, 2018.