# semirandom_impossibilities_of_condorcet_criterion__057ad6e2.pdf

Semi-random Impossibilities of Condorcet Criterion

RPI, Troy, NY, USA xialirong@gmail.com

The Condorcet criterion (CC) is a classical and well-accepted criterion for voting. Unfortunately, it is incompatible with many other desiderata including participation (PAR), halfway monotonicity (HM), Maskin monotonicity (MM), and strategy-proofness (SP). Such incompatibilities are often known as impossibility theorems, and are proved by worstcase analysis. Previous work has investigated the likelihood for these impossibilities to occur under certain models, which are often criticized of being unrealistic. We strengthen previous work by proving the first set of semirandom impossibilities for voting rules to satisfy CC and the more general, group versions of the four desiderata: for any sufficiently large number of voters n, any size of the group 1 B n, any voting rule r, and under a large class of semi-random models that include Impartial Culture, the likelihood for r to satisfy CC and PAR, CC and HM, CC and MM, or CC and SP is 1 Ω( B n). This matches existing lower bounds for CC&PAR (B = 1) and CC&SP and CC&HM (B n), showing that many commonly-studied voting rules are already asymptotically optimal in such cases.

1 Introduction The Condorcet criterion of voting (Condorcet 1785) is a classical desideratum that has nearly universal acceptance (Saari 1995, p. 46). It requires a voting rule to choose the Condorcet winner the alternative who beats other alternatives in head-to-head competitions whenever it exists. Unfortunately, it is well-known that the Condorcet criterion (CC for short) is incompatible with many other desiderata (a.k.a. axioms) when the number of alternatives m is at least 3. Such incompatibilities are often called impossibility theorems. For example, no voting rule satisfies

CC and participation (PAR for short, which requires that no voter has incentive to abstain from voting), when m 4 (Moulin 1988); CC and half-way monotonicity (HM for short, which requires that no voter has incentive to reverse his/her vote (Sanver and Zwicker 2009)); CC and Maskin monotonicity (MM for short, which requires that any voter raising the position of the winner

Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

relative to other alternatives does not change the winner (Maskin 1999)), as a special case of the Muller Satterthwaite theorem (1977); or CC and strategy-proofness (SP for short, which requires that no agent has incentive to lie), as a special case of the Gibbard-Satterthwaite theorem (1973; 1975).

The four combinations of axioms are therefore denoted by CC&PAR, CC&HM, CC&MM, and CC&SP, respectively. Proofs for these impossibility theorems are based on worst-case analysis, by identifying a single instance of violation. Therefore, they do not preclude the possibility that such violations are rare in practice. Indeed, if so, then one need not be unduly worried (Pattanaik 1978). Studying how rare such impossibilities are in practice has been a popular and active field of research (Gehrlein and Lepelley 2011; Diss and Merlin 2021). Recently, the topic was investigated using smoothed analysis (Spielman and Teng 2009; Baumeister, Hogrebe, and Rothe 2020; Xia 2020), which can be viewed as a worst average-case analysis under semi-random models (Feige 2021), following the frequentists principle: the likelihood of violation of axioms is estimated under an adversarially chosen (i.e., worst-case) distribution for the votes from a given set of distributions. For example, the likelihood for CC or PAR to be violated is Θ( 1 n) for many voting rules for n voters, under a large class of semi-random models (Xia 2021b). While this is good news, as violations vanish at a Θ( 1 n) rate, they are not rare enough when the cost of violation is high. For example, if a violation of CC or PAR leads to a revote, whose social cost is Θ(n), then the expected social cost is Θ( n), which is non-negligible. As another example, if everyone complaints on social media about the violation and gets 1 utility every time when seeing a complaint, then the social cost can be as high as Θ(n2), meaning that the expected social cost is Ω(n1.5), or in other words, Ω( n) per person. In such situations, voting rules with rarer violations are desirable. But can any voting rule do better, and if so, by how much? The answer lies in the lower bound on the likelihood of violations (under all rules), or equivalently, the upper bound on the likelihood of satisfying the axioms. In this paper, we address this question for the four combinations of axioms involving CC mentioned earlier, by proving semi-

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

random impossibilities (Xia 2020) under a large class of semi-random models that are more general and realistic than the commonly-used i.i.d. uniform distribution, known as the Impartial Culture (IC). Therefore, the research question of this paper can be phrased as:

What are the semi-random impossibilities of CC?

More precisely, we consider the more general, group versions of X {CC&PAR, CC&HM, CC&MM, CC&SP}. For any B 1, any collection of votes P (called a profile), and any voting rule r, we let X(r, P, B) = 1 if r satisfies CC at P and no group of at most B voters in P can collaboratively violate X; otherwise X(r, P, B) = 0. Then, given a set of distributions Π over the votes and n agents, the semirandom version of X (Xia 2020, 2021b) is defined as:

e Xmin Π (r, n, B) inf π Πn Pr P π (X(r, P, B) = 1) (1)

That is, e Xmin Π (r, n, B) is the worst-case (lower bound) on the probability for X to be 1 under the profile P generated from a vector π of n distributions in Πn, one for each agent. Notice that while agents votes are independently generated, their underlying distributions are adversarially chosen and can be different. A high e Xmin Π value is desirable, because it implies that the expected satisfaction of X is high even under the worst distribution π Πn.

1.1 Our Contributions The main results of this paper are four semi-random impossibility theorems: for X = CC&PAR (Theorem 1), CC&HM (Theorem 2), CC&MM (Theorem 3), or CC&SP (Theorem 4), any m 4 (m 3 for CC&MM and CC&SP), any sufficiently large n, any 1 B n, any voting rule r, and any Π satisfying certain conditions (Assumption 1), e Xmin Π (r, n, B) = 1 Ω B n

In other words, no voting rule can guarantee that X is violated with probability smaller than Ω( B n). The results also imply that every additional member in the group (up to n) roughly increase the likelihood of violation by Θ( 1 n). Specifically, when B = Ω( n), the likelihood of violation does not vanish even in large elections (n ). Our results match the lower bound for CC&PAR when B = 1 (Xia 2021b) and for CC&SP and CC&HM1 for every B n (Xia 2022), which are achieved by many voting rules that satisfies CC, such as Copeland, maximin, ranked pairs, and Schulze in contrast, for CC&PAR, positional scoring rules and STV are much worse, as their satisfactions are 1 Θ(1) (Xia 2021b).

Good or bad news? On the positive side, it is the first time, to the best of our knowledge, that the optimal likelihood of avoiding impossibility theorems that involve CC is known. It is surprising to us that many existing rules are already optimal. On the negative side, the tightness suggests that there is

1This is because an upper bound for CC&SP is also an upper bound of CC&HM. We thank Dominik Peters for pointing this out to us.

little room for improvement, which can be a critical concern when the cost of violation is high. After all, we believe that these semi-random impossibility theorems are useful and informative in theory, as they reveal limitations of the optimal rules, as well as in practice, for the decision maker to choose the voting rule and decide the policies when a violation of axioms occurs.

Generality and limitations. The generality of the semirandom impossibilities proved in this paper largely depends on the restrictiveness of Assumption 1. We defer the formal technical definition and discussions to Section 2, and feel that the assumption is mild in practice, because it is satisfied by many single-agent preference models, including IC, the single-agent Mallows and single-agent Plackett-Luce with bounded parameters (Xia 2020). As a result, the 1 Ω( B n) upper bound naturally holds under IC (Corollary 1). The major limitations are, first, the constant in Ω( B n) may be exponentially large in m, though it does not depend on n, B, or r. Second, the semi-random model in this paper assumes that the votes are statistically independent (but not necessarily identically distributed). These are common limitations/assumptions in preference modeling, see, e.g., (Thurstone 1927; Berry, Levinsohn, and Pakes 1995; Train 2009). Addressing them may require breakthroughs in probability theory and are important and challenging directions.

Proof overview. The high-level idea is surprisingly simple: for each X studied in this paper, in step 1, we leverage existing proof of the (worst-case) impossibility theorem to identify sufficiently many profiles where X is violated. Then, in step 2, we prove that there exists π Πn under which with Ω( B n) probability, a profile falls in the set identified in step 1. Nevertheless, the actual calculations are technical challenging due to the generality of r. In step 1, we introduce a rotated template by scaling up an existing proof diagram (e.g., (Peters 2019, Chapter 1)) to identify profiles where X is violated, and prove that there are sufficiently many such violation profiles by upper-bounding the number of times each of them is identified by the rotated template. Then in step 2, we use an averaging argument over all n! permutations of a carefully chosen π to convert the problem to the likelihood about the histogram of profiles, which is then tackled by applying the point-wise concentration bound (Xia 2021a, Lemma 1). The idea and techniques have the potential to leverage other (worst-case) impossibility theorems to their semirandom versions. See Section 4 for more discussions.

1.2 Related Work and Discussions Condorcet criterion (CC) is satisfied by many commonlystudied voting rules. Prominent exceptions are positional scoring rules (Fishburn 1974b) and multi-round-score-based elimination rules, such as STV. Much previous work aimed at theoretically characterizing the Condorcet efficiency, which is the probability for the Condorcet winner to win conditioned on its existence (Fishburn 1974c,a; Paris 1975; Gehrlein and Fishburn 1978; Newenhizen 1992).

Participation (PAR) was introduced to study voting rules that avoid the no-show paradox (Fishburn and Brams 1983). Moulin (1988) proved that when m 4 and n 25, no voting rule satisfies CC and PAR simultaneously. The bound on n was characterized to be 12 by simplified, SAT-solverbased proofs (Brandt, Geist, and Peters 2017; Peters 2019). The likelihood of PAR satisfaction by popular voting rules under IC was investigated in a series of work as summarized by Gehrlein and Lepelley (2011, Chapter 4.2.2), and also more recently by Brandt, Hofbauer, and Strobel (2021).

Half-way monotonicity (HM) was introduced to study voting rules that avoid the preference reversal paradox, and was proved to be incompatible with CC (Sanver and Zwicker 2009). Peters (2017) used SAT solvers to characterized the number of voters under which the impossibility holds.

Maskin monotonicity (MM) was introduced to characterize Nash implementability (Maskin 1999). The Muller Satterthwaite theorem (Muller and Satterthwaite 1977) establishes the equivalence between MM and SP in the worstcase sense: a voting rule satisfies MM if and only if it satisfies SP.

Strategy-proofness (SP) cannot be satisfied by any nondictatorial and unanimous voting rules when m 3, due to the Gibbard-Satterthwaite theorem (Gibbard 1973; Satterthwaite 1975). SP is stronger than HM, because the latter uses a special form of manipulation (by reversing the truthful vote). At a high-level, PAR can be viewed as a weak form of SP that prevents manipulation by abstention, though PAR is not weaker than SP by definition, because PAR reasons about elections of different sizes. A quantitative Gibbard Satterthwaite theorem (under IC) was proved for m = 3 by Friedgut et al. (2011), and was subsequently developed in (Dobzinski and Procaccia 2008; Xia and Conitzer 2008; Isaksson, Kindler, and Mossel 2010), and the case for general m was resolved by Mossel and Racz (2015).

Semi-random CC&PAR, CC&HM, CC&MM, and CC&SP. We are not aware of any semi-random impossibility theorem about the satisfaction of CC&PAR, CC&HM, or CC&MM, even under IC. For SP, the quantitative Gibbard-Satterthwaite theorem by Mossel and Racz (2015) establishes an 1 Ω( 1

n67 ) upper bound under IC for any voting rule that is sufficiently different from dictatorships. Therefore, the same bound holds for CC&SP for any rule that satisfies CC. The 1 Ω( B n) upper bound for CC&SP in our Theorem 4 also applies to all CC rules, which is stronger than the special case of (Mossel and Racz 2015), because our bound is lower and works for every B n under more general models. For possibility results (i.e., lower bound for optimal rules), as discussed in Section 1.1, our results imply that the bounds are tight for CC&PAR (when B = 1) and for CC&SP (when B n). We conjecture that they are tight for other axioms studied in this paper with all B n.

Quantitative and semi-random impossibilities. There is a large body of literature on quantitative impossibility theorems in social choice under IC. For example, quantitative

versions of Arrow s impossibility theorem (Arrow 1963) were proved (Kalai 2002; Mossel 2012; Keller 2012; Mossel, Oleszkiewicz, and Sen 2013). In judgement aggregation, Nehama (2013) and Filmus et al. (2020) developed quantitative characterizations of AND-homomorphism as oligarchy, whose worst-case version was due to List and Pettit (2002, 2004). Xia (2020) proved a semi-random version of the ANR impossibility theorem on anonymity and neutrality, whose worst-case version was proved by Moulin (1983).

Other smoothed/semi-random results. Semi-random models have been widely adopted to analyze the performance of algorithms in practice in combinatorial optimization (Blum and Spencer 1995), mathematical programming (Spielman and Teng 2004), machine learning (Blum and Dunagan 2002), and algorithmic game theory (Chung et al. 2008; Psomas, Schvartzman, and Weinberg 2019; Boodaghians et al. 2020; Blum and G olz 2021), etc. We refer the readers to recent surveys on semi-random models (Feige 2021) and general approaches beyond worstcase analysis (Roughgarden 2021). In addition to the work discussed above, semi-random/smoothed analysis has been applied to other social choice problems, e.g., likelihood of ties (Xia 2021a), complexity of winner determination (Xia and Zheng 2021), judgement aggregation (Liu and Xia 2022), and fair division (Bai et al. 2022).

2 Preliminaries For any q N, we let [q] = {1, . . . , q}. Let A = [m] denote the set of m 3 alternatives. Let L(A) denote the set of all linear orders over A. Let n N denote the number of voters (agents). Each voter uses a linear order R L(A) to represent his or her preferences, called a vote, where a R b means that the agent prefers alternative a to alternative b. The vector of n voters votes, denoted by P, is called a (preference) profile, sometimes called an n-profile. A voting rule r maps any profile to a single winner. For any profile P, let Hist(P) Rm! 0 denote the anonymized version of P, also called the histogram of P, which contains the total number of each linear order in L(A) according to P.

Weighted majority graphs and the Condorcet winner. For any profile P and any pair of alternatives (a, b), let P[a b] denote the number of votes in P where a is preferred to b. Let WMG(P) denote the weighted majority graph of P, whose vertices are A and whose weight on edge a b is w P (a, b) = P[a b] P[b a]. The Condorcet winner of a profile P is the alternative whose outgoing edges in WMG(P) are positively weighted.

Axioms. All axioms studied in this paper are per-profile axioms (Xia 2020), each of which is modeled as a function X that maps a voting rule r, a profile P, and a group size B 1 to {0, 1}, where 0 (respectively 1) means that r violates (respectively, satisfies) the axiom at P w.r.t. group size B. Then, the classical (worst-case) satisfaction of the axiom under r becomes min P X(r, P). For any voting rule, any profile P, and any B 1, Condorcet criterion is modeled as a function CC such that CC(r, P, B) = 1 if and only if either (1) there is no Con-

+2 [1234] +2 [4321]

-3 [2431] -2 [4312] -3 [3124]

P{1,2} P{3,4}

-3 [3124] -2 [1243] -3 [2431]

2 [1243] 3 [2431] 3 [3124] 2 [4312]

Figure 1: Proof diagram of CC&PAR impossibility (Peters 2019, Chapter 1). WMGs of the root and the leaves are shown (where all unweighted edges in the leaves have weight 1). Each edge represents a sequence of operations conditioned on the winner of the source profile being a highlighted alternative. Condorcet winners in the leaf nodes are highlighted.

dorcet winner under P, or (2) the Condorcet winner is the winner of P under r. Notice that technically CC does not depend on B, which is included for notational consistency. Participation is modeled by a function PAR such that PAR(r, P, B) = 1 if and only if no group of at most B voters have incentive to abstain from voting; otherwise PAR(r, P, B) = 0. Formally, PAR(r, P, B) = 0 if and only if there exists a subvector P of P such that |P | B and for all R P , r(P ) R r(P). The simultaneous satisfaction of CC and PAR is denoted by CC&PAR, such that CC&PAR(r, P, B) = 1 if and only if CC(r, P, B) = 1 and PAR(r, P, B) = 1. Due to the space constraint, we focus on presenting the result about CC&PAR in the main text. The formal definitions of other axioms, i.e., half-way monotonicity (HM), Maskin monotonicity (MM), and strategy-proofness (SP), and the simultaneous satisfaction of CC and them, i.e., CC&HM, CC&MM, and CC&SP, are deferred to Appendix ?? of the full version of this paper (Xia 2023).

Proof diagram of the CC&PAR impossibility. We briefly recall the proof diagram by Peters (2019, Chapter 1) in Figure 1 to show that when m = 4, no voting rule r satisfies CC&PAR, which will play an important role in our proofs later. Each edge represents a sequence of operations, conditioned on the winner of the source profile being highlighted. Peters (2019, Chapter 1) proved that a violation of CC and/or PAR exists in the diagram. Take the leftmost branch for example. If r(P0) {1, 2}, then two copies of [1234] are added one by one. If the winner is no longer 1 or 2 during this process, then PAR is violated. Otherwise, starting from P{1,2}, if r(P{1,2}) = {1}, then three votes of [2431] are subtracted one by one. If the winner is not 1 at any point, then PAR is violated. However, 3 is the Condorcet winner in the leaf node, which means that CC is violated if PAR has not been violated on the leftmost branch so far.

Semi-random satisfaction of axioms. Given a per-profile axiom X, a set Π of distributions over L(A), a voting rule r, n N, and a group size B, the semi-random satisfaction of X under r with n agents, denoted by e Xmin Π (r, n, B), is defined in Equation (1) in the Introduction. We note that the

min in the superscript means that the adversary aims at minimizing the satisfaction of X. The semi-random analysis generalizes the classical quantitative analysis in social choice (under IC). To see this, let πuni denote the uniform distribution over L(A) and let ΠIC = {πuni}. Then, e Xmin ΠIC becomes the likelihood of satisfaction of X under IC. Throughout the paper, we make the following assumptions on Π. Assumption 1 We assume that Π is strictly positive, which means that there exists ϵ > 0 such that for every π Π and every R L(A), π(R) ϵ; closed, which means that Π is a closed subset of the probability simplex in Rm!; and πuni CH(Π), where CH(Π) is the convex hull of Π. The first part of Assumption 1 requires that no distribution in Π is too deterministic . The second part is a mild technical assumption. The first two parts guarantee that the semirandom analysis using Π is sufficiently different from the worst-case analysis. The third part requires that the uniform distribution πuni is in the convex hull of Π, though πuni itself may not be in Π. We believe that Assumption 1 is mild, because it is satisfied by many classical models for preferences. For example, it is satisfied by IC, which corresponds to Π = {πuni}, and the models in the following example, which is taken from (Xia 2020). Example 1 In the single-agent Mallows with bounded dispersion, given φ > 0, each distribution is parameterized by a central ranking W L(A) and a dispersion φ [φ, 1], such that the probability for R L(A) is proportional to φKT(R,W ), where KT(R, W) is the total number of pairwise differences between R and W, i.e., the Kendall-Tau distance. In the single-agent Plackett-Luce with bounded parameters, given φ > 0, each distribution is parameterized by a vector θ [φ, 1]m such that θ 1 = 1. The probability for R = a1 a2 am is Qm 1 i=1 (θai/Pm ℓ=i θaℓ). If φ = 0 is allowed in Example 1, then the semi-random analysis degenerates to worst-case analysis, which trivializes the question.

! " # flip(B [2431])

$ " # flip(B [4312])

! " # flip(B [3124])

$ " # flip(B [1243])

! " # flip(B [2431])

! " # flip(B [3124])

$ " # flip(B [4321])

$ " # flip(B [1234])

Figure 2: The violation template. represents the upper and lower bounds on the weight. ℓ flip(B R) represents ℓ operations, each of which flips B votes that are R. In the leaves, weights are not shown and Condorcet winners are highlighted.

3 Semi-random Impossibility of CC and PAR Theorem 1 (CC+Participation) For any fixed m 4, any Π that satisfies Assumption 1, any voting rule r, any n 12, and any 1 B n, CC&PAR min

Π (r, n, B) = 1 Ω B n

The theorem is more general than its classical, worst-case counterpart, as the likelihood is strictly smaller than 1. It is also more general than its quantitative counterparts (under IC), because the latter is a special case of the former, where Π = {πuni}, as discussed in the last section.

3.1 Proof sketch of Theorem 1

Overview. To illustrate the idea, we make the following assumptions in the proof sketch: (i) m = 4, (ii) n is an integer, (iii) B | n, and (iv) m! | n. In addition, it suffices to prove the theorem when n 12 and is sufficiently large, because the (worst-case) impossibility theorem holds for every n 12 (Brandt, Geist, and Peters 2017; Peters 2019). The proof for the general case can be found in Appendix ??. Let PARB denote the group version of participation with

size B. Instead of upper-bounding CC&PAR min

Π , we will

lower-bound its complement (CC&PAR) max

Π as Ω( B n), which is the max-semi-random likelihood for CC or PARB to be violated and is defined similarly to e Xmin Π in (1), except that inf is replaced by sup. The theorem then follows after noticing CC&PAR min

Π (r, n, B) = 1 (CC&PAR) max

Π (r, n, B) As discussed in Section 1.1, the proof proceeds in two steps. In step 1, we identify a set of n-profiles, denoted by Vn,B, where CC or PARB is violated, and prove that Vn,B contains sufficiently many profiles. This will be achieved by first scaling the (worst-case) proof diagram in (Peters 2019, Chapter 1), i.e., Figure 1 in Section 2, by a factor of n to define a violation template, and then implementing it at profiles whose histograms are in an O( n) neighborhood of

n m! 1. Each implementation leads to a violation tree, which contains at least one violation of CC or PARB. Then, we upper-bound the number of violation trees any profile P Vn,B can be on, by considering the rotated trees generated by the rotated template rooted at P . Then in step 2, we prove that there exists π Πn so that the likelihood of Vn,B found in step 1 is lower-bounded by Ω( B n). This is achieved by starting with a π Πn such that Pn j=1 πj is O(1) away from n m! 1, and then considering the sum of likelihood of Vn,B under all n! permutations of components in π. This converts the likelihood of Vn,B to the likelihood about the histogram of a randomly-generated profile. Finally, we apply the point-wise concentration bound (Xia 2021a, Lemma 1) to derive the desired lower bound.

Step 1. We first formally define the violation template illustrated in Figure 2.

Definition 1 (Violation template) Given any n-profile P with at least 7 n copies of L(A) and any 1 B n, a violation template is defined by modifying the proof diagram (Figure 1) as follows, where Rev (R) denote the reverse ranking of R, also called the flip of R:

every +R operation on an edge in Figure 1 is replaced by a sequence of n

B operations, each of which flips B Rev (R) votes and is denoted by flip(B Rev (R)); every R operation on an edge in Figure 1 is replaced by a sequence of n

B operations, each of which flips B R votes and is denoted by flip(B R).

The violation template will be implemented multiple times, by letting its root to be n-profiles whose WMGs are similar to the WMG at the root in Figure 1 (scaled by a factor of n) and whose histograms are close to n m! 1. Formally, we define the set of such profiles P, denoted by Pn, as follows. Let w(e) denote the weight on edge e in the root of Figure 1.

Definition 2 Let Pn denote the set of n-profiles P such that

for every edge e [4] [4], |w P (e) n w(e)| n;

! " # flip(B [1342])

$ " # flip(B [3124])

! " # flip(B [1234])

! " # flip(B [1234])

" # flip(B [2431])

! " # flip(B [1243])

$ " # flip(B [2431]) P*

! " # flip(B [4312])

$ " # flip(B [3124])

Figure 3: A rotated template rooted at P . Reversed edges and rankings are highlighted.

|Hist(P) n m! 1| 4 n.

We note that any flip operation in the violation template does not completely specify the set of voters whose votes should be flipped (except that their votes must be the same as the designated ranking). Consequently, different combinations of votes when implementing the violation template lead to different violation trees, formally defined as follows.

Definition 3 (Violation trees) For any P Pn and any 1 B n, a violation tree is a tree of 20 n

B + 1 profiles obtained from implementing the violation template rooted at P. Let TP,B denote the set of all violation trees rooted at P.

For example, in a violation tree rooted at P Pn, the leftmost branch of Figure 2 consists of profiles P, P1, .. . , P 2 n

B , .. . , P 1 , .. . , P 3 n

B , such that each Pj is

obtained from Pj 1 by flipping B votes of [4321] (where P0 = P); and each P j is obtained from P j 1 by flipping B votes of [2431] (where P 0 = P 2 n

B ). The following claim lower-bounds the size of TP,B. All missing proofs can be found in the appendix.

Claim 1 For any P Pn and any 1 B n, |TP,B| = Ω(( n m! B

The next claim states that each violation tree contains a violation of CC or PARB.

Claim 2 For every P Pn and every T TP,B, CC or PARB is violated in T.

Let Vn,B denote the set of all profiles on violation trees S P Pn TP,B, where CC or PARB is violated. The next claim upper-bounds the number of violation trees that each profile in Vn,B can possibly be on.

Claim 3 Every P Vn,B is on no more than O( n

B!)20 n) violation trees rooted in Pn.

Proof sketch. The proof is done by defining a rotated template rooted at every node V in the violation template, which reverses all edges along the path from the root to V . That is, an edge V1 V2 along the path that flips B R becomes V1 V2 in the rotated template that flips B Rev (R). Consequently, the rotated template is a diagram rooted at V . Because each violation template has 20 n

B + 1 nodes, there

B + 1 rotated templates. Figure 3 illustrates a rotated template rooted at a node in the leftmost branch. Then, Claim 3 is proved by upper-bounding the number of rotated trees obtained by applying the rotated template, which provides an upper bound on the violation trees rooted in Pn that contains P . We are now ready to lower-bound |Vn,B|. To this end, we count the number of (profile, violation tree) pairs, denoted by (P, T), where T is rooted at a profile in Pn, P is on T, and CC and/or PARB is violated at P. By Claim 1 and Claim 2, the total number of such (profile, violation tree)

pairs is at least |Pn| Ω n m! B

20 n . By Claim 3,

the total number of such (profile, violation tree) pairs is at

most |Vn,B| O n

20 n . Therefore,

|Pn| Ω n m! B

20 n = Ω B n

Step 2. Let π Πn be such that Pn j=1 πj is O(1) away from

n m! 1, which can be defined by rounding as shown in (Xia 2021a). Let Sn denote the set of all permutations over [n]. For any permutation η Sn, let η( π) denote the vector of distributions where the indices are permuted according to η. That is, η( π) = (πη(1), . . . , πη(n)). We prove that there exists a permutation η over [n], such that

Pr P η( π)(P Vn,B) = Ω( B n) (3)

It suffices to prove that the sum of the left hand side of (3) for all η Sn is at least n! times the right hand side of (3), that is, X

η Sn Pr P η( π)(P Vn,B) = Ω(n! B n) (4)

Nevertheless, (4) is still hard to prove due to the lack of information about the profiles in Vn,B. The key insight of our proof is to convert the left hand side of (4) to probabilities for the histogram of P to be the histograms of profiles in

Vn,B. Notice that the left hand side of (4) is equivalent to X

P Vn,B Pr P η( π)(P = P )

η Sn Pr P π(P = η 1(P ))

R L(A)(n R!)

Pr P π(Hist(P) = Hist(P )), (5)

where n R is the number of R votes in P . (5) follows the following claim, whose proof can be found in Appendix ??. Claim 4 For any P Vn,B, X

η Sn Pr P π(P = η 1(P )) = Y

R L(A)(n R!) Pr P π(Hist(P) = Hist(P ))

Because Hist(P ) is 7 n away from n m! 1, we have Q R L(A)(n R!) = Θ n

m! ! . By the point-wise concentration lemma (Xia 2021a, Lemma 1), the likelihood for the histogram of P to be any x in an O( n) neighborhood of Pn j=1 πj is Ω(n(1 m!)/2). Recall that Pn j=1 πj is O(1) away from n m! 1. Therefore, for every P Vn,B,

Pr P π(Hist(P) = Hist(P )) = Ω(n(1 m!)/2) (6)

Combining (2), (5), and (6), the left hand side of (4) becomes

! n(1 m!)/2

! |Pn| n(1 m!)/2 (7)

Next, we lower-bound |Pn| in the following claim, whose proof is in Appendix ??.

Claim 5 |Pn| = Ω( n! ( n

m!)! n(m! 1)/2).

Finally, (4) follows after (7) and Claim 5, which completes the proof for the special case of Theorem 1.

4 Other Semi-random Impossibilities The proof of Theorem 1 can leverage any proof diagram like Figure 1, that has the following three high-level features: 1. The diagram consists of constantly many nodes. 2. The diagram works all slightly perturbed root profiles. 3. X is violated in each violation tree (scaled by n) . Therefore, any existing proof diagram for CC&PAR, e.g., the one used in (Brandt, Geist, and Peters 2017), can be used to prove Theorem 1. We chose the diagram in (Peters 2019, Chapter 1) for its simplicity. In this section, we prove semi-random impossibilities for the other three combinations of axioms, i.e., CC&HM, CC&MM, and CC&SP, by leveraging existing proof diagrams that have the three aforementioned features. Theorem 2 (CC+half-way monotonicity) For any fixed m 4, any Π that satisfies Assumption 1, any voting rule r, any n 24, and any 1 B n, CC&HM min

Π (r, n, B) = 1 Ω B n

The proof leverages the same diagram (Peters 2019, Chapter 1) as in the proof of Theorem. The only difference is to verify that it has the third feature above. The full proof can be found in Appendix ??.

Theorem 3 (CC+Maskin monotonicity) For any fixed m 3, any Π that satisfies Assumption 1, any voting rule r, any n N, and any 1 B n, CC&MM min

Π (r, n, B) = 1 Ω B n

The theorem is proved by leveraging a simple proof diagram rooted at profiles that have a (Condorcet) cycle over 3 alternatives in the WMG, where votes are changed to make certain alternatives the Condorcet winner in the leaves. The full proof can be found in Appendix ??.

Theorem 4 (CC+strategy-proofness) For any fixed m 3, any Π that satisfies Assumption 1, any voting rule r, any n N, and any 1 B n, CC&SP min

Π (r, n, B) = 1 Ω B n

When m 4, Theorem 4 follows after Theorem 2, as SP is stronger than HM. The proof (for all m 3) uses the same diagram for Theorem 3 and can be found in Appendix ??. Recall that IC corresponds to Π = {πuni}. Therefore, all semi-random impossibilities in this paper hold for IC.

Corrollary 1 (Quantitative Impossibilities under IC) For any X {CC&PAR, CC&HM, CC&MM, CC&SP}, any m 4 (m 3 for CC&MM and CC&SP), any voting rule r, any sufficiently large n N, and any 1 B n,

Pr P IC X(r, P, B) = 1 Ω B n

Corollary 1 also implies that for any voting rule that satisfies CC, the likelihood for r to satisfy PAR, HM, MM, or SP, respectively, is Ω B n under IC.

5 Summary and Future Work We prove the first set of semi-random impossibility results involving CC, showing that many existing voting rules are already optimal for CC&PAR (for B = 1) and CC&SP (for every B n). The proof technique has potential to strengthen other worst-case impossibilities to their semirandom variants. For future work, we conjecture that all bounds for the axioms are tight and can be achieved by many rules that satisfy CC. How to strengthen the theorems by studying variable m and allowing ϵ to depend on n are natural open questions. Other promising directions include addressing the limitations discussed in Section 1.2 and proving semi-random variants of other worst-case impossibility results, such as Arrow s, Gibbard-Satterthwait (for non-CC rules), and various impossibility theorems in judgement aggregation. The proof technique developed in this paper (see Section 4) does not seem to be directly applicable, because existing proofs use diagrams that contains Θ(n) nodes. Studying the empirical likelihood of the impossibility results in practice, for example on Preflib data (Mattei and Walsh 2013) and considering probabilistic versions of domain restrictions are promising future directions as well.

Acknowledgements We thank anonymous reviewers and Dominik Peters for helpful comments. This work is supported by NSF #1453542, #2007994, and #2106983, and a Google Research Award.

References Arrow, K. 1963. Social choice and individual values. New Haven: Cowles Foundation, 2nd edition. 1st edition 1951. Bai, Y.; Feige, U.; G olz, P.; and Procaccia, A. D. 2022. Fair Allocations for Smoothed Utilities. In Proceedings of ACM EC. Baumeister, D.; Hogrebe, T.; and Rothe, J. 2020. Towards Reality: Smoothed Analysis in Computational Social Choice. In Proceedings of AAMAS, 1691 1695. Berry, S.; Levinsohn, J.; and Pakes, A. 1995. Automobile Prices in Market Equilibrium. Econometrica, 63(4): 841 890. Blum, A.; and Dunagan, J. D. 2002. Smoothed Analysis of the Perceptron Algorithm for Linear Programming. In Proceedings of SODA, 905 914. Blum, A.; and G olz, P. 2021. Incentive-Compatible Kidney Exchange in a Slightly Semi-Random Model. In Proceedings of ACM EC. Blum, A.; and Spencer, J. 1995. Coloring Random and Semi-Random k-Colorable Graphs. Journal of Algorithms, 19(2): 204 234. Boodaghians, S.; Brakensiek, J.; Hopkins, S. B.; and Rubinstein, A. 2020. Smoothed Complexity of 2-player Nash Equilibria. In Proceedings of FOCS. Brandt, F.; Geist, C.; and Peters, D. 2017. Optimal bounds for the no-show paradox via SAT solving. Mathematical Social Sciences, 90: 18 27. Brandt, F.; Hofbauer, J.; and Strobel, M. 2021. Exploring the No-Show Paradox for Condorcet Extensions. In Diss, M.; and Merlin, V., eds., Evaluating Voting Systems with Probability Models. Springer. Chung, C.; Ligett, K.; Pruhs, K.; and Roth, A. 2008. The Price of Stochastic Anarchy. In International Symposium on Algorithmic Game Theory, 303 314. Condorcet, M. d. 1785. 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. Diss, M.; and Merlin, V., eds. 2021. Evaluating Voting Systems with Probability Models. Studies in Choice and Welfare. Springer International Publishing. Dobzinski, S.; and Procaccia, A. D. 2008. Frequent Manipulability of Elections: The Case of Two Voters. In Proceedings of the Fourth Workshop on Internet and Network Economics (WINE), 653 664. Shanghai, China. Feige, U. 2021. Introduction to Semi-Random Models. In Roughgarden, T., ed., Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press. Filmus, Y.; Lifshitz, N.; Minzer, D.; and Mossel, E. 2020. AND testing and robust judgement aggregation. In Proceedings of STOC.

Fishburn, P. C. 1974a. Aspects of One-Stage Voting Rules. Management Science, 21(4): 422 427. Fishburn, P. C. 1974b. Paradoxes of Voting. The American Political Science Review, 68(2): 537 546. Fishburn, P. C. 1974c. Simple voting systems and majority rule. Behavioral Science, 19(3): 166 176. Fishburn, P. C.; and Brams, S. J. 1983. Paradoxes of Preferential Voting. Mathematics Magazine, 56(4): 207 214. Friedgut, E.; Kalai, G.; Keller, N.; and Nisan, N. 2011. A Quantitative Version of the Gibbard-Satterthwaite theorem for Three Alternatives. SIAM Journal on Computing, 40(3): 934 952. Gehrlein, W. V.; and Fishburn, P. C. 1978. Coincidence probabilities for simple majority and positional voting rules. Social Science Research, 7(3): 272 283. Gehrlein, W. V.; and Lepelley, D. 2011. Voting Paradoxes and Group Coherence: The Condorcet Efficiency of Voting Rules. Springer. Gibbard, A. 1973. Manipulation of voting schemes: A general result. Econometrica, 41: 587 601. Isaksson, M.; Kindler, G.; and Mossel, E. 2010. The Geometry of Manipulation: A Quantitative Proof of the Gibbard Satterthwaite Theorem. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), 319 328. Washington, DC, USA. Kalai, G. 2002. A Fourier-theoretic perspective on the Condorcet paradox and Arrow s theorem. Advances in Applied Mathematics, 29(3): 412 426. Keller, N. 2012. A tight quantitative version of Arrow s impossibility theorem. Journal of the European Mathematical Society, 14: 1331 1355. List, C.; and Pettit, P. 2002. Aggregating sets of judgments: An impossibility result. Economics and philosophy, 18(1): 89 110. List, C.; and Pettit, P. 2004. Aggregating Sets of Judgments: Two Impossibility Results Compared. Synthese, 140: 207 235. Liu, A.; and Xia, L. 2022. The Semi-Random Likelihood of Doctrinal Paradoxes. In Proceedings of AAAI. Maskin, E. 1999. Nash Equilibrium and Welfare Optimality. Review of Economic Studies, 66: 23 38. Mattei, N.; and Walsh, T. 2013. Pref Lib: A Library of Preference Data. In Proceedings of Third International Conference on Algorithmic Decision Theory, Lecture Notes in Artificial Intelligence. Mossel, E. 2012. A quantitative Arrow theorem. Probability Theory and Related Fields, 154: 49 88. Mossel, E.; Oleszkiewicz, K.; and Sen, A. 2013. On reverse hypercontractivity. Geometric and Functional Analysis, 23(3): 1062 1097. Mossel, E.; and Racz, M. Z. 2015. A quantitative Gibbard Satterthwaite theorem without neutrality. Combinatorica, 35(3): 317 387. Moulin, H. 1983. The Strategy of Social Choice. Elsevier.

Moulin, H. 1988. Condorcet s principle implies the no show paradox. Journal of Economic Theory, 45(1): 53 64. Muller, E.; and Satterthwaite, M. 1977. The Equivalence of Strong Positive Association and Strategy-proofness. Journal of Economic Theory, 14: 412 418. Nehama, I. 2013. Approximately classic judgement aggregation. Annals of Mathematics and Artificial Intelligence, 68: 91 134. Newenhizen, J. V. 1992. The Borda Method Is Most Likely to Respect the Condorcet Principle. Economic Theory, 2(1): 69 2 83. Paris, D. C. 1975. Plurality distortion and majority rule. Behavioral Science, 20(2): 125 133. Pattanaik, P. K. 1978. Strategy and group choice. Elsevier North-Holland. Peters, D. 2017. Condorcet s principle and the preference reversal paradox. In Proceedings of TARK. Peters, D. 2019. Fair Division of the Commons. Ph.D. thesis, Oxford University. Psomas, A.; Schvartzman, A.; and Weinberg, M. S. 2019. Smoothed Analysis of Multi-Item Auctions with Correlated Values. In Proceedings of ACM EC. Roughgarden, T. 2021. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press. Saari, D. G. 1995. Basic Geometry of Voting. Springer. Sanver, M. R.; and Zwicker, W. S. 2009. One-way monotonicity as a form of strategy-proofness. International Journal of Game Theory, 38: 553 574. Satterthwaite, M. 1975. Strategy-proofness and Arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10: 187 217. Spielman, D. A.; and Teng, S.-H. 2004. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3). Spielman, D. A.; and Teng, S.-H. 2009. Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice. Communications of the ACM, 52(10): 76 84. Thurstone, L. L. 1927. A law of comparative judgement. Psychological Review, 34(4): 273 286. Train, K. E. 2009. Discrete Choice Methods with Simulation. Cambridge University Press, 2nd edition. Xia, L. 2020. The Smoothed Possibility of Social Choice. In Proceedings of Neur IPS. Xia, L. 2021a. How Likely Are Large Elections Tied? In Proceedings of ACM EC. Xia, L. 2021b. The Semi-Random Satisfaction of Voting Axioms. In Proceedings of Neur IPS. Xia, L. 2022. How Likely A Coalition of Voters Can Influence A Large Election? ar Xiv:2202.06411. Xia, L. 2023. Semi-Random Impossibilities of Condorcet Criterion. ar Xiv:2107.06435.

Xia, L.; and Conitzer, V. 2008. A Sufficient Condition for Voting Rules to Be Frequently Manipulable. In Proceedings of the ACM Conference on Electronic Commerce (EC), 99 108. Chicago, IL, USA. Xia, L.; and Zheng, W. 2021. The Smoothed Complexity of Computing Kemeny and Slater Rankings. In Proceedings of AAAI.