# the_semirandom_satisfaction_of_voting_axioms__f127c139.pdf

The Semi-Random Satisfaction of Voting Axioms

Lirong Xia RPI, Troy, NY 12180, USA xialirong@gmail.com

We initiate the work towards a comprehensive picture of the worst average-case satisfaction of voting axioms in semi-random models, to provide a ﬁner and more realistic foundation for comparing voting rules. We adopt the semi-random model and formulation in [54], where an adversary chooses arbitrarily correlated ground truth preferences for the agents, on top of which random noises are added. We focus on characterizing the semi-random satisfaction of two well-studied voting axioms: Condorcet criterion and participation. We prove that for any ﬁxed number of alternatives, when the number of voters n is sufﬁciently large, the semirandom satisfaction of the Condorcet criterion under a wide range of voting rules is 1, 1 exp( Θ(n)), Θ(n 0.5), exp( Θ(n)), or being Θ(1) and 1 Θ(1) at the same time; and the semi-random satisfaction of participation is 1 Θ(n 0.5). Our results address open questions by Berg and Lepelley [3] in 1994, and also conﬁrm the following high-level message: the Condorcet criterion is a bigger concern than participation under realistic models.

1 Introduction

The widespread presence of impossibility results [48] is one of the most fundamental and significant challenges in social choice theory. These impossibility results often assert that no perfect voting rule exists for three or more alternatives [1, 28, 45]. Nevertheless, an (imperfect) voting rule must be designed and used in practice for agents to make a collective decision. In the social choice literature, the dominant paradigm of doing so has been the axiomatic approach, i.e., voting rules are designed, evaluated, and compared to each other w.r.t. their satisfaction of desirable normative properties, known as (voting) axioms.

Most deﬁnitions of dissatisfaction of voting axioms are based on worst-case analysis. For example, a voting rule r does not satisfy CONDORCET CRITERION (CC for short), if there exists a collection of votes, called a proﬁle, where the Condorcet winner exists but is not chosen by r as a winner. The Condorcet winner is the alternative who beats all other alternatives in their head-to-head competitions. As another example, a voting rule r does not satisfy PARTICIPATION (PAR for short), if there exists a proﬁle and a voter who has incentive to abstain from voting. An instance of dissatisfaction of PAR is also known as the no-show paradox [19]. Unfortunately, when the number of alternatives m is at least four, no irresolute voting rule satisﬁes CC and PAR simultaneously [39].

While the classical worst-case analysis of (dis)satisfaction of axioms can be desirable in high-stakes applications such as political elections, it is often too coarse to serve as practical criteria for comparing different voting rules in more frequent, low-stakes applications of social choice, such as business decision-making [5], crowdsourcing [34], informational retrieval [33], meta-search engines [14], recommender systems [51], etc. A decision maker who desires both axioms would ﬁnd it hard to choose between a voting rule that satisﬁes CC but not PAR, such as Copeland, and a voting rule that satisﬁes PAR but not CC, such as plurality. A ﬁner and more quantitative measure of satisfaction of axioms is therefore called for.

35th Conference on Neural Information Processing Systems (Neur IPS 2021).

One natural and classical approach is to measure the likelihood of satisfaction of axioms under a probabilistic model of agents preferences, in particular the independent and identically distributed (i.i.d.) uniform distribution over all rankings, known as Impartial Culture (IC) in social choice. This line of research was initiated and established by Gehrlein and Fishburn in a series of work in the 1970 s [24, 26, 25], and has become a new sub-domain of the theory of social choice [13]. Some classical results were summarized in the 2011 book by Gehrlein and Lepelley [27], and recent progresses can be found in the 2021 book edited by Diss and Merlin [13].

While this line of work is highly signiﬁcant and interesting from a theoretical point of view, its practical implications may not be as strong, because most previous work focused on a few speciﬁc distributions, especially IC, which has been widely criticized to be unrealistic (see, e.g., [42, p. 30], [23, p. 104], and [30]). Indeed, conclusions drawn under any speciﬁc distribution may not hold in practice, as all models are wrong [9]. Technically, characterizing the likelihood of satisfaction of CC and of PAR are already highly challenging w.r.t. IC, and despite that Berg and Lepelley [3] explicitly posed them as open questions in 1994, not much is known beyond a few voting rules. Therefore, the following question largely remains open.

How likely are voting axioms satisﬁed under realistic models?

The importance of successfully answering this question is two-fold. First, it tells us whether the worst-case violation of an axiom is a signiﬁcant concern in practice. Second, it provides a ﬁner and more quantitative foundation for comparing voting rules.

We believe that the semi-random models [15], originally investigated by Blum [7] and [8] and includes the models employed in the celebrated smoothed analysis proposed by Spielman and Teng [49], provides a promising framework for addressing the question. In this paper, we adopt the semirandom model by Xia [54], which models the satisfaction of a per-proﬁle voting axiom X by a function X(r, P) {0, 1}, where r is a voting rule and P is a proﬁle, such that r satisﬁes X if min P X(r, P) = 1. Let Π denote a set of distributions over all rankings over the m alternatives (denoted by L(A)), which represents the ground truth preferences for a single agent that the adversary can choose from. Let n denote the number of agents. Because a higher value of X(r, P) is more desirable to the decision maker, the adversary aims at minimizing expected X(r, P) by choosing π Πn the proﬁle P is generated from π. The semi-random satisfaction of X under r with n agents, denoted by e Xmin Π (r, n), is deﬁned as follows [54]:

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

Notice that agents ground truth preferences can be arbitrarily correlated, while the noises are independent, which is a standard assumption in the literature and in practice [54].

Example 1 (Semi-Random CC under plurality). Let X = CC and r = Plu denote the irresolute plurality rule, which chooses all alternatives that are ranked at the top most often as the (co-)winners. Suppose there are three alternatives, denoted by A = {1, 2, 3}, and suppose Π = {π1, π2}, where π1 and π2 are distributions shown in Table 1.

Then, we have f CC min Π (Plu, n) = inf π {π1,π2}n Pr P π CC(Plu, P). When n = 2, the adversary has four choices of π, i.e., {(π1, π1), (π1, π2), (π2, π1), (π2, π2)}.

123 132 231 321 213 312 π1 1/4 1/4 1/8 1/8 1/8 1/8 π2 1/8 1/8 3/8 1/8 1/8 1/8

Table 1: Π in Example 1.

Each π leads to a distribution over the set of all proﬁles of two agents, i.e., L(A)2. We have f CC min Π (Plu, 2) = 1, because CC is satisﬁed at all proﬁles of two agents. As we will see later in

Example 3, for all sufﬁciently large n, f CC min Π (Plu, n) = exp( Θ(n)).

1.1 Our Contributions

We initiate the work towards a comprehensive picture of semi-random satisfaction of voting axioms under commonly-studied voting rules, by focusing on CC and PAR in this paper due to their importance, popularity, and incompatibility [39]. Recall that m is the number of alternatives and n is the number of agents. Our technical contributions are two-fold.

First, semi-random satisfaction of CC (Theorem 1 and 2). We prove that, under mild assumptions, for any ﬁxed m 3 and any sufﬁciently large n, the semi-random satisfaction of CC under a wide range of voting rules is 1, 1 exp( Θ(n)), Θ(n 0.5), exp( Θ(n)), or being Θ(1) and 1 Θ(1) at the same time (denoted by Θ(1) (1 Θ(1))). The 1 exp( Θ(n)) case is positive news, because it states that CC is satisﬁed almost surely when n is large, regardless of the adversary s choice. The remaining three cases are negative news, because they state that the adversary can make CC to be violated with non-negligible probability, no matter how large n is.

Second, semi-random satisfaction of PAR (Theorems 3, 4, 5, 6). We prove that, under mild assumptions, for any ﬁxed m 3 and any sufﬁciently large n, the semi-random satisfaction of PAR under a wide range of voting rules is 1 Θ(n 0.5). These are positive news, because they state that PAR is satisﬁed almost surely for large n, regardless of the adversary s choice. While this message may not be surprising at a high level, as the probability for a single agent to change the winner vanishes as n , the theorems are useful and non-trivial, as they provide asymptotically tight rates.

In particular, straightforward corollaries of our theorems to IC address open questions posed by Berg and Lepelley [3] in 1994, and also provides a mathematical justiﬁcation of two common beliefs related to PAR: ﬁrst, IC exaggerates the likelihood for paradoxes to happen, and second, the dissatisfaction of PAR is not a signiﬁcant concern in practice [31], especially when it is compared to our results on semi-random CC. Table 2 summarizes corollaries of our results under some commonlystudied voting rules w.r.t. IC as well as the satisfaction of CC and PAR on Preﬂib data [35], where Θ(1) (1 Θ(1)) means that there exists constants 0 < α < β 1 that do not depend on n, such that the likelihood is in [α, β].

Table 2: Satisfaction of CC and PAR w.r.t. IC and w.r.t. 315 Preﬂib proﬁles of linear orders under elections category. Experimental results are presented in Appendix G.

Axiom Plu. Borda Veto STV Black MM Sch. RP Copeland0.5

Theory CC Θ(1) (1 Θ(1)) always satisﬁed PAR always satisﬁed 1 Θ n 0.5

Preﬂib CC 96.8% 92.4% 74.2% 99.7% 100% 100% 100% 100% 100% PAR 100% 100% 100% 99.7% 99.4% 100% 100% 100% 99.7%

Table 2 provides a more quantitative way of comparing voting rules. Suppose the decision maker puts 50% weight (or any ﬁxed non-zero ratio) on both CC and PAR, and assume that the preferences are generated from IC. Then, when n is sufﬁciently large, the last ﬁve voting rules in the table (that satisfy CC) outperform the ﬁrst ﬁve voting rules in the table (the ﬁrst four satisﬁes PAR).

Beyond CC and PAR. Theorems 1 6 are proved by (non-trivial) applications of a categorization lemma (Lemma 1), which characterizes semi-random satisfaction of a large class of axioms that can be represented by unions of ﬁnitely many polyhedra, including CC and PAR. We believe that Lemma 1 is a promising tool for analyzing other axioms in future work.

1.2 Related Work and Discussions

The Condorcet criterion (CC) was proposed by Condorcet in 1785 [11], has been one of the most classical and well-studied axioms, and has nearly universal acceptance [44, p. 46]. CC is satisﬁed by many commonly-studied voting rules, except positional scoring rules [18] and multiround-score-based elimination rules, such as STV. Most previous work focused on characterizing the Condorcet efﬁciency, which is the probability for the Condorcet winner to win conditioned on its existence [17, 16, 43, 25, 40]. Beyond positional scoring rules, the study was mostly based on computer simulations, see, e.g., [20, 21, 37, 41].

The participation axiom (PAR) was motivated by the no-show paradox [19] and was proved to be incompatible with CC for every m 4 [39]. The likelihood of PAR under commonly studied voting rules w.r.t. IC was posed as an open question by Berg and Lepelley [3] in 1994, and has been investigated in a series of works including [32, 31, 52], see [27, Chapter 4.2.2]. In particular, Lepelley and Merlin [31] analyzed the likelihood of various no-show paradoxes for three alternatives under scoring runoff rules, which includes STV, w.r.t. IC and other distributions, and strongly believe that the no-show paradox is not an important ﬂaw of the scoring run-off voting systems .

Our work vs. previous work on CC and PAR. Our results address open questions by Berg and Lepelley [3] about the likelihood of satisfaction of CC and PAR in two dimensions: ﬁrst, we conduct semi-random analysis, which extends i.i.d. models and is believed to be signiﬁcantly more general and realistic. Second, our results cover a wide range of voting rules whose likelihood of satisfaction under CC or PAR even w.r.t. IC were not mathematically characterized before, including CC under STV, and PAR under maximin, Copeland, ranked pairs, Schulze, and Black s rule. While all results in this paper assume that the number of alternatives m is ﬁxed, they are already more general than many previous work that focused on m = 3.

Semi-random analysis. There is a large body of literature on the applications of semi-random analysis, especially smoothed analysis, to computational problems [50]. Its main idea, i.e., the worst average-case analysis, has been proposed and investigated in other disciplines as well. For example, it is the central idea in frequentist statistics (as in the frequentist expected loss and minimax decision rules [4]) and is also closely related to the min of means criteria in decision theory [29].

Recently, Baumeister et al. [2] and Xia [54] independently proposed to conduct smoothed analysis in social choice. We adopt the framework in the latter work, though our motivation and goal are quite different. We aim at providing a comprehensive picture of semi-random satisfaction of voting axioms, while [54] focused on analyzing semi-random likelihood of Condorcet s voting paradox and an impossibility on anonymity and neutrality. On the technical level, while Lemma 1 is a straightforward corollary of [55, Theorem 2], applications of results like Lemma 1 can be highly non-trivial and problem dependent as commented in [55], which is the case of this paper. We believe that Lemma 1 s main merit is conceptual, as it provides a general categorization of semi-random satisfaction of a large class of per-proﬁle axioms beyond CC and PAR for future work.

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 agents (voters). Each agent 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 agents votes, denoted by P, is called a (preference) proﬁle, sometimes called an n-proﬁle. The set of n-proﬁles for all n N is denoted by L(A) = S n=1 L(A)n. A fractional proﬁle is a proﬁle P coupled with a possibly non-integer and/or negative weight vector ωP = (ωR : R P) Rn for the votes in P. It follows that a non-fractional proﬁle is a fractional proﬁle with uniform weight, namely ωP = 1. Sometimes the weight vector is omitted when it is clear from the context or when ωP = 1.

For any (fractional) proﬁle P, let Hist(P) Rm! 0 denote the anonymized proﬁle of P, also called the histogram of P, which contains the total weight of every linear order in L(A) according to P. An irresolute voting rule r : L(A) (2A \ { }) maps a proﬁle to a non-empty set of winners in A. A resolute voting rule r is a special irresolute voting rule that always chooses a single alternative as the (unique) winner. We say that a voting rule r is a reﬁnement of another voting rule r, if for every proﬁle P, r(P) r(P).

(Un)weighted majority graphs and (weak) Condorcet winners. For any (fractional) proﬁle P and any pair of alternatives a, b, let P[a b] denote the total weight 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]. Let UMG(P) denote the unweighted majority graph, which is the unweighted directed graph that is obtained from WMG(P) by keeping the edges with strictly positive weights. Sometimes a distribution π over L(A) is viewed as a fractional proﬁle, where for each R L(A) the weight on R is π(R). In such cases, we let WMG(π) denote the weighted majority graph of the fractional proﬁle represented by π.

The Condorcet winner of a proﬁle P is the alternative that only has outgoing edges in UMG(P). A weak Condorcet winner is an alternative that does not have incoming edges in UMG(P). Let CW(P) and WCW(P) denote the set of Condorcet winners and weak Condorcet winners in P, respectively. Notice that CW(P) WCW(P) and |CW(P)| 1. The domain of CW( ) and WCW( ) can be naturally extended to all weighted or unweighted directed graphs.

For example, a distribution ˆπ, WMG(ˆπ), and UMG(ˆπ) for m = 3 are illustrated in Figure 1. We have CW(ˆπ) = and WCW(ˆπ) = {1, 2}. As another example, let πuni denote the uniform

distribution over L(A). Then, the weight on every edge in WMG(πuni) is 0 and UMG(πuni) does not contain any edge.

( 1 2 3 w.p. 1/4 2 1 3 w.p. 1/4 every other ranking w.p. 1/8 = WMG(ˆπ) =

! " ! " = UMG(ˆπ) =

Figure 1: ˆπ, WMG(ˆπ) (only positive edges are shown), and UMG(ˆπ).

Due to the space constraint, we focus on presenting semi-random CC on positional scoring rules and multi-round score-based elimination (MRSE) rules rules in the main text, whose irresolute versions are deﬁned below. Their resolute versions can be obtained by applying a tie-breaking mechanism on the co-winners. See Section A for deﬁnitions of other rules studied in Section 3 for PAR.

Integer positional scoring rules. An (integer) positional scoring rule r s is characterized by an integer scoring vector s = (s1, . . . , sm) Zm 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 with weights ωP , the positional scoring rule r s chooses all alternatives a with maximum P

R P ωR s(R, a). For example, plurality uses the scoring vector (1, 0, . . . , 0), Borda uses the scoring vector (m 1, m 2, . . . , 0), and veto uses the scoring vector (1, . . . , 1, 0).

Multi-round score-based elimination (MRSE) rules. An irresolute MRSE rule r for m alternatives is deﬁned by a vector of m 1 rules (r2, . . . , rm), where for every 2 i m, ri is a positional scoring rule over i alternatives that outputs a total preorder over them in the decreasing order of their scores. Given a proﬁle P, r(P) is selected in m 1 rounds. For each 1 i m 1, in round i, a loser (an alternative with the lowest score) under rm+1 i is eliminated. We use the parallel-universes tie-breaking (PUT) [12] to select winners an alternative a is a winner if there is a way to break ties among the losers in each round, so that a is the remaining alternative after m 1 rounds. If an MRSE rule r only uses integer position scoring rules, then it is called an int-MRSE rule. Commonly studied int-MRSE rules include STV, which uses plurality in each round, Coombs, which uses veto in each round, and Baldwin s rule, which uses Borda in each round.

Example 2 (Irresolute STV). Figure 2 illustrates the execution of irresolute STV,

denoted by STV, under πuni (the uniform distribution) and ˆπ (the distribution in Figure 1), where each node represents the (tied) losers of the corresponding round, and each edge represents the loser to be eliminated. We have STV(πuni) = {1, 2, 3} and STV(ˆπ) = {1, 2}.

πuni !𝜋 Profile

Round 1 (#𝑟%)

Round 2 (#𝑟&)

Figure 2: STV under πuni and ˆπ (deﬁned in Figure 1).

Axioms of voting. We focus on per-proﬁle axioms [54] in this paper. A per-proﬁle axiom is deﬁned as a function X that maps a voting rule r and a proﬁle P to {0, 1}, where 0 (respectively 1) means that r dissatisﬁes/violates (respectively, satisﬁes) the axiom at P. Then, the classical (worst-case) satisfaction of the axiom under r is deﬁned to be min P L(A) X(r, P).

For example, a (resolute or irresolute) rule r satisﬁes CC, if min P L(A) CC(r, P) = 1, where CC(r, P) = 1 if and only if either (1) there is no Condorcet winner under P, or (2) the Condorcet winner is a co-winner of P under r. A resolute rule r satisﬁes PAR, if min P L(A) PAR(r, P) = 1, where PAR(r, P) = 1 if and only if no voter has incentive to abstain from voting. Formally, let P = (R1, . . . , Rn), then [PAR(r, P) = 1] j n, r(P) Rj r(P Rj) , where P Rj is the (n 1)-proﬁle that is obtained from P by removing the j-th vote. For any pair of alternatives a

and b, we write {a} Rj {b} if and only if agent j, whose preferences are Rj, prefers a to b. See Appendix B for a list of 13 well-studied per-proﬁle axioms and one non-per-proﬁle axiom.

Semi-random satisfaction of axioms. Given a per-proﬁle axiom X, a set Π of distributions over L(A), a voting rule r, and n N, the semi-random satisfaction of X under r with n agents, denoted by e Xmin Π (r, n), is deﬁned 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. Formally, Π is part of the single-agent preference model deﬁned as follows.

Deﬁnition 1 (Single-Agent Preference Model [54]). A single-agent preference model is denoted by M = (Θ, L(A), Π), where Θ is the parameter space, L(A) is the sample space, and Π consists of distributions indexed by Θ. M is strictly positive if there exists ϵ > 0 such that the probability of any linear order under any distribution in Π is at least ϵ. M is closed if Π (which is a subset of the probability simplex in Rm!) is a closed set in Rm!.

Example 1 illustrates a strictly positive and closed single-agent preference model for m = 3, where Π = {π1, π2} and ϵ = 1/8. Other examples can be found in [54, Example 2 in the appendix].

3 The Semi-random Satisfaction of CC and PAR

Semi-random CC under Integer Positional Scoring Rules. To present the results, we ﬁrst deﬁne almost Condorcet winners (ACW) of a proﬁle P, which are the two alternatives (whenever they exist) that are tied in the UMG and beat all other alternatives in head-to-head competitions.

Deﬁnition 2 (Almost Condorcet Winners). For any unweighted directed graph G over A, a pair of alternatives a, b are almost Condorcet winners (ACWs), denoted by ACW(G), if (1) a and b are tied in G, and (2) for any other alternative c / {a, b}, G has a c and b c. For any proﬁle P, let ACW(P) = ACW(UMG(P)).

For example, 1 and 2 are ACWs of ˆπ (as a fractional proﬁle) in Figure 1. By deﬁnition, for any proﬁle P, |ACW(P)| is either 0 or 2, and when it is 2, WCW(P) = ACW(P).

We now present a full characterization of semi-random CC under integer positional scoring rules. Let CH(Π) denote the convex hull of Π.

Theorem 1 (Semi-random CC: Integer Positional Scoring Rules). For any ﬁxed m 3, let M = (Θ, L(A), Π) be a strictly positive and closed single-agent preference model, let r s be an irresolute integer positional scoring rule, and let r s be a reﬁnement of r s. For any n 8m + 49 with 2 | n,

f CC min Π (r s, n) =

1 exp( Θ(n)) if π CH(Π), |WCW(π)| |r s(π) WCW(π)| 1

Θ(n 0.5) if (1) π CH(Π), CW(π) (A \ r s(π)) = and (2) π CH(Π) s.t. |ACW(π) (A \ r s(π))| = 2 exp( Θ(n)) if π CH(Π) s.t. CW(π) (A \ r s(π)) = Θ(1) (1 Θ(1)) otherwise

For any n 8m + 49 with 2 n,

f CC min Π (r s, n) =

1 exp( Θ(n)) same as the 2 | n case

exp( Θ(n)) if π CH(Π) s.t. (1) CW(π) (A \ r s(π)) = or (2) |ACW(π) (A \ r s(π))| = 2 Θ(1) (1 Θ(1)) otherwise

Generality. We believe that Theorem 1 is quite general, as it can be applied to any reﬁnement of any irresolute integer positional scoring rule (i.e., using any tie-breaking mechanism) w.r.t. any Π that satisﬁes mild conditions. The power of Theorem 1 is that it converts complicated probabilistic arguments about semi-random CC to deterministic arguments about properties of (fractional) proﬁles in CH(Π), i.e., r s(π), CW(π), ACW(π), and WCW(π), which are much easier to check. In particular, Theorem 1 can be easily applied to i.i.d. distributions (including IC) as shown in Example 3 below.

Intuitive explanations of the conditions. While the conditions for the cases in Theorem 1 may appear technical, they have intuitive explanations. Take the 2 | n case for example. The 1

exp( Θ(n)) case happens if every π CH(Π) is a robust instance of CC satisfaction, in the sense that after any inﬁnitely small perturbation δ Rm! is introduced to π, π + δ is still an instance of CC satisfaction. For the Θ(n 0.5) case, condition (1) states that every π CH(Π) is an instance of CC satisfaction, and condition (2) requires that some π CH(Π) corresponds to a non-robust instance of CC satisfaction, in the sense that after a small perturbation η is added to π, CC is violated at π + η. The exp( Θ(n)) case happens if there exists a robust instance of CC dissatisfaction π CH(Π), in the sense that after any small perturbation is introduced to π, it is still an instance of CC dissatisfaction. Otherwise, the Θ(1) (1 Θ(1)) case holds.

Odd vs. even n. The 2 n case has similar explanations. The main difference is that when 2 n, the UMG of any n-proﬁle must be a complete graph. Therefore, when ACW(π) = , with high probability an alternative in ACW(π) is the Condorcet winner in the randomly-generated n-proﬁle. Then, the Θ(n 0.5) case in 2 | n becomes part of the exp( Θ(n)) case in 2 n.

Example 3 (Applications of Theorem 1 to plurality). In the setting of Example 1, we apply Theorem 1 to any sufﬁciently large n with 2 | n and any reﬁnement of irresolute plurality, denoted by Plu, for the following sets of distributions.

Π = {π1, π2}. We have f CC min Π (Plu, n) = exp( Θ(n)), because let π = 3π1+π2

4 , we have CW(π ) = WCW(π ) = {2}, ACW(π ) = , and Plu(π ) = {1}.

ΠIC = {πuni}, i.e., semi-random CC becomes likelihood of CC w.r.t. IC. We have f CC min ΠIC (Plu, n) = Θ(1) (1 Θ(1)), because CW(πuni) = , WCW(πuni) = {1, 2, 3}, and ACW(πuni) = .

Semi-random CC under int-MRSE Rules. Semi-random CC under an MRSE rule r depends on whether the positional scoring rules it uses satisfy the CONDORCET LOSER (CL) criterion, which requires that the Condorcet loser, whenever it exists, never wins. The Condorcet loser is the alternative that loses to all head-to-head competitions. For any voting rule r, we write CL(r) = 1 if and only if r satisﬁes CONDORCET LOSER.

To present the result, we ﬁrst deﬁne parallel universes under an MRSE rule r at x Rm!, denoted by PUr( x), to be the set of all elimination orders in the execution of r at x. Then, for any alternative a, let the possible losing rounds, denoted by LRr( x, a) [m 1], be the set of all rounds in the parallel universes where a drops out. The formal deﬁnitions and an example can be found in Deﬁnition 26 and Example 12 in Appendix E.3, respectively.

We are now ready to present the 2 | n case of our characterization of semi-random CC under MRSE rules. The full version can be found in Appendix E.3.

Theorem 2 (Semi-random CC: int-MRSE rules, 2 | n). For any ﬁxed m 3, let M = (Θ, L(A), Π) be a strictly positive and closed single-agent preference model, let r = (r2, . . . , rm) be an int-MRSE rule and let r be a reﬁnement of r. For any n N with 2 | n, we have

f CC min Π (r, n) =

1 if 2 i m, CL(ri) = 1

1 exp( Θ(n)) if

(1) 2 i m s.t. CL(ri) = 0 and (2) π CH(Π), a WCW(π), i LRr(π, a), we have CL(rm+1 i ) = 1

Θ(n 0.5) if (1) π CH(Π), CW(π) (A \ r(π)) = and (2) π CH(Π) s.t. |ACW(π) (A \ r(π))| = 2 exp( Θ(n)) if π CH(Π) s.t. CW(π) (A \ r(π)) = Θ(1) (1 Θ(1)) otherwise

The most interesting cases are the 1 case and the 1 exp( Θ(n)) case. The 1 case happens when all positional scoring rules used in r satisfy CONDORCET LOSER. In this case, if the Condorcet winner exists, then it cannot be a loser in any round, which means that it is the unique winner under r. The 1 exp( Θ(n)) case happens when (1) the 1 case does not happen, and (2) for every distribution π CH(Π), every weak Condorcet winner a, and every possible losing round i for a, the positional scoring rule used in round i , i.e. rm+1 i , must satisfy CONDORCET LOSER. (2) guarantees that when a small permutation is added to π, if a weak Condorcet winner a becomes the Condorcet winner, then it will be the unique winner under r. See Example 13 in Appendix E.3 for an application of Theorem 2 to STV.

Like Theorem 1, Theorem 2 can also be easily applied to i.i.d. distributions,which corresponds to ΠIC = {πuni}. Corrollary 1 (Likelihood of CC under int-MRSE rules w.r.t. IC). For any ﬁxed m 3, any reﬁnement r of any int-MRSE rule r, and any n N,

Pr P (πuni)n(CC(r, P) = 1) = 1 if 2 i m, CL(ri) = 1 Θ(1) (1 Θ(1)) otherwise

Proof sketches for Theorem 1 and 2. In light of various multivariate central limit theorems (CLTs), when n is large, the proﬁle is approximately n π for π = (Pn j=1 πj)/n CH(Π) with high probability. Despite this high-level intuition, the conditions of the cases are quite differently from semi-random CC by deﬁnition. To see this, note that (i) the adversary may not be able to set any agent s ground truth preferences to be π CH(Π), because π may not be in Π as shown in Example 3, and (ii) in the deﬁnition of semi-random CC, agent j s vote is a random variable distributed as πj, instead of the fractional vote πj. Standard CLTs can probably be applied to prove the 1 exp( Θ(n)) case and the Θ(1) (1 Θ(1)) case, but they are too coarse for other cases.

To address this challenge, we model the satisfaction of CC by the union of multiple polyhedra C as exempliﬁed in Section 4. This converts the semi-random CC problem to a PMV-in-C problem [55] (Deﬁnition 3 below). Then, we reﬁne [55, Theorem 2] to prove a categorization lemma (Lemma 1), and apply it to obtain Lemma 2 that characterizes semi-random CC for a large class of voting rules called generalized irresolute scoring rules (GISRs) [22, 53] (Deﬁnition 7 in Appendix D.1). Finally, we apply Lemma 2 to integer positional scoring rules and int-MRSE rules to obtain Theorem 1 and Theorem 2. The full proof can be found in Appendix E.2 and E.3, respectively. 2

The semi-random satisfaction of PAR. Due to the space constraint, we brieﬂy introduce our characterizations of semi-random PAR under commonly-studied voting rules deﬁned in Appendix A, which belong to a large class of voting rules called generalized scoring rules (GSRs) [56] (Deﬁnition 7 in Appendix D.1). Formal statements and proofs of the theorems can be found in Appendix F.2 F.5.

Theorems 3, 4, 5, 6 (Semi-random PAR under commonly-studied rules). For any ﬁxed m 4, any GSR r that is a reﬁnement of maximin, STV, Schulze, ranked pairs, Copeland, any int-MRSE, or any Condocetiﬁed positional scoring rule (such as Black s rule), and any strictly positive and closed

Π over L(A) with πuni CH(Π), there exists N N such that for every n N, g PAR min Π (r, n) = 1 Θ( 1 n).

In fact, if πuni CH(Π), then semi-random PAR converges to 1 at a faster rate, which is more positive news, as shown in Lemma 3 (Appendix F.1).

4 Beyond CC and PAR: The Categorization Lemma

In this section, we present a general lemma that characterizes semi-random satisfaction of per-proﬁle axioms that can be represented by unions of polyhedra, including CC and PAR. To develop intuition, we start with an example of modeling CC under irresolute plurality as the union of the following two types of polyhedra in Rm!.

CNCW represents that there is no Condorcet winner, which is the union of polyhedra HG, where G is an unweighted graph over A that does not have a Condorcet winner, as exempliﬁed in Example 4.

CCWW represents that the Condorcet winner exists and also wins the plurality election, which is the union of polyhedra Ha for every a A, that represents a being the Condorcet winner as well as a Plu co-winner, as exempliﬁed in Example 5. Example 4 (HG). Let m = 3 and let xabc denote the number of [a b c] votes in a proﬁle. The following ﬁgure shows G (left) and HG (right).

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

Among the four inequalities, (2) represents the 1 2 edge in G, (3) represents the 3 1 edge in G, and (4) and (5) represent the tie between 2 and 3 in G. Example 5 (Ha). Let m = 3. H1 is the polyhedron represented by the following four inequalities: (x213 + x231 + x321) (x123 + x132 + x312) 1 (x231 + x321 + x312) (x123 + x132 + x213) 1

1 is the Condorcet winner

(x213 + x231) (x123 + x132) 0 (x321 + x312) (x123 + x132) 0

1 is a Plu co-winner

It is not hard to see that Plu satisﬁes CC at a proﬁle P if and only if Hist(P) is in C = CNCW CCWW, where CNCW = S

G:CW(G)= HG and CCWW = S

a A Ha. An example of PAR under Copeland can be found in Appendix C.1. In general, the satisfaction of a wide range of axioms can be represented by unions of ﬁnitely many polyhedra. Then, the semi-random satisfaction problem reduces to the lower bound of the following PMV-in-C problem. Deﬁnition 3 (The PMV-in-C problem [55]). Given q, I N, C = S

i I Hi, where i I, Hi Rq is a polyhedron, and a set Π of distributions over [q], we are interested in

the upper bound sup π Πn Pr( X π C), and the lower bound inf π Πn Pr( X π C),

where X π is the (n, q)-Poisson multinomial variable (PMV) that corresponds to the histogram of n independent random variables distributed as π.

See Example 7 in Appendix C.2 for an example of PMV. The following lemma provides an asymptotic characterization on the lower bound of the PMV-in-C problem. Lemma 1 (Categorization lemma, simpliﬁed). For any PMV-in-C problem and any n N, inf π Πn Pr( X π C) is 0, exp( Θ(n)), poly 1(n), Θ(1) (1 Θ(1)), 1 poly 1(n), 1 exp( Θ(n)), or 1.

The full version of Lemma 1 (Appendix C.2) also characterizes the condition for each case, the degree of polynomial, and sup π Πn Pr( X π C). Lemma 1 s main merit is conceptual, as it categorizes the semi-random likelihood into seven cases for quantitative comparisons, summarized in the increasing order in the table below, which are 0, very unlikely (VU), unlikely (U), medium (M), likely (L), very likely (VL), and 1. The ﬁrst three cases (0, VU, U) are negative news, where the adversary can set the ground truth so that the axiom is almost surely violated in large elections (n ). The last three cases (L, VL, and 1) are positive news, because the axiom is satisﬁed almost surely in large elections, regardless of the adversary s choice. The M case can be interpreted positively or negatively, depending on the context.

Name 0 VU U M L VL 1 Lem. 1 0 exp( Θ(n)) poly 1(n) Θ(1) (1 Θ(1)) 1 poly 1(n) 1 exp( Θ(n)) 1

5 Future work

There are many open questions for future work. While we believe that the assumptions (of strict positiveness and closedness) on Π are mild, it is an important and interesting open question to extend the analysis to variable ϵ s, and perhaps establish bounds that explicitly depend on ϵ. What are the semi-random CC and semi-random PAR for voting rules not sdudied in this paper, such as Bucklin? What is the semi-random satisfaction of PAR when a group of agents can simultaneously abstain from voting [31]? More generally, we believe that drawing a comprehensive picture of semi-random satisfactions of other voting axioms and/or paradoxes, such as those described in Appendix B, is an important, promising, and challenging mission, and the categorization lemma (Lemma 1) can be a useful conceptual and technical tool to start with.

Acknowledgments

We thank attendees at COMSOC-21 and anonymous reviewers for helpful comments. This work is supported by NSF #1453542, ONR #N00014-17-1-2621, and a gift fund from Google.

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

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

[3] S. Berg and D. Lepelley. On probability models in voting theory. Statistica Neerlandica, 48 (2):133 146, 1994.

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

[5] Debarun Bhattacharjya and Jeffrey Kephart. Bayesian interactive decision support for multiattribute problems with even swaps. In Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artiﬁcial Intelligence, 2014.

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

[7] Avrim Blum. Some tools for approximate 3-coloring. In Proceedings of FOCS, 1990.

[8] Avrim Blum and Joel Spencer. Coloring Random and Semi-Random k-Colorable Graphs. Journal of Algorithms, 19(2):204 234, 1995.

[9] George E. P. Box. Robustness in the strategy of scientiﬁc model building. In R. L. Launer and G. N. Wilkinson, editors, Robustness in Statistics, pages 201 236. Academic Press, 1979.

[10] Felix Brandt, Johannes Hofbauer, and Martin Strobel. Exploring the No-Show Paradox for Condorcet Extensions. In Mostapha Diss and Vincent Merlin, editors, Evaluating Voting Systems with Probability Models. Springer, 2021.

[11] 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.

[12] Vincent Conitzer, Matthew Rognlie, and Lirong Xia. Preference functions that score rankings and maximum likelihood estimation. In Proceedings of the Twenty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 109 115, Pasadena, CA, USA, 2009.

[13] Mostapha Diss and Vincent Merlin, editors. Evaluating Voting Systems with Probability Models. Studies in Choice and Welfare. Springer International Publishing, 2021.

[14] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th World Wide Web Conference, pages 613 622, 2001.

[15] Uriel Feige. Introduction to Semi-Random Models. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2021.

[16] Peter C. Fishburn. Aspects of One-Stage Voting Rules. Management Science, 21(4):422 427, 1974.

[17] Peter C. Fishburn. Simple voting systems and majority rule. Behavioral Science, 19(3):166 176, 1974.

[18] Peter C. Fishburn. Paradoxes of voting. The American Political Science Review, 68(2):537 546, 1974.

[19] Peter C. Fishburn and Steven J. Brams. Paradoxes of Preferential Voting. Mathematics Magazine, 56(4):207 214, 1983.

[20] Peter C. Fishburn and William V. Gehrlein. An analysis of simple two-stage voting systems. Behavioral Science, 21(1):1 12, 1976.

[21] Peter C. Fishburn and William V. Gehrlein. An analysis of voting procedures with nonranked voting. Behavioral Science, 22(3):178 185, 1977.

[22] Rupert Freeman, Markus Brill, and Vincent Conitzer. General Tiebreaking Schemes for Computational Social Choice. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 1401 1409, 2015.

[23] William V. Gehrlein. Condorcet s Paradox. Springer, 2006.

[24] 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.

[25] William V. Gehrlein and Peter C. Fishburn. Coincidence probabilities for simple majority and positional voting rules. Social Science Research, 7(3):272 283, 1978.

[26] William V. Gehrlein and Peter C. Fishburn. Probabilities of election outcomes for large electorates. Journal of Economic Theory, 19(1):38 49, 1978.

[27] William V. Gehrlein and Dominique Lepelley. Voting Paradoxes and Group Coherence: The Condorcet Efﬁciency of Voting Rules. Springer, 2011.

[28] Allan Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41:587 601, 1973.

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

[30] Aki Lehtinen and Jaakko Kuorikoski. Unrealistic Assumptions in Rational Choice Theory. Philosophy of the Social Sciences, 37(2):115 138, 2007.

[31] Dominique Lepelley and Vincent Merlin. Scoring run-off paradoxes for variable electorates. Economic Theory, 17:53 80, 2001.

[32] Dominique Lepelley, Frederic Chantreuil, and Sven Berg. The likelihood of monotonicity paradoxes in run-off elections. Mathematica Slocial Science, 31:133 146, 1996.

[33] Tie-Yan Liu. Learning to Rank for Information Retrieval. Springer, 2011.

[34] Andrew Mao, Ariel D. Procaccia, and Yiling Chen. Better human computation through principled voting. In Proceedings of the National Conference on Artiﬁcial Intelligence (AAAI), Bellevue, WA, USA, 2013.

[35] Nicholas Mattei and Toby Walsh. Pref Lib: A Library of Preference Data. In Proceedings of Third International Conference on Algorithmic Decision Theory, Lecture Notes in Artiﬁcial Intelligence, 2013.

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

[37] Samuel Merrill. A statistical model for Condorcet efﬁciency based on simulation under spatial model assumptions. Public Choice, 47(2):389 403, 1985.

[38] Elchanan Mossel, Ariel D. Procaccia, and Miklos Z. Racz. A Smooth Transition From Powerlessness to Absolute Power. Journal of Artiﬁcial Intelligence Research, 48(1):923 951, 2013.

[39] Herv e Moulin. Condorcet s principle implies the no show paradox. Journal of Economic Theory, 45(1):53 64, 1988.

[40] Jill Van Newenhizen. The Borda Method Is Most Likely to Respect the Condorcet Principle. Economic Theory, 2(1):69 2 83, 1992.

[41] Hannu Nurmi. An Assessment of Voting System Simulations. Public Choice, 73(4):459 487, 1992.

[42] Hannu Nurmi. Voting Paradoxes and How to Deal with Them. Springer-Verlag Berlin Heidelberg, 1999.

[43] David C. Paris. Plurality distortion and majority rule. Behavioral Science, 20(2):125 133, 1975.

[44] Donald G. Saari. Basic Geometry of Voting. Springer, 1995.

[45] Mark Satterthwaite. Strategy-proofness and Arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187 217, 1975.

[46] Alexander Schrijver. Theory of Linear and Integer Programming. Wiley, 1998.

[47] Markus Schulze. A new monotonic, clone-independent, reversal symmetric, and condorcetconsistent single-winner election method. Social Choice and Welfare, 36(2):267 303, 2011.

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

[49] 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.

[50] 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.

[51] Shuaiqiang Wang, Shanshan Huang, Tie-Yan Liu, Jun Ma, Zhumin Chen, and Jari Veijalainen. Ranking-Oriented Collaborative Filtering: A Listwise Approach. ACM Transactions on Information Systems, 35(2):Article No. 10, 2016.

[52] Mark C. Wilson and Geoffrey Pritchard. Probability calculations under the IAC hypothesis. Mathematical Social Sciences, pages 244 256, 2007.

[53] Lirong Xia. Generalized Decision Scoring Rules: Statistical, Computational, and Axiomatic Properties. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 661 678, Portland, Oregon, USA, 2015.

[54] Lirong Xia. The Smoothed Possibility of Social Choice. In Proceedings of Neur IPS, 2020.

[55] Lirong Xia. How Likely Are Large Elections Tied? In Proceedings of ACM EC, 2021.

[56] Lirong Xia and Vincent Conitzer. Generalized scoring rules and the frequency of coalitional manipulability. In Proceedings of the ACM Conference on Electronic Commerce, pages 109 118, 2008.

[57] Lirong Xia and Vincent Conitzer. Finite local consistency characterizes generalized scoring rules. In Proceedings of the Twenty-First International Joint Conference on Artiﬁcial Intelligence, pages 336 341, 2009.