The Semi-Random Satisfaction of Voting Axioms
Authors: Lirong Xia
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: social choice
voting
axioms
smoothed analysis

Abstract: We initiate the work towards a comprehensive picture of the worst average-case satisfaction of  voting axioms in semi-random models, to provide a finer and more realistic foundation for comparing voting rules. We adopt the semi-random model and formulation in [Xia 2020],  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 fixed number of alternatives, when the number of voters $n$ is sufficiently large, the semi-random satisfaction of the Condorcet criterion under a wide range of voting rules is $1$, $1-\exp(-\Theta(n))$, $\Theta(n^{-0.5})$, $ \exp(-\Theta(n))$, or being $\Theta(1)$ and $1-\Theta(1)$ at the same time; and the semi-random satisfaction of participation is  $1-\Theta(n^{-0.5})$.   Our results  address  open questions by Berg and Lepelley in 1994, and also  confirm the following high-level message: the Condorcet criterion is a bigger concern than participation under realistic models. 

The Satisfaction of Voting Axioms
Lirong Xia RPI, Troy, NY 12180, USA xialárong@gmail.com
Abstract
We initiate the work towards comprehensive picture of the worst average-case satisfaction of voting axioms in semi-random models, to provide finer 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 characterizing the semi-random satisfaction of two well-studied voting axioms: Condorcet criterion and participation. We prove that for any fixed num- ber of alternatives, when the number of voters is sufficiently large, the semi- random satisfaction the Condorcet criterion under a wide range of voting rules is 1, 1 - cxp(-et ( 0n.50.5,, exp(-O(n)) or being ((1) and @(1) at the same time; and the semi-random satisfaction of participation is - O(n 0.6). ). Our results address open questions by Berg and Lepelley [3] in 1994, and also confirm the following high-level message: the Condorcet criterion a bigger concern than participation under realistic models.
1 Introduction
The "widespread presence of impossibility results" [48] is one of the most fundamental and signif- icant challenges in social choice theory. These impossibility results often assert that no "perfect" voting rule exists for three more alternatives 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.
28, 45J. Nevertheless, an (imperfect) voting rule
Most definitions of dissatisfaction of voting axioms are based on worst-case analysis. For example, voting rule does satisfy CONDORCET CRITERION (CC for short), there exists collection of votes, called profile, where the Condorcet winner exists but is not chosen by as a winner. The Condorcet winner is the alternative who beats all other alternatives in their head-to-head competi- tions. As another example, voting rule r does not satisfy PARTICIPATION (PAR for short), if there exists profile and 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 satisfies CC and PAR simultaneously [39].
While the classical worst-case analysis of (dis) satisfactio of axioms can be desirable in high-stakes applications such political elections, it often too coarse serve practical criteria for compar- ing different voting rules in more frequent, low-stakes applications of social choice, such as business decision-mal making [5], crowdsourcing [34], informational retrieval [33], meta-search engines [14], recommender systems [51], etc. A decision maker who desires both axioms would find it hard to choose between voting rule that satisfies CC but not PAR, such as Copeland, and voting rule that satisfies PAR but not CC, such as plurality. A finer and more quantitative measure of satisfaction of axioms therefore called for.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

One natural and classical approach is to measure the likelihood of satisfaction of axioms under probabillitic model of agents' preferences, in particular the independent and identically distributed (i.i..) uniform distribution over all rankings, known 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 "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 I book edited by Diss and Merlin [13].
While this line of work is highly significant and interesting from a theoretical point of view, its practical implications may not be as strong, because most previous work focused on few specific distributions, especially IC. which has been widely criticized to be unrealistic (see, e.g., [42, p. 30], [23, 104]. and [30].. Indeed, conclusions drawn under any specific 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 few voting rules. Therefore, the following question largely remains open.
How likely are voting axioms satisfied under realistic models?
The importance of successfully answering this question is two-fold. First, it tells whether the worst-case violation of an axiom a significant concern in practice. Second, it provides finer and more quantitative foundation for comparing voting rules.
We believe that the cludes 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 semi- random model by Xia [54], which models the satisfaction of per-profile voting axiom X by function X (r. P) E {0, 1J. where r is a voting rule and P is profile, such that r satisfies X of distributions over all rankings over the m alternatives (denoted by L(A)), which represents the "ground truth" preferences for single agent that the ad- versary can choose from. Let n denote the number of agents. Because higher value of X (r; P) is more desirable to the decision maker, the adversary aims at minimizing expected X X(r, P) by choos- ing 11"-the profile P is generated from म. The semi-random satisfaction of X under with agents, denoted by Xiiia (r, n). defined as follows [54]: Xmin (r, ra) - infæen= Pre-s X(r, P)
models [15], originally investigated by Blum [7] and [8] and in-
minp X (r, P) 1. Let II denote
Notice that agents' ground truth preferences be arbitrarily correlated, while the noises are inde- pendent, which is a standard assumption in the literature and in practice [54].
Example 1 (Semi- Random CC under plurality). Let X CC and Plu denote the ir- resolute plurality rule, which chooses all alternatives that are ranked at the top most often as the (co-)winners. Suppose there are three allernatives, denoted by A (1,2,3), and suppose n²), where x! and n? are distributions shown in Table 1.
II (==) (x)xx²),
Then, inf =² Pro-r CC(Plu, P).
have CC min (Plu,
123
132
231
321
213
312
When = the adversary has four choices of म,, i.e.,
π
1/4
1/4
1/8
1/8
1/8
1/8
1/8
1/8
3/8
1/8
1/8
1/8
((x),=t), mT), (nr1 (.,x 2),, (T7 (x² x2)).
Table 1: II in Example 1.
Each 5 leads to a distribution over the set of all profiles of two agents, i.e., L(A)? We have
CC min (Plu, 2) = because CC is satisfied at all profiles of two agents. As we will see later in min Example 3, for all sufficiently large n, CCT (Plu, = exp(-
1.1 Our Contributions
We initiate the work towards a comprehensive picture semi-random satisfaction of voting axioms under commonly-studied voting rules, by focusing on CC and PAR in this paper due to their impor- tance, popularity, and incompatibility [39]. Recall that m the number of alternatives and the number of agents. Our technical contributions two-fold.

---

First, semi-random satisfaction of CC (Theorem 1 and 2). We prove that, under mild assump- tions, for any fixed m 2 and any sufficiently large n, the exp(-O(()). Onn-0.), exp( (n)),, or being ( ) and 1 (1) at the same time (denoted by @(1) A (1 (1-))) The exp(-e(m) case is positive news, because it states that CC is satisfied almost surely when is large, regardless of the adver- sary'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, matter how large n is.
satisfaction of CC under
a wide range of voting rules is 1,
Second, semi-random satisfaction of PAR (Theorems 3, 4, 5, 6). We prove that, under mild assumptions, for any fixed m 2 3 and any sufficiently large n. the semi-random satisfaction of PAR under wide range of voting rules is 1 (n -05).. These are positive news, because they state that PAR is satisfied almost surely for large n, regardless of the adversary's 's choice. While this message may not be surprising at a high level, as the probability for single agent to change the winner vanishes as n -> oo, 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 justification of two common beliefs related to PAR: first, IC exaggerates the likelihood for paradoxes to happen, and second, the dissat- isfaction of PAR not significant concern practice [31], especially when it is compared to our results on semi-random CC. Table 2 summarizes corollaries of our results under some commonly- studied voting rules w.r.t. IC as well as the satisfaction of CC and PAR on Preflib data [35], where that do not depend on n, such
((1) A (1 ())) means that there exists constants 0 < a < B < that the likelihood is in (a, 3).
Table 2: Satisfaction of CC and PAR w.r.t. IC and w.r.t. 315 Preflib profiles of linear orders under elections category. Experimental results are presented in Appendix G.
Axiom
Plu. Borda
Veto
STV
Black
MM
Sch.
RP
Copelando.s
CC
((1) (1 (1-)(1))
always satisfied
Theory
PAR
always satisfied
θ (n U.0
CC
96.8%
92.4%
74.2%
99.7%
100%
100%
100%
100%
100%
Preflib
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 fixed non-zero ratio) on both CC and PAR, and assume that the preferences are generated from IC. Then, when is sufficiently large, the last five voting rules in the table (that satisfy CC) outperform the first five voting rules in the table (the first four satisfies 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 large class of axioms that can be represented by unions of finitely many polyhedra, including CC and PAR. We believe that Lemma I 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 acceplance" [44, p. 46). CC is satisfied by many commonly-studiee
voting rules, except positional scoring rules [18] and multi- round-score-hasele elimination rules, such STV. Most previous work focused on characterizing the Condorcet efficiency, which is the probability for the Condorcet winner to win conditioned on its existence [17, 16, 43, 25, 40J. Beyond positional scoring rules, the study was mostly based on computer simulations, see, e.g.. [20, 27,37,45 41].
The participation axiom (PAR) was motivated by the no-show paradox [19] and was proved to be incompatible with CC for every m 2 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- no-show paradox is not important flaw of the scoring run-off voting systems".
3

---

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: first, we conduct semi-random analysis, which extends i.i.d. models and is believed to be significantly 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 fixed, 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, is the central idea frequentist statistics (as 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 conduct smoothed analysis in social choice. We adopt the framework in the latter work, though our motivation and goal are quite different. We aim providing 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 is a straightforward corollary of [55, Theorem 21, applications of results like Lemma 1 can be highly non non-trivial and problem dependent as commented in [55], which is the case of this paper. We believe that Lemma I's main merit is conceptual, as it provides a general categorization of semi-random satisfaction of a large class of per-profile axioms beyond CC and PAR for future work.
2 Preliminaries
For any q N. we let [g] {1, (1.....94 .) Let A [m]] denote the set of 3 alternatives. Let ((AA denote the set of all linear orders over A. Let n E N denote the number of agents (voters). Each agent uses a linear order R L(A) to represent his or her preferences, called vole, where a >>n b means that the agent prefers alternative a to alternative b. The vector of n agents' votes, denoted by P, is called (preference) profile, sometimes called n-profile. The set of n-profiles for all n E N is denoted by C(A)* = = L(A)". A fractional profile is profile I' coupled with a possibly non-integer and/or negative weight vector up (WR: R E P) E R" for the votes in P. It follows that non non-fractional profile a fractional profile with uniform weight, namely Wp I. Sometimes the weight vector is omitted when it is clear from the context or when Wpp I.
For any (fractional) profile P, let Hist(P) P) E Reg) denote the anonymized profile of P, also called the histogram of P, which contains the total weight of every linear order in ((A) according to P. An irresolute voting rule F L(A)* - (24) \. (0}) maps profile
non-empty set of winners in A. A resolute voting rule r is special irresolute voting rule that always chooses a single alternative as the (unique) winner. We say that a voting rule r a refinement of another voting rule 7, if for every profile P. r(P) C F(P).
(Unnweighted majority graphs and (weak) Condorcet winners. For any (fractional) profile P and any pair of alternatives a, b, let Pia > bj 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 wp(a, b) = Pla > 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 profile, where for each R L(A) the weight on is 5 (R).. In such cases, we let (MG((T denote the weighted majority graph of the fractional profile represented by π.
The Condorcet winner of profile 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 CP( and WCW P)) denote the set of Condorcet winners and weak Condorcet winners in P. respectively. Notice that CW(P) C 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 C+) = @ and WCW (1, As another example, let uuni denote the uniform
4

---

distribution over ((A). Then, the weight on every edge in WMG( is 0 and (MG (Tmi) does contain any edge.
1>223 2 2>1>3
w.p. 1/4
A =
w.p. 1/4
= WMG
UMG(R) =
every other ranking
w.p. 1/8
Figure 4, WMG(ft (only positive edges are shown), and UMG(R).
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 defined below. Their resolute versions can be obtained by applying a tie tie-breaking mechanism on the co- no-winners. See Section for definitions of other rules studied Scction for PAR.
Integer positional scoring rules. An (integer) positional scoring rule Ts is characterized by an integer scoring vector
($1,...,$m) E 2 with 81 2 82 Z 2 8m and 81 > Sm- For any alternative and any linear order R E L(A). we let S(R,a) Given a profile P with weights Wp, the positional scoring rule Tz chooses all alternatives a with maximum Σ RE wi RR, a). For example, plurality uses the scoring vector (1, 0, . 0), Borda uses the scoring vector (m - 1,m m 2, ,,..., 0), and veto uses the scoring vector (1,...,,,00
where i is the rank of in R.
Multi-round score-based elimination (MRSE) rules. An irresolute MRSE rule for m alterna- tives is defined by a vector of m - rules (f2...., Fmm), where for every 2 S I m, T; is a positional scoring rule order of their scores. Given a profile P, F(P) P) is selected in m - rounds. For each 1 S i S. m - 1, in round loser (an alternative with the lowest score) under mm+1- eliminated. We use the parallel-universes tie-breaking (PUT) [12] to select winners-ar alternative a a winner if there is way to break ties among the losers in each round, so that is the remaining alternative after - rounds. If an MRSE rule F 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 's rule, which uses Borda in each round.
alternatives that outputs total preorder over them in the decreasing
Example 2
(Irresolute
STV).
Figure 2 illustrates the execution of irresolute STV,
denoted by STV, under Tuni (the uniform dis- tribution) and & (the distribution in Figure 1), where each node rep- resents the (tied) losers of the corresponding round, and each edge represents the loser to be eliminated. We have (TV())))) = 2,, and STV(#) = (1,2}.
Profile
Tuii
ft
{1.2.3] 2, 2}
{3}
Round (75)
{2.3}
{1,3) 3} {1,2) 2}
(1,2}
Round 2 (Fg)
2/
Winner
(3) (2} {3} (1) (2) (1)
{2) {1)
Figure 2: STV under Vuii and R (defined in Figure I).
Axioms of voting, We focus on per-profile axioms [54] in this paper. A per-profile axiom is defined as function X that maps a voting rule 7 and a profile P {0, 1}. where (respectively 1) means that 7 dissatisfies/violate (respectively, satisfies) the axiom at P. Then, the classical (worst-case) satisfaction of the axiom under defined to be minreC(A)- Pr.
For example, (resolute or irresolute) rule F satisfies CC, if minPEC(A)- CC(F, P) = 1, where CC(r, P) = if and only if either (1) there is no Condorcet winner under P. or (2) the Condorcet winner a co-winner of P under r. A resolute rule satisfies PAR, minpe 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,... R,), then [PAR(r, P) 1] = [Vj < r(P) ZR, r(P Ry)] where P R, is the (n- 1)-profile that is obtained from P by removing the j-th vote. For any pair of alternatives
5

---

and b, we write {a} ZR, {b} if and only if agent j. whose preferences are R3, prefers a to b. See Appendix B for a list of 13 well-studied per-profile axioms and one non-per non-per-prooe per-profile axiom.
Semi-random satisfaction of axioms. Given a per-profile axiom X, set IT of distributions over ((A), voting rule and n E N, the semi-random satisfaction of X under F with n agents, denoted by X (7, n),, is defined in Equation (I) in the Introduction. We note that the "min" the superscript means that the adversary aims at minimizing the satisfaction of X. Formally, II is part of the single-agent preference model defined as follows.
Definition 1 (Single-Agent Preference Model [54). single-agent preference model is denoted by M = (θ, C(A),, M., where @ is the purameter space, L(A) is the sample space, and II consists of distributions indexed by O .M strictly positive if there exists > O such that the probability of any linear order under any distribution in II is at least .M is closed if IT (which is subset of the probability simplex in TR.")) ) is closed set Tim
Example &illustrates strictly positive and closed single-agent preference model for 3, where I= {x x 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 first define almost Condorcet winners (ACW) of a profile P. which are the two alternatives (whenever they exist) that are tied in the UMG and beat all other alternatives in head-to- -o-- competitions.
Definition (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)) (1) and b are tied in G, and (2) for any other alternative & {a,b), G has a + c. and b + G. For any profile P. let ACW(P) P) (CM(UMG(P)
For example, and 2 are ACWs of â (as a fractional profile) in Figure 1. By definition, for any profile 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(IT) denote the convex hull of IT.
Theorem 1 (Semi-random CC: Integer Positional Scoring Rules). For any fixed m 2 3, let
M = (O, 1I), be a strictly positive and closed single-agent preference model, let Tz be an irresolute integer positional scoring rule, and let rg be refinement of Tz. For any 2 8m + 49 with n,
1 - exp(-O(n))
if E (WC(() x (T(TT) U WCW(()) - if (()) VT E CH(IT), CW(x) (A) r=(*)) ( and (2) En CH(II) s.t. (AC((T) n (4 \ F2( fr E CH(II) s.t. CW(T) T=(T)) * otherwise
min CC
(n-555)
(ra,n)=
exp(-O(n)) (11) O(1)
For any 2 8m + 49 with 2 2
1- (-exp(--(m))
same as the 2 n case
min
3 E CH(IT) s.1. ((1) CW(T) ) n (A (F((T)) + or ((2) (ACW(T) n (A Fz(T)) =
CC (r3, n)
exp(-)(n)) ( (1- O(1) otherwise
Generality. We believe that Thcorem 1 is quite general, as it can be applied to any refinement of any irresolute integer positional scoring rule (i.e., using any tie-breaking mechanism) w.r.t. any I1 that satisfies mild conditions. The power of Theorem is that it converts complicated probabilistic argu- ments about semi-random CC to deterministic arguments about properties of (fractional) profiles in CHIII), i.., Tx(T), CW ACW (T), and WCW(T), which are much easier to check. In particular, Theorem 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

---

(x)(--(n)) case happens if every т E CH(IT) is "robust" instance of CC satisfaction, in the sense that after any infinitely small perturbation 8' E R is introduced n, 5 is still an instance of CC satisfaction. For the ( case, condition (1) states that every π E CH( is an instance of CC satisfaction, and condition (2) requires that some π CH(II) corresponds to "non-robust" instance of CC satisfaction, in the sense that after a small perturbation is added to n, CC is violated at ı + 1j. The (x)(-((n) case happens if there exists "robust" instance of CC dissatisfaction E CH(IT), in the sense that after any small perturbation is introduced to π, it is still an instance of CC dissatisfaction. Otherwise, the (1) A (1 (1)) case holds.
Odd vs. even n. The 2 Y n case has similar explanations. The main difference is that when 2 f n, the UMG of any n-profile must be a complete graph. Therefore, when ACW( A 0, with high probability an alternative in (CW( is the Condorcet winner in the madooml-ggeeraate n- --profille Then, the (n -0.) case in 2 becomes part of the exp(-O case in 2
Example 3 (Applications of Theorem 1 to plurality). In the setting of Example 1, we apply The- orem I to any sufficiently large n with 2 n and any refinement of irresolute plurality, denoted by Plu, for the following sets of distributions.
111 {x², , We have CCn min (Plu, exp(- because let n' 3x 3x² we have CW(x') = WCW(=') = {2], ACW(=') = 0, and Plu(T') {1}.
min
I1 amn J, i.e., semi-random CC becomes likelihood of CC w.r.t. IC. We have CC (Plu, n) (1) A (1 (()), because (TTa)))) 0. WCW(Fum)) = 2,3, and ACW((um)) 0.
Semi-random CC under int-MRSE Rules. Semi-random CC under an MRSE rule 7 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 alter- native that loses to all head-to-head competitions. For any voting rule T, we write CL.(F) if and only if satisfies CONDORCET LOSER.
To present the result, we first define parallel universes under an MRSE rule F at R denoted by PU+(T), to be the set of all elimination orders in the execution of 7 at Æ. Then, for any alternative a, let the possible losing rounds, denoted by LR=(# a) S [m 1]. be the set of all rounds in the parallel universes where a drops out. The formal definitions and an example can be found in Definition 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 fixed m 2 3, let M (9, C(A), II) be a strictly positive and closed single-agent preference model, let r = (T F') be an iRR- rule and let be refinement of.. For any n E N with 2 n, we have
if 42 < S m. CL(F.) =1
(1) 32 Sis m s.t. CL(T,) = and
1 - ex))(((((n)
if (2) VJ E CH(II), Va E Vi E LRF(TT a), we have C[(Tm+1=:)=1
min
CCn (r,m)
if (1) VT E CH(II), (4) = 0 and
O(n -05)
(2) 3 E CH(II) s.t. (ACW(T) (A F(m)) =
exp(-
if 3m E CH(II) s. C (T)) #
(1-))(1-00)
otherwise
The most interesting cases are the 1 case and the 1 1 exp(-(((((()) case. The I 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 (n)) case happens when (1) the 1 case does not happen, and (2) for every
The 1 distribution x E CHIII), every weak Condorcet winner a, and every possible losing round i" for a, the positional scoring rule used in round i", i.e. Tm+l-=*, must satisfy CONDORCET LOSER. (2) guarantees that when a small permutation is added to r,, if a weak Condorcet winner 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.
7

---

Like Theorem 1, Theorem 2 can also be easily applied to i..d. distributions, which corresponds to Ihc {mii.
Corrollary 1 (Likelihood of CC under int-MRSE rules w.r.t. IC). For any fixed m 2 3, any
refinement of any int-MRSE rule r, and any E N,
1 Pr (CC(r, P) = 1)
if sis m, CL( =
(
otherwise
Proof sketches for Theorem and 2. In light of various multivariate central limit theorems (CLTs), when is large, the profile is approximately n '-" for π (Ei= Ty)/n E CH((I) with high probability. Despite this high-level intuition, the conditions of the cases quite differently from semi-random CC by definition. To see this, note that (i) the adversary may not be able to set any agent's ground truth preferences to be x' CH(LI), because ''" may not be in II as shown in Example 3, and (ii) in the definition of semi-random CC, agent j"s vote is a random variable distributed ;, instead of the fractional vote ς.. Standard CLTs probably be applied to prove the 1 1- cxp(-6(m)) case and the ((1) A (1 - O(1) case, but they are too coarse for other cases.
To address this challenge, model the satisfaction of CC by the union of multiple polyhedra C as exemplified Section This converts the semi-random CC problem to a PMV-in-C problem [55] (Definition 3 below). Then, we refine [55, Theorem 2] to prove a categorization lemma (Lemma 1), and apply it to obtain Lemma that characterizes semi-random CC for a large class of voting rules called generalized irresolute scoring rules (GISRs) [22, 53] (Definition 7 in Appendix D.I). Finally, we apply Lemma to integer positional scoring rules and int-MRSE rules to obtain Thcorem I and Theorem 2. The full proof can be found in Appendix E.2 and E.3, respectively.
The semi-random satisfaction of PAR. Due to the space constraint, we briefly introduce our charac- terizations of
PAR under commonly-sten studiee voting rules defined in Appendix A, which belong to a large class of voting rules called generalized scoring rules (GSRs) [56] (Definition 7 in Appendix D. I). Formal statements and proofs of the theorems can be found in Appendix F.2-R5.
Theorems 3, 4, 5, 6 (Semi-random PAR under commonly-studied rules). For any fixed m 4, any GSR r that is refinement of maximin, STV, Schulze, ranked pairs, Copeland, any int-MRSE, or any Condocetified positional scoring rule (such as Black's rule), and any strictly positive and closed min (r,
II over ((A) with Tuii E CH(TT), there exists N E N such that for every N, PARTI 1 0 (a)
In fact, if Tuni & CH(IT), then semi-random PAR converges to 1 at a faster rate, which is more positive news, as shown in Lemma 3 (Appendix F.
4 Beyond CC and PAR: The Categorization Lemma
In this section, we present general lemma that characterizes semi-random satisfaction of per-profile axioms that can be represented by unions of polyhedra, including CC and PAR. To develop intuition, start with an example of modeling CC under irresolute plurality as the union of the following two types of polyhedra in ITn!
CNew represents that there is Condorcet winner, which is the union of polyhedra H. where G is an unweighted graph over A that does not have a Condorcet winner, as exemplified in Example 4.
Ceww represents that the Condorcet winner exists and also wins the plurality election, which is the union of polyhedra He for every a E A, that represents a being the Condorcet winner as well as a Plu co- co-winner, exemplified in Example
Example 4 (H Let 3 and let Zabe denote the number of [a b > c) votes in profile. The following figure shows (left) and HC (right).
(I213 + T231 + T321) ) (Ø123 + Z132 + T312) < -1
(2)
G
(I123 + 2232 + 2211) (Ø231 + +3321 + T312) < -1
(3)
(I132 + 2312 D321) ) (x123 + 2213 T231) < 0
(4)
3
(I123 + 2213 + 2231) - (œ132 + #312 + x321) 0
(5)
8

---

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 and G.
Example 5 ). Let m = 3. Ht' is the polyhedron represented by the following four inequalities:
(2213 + D231 + T321) (Ø123 + 2132 + 2312) - -1
is the Condorcet winner
(2231 3321 2312)
(I123 2132 + 2213) - -1
(1213 + 2231) (#123 2132) S 0
is a Plix co-winner
(1321 + 2212) - (1123 + 2132) 50
It is not hard to see that Plu satisfies CC at profile if and only if Hist(P) is in C CNew UCwww, where UNew UG:cw(C)=) HS and Ccww = -aEA H.S An example of PAR under Copeland can be found in Appendix C.I. In general, the satisfaction of wide range of axioms can be represented by unions of finitely many polyhedra. Then, the semi-rane semi-random satisfaction problem reduces to the lower bound of the following PMV-in-C problem.
Definition 3 (The PMV-in-C problem [55]). Given q, E N, C = -isI Hi where Vi S I, H4 S IR9 is polyhedron, and a set IT of distributions over [g], we are interested in
the upper bound supæEm= Pr(X, E C), and the lower bound inf Pr(X# EC),
where X is the (n, P)PPosn multinomial variable (PMV) that corresponds the histogram of independent random variables distributed as म.
See Example 7 in Appendix C.2 for example of PMV. The following lemma provides asymp- totic characterization on the lower bound the PMV-in-C problem.
Lemma 1 (Categorization lemma, simplified). For any PMV-in-C problem and any N. inf=em- Pr(X= C) is O, exp(-O(n)), (n), @(1) A (1 0(1), 1 p poly (n), - --exp(-O(m)) or 1.
The full version of Lemma (Appendix C.2) also characterizes the condition for each case, the degree of polynomial, and sup Pr(X= E C). Lemma I's main merit is conceptual, it catego- rizes the semi-rande 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 first three cases (0, VU, U) are negative news, where the adversary can set the ground truth that the axiom is almost surely violated in large elections (n - oc). The last three cases (L, VL, and 1) are positive news, because the axiom is satisfied almost surely in large elections, regardless of the adversary's choice. The M case be interpreted positively or negatively, depending on the context.
Name 0
VU
M
VL
1
Lem. 0
exp( (n))
poly (n) 0(1) A (1 0(1)) 1 poly (n)
exp(-O(n)) (n))
1
Future work
There are many open questions for future work. While we believe that the assumptions (of strict positiveness and closedness) on II are mild, is an important and interesting open question to extend the analysis to variable e'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 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, an important, promising, and challenging mission, and the categorization lemma (Lemma 1) can be useful conceptual and technical tool to start with.
Acknowledgments
We thank attendees COMSOC-21 and anonymous reviewers for helpful comments. This work supported by NSF #1 #1453542, ONR #N00014-17-1-262.1 and a gift fund from Google.

---

References
[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örg 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 multi- attribute problems with even swaps. Proceedings of the Thirtieth Conference Annual Con- ference on Uncertainty in Artificial 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):244-33, 1995.
[9] George E. P. Box. Robustness in the strategy of scientific 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 Voling Sys- lems with Probability Models. Springer, 2021.
[1]] Marquis de Condorcet. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. Paris: L' 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-Firs First International Joint Conference on Artificial Intelligence (IJCAI), pages 109-115, Pasadena, CA, USA, 2009.
[13] Mostapha Diss and Vincent Merlin, editors. Evaluating Voting Systems with Probability Mod- els. 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 Worst-Case Analysis of Algorithms. Cambridge University Press, 2021.
Models. In Tim Roughgarden, editor, Beyond the
[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 Brams, Paradoxes of Preferential Voting. Mathematics Maga- zine, 56(4):207-114, 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. 2783):178-1885 1977.
10

---

[22] Rupert Freeman, Markus Brill, and Vincent Conitzer. General Tiebreaking Schemes for Com- putational Social Choice. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 1401-1409, 2015.
[23] William V. Gehrlein. Condorcer'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 Fishburn. Coineidence probabilities for simple majority and positional voting rules. Social Science Research, 7(3):722-283, 1978.
[26] William V. Gehrlein and Peter C. Fishburn. Probabilities of election outcomes for large elec- torates. Journal of Economic Theory, 19(1):38 49, 1978.
[27] William V. Gehrlein and Dominique Lepelley. Voting Paradoxes and Group Coherence: The Condorcet Efficiency 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 prin- cipled voting. In Proceedings of the National Conference on Artificial Intelligence (AAAI), Bellevue, WA, USA, 2013.
[35] Nicholas Mattei and Toby Walsh. PrefLib: A Library of Preference Data. In Proceedings of Third International Conference on Algorithmic Decision Theory, Lecture Notes Artificial Intelligence, 2013.
[36] David C. McGarvey. A theorem the construction of voting paradoxes. Econometrica, 21 (4):608-610, 1953.
[37] Samuel Merrill. A statistical model for Condorcet efficiency 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 Power- lessness to Absolute Power. Journal of Artificial Intelligence Research, 48(1):923 951999111111 2013.
[39] Hervé Moulin. Condorcet's principle implies the no show paradox. Journal of Economic Theory, 45(1):33-64, 1988.
[40] Jill Van Newenhizen. The Borda Method Is Most Likely Respect the Condorcet Principle. Economic Theory, 2(1)):9-2-8)) 1992.
[41] Hannu Nurmi. An Assessment Voting System Simulations. Public Choice, 73(4):459-487, 1992.
[42] Hannu Nurmi. Voting Paradoxes and How to Deal with Them. Springer- Berlin Heidel- berg, 1999.
[43] David C. Paris. Plurality distortion and majority rule. Behavioral Science, 20(2): 13-3133,, 1975.

---

[44] Donald G. Saari. Basic Geometry of Voting. Springer, 1995.
[45] Mark Satterthwaite. Strategy-proofnes, and Arrow's conditions: Existence and correspon- dence theorems for voting procedures and social welfare functions. Journal of Economic The- ory, 10:187-217, 1975.
[46] Alexander Schrijver. Theory of Linear and Integer Programming. Wiley, 1998.
[47] Markus Schulze. A monotonic, clone-independent, reversal symmetric, and condorcet- consistent single-winner election method. Social Choice and Welfare, 36(2):267- -03, 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 Infor- mation Systems, Articce 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 Sixleenth ACM Conference on Economics and Computation, pages 661-678, Portland, Oregon, USA, 2015.
[54] Lirong Xia. The Smoothed Possibility of Social Choice. Proceedings of NeurlPS, 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. Proceedings of the ACM Conference Electronic Commerce, pages 109-
118, 2008.
[57] Lirong Xia and Vincent Conitzer. Finite local consistency characterizes generalized scoring rules. Proceedings of the Twenty-First International Joint Conference on Artificial Intelli- gence, pages 336-341, 2009.
12


Reviews:
[{"review_id": "wdq5lcnHGbl", "reviewer": "Reviewer_XDdy", "summary": "This paper addressed a comprehensive picture of smoothed satisfaction of voting axioms\nunder commonly-studied voting rules, by focusing on CC and PAR (Condorcet criterion and participation).", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The theoretical contribution of the paper is sound and overall comprehensive to parse. Under certain assumptions, the main results derive the smoothed satisfaction of Condorcet Criterion (for m>3 and sufficiently large n) and PAR, under a wide range of voting rules. \n\nThere should be a discussion on how brittle the analyses are under the imposed assumptions (Thm 1 to 6), to what generality the results can be argued upon lifting them? How the current analyses could be extended to smoothed satisfaction of other voting axioms?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~3-4"}, "extra_text": {}}, {"review_id": "gfGhFI_84Em", "reviewer": "Reviewer_mLZB", "summary": "This paper studies the smoothed satisfaction of voting axioms, which is a novel notion to quantify the dissatisfaction of voting axioms based on smoothed analysis. This paper aims to address the following open question: \"How likely are voting axioms satisfied under realistic models?\"\n\nThe main contribution of this work is that they propose the framework of smoothed satisfaction and give pretty general quantitative results of dissatisfaction of various voting axioms for different voting rules. In particular, their results imply two important but contradicting axioms (under worst-case analysis): Condorcet criterion (CC) and Participation both can be actually satisfied in many realistic settings.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The smoothed social choice framework was first proposed by Xia, which is a mid-point between the impartial culture setting and the traditional worst-case analysis. In this paper, they use this framework to define smoothed satisfaction and analyze how likely voting axioms satisfied under realistic settings. I believe it is a very important question to ask, and it is a sweet spot for smoothed analysis. This paper demonstrates that some axioms which cannot coexist in worst-case analysis can be satisfied simultaneously in some realistic settings.\n\nMajor technical contribution of this paper is that authors show several pretty general quantitative results of how likely various voting axioms could coexist in realistic setting. Having that said, I do think the writing of the technical part can be improved. I feel it is just too dense, notations are a bit overwhelming.\n\nOverall, it is a very strong paper, it addresses a long-standing (and important) open problem and demonstrate the power of smoothed analysis. The highlight of this paper is that it proposes a pretty general (and sound) framework to analyze satisfaction of voting axioms in somewhat realistic settings. This paper also shows quantitative results for two important axioms (Condorcet and Participation) under many important voting rules. The major concern is that this paper might be too technical to follow, I would strongly recommend the authors to make the body less technical, front-loading some intuition and maybe dumping some results into appendix may help.\n\ntypos: \n1) Line 28, \"exist\" -> \"exists\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitation", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "AA-782wR0av", "reviewer": "Reviewer_mywX", "summary": "The authors study the likelihood that two voting axioms -- the Condorcet criterion and participation -- will be satisfied when an adversary chooses an arbitrary set of preferences of the agents, and then these preferences are perturbed with random noise. They establish two main theorems that show that the likelihood that each axiom is satisfied under smooth analysis is very case-dependent, but that the Condorcet criterion is generally less likely to be satisfied than participation.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On a high level, I agree that voting axioms are generally quite rigid and oftentimes too coarse. It is also definitely discouraging sometimes to only prove impossibility results. In this sense, smoothed analysis makes sense for studying the satisfiability of voting axioms under more realistic models of vote generation, and I appreciate the approach taken by the authors in this paper.\n\nIn general, I found the technical exposition to be quite dense and incredibly notation-heavy. I appreciated the efforts of the authors to provide high-level intuition for many of the results, and the tables really help the reader. \n\nOverall, I was very impressed (and daunted) by the technical content of the paper (really the appendix, I guess, given the page limit), and I think the authors did a good job cleaning up the presentation and adding intuition for a shorter format. I do think the best fit for this work is in a social choice journal, given the scope of the work, but I do not think it is outside the scope of NeurIPS.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "0YHWA_WPw_t", "reviewer": "Reviewer_Ck6b", "summary": "The paper builds up on a semi-random model for preference profiles by Xia. For a constant number of alternatives and a number of agents going to infinity, the authors study how likely different voting rules violate Condorcet consistency / participation on the semi-randomly drawn preference profile. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper contains a trove of fascinating results. The main results characterize integer scoring rules and their asymptotic behavior with respect to Condorcet consistency and participation, and the appendix give a range of additional results characterizing participation for other prominent voting rules. The paper makes a convincing case in the introduction that these (fairly abstract) characterizations have plenty of implications that social-choice researchers should care about, such as new results for participation under impartial culture and general take-aways for the relative likelihood of violations of the two properties (where it is known that Condorcet consistency and participation cannot be simultaneously guaranteed for 4 and more items).\nAt least as important is Lemma 1, an abstracted version of the results by Xia 2021, which builds the foundation of the previous results, but is also clearly applicable to axioms other than participation and Condorcet consistency. I cannot judge how much of that generality was already present in Xia 2021, but, if this is indeed new, this seems like a big and valuable contribution that can likely draw a whole string of papers behind it.\n\nA first comment that I have is that I think the term \"smoothed analysis\" is a misleading description of what the paper does. I realize, of course, that this terminology is taken over from Xia 2020 (where another reviewer pointed out the same thing [1]), but I think it would be a service to the community to adapt the terminology. In smoothed analysis as introduced by Spielman and Teng, (a) a worst-case instance is randomly perturbed and (b) results are analyzed as a function of both n and sigma, the variance of the noise. By contrast, Xia's model presumes a menu of distributions and then has an adversary combine these distributions; and the paper does not analyze the dependency on the \"noise\" (here: the epsilon in the definition of a strictly-positive single-agent preference model).\nI think a better terminology would be to call the model a semi-random model since it interleaves worst-case and probabilistic steps. In the literature on semi-random models, adversarial and probabilistic steps have been interleaved in many different ways (see, for example, Section 2.3 of this paper by Kolla, Makarychev, and Makarychev [2]). None of this should be understood as a critique of the model, and I think that the model indeed is useful for similar reasons as a smoothed-analysis model, which makes sense that both models are semi-random. Still, the term smoothed analysis is misleading and should be avoided.\n\nMy second concern is with the presentation of the paper. My impression is that the nine-page format does this paper a real disservice. The authors clearly know their craft, but the space constraints riddle the paper with abbreviations, quick sequences of theorem environments, and a lot of the paper \"tells rather than shows\", which is natural given the 60 pages of theoretical appendices and the fact that Theorems 3–6 don't even fit into the body. While reading, I was missing more signposting of what was up ahead, and more patient discussions relating the results (the introduction does this very well, I just would have liked more of it). Within these constraints, the exposition is clear, but it is a harder read than it would have to be with extra pages, and I am concerned that there is to little space to reflect on the results and make them shine. I don't think this is reason enough to reject the paper, but I think it severely limits the usefulness of the paper as printed at NeurIPS. I strongly encourage the authors to publish a longer, more patient version on arxiv/in a journal to maximize the impact of the work.\n\n\nSmaller comments:\n- I think \\Theta(1) /\\ 1 - Theta(1) should be spelled out somewhere: for large enough n, the probabilities will be bounded by some constants alpha, beta with 0 < alpha < beta < 1.\n- In Figure 1, the formulation \"other ranking w.p. 1/8\" was very misleading to me. After reading a section coming much later, I think this is supposed to mean that \"every other ranking\" has probability 1/8 (the adding-up-to-1 constraint was less obvious to me given that your weighted preference profiles don't have normalized weights). Moreover, I'm pretty sure that the weighted majority graph should have weights 1/8 rather than 1/4.\n- in line 254, it wasn't clear to me what in the condition corresponds to the \"small perturbation\", this deserves more details.\n- based on the introduction, I would have expected Lemma 1 to appear before the main results rather than after. I think this should be signposted in the sections where the main results appear.\n- the first paragraph of Section 3 did little to explain what was the goal of the section, and instead paraphrased the immediately following definition 2. This paraphrase threw me off rather than helping me.\n- a whole range of abbreviations were undefined at first use (there might be some false positives): ANR in line 142, MRSE is used in line 181 before being introduced in line 190, CH in line 240, PMV in line 324 is only defined in line 361.\n- in the equation in line 240, for example, many sets are intersected with A \\setminus r(\\pi). It seems easier to just subtract the set r(\\pi), which is equivalent.\n- typo: \"Condocetified\" in line 336, \"sutdied\" in line 379\n\n––\n[1] https://papers.nips.cc/paper/2020/file/7e05d6f828574fbc975a896b25bb011e-Review.html\n[2] https://arxiv.org/pdf/1104.3806.pdf", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think that more could be said in terms of the limitations of the paper: To which degree can and should one see the model as a proxy for preference profiles in practice? What are examples for properties that cannot be phrased as the union of finitely many polyhedra (i.e., for which Lemma 1 does not apply)?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives several interesting results on the smoothed satisfaction of voting axioms. I, and all of the reviewers, have a positive view of the paper. I recommend acceptance.
Decision: Accept (Spotlight)