The Distortion of Binomial Voting Defies Expectation
Authors: Yannai Gonczarowski
Gregory Kehne
Ariel D. Procaccia
Ben Schiffer
Shirley Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: computational social choice
statistics
distortion
TL;DR: A new voting rule called binomial voting provides strong guarantees with respect to expected distortion, a novel measure of social desirability.

Abstract: In computational social choice, the distortion of a voting rule quantifies the degree to which the rule overcomes limited preference information to select a socially desirable outcome. This concept has been investigated extensively, but only through a worst-case lens. Instead, we study the expected distortion of voting rules with respect to an underlying distribution over voter utilities. Our main contribution is the design and analysis of a novel and intuitive rule, binomial voting, which provides strong distribution-independent guarantees for both expected distortion and expected welfare.

The Distortion of Binomial Voting Defies Expectation"
Yannai A. Gonezarowskit
Gregory Kehne
Ariel D. Procaccia
Ben Schiffer
Shirley Zhang
Abstract
In computational social choice, the distortion of voting rule quantifies the degree to which the rule overcomes limited preference information to select a socially desirable outcome. This concept has been investigated extensively, but only through a worst-case lens. Instead, we study the expected distortion of voting rules with respect to an underlying distribution over voter utilities. Our main contribution is the design and analysis of novel and intuitive rule, binomial voting, which provides strong inarieetioon-dddeeeddent guarantees for both expected distortion and expected welfare.
Introduction
In an election, voters report their preferences by casting ballots. Under the ubiquitous plurality rule, each voter names single alternative, whereas other rules rules-sume such as the badly named ranked-choice voting," 7 whose adoption is rapidly expanding in the United States- require voters to rank the alternatives. However, even these ostensibly expressive ordinal ballots (whereby voters rank the alternatives) fail to capture voters' intensity preference under truthful reporting.
If voters could report utility functions that are comparable to each other, then we would want to select socially desirable alternatives with respect these utilities, but it is typically impractical to expect voters to compute and report such utilities. This creates tension between the limited information available to the voting rule (through the report of ordinal ballots only) and its goal (good outcomes with respect to latent cardinal utilities).
significant body of work in computational social choice aims to understand and alleviate this tension [Anshelevich et al., 2021]. It revolves around the notion of distortion, defined as the worst-case ratio between the utilitarian social welfare (sum of utilities) of the voting rule's outcome and that of the welfare- maximmiing alternative. The worst case is taken over rankings, which serve as input the voting rule, and over utilities that are consistent with these rankings.
"Gonezarowski gratefully acknowledges research support by the Harvard FAS Incquality in America Initiative. Procaccia gratefully acknowledges research support by the National Science Foundation under grants 114-2147187, IIS-2229881 and CCF-2007080; and by the Office Naval Research under grant N00014-20-1-2488 Schiffer was supported by an NSF Graduate Research Fellowship. Zhang was supported by NSF Graduate Research Fellowship.
Department Economics and Paulson School of Engineering and Applied Sciences, Harvard University E E-mall: yannai @ gonch.name.
l Department Computer Science, University of Texas Austin E-mail: gkchne@utexas. edu.
Paulson School of Engineering and Applicd Sciences, Harvard University E-mail: ariel-
scas. hawaaddaavaddddd.
Department of Statistics, Harvard University E-mail: bschifferl @ harvard.ddddd.
Paulson School of Engineering and Applied Sciences, Harvard University E-mail: szhang2 @ hdr. Also known as "instant-runoff" voting" or "alternative vote."
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

As is often the case with worst-case analysis. however, the classic notion of distortion is arguably too conservative. In particular, nontrivial guarantees require restrictive assumptions (see Section 1.2). and so this type of analysis may not help identify appealing voting rules.
With this difficulty in mind, focus on expected distortion. Its definition includes the same ratio as before, and we are still interested in the worst case over rankings. However, we now take the condi- tional expectation over utilities consistent with the rankings, given an i.i.d. distribution over the utili- ties. Of course, it might not be realistic for such a distribution to be known a priori, and thus we search for voting rules that are distribution independent': rules that choose the outcome in a way that does not depend on this distribution, even though their guarantees are stated in terms of this distribution.
Overall, our goal is to design distribbttioninddeeedde voting rules that provide appealing expected distortion guarantees. We uncover novel, potentially practical, voting rules with these properties.
1.1 Our Results
We start by considering the important case of two alternatives (e.g.. US presidential elections or yes/no decisions) in Section 3. We show that, for any underlying distribution, the majority rule optimizes both expected distortion and expected social welfare.
This result suggests that maximizing expected social welfare may be a good approach for optimizing expected distortion. Indeed, our main result in Section 4 is that, under mild conditions on the underlying distribution and for a sufficiently large number of voters or alternatives, the expected- welfare- maximizing rule optimizes expected distortion almost perfectly.
The weeedddwwlfl--maateeee
rule, however, is tailored to the underlying distribution and relies on intimate knowledge thereof. Our aim is therefore to approximately optimize expected welfare via a iisaributiin-independeee
rule.
In Section 5, we design and analyze such a rule, which belongs to the family of (positional) scoring rules. Under this rule, which we call binomial voting, each voter awards V (7) points to the alternative ranked in the kth position, where m is the number of alternatives, and the alternative awarded the largest number of points overall is selected; note that this rule is distribution independent. Our main result of Section 5 is that for any underlying distribution supported on [0, 1] with (largest) median v/ binomial voting provides a multiplicative --approximation to the optimal expected welfare. Combining this result with that of Section 4, it follows that binomial voting gives almost the same Y guarantee for expected distortion, when the number of voters or alternatives is sufficiently large.
is worth noting that binomial voting is not an outlandish rule designed purely to achieve low expected distortion. On the contrary: positional voting rule, inherits the desirable properties of this family. In fact, positional scoring rules are characterized by a number of natural axioms [Young, 1975]. Furthermore, we are aware of very few positional scoring rules that have received attention in their own right, as it is typically difficult to justify any specific choice of scores; in this sense, the expected distortion framework can be seen as a way of pinpointing particularly useful parameters. In summary, we identify binomial voting as an unusually attractive rule when viewed through the lens of expected distortion.
1.2 Related Work
The literature on (worst-case) distortion [Anshelevich et al., 2021] can generally be partitioned into two threads. In the first thread [Procaccia and Rosenschein, 2006, Boutilier et al., 2015, Caragiannis et al., 2017, Mandal et al., 2019, Ebadian et al., 2022], it is assumed that voters have normalized utilities, that is, for each voter, the sum of utilities is one. Even with this restrictive assumption, deterministic voting rules cannot give nontrivial distortion bounds [Caragiannis et al., 2017], and the best possible distortion for randomized rules is ((//m)) [Ebadian et al., 2022]. In the second thread [Anshelevich and Postl, 2017, Gross et al., 2017, Anshelevich et al., 2018, Gkatzelis et al., 2020, Kizilkaya and Kempe, 2022], known as metric distortion, it is assumed that utilities (rather, costs) are induced by an underlying metric space. While some well-known voting rules have constant
$ Foor this reason, we avoid calling this distribution a Bayesian prior.
9This term is inspired by the literature on indeeeindeenneett mechanisms within mechanism design.

---

distortion in this setting [Anshelevich et al., 2018], the metric assumption is arguably difficult to justify in most domains of interest. By contrast, we make no assumptions on utilities.
Our work is most closely related to that of Boutilier et al. [2015]. While their most substantial results pertain to worst-case distortion, one of their results deals with distributional setring that can be seen as the starting point for our work. They show that the voting rule that maximizes expected social welfare is a scoring rule whose scores depend on the underlying distribution; we will revisit and build on this result. However, they do not study expected distortion, nor do they explore (in this context) voting rules that are agnostic to the distribution.
Previous papers that analyze expected distortion include those of Cheng et al. [2017, 2018]. However, their papers are fundamentally different. For one, they study metric distortion. More importantly, they focus on one intuitive but very specific distribution, where the positions of alternatives in the underlying metric space are drawn uniformly at random from the voter positions. By contrast, study general (i.i.d.) distributions over utilities and design dissributionnindeeeeden voting rules. The work of Ghodsi et al. [2019] more distantly related: they also analyze expected distortion in the metric setting, assuming that voters abstain with some probability.
By replacing worst-case analysis with expectation, our work introduces Bayesian view canonical to economic theory into the literature on distortion. The Wilson doctrine [Wilson, 1987] advocates for the use of mechanisms that require as little prior information possible. (sometimes called (roeenndepenn)et) mechanisms are, through this lens, the most desirable ones as they require prior information at all, and have been studied within economics [see, e-g., McAfee, 1992, Segal, 2003] as well as within computer science [see, e.g., Hartline and Roughgarden, 2009, Devanur al., 2011, Babaioff et al., 2018]. Our work can also be within computer science on "beyond worst-case" analysis of algorithms [Roughgarden, 2021].
belonging recent push
2 Model and Preliminaries
of voters and a set A = (1,,2....,m m.) of alternatives. Each voter has utility Ua for each alternative j. The voter utilities collectively form utility profile u, and the utilitarian social welfare for alternative j is denoted as sw(j, u) --= EiEN Viy. Each voter's utilities induce a ranking 0, = o, (u) over alternatives, where j is ranked higher than k in o; only Ui 2 U4k. Let = (01. .......... o,) be the preference profile consisting of the rankings of all voters.
Let there be a set N
(deterministic) voting rule f takes as input a preference profile and outputs a winning alternative f(a) E A. One can also define randomized voting rule, which returns distribution over alterna- tives. The definitions given below easily generalize to randomized rules, by considering their expected social welfare, where the expectation is taken over the randomness of the rule. We focus on determin- istic rules, however, for two reasons: first, for ease of exposition, and second, because deterministic rules are in fact powerful as randomized rules in our setting,
show in Appendix A.
The worst-case distortion of f intuitively measures the loss in social welfare incurred by f, and is given by:
max sw sw(j.u) u) sup SW (f(o(()))
The numerator is the optimal social welfare, whereas the denominator is the social welfare of the outcome under f: the worst case of this ratio is taken over utility profiles u. Note that a voting rule f minimizes this expression if and only if it maximizes its inverse, and, more generally, that inverting this ratio does not change any of the results for worst-case distortion.
2.1 Distributional and Expected Distortion
Our point of departure is that we introduce an "average-case" setting; for the rest of this paper, we will assume that the voters' utilities for the alternatives are drawn i.i.d. from an underlying distribution D. Unless otherwise noted, we will also assume that D is supported on [0, 1]. We will frequently use μ and 8² to denote the mean and variance of D. respectively.
1TTie breaking can be performed arbitrarily, and is of no consequence for results.
3

---

Let i o denote that the utility vector u is consistent with the preference profile o. Given preference profile or a utility vector u drawn with respect the distribution D follows. Each voter i N draws m i.i.d. utilities from D, and these m utilities are assigned from highest to lowest to the m alter- natives according to the order of s the ranking of voter i under a. We define the distributional distor- fion under D of a voting rule f for preference profile o as the following random variable, in the prob- ability space defined by the above construction (for drawing u u ar with respect to the distribution D);
sw(f(o), u)
ddist( maxjEA (w(
Note that this random variable representation of distributional distortion is in contrast to the single number representation in worst-case distortion. For the rest of this paper, when we refer to the distortion of a rule f. we are referring to the distributional distortion. We define the expected distortion of f for a as E[ddist(f,
In Equation (2), we have defined distortion with the maximum in the denominator of the fraction. This means that the expected distortion of a voting rule lies in the range [0, 1], and a larger value of expected distortion (closer to 1) corresponds to a better voting rule. Note that this choice stands in contrast to Equation (1). As noted previously, inverting the ratio does not change the optimal rule J for worst-case distortion. However, this no longer holds true when considering expected
distortion. For a random variable X, in general E [ * E[XT and therefore rules that minimize
E[X] can look very different compared rules that maximize B [ The reason for our choice is twofold. First, if the ratio were inverted then the random variable would be unbounded, which would imply that its expectation could be infinite even when the distribution D bounded on [o, 1]. It turns out that this might be the case even for nice distributions such as beta distributions, as we prove in Appendix B. Second, if the ratio were inverted then there would exist distributions for which the best deterministic rule performs arbitrarily worse than the best randomized rule, even in situations where we would normatively expect the two rules to behave the same. That would prevent us from focusing on deterministic rules, as we are able to do here. For more details, see Appendix C.
We define oppectaldiistoriinn-mmiii every preference profile a, maximizes the expected distortion under that profile. In other words, an distortion
rule (henceforth, an EDMR) as rule that, for
rule f satisfies
E[ddist (f, a)] = max [[ddist m]]
for all preference profiles σr, where the maximum is taken over all possible voting rules g. We write edmr(.) .) to refer to an EDMR.
2.2 Distributional and Expected Social Welfare
Similarly to Boutilier et al. [2015], we also wish to consider expected social welfare. To this end, we define the distributional social welfare of a rule f for preference profile or as the random variable
dsw(f. σ) sw(f(r), u)
in the same probability space before (defined by the construction for drawing u with respect to a distribution D). We define the expected social welfare of f for o as B[dsw(f.or]
An expette-weljare-nnaiiniiig rule (henceforth, an EWMR) is a rule f that, for all preference profiles o, maximizes the expected social welfare, i.e., such that for all o,
E [[dsw(( (f,o)) = max E dsw(g, o)).
9
We write ewmr(.) to refer to an EWMR.
The family of (positional) scoring rules consists of voting rules that assign a vector of scores (81, ..., 8m) to alternatives, from highest ranked through lowest ranked, respectively. The alternative that is chosen is the alternative that has the highest total score when adding up all of the rankings across the n voters, with ties broken arbitrarily. Boutilier et al. [2015] show that a scoring rule using scores
(S1, 8m) = (m)) E[X (1[X(mm)))) 1)]- ((x(1)))
an EWMR, where E. E[X (m)) is the expected value of the m m order statistic from m i.i.d. draws from D. Note, however, that this rule is tailored to the specific distribution D.

---

2.3 Approximately Optimal Rules
The goal of this paper is to explore rules that are approximately as good as an EDMR, but are distribution independent, i.e., are not tailored to D. This will rely on approximations to an EWMR. We call a voting rule an a-Expected Exxpected-Distortion--- Iistortion-Maximiziin Rule (a-EDMR) for distribution D if, for all preference profiles the expected distortion of f is at least a times the expected distortion of an EDMR. In other words, f is an a-EDMR for D if for all a,
[[dddist(J, o)] 2 a [Edddis(eedmr, a
If a voting rule a EDMM), then we refer to it as an E-approximation of an EDMR.
We use the analogous terminology of a-EWMR for rules f such that, for all or
E [[dsw(J, (f, m)] 2 a [eww(e ar)
To make our goal more tangible, consider policy maker in charge of choosing voting rule for a certain municipality. There are various guarantees such a policy maker might wish for the voting rule to satisfy with respect to (expected) distortion. If said policy maker is choosing voting rule to use for years to come, they are likely to be interested in distribution-indeeenden guarantees, since demographic distributions might shift over time.
first guarantee in which such a policy maker might be interested is that ex ante, before an election is held, the distortion is expected to be low. Note that this expectation is over the entire space of voter utility profiles. While this is an appealing guarantee, it is rather weak (and easy to satisfy). To see the sense in which it is weak, consider the policy maker not at the day on which they choose the voting rule, but rather while later, in specific election that uses this rule, after the votes have been cast and officially tallied. At this point in time, the ordinal preferences a are public knowledge, and, depending on what they are, it might be the case that despite the expected distortion having been low ex ante, turns out that the expected distortion is high post, that is, it turns out that conditioned on all of the public information so far-i.e., conditioned on the ordinal preference profile ohe (conditioned) ex- pected distortion is high. While the policy maker had good reasons to choose the voting rule ex ante, news outlet might still run a news story noting that given the tallied (realized, possibly low probability) ordinal preferences o,, there is reason expect very high distortion. A forward-lookee press-averse) policy maker might want a (worst-case) guarantee that this scenario cannot happen, i.e., worst-case guarantee the ex post expected distortion. This is of course a much stronger guarantee (in particular, it also implies the same guarantee on ex ante expected distortion), and is considerably harder to satisfy. Seeking rules that give such guarantee is precisely the goal of this paper.
(and negative-
We note that such an ex post guarantee is in a sense the strongest guarantee that such a negative-press averse policy maker might wish for. Indeed, an even stronger guarantee would be for the distortion to be low given the actual realized cardinal preferences u, which coincides with "traditional" worst-case distortion, but since the policy maker cares about press coverage, and since the realized cardinal preferences never become public knowledge (and hence, never become the basis for a news story), such strong guarantee would be overkill for the policy maker. This is of course fortunate, because as noted in Section 1.2, there are impossibilities that preclude getting such an overly strong guarantee in iesributtion-idepeedeeee setting like ours.
3 The Case of Two Alternatives
To develop some intuition, let us start with a naive attempt to compute an EDMR: calculate the expected distortion for each alternative j E A, and choose the alternative that optimizes the expected distortion. This algorithm has two major shortcomings, however. First, calculating the expected distortion of fixed alternative requires nm concentric integrals, and therefore this algorithm would take time that is exponential in both n and m. Second, the naive algorithm requires knowledge of the underlying distribution D.
Even for the case of two alternatives, the above algorithm is exponential in n and therefore not computationally feasible-not not to mention that it still requires knowledge of the distribution. However, turns out that for this special case, which selects the alternative preferred by the majority of voters (with ties broken arbitrarily) both an EDMR and an EWMR. Majority is furthermore computationally efficient and iestributioninndeeeedeee all of the desiderata discussed so far. As bonus, it is also indisputably practical.
(i.e., agnostic to the distribution), so it satisfies
5

---

Theorem 3.1
Let m = 2. For every distribution D. majority is both an expected-distortionn maximizing rule and an weeteeedwwweff-mmmaaxiee
rule.
Proof. We first show that majority is EWMR. Let i and μ22 be the expected values for the minimum and maximum, respectively, of two i.i.d. draws from DD Let 0 s k S n be the number of voters that prefer alternative 1 to alternative 2. Then, by linearity of expectation, the expected welfares for alternative and alternative are k112 + (n k)p1 and (n - {) kj4,, respectively. Since μ12 2 μl, alternative 1 an expected wellarre-mxximiiing alternative if and only if k: 2 k.
To prove that majority an EDMR, we use a coupling argument to show that the expected distortion of alternative that is ranked first by & out of n voters is increasing in k. A direct consequence of this is that a majority winner is an
alternative.
Recall that úiy is defined as the utility that voter i has for alternative j for i E N and j E {1, 2}. Let o% be the preference profile for voters that has alternative 1 ranked first by the first l voters (and only by them). Similarly, let o g++1 be the preference profile for n voters that has alternative 1 ranked first by the first k voters and by the last voter (and only by them). To show that the majority winner is an EDMR, sufficient (by symmetry) to show that
E U4
E U4
E max Ei=1 M1l E (x2)
E
uD
ub a
max EE= Ual Ei= U.2
Note that we used Euro* * to denote the expectation over a draw of a utility profile u consistent with of, and similarly for + 1.
Next, define Zj = - Mij for (1, Furthermore, define af as preference profile on n-1 1 voters that has the first & voters ranking alternative higher than alternative 2. Finally, let u be the truncated version of that excludes the nihh voter. By the law of total expectation, we can take an outer expectation over the utilities of the first n voters and an inner expectation over the utilities of the nehh voter:
i= U4
Z1 - Un1
E on
E aart
E Mnd S. 14s2
max Σ 1=1 Uil EE U12
max Z/ + Unl Zz + un2
17
Z1 - Un1
E un 1h11
E U
E Mad 2
max E U11. Em=1 U22
max Zz + Un. Zz + Un2
n
By the definition of o* and o k+1 the two final expressions only differ in the inequality between the random variables u,1 and un2- Furthermore, since Z₁ and Zo are both functions of u-n, they are both constants in the inner expectation. Therefore, to prove the desired result it is sufficient to show that for any constants Z1, Z2 2
Z1 + Un1
Z1 + Unl
E Riy Mu2
E Mnd 2222
max Z1 + Un1, Ze + unz)
max ( Zz + Uni, Ze + unz
Assume first that f continuous distribution. Let ff be the PDF of D. The joint PDF of the minimum and maximum of two draws from D is 2f(x)f(v) for æ 2 y. This means that the expectation can be rewritten as double integral giving the desired result:
Zi + Un!
21 +
E My11 20,2
ff
max Zi + un Ze + un2
max
[1 + x, Lz + y
00
Z1 +
2f(x)) (y)d
max (71 + y, 72 x²
Zi + Un1
E
Uyx S Un2
max Z1 + Un1 Uo + un
The inequality the second line follows from a simple lemma in Appendix D, which takes advantage of the fact that 2 y.

---

A similar derivation using the Lebesgue decomposition or the Riemann -tinannn-tieltjess integral gives the same result for general (not necessarily continuous) f.
When m 2 2, majority is no longer defined, and simple extensions (like plurality) are neither an EDMR nor an EWMR. We therefore require different strategy for such m.
From Expected Distortion to Expected Welfare
Despite failing to extend beyond the case of two alternatives, Theorem 3.1 does give some hope that perhaps an segected-wellarr-mmimiiiaz
rule, which is equivalent to an expected-distortion- can provide good expected distortion for larger m. This is the case in general, however: If we consider the space of all distributions 'D supported on [0, 1], an EWMR may not provide good approximation to EDMR. In fact, there exist distributions and preference profiles for which the expected distortion of an EWMR is an (2(m) factor worse than that of an EDMR, shown in Appendix E.
maximizing rule when
Theorem 4.1 There exists constant C > 0 such that for every m 5 there exist a num- ber of voters nr a distribution D supported on [0, 1}, and preference profile o, such that E @[ddist(ewmr, or] < C. [[[ddist )
is worth noting that the rule that chooses one of the m alternatives uniformly at random has expected distortion no more than factor ((m) wose than that of EDMR. Therefore, this theorem shows that for some distributions and preference profiles, an EWMR performs almost as poorly as the rule that chooses an alternative uniformly random.
One distinctive trait of the distribution used to prove Theorem 4.1 is that both the values that the distribution can take and their respective probabilities depend on and m. This is perhaps unnatural, as we might expect that as the numbers voters and alternatives increase, the i.i.d. distribution from which each voter draws utilities is fixed. In fact, with such assumption that the distribution DD independent of n and m, an EWMR will he an e-approximation for an EDMR for sufficiently large (regardless of the value of m). Furthermore, with the additional assumptions that the distribution is continuous and that the derivative of the CDF is bounded from below, an EWMR will also be an e-approximation for an EDMR for sufficiently large (regardless of the value of n)). Therefore, asymptotically in both n and m, an EWMR does perform well by the metric of expected distortion; the proof is relegated Appendix
Theorem 4.2 Assume is supported on [0, 1] and has constant (relative to n. m) mean and variance s². Then for every > 0, there exists no such that if n 2 no. then (dddisteewmr, o)] 2 (1 E)E [ddist
of > then there exists my Furthermore, if DD has continuously differentiable CDF F satisfying de such that the same result holds if m 2 m/.
Note that it is not priori obvious that either large or large are sufficient conditions in Theorem 4.2, and in fact the proofs rely on different forms of concentration. For large n, the key to the proof is that sums of i.i.d. bounded random variables concentrate by Hoeffding's 's inequality. For large m, the key idea is that, for continuous distributions, the variance of the order statistics goes to 0 as the number of samples grows.
5 Distribation-Indeeendd
Expected-Welfare Maximization
Theorem 4.2 gives computationally simple way to calculate an "almost EDMR" for fixed μ and s² by simply calculating an EWMR, which as noted Section can be done by using scoring rule based on the expected order statistics of D. This is satisfying because it has a practical form and performs well for both metries, namely expected distortion and expected welfare. fundamental flaw with such rule, however, is that it relies on knowing the entire underlying distribution D, which might not be realistic in practice. Our strategy for approximating an EDMR, therefore, is seek iistribution-iddeeeneenn independent approximation to an EWMR, that is, a rule that simultancously provides distribution
7

---

guarantees for every distribution (at least under some assumptions). To this end, we leverage the following observation.
Observation 5.1 If a voting rule f is a B-EWMR, and an EWMR is 7-EDMR, then f is 8y-EDMR.
In particular, for any E > 0, Theorem 4.2 yields = (1 E) for sufficiently large or m. Our goal this section, therefore, is to seek a rule f for which we can establish a value of /3 distribtiooninndeeeneet way.
Our first result negative: It is impossible for single voting rule to achieve high expected social welfare for all distributions supported on [0, 1].
Theorem 5.2 For every < a S 1 there exist n, m, a and two distributions D1, D2 that are both supported on [0, 1] such that alternative is an a-EWMR for both D2 and D2 under o.
We prove Theorem 5.2 in Appendix G. We will circumvent Theorem 5.2 in two natural ways. Our first way will do so by restricting the class of distributions. Specifically, we first focus on the class of symmetric distributions supported on [0. 1], that is, distributions D such that PraND( < 1 - = (I 2 + +) for all s [0. [].
The fact that EWMR is given by scoring rule [Boutilier et al., 2015], albeit that depends on the distribution, suggests that defining a scoring rule in a distribution-indeenneem way may be good approach. Consider the following scoring rule, whereby voters give their approval to the top half their ranking.
Definition 5.3 Top-half approval the scoring rule that assigns a score of alternatives ranked in the highest [m positions and 0 to all other alternatives.
turns out that top-half approval gives good guarantees for the subclass of symmetric distributions, we prove in Appendix H.
Theorem 5.4 For all n, m, top-half approval is -EWMR for all symmetric distributions D.
Given the attractiveness of top-half approval, a natural follow-up question is whether another distributionnindeeennenn rule can give an even better EWMR approximation for every symmetric distribution. While we cannot preclude this possibility altogether, we do give an upper bound (negative result) on the feasible approximation Appendix which holds not just for scoring rules but for any voting rule.
Theorem 5.5 No distribationnindeeeedee voting rule is an a-EWMR for all symmetric distributions
D. for any a
5.1 Binomial Voting
Tol-half approval clearly leaves some information on the table, it ignores the ranking of alternatives within each half. Let us refine it, then, by considering a variant that accounts for this additional information. As we will see, this refinement will allow to dispense with the assumption of symmetric distribution.
Definition 5.6 Binomial voting the scoring rule that assigns a score of Σizk (m) to an alternative that is ranked k.
Binomial voting can be seen as a "smoother" version of top-half approval. Indeed, because the binomial coefficients are largest in the vicinity of m the top, say, v positions have scores close to the maximum, and the bottom 2 /mm positions have scores close to the minimum, with the transition occurring rapidly in between.
Our main result for binomial voting is the following, which we prove in in Appendix J. This result circumvents Theorem 5.2 not by restricting the class of distributions, but rather by giving guarantee that depends on the median of the distribution.

---

Theorem 5.7 Let D be distribution supported on [0. 1] whose largest median is i.e. v' -uup(y y Prawp(# S y) S }.) Then binomial voting is a 5-EWMR for D.
Note that any symmetric distribution has largest median of v 2 5. so for such distributions Theorem 5.7 almost recovers the guarantee given by top-half approval for symmetric distributions. Needless to say, the guarantee for binomial voting (Theorem 5.7) is much more powerful than that for top-half approval (Theorem 5.4), as the former applies to any distribution and not only to symmetric ones. Note that while Theorem 5.7 gives guarantee that depends on the median of the distribution D, because binomial voting is seerriutiooniddeeeddenn it achieves this guarantee even when nothing is known about the distribution, including its median.
By putting together Theorem 4.2, Observation 5.1, and Theorem 5.4, get the following corollary, which ties these results back to expected distortion.
Corollary 5.8 Let D be supported on [0, with constant (relative n, m) mean, variance, and largest median v. Then for every &, there exists no such that if n Z no. binomial voting is (1 ()) for D.
Furthermore, D has a continuously differentiable CDF F satisfying inf, dF(x) exists my such that the same result holds if m mg-
de > 0, then there
5.2 Beyond the Median of the Distribution
natural generalization of binomial voting is to consider quantiles other than the median. For example, one might wish to guarantee 3-EWMM where 3 depends the third quartile. The following corollary generalizes binomial voting to other distribution-free scoring rules with expected social welfare guarantees based on the quantile of interest. All proofs for this section can be found in Appendix K.
Corollary 5.9 Let
10, Consider the scoring rule that assigns score of Epe (1) m0p to an alternative ranked k. This scoring rule is (1 (1- P)Q-E-WRRR, where Q is the p-quantile of D, i.e. Q = sup Pro-d( S y) sp.
iestribution-iddeendeeen independent rules where the rules stay the same but the bounds change depending on the underlying distribution. By contrast, the known EWMR of Boutilier et al. [2015] that requires complete knowledge about the underlying distributions looks very different for each distribution. It turns out that we can interpolate between these two extremes by incorporating par- tial information that might be known about the distribution tiles of the distribution, then we can extend binomial voting to distribution-depennie
So far we have focused on distribution
we are given access to multiple quan-
rule as follows.
Definition 5.10 Suppose we have access to quantiles Q1,..., QT corresponding to fractions 0 P1 < P2 < ... Pr S 1, where Q = sup Pra-o(æ S y) S pk). Define generalized binomial voting as the scoring rule that gives to the alternative ranked ls score of
ΣΦ
T
m (
Σ E=b
pm)'
m e {(w)
Σ t=k
1-P-)) m- PE-1
8k =
1=1
Theorem 5.11 If the distribution 0 < P1 < .... < PT &. 1 (define PT+1 1), then generalized binomial voting is a 3-EWMR for 3 = - - Qx(p.11 pp))
has quantiles Q1....,Qr corresponding fractions
As an example, suppose the only information known about the underlying distribution that the values Q1, Q2, Qa are the three quartiles (25%, 50%, 75%). Then generalized binomial voting is Q++Q++Qu -EWRR. Whenever Q3 > Q2 or Q > 0, this is strictly stronger than vanilla binomial voting, which is guaranteed to be Q -EWMR. Given more quantiles, generalized binomial voting gives weakly stronger approximations of an EWMR. Intuitively, generalized binomial voting is approximating the distribution D with left-oriented rectangles based on the quantile information. In fact, with sufficient quantile information, the rule will exactly approach an EWMR in the limit as T - xo. This result follows from generalized binomial voting being an approximation based on quantile rectangles, which in the limit becomes exactly the integral for expectation.

---

Corollary 5.12 For the quantiles .r. ( j.... 7). generalized binomial voting approaches an seggreedwwefareemmmmmitte rule as ' oc.
Discussion
In this section we discuss limitations of our work and present some extensions thereof.
6.1 Limitations
In our view, the main limitation of our work is the simplifying assumption that voters' utilities for all alternatives are independent and identically distributed. In reality, some alternatives are inherently stronger than others. In addition, utilities are typically correlated; for example, in US polities, if a voter's favorite candidate is a Republican, they are likely to prefer another Republican candidate to Democratic candidate.
That said, similar i.id. assumptions are commonly made in computational social choice and mechanism design [see, e.g., Dickerson et al., 2014]. Moreover, there is large body of literature that relies on the impartial culture assumption [Tsetlin et al., 2003, Pritchard and Wilson, 2009], under which rankings by utilities, the i.i.d. assumption on utilities gives rise to impartial culture. While these assumptions are admittedly strong, they lead to clean insights and solutions that often generalize well.
drawn independently and uniformly at random; when rankings induced
6.2 Benchmarks
We chose to define our benchmarks of expected distortion and expected welfare with respect to an arbitrary fixed preference profile a. Our main results therefore hold for any choice of preference profile a. In other words, our results should be interpreted being in the worst-case regime for preference profiles while being in the average-case regime for utilities. We chose to use the EDMR and EWMR as benchmarks in our main theorems because, by definition, these are the rules which maximize our objectives. However, the proof's of our results do not fundamentally rely on the use of these benchmarks. In fact, many of our main results (including Theorem 4.2 and Theorem 5.7) can be adapted to directly lower bound the actual values of expected distortion and expected welfare. More details can be found in Appendix M.
6.3 Extensions
We have shown that an EWMR can be good approximation to an EDMR. One follow-up question whether it is possible to do better by directly computing an EDMR. As noted earlier, potential EDMR is to choose the deterministic alternative with the highest expected distortion. Unfortunately, this rule requires exponential computation time. One way to circumvent this is to use i.i.d. samples from the underlying distribution to empirically approximate the expected distortion alternative, shown in Appendix L. With polynomially many samples from D and polynomial time, such a rule is a (1 e)- EDMR with high probability. However, it may be unrealistic to expect i.i.d. sample access to the underlying distribution, which limits the practicality of this approach.
each
Theorem 5.2 states that for a given constant a, no rule can an a-EWMR for all distributions. Despite this, one might hope that a rule that is an EWMR for one distribution could also be good approximation for an EWMR for another similar distribution. This is in fact not the case. Specifically, for any a,E O, an EWMR for distribution D may not even be an <-EWMR for another distribution that has total variation distance only E away from D. Surprisingly, though, a voting rule called Borda count, which is an EWMR for the uniform distribution, is in fact (1-e)-EWMR for all distributions that are sufficiently close to uniform. For more details, see Appendix N.
Finally, Theorem 5.7 gives strong positive result for the expected welfare of binomial voting that depends on the median of the distribution. Appendix O, we show that for any distribution (regardless of its median) and any n, m, plurality is an a-EWMR for conjecture that plurality may be "tight" the sense that no rule can provide better guarantee, but we leave this question open for future work.
max 4 } We
10

---

References
E. Anshelevich and J. Postl. Randomized social choice functions under metric preferences. Journal of Artificial Intelligence Research, 18:797-827, 2017.
E. Anshelevich, O. Bhardwaj. E. Elkind, J. Postl, and P. Skowron, Approximating optimal social choice under metric preferences. Artificial Intelligence, 264:27-51, 2018.
E. Anshelevich, A. Filos-Ratsikan N. Shah, and A. A. Voudouris. Distortion in social choice problems: The first 15 years and beyond. EXXi:21033009111 2021.
M. Babaioff, Y. Cai, Y. A. Gonczarowski, and M. Zhao. The best of both worlds: Asymptotically efficient mechanisms with guarantee on the expected sains-from-trade. In Proceedings of the 19th ACM conference on Economics and Computation (EC), page 373, 2018.
C. Boutilier, I. Caragiannis, S. Haber, T. Lu, A. D. Procaccia, and O. Sheffet. Optimal social choice functions: utilitarian view. Artificial Intelligence, 227:190-213 2015.
I. Caragiannis, S. Nath, A. D. Procaccia, and N. Shah. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 18:12115 2017.
Y. Cheng, Dughmi, and Kempe. Of the people: Voting is more effective with representative candidates. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 305-322, 2017.
Y. Cheng, S. Dughmi, and D. Kempe. On the distortion of voting with multiple representative candidates. In Proceedings of the 32nd AAAI Conference Artificial Intelligence (AAAI), pages 973-980, 2018.
K. Chung. An estimate concerning the Kolmogoroff limit distribution. Transactions of the American Mathematical Sociery, 67:36-50, 1949.
N. Devanur, J. Hartline, A. Karlin, and T. Nguyen. fiirrindependent multi pullte-e mechanism design. In Proceedings of the 7th International Workshop Internet and Network Economics (WINE), pages 122-133, 2011.
J. P. Dickerson, J. Goldman, J. Karp, A. D. Procaccia, and T. Sandholm. The computational rise and fall of fairness. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pages 1405-1411, 2014.
S. Ebadian, A. Kahng, D. Peters, and N. Shah. Optimized distortion and proportional faimeess in voting. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), pages 563-600, 2022.
M. Ghodsi, M. Latifian, and M. Seddighin. On the distortion value of the elections with abstention. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pages 1981-1988, 2019.
V. Gkatzelis, D. Halpem, and N. Shah. Resolving the optimal metric distortion conjecture. In Proceed- ings of the 61st Symposium on Foundations of Computer Science (FOCS), pages 1427-1438, 2020.
S. Gross, E. Anshelevich, and L. Xia. Vote until two of you agree: Mechanisms with small distortion and sample complexity. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 544-550, 2017.
J. Hartline and T. Roughgarden. Simple versus optimal mechanisms. In Proceedings of the 10th ACM conference on Electronic Commerce (EC), pages 225-234, 2009.
F. E. Kizilkaya and D. Kempe. Plurality Veto: A simple voting rule achieving optimal metric distortion. In Proceedings of the 31st International Joint Conference Artificial Intelligence (IJCAI), pages 349-355, 2022.
D. Mandal, A. D. Procaccia, N. Shah, and D. P. Woodruff. Efficient and thrifty voting by any means necessary. Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS), pages 7178-7189, 2019.

---

R. P. McAfee. A dominant strategy double auction. Journal of Economic Theory, 56(2):434 450, 1992.
G. Pritchard and M. Wilson. Asymptotics of the minimum manipulating coalition size for positional voting rules under impartial culture behaviour. Mathematical Social Sciences, 58(1):35-57, 2009.
A. D. Procaccia and J. S. Rosenschein. The distortion of cardinal preferences in voting. In Proceedings of the 10th International Workshop on Cooperative Information Agents (CIA), pages 317-331, 2006.
Roughgarden. Beyond the Worst-Cass Analysis of Algorithms. Cambridge University Press, 2021.
I. Segal. Optimal pricing mechanisms with unknown demand. American Economic Review, 93(3): 509-529, 2003.
N. V. Smirnov. An approximation to distribution laws of random quantities determined by empirical data. Uspekhi Mutematicheskikh Nauk, 10:179-206, 1944.
I. Tsetlin, M. Regenwetter, and B. Grofman. The impartial culture maximizes the probability of majority cycles. Social Choice and Welfare, 21:387-398, 2003.
J. Weber. Reproducing voting systems. Cowles Foundation Discussion Paper No. 498, 1978.
Robert Wilson. Game-theoretic analysis of trading processes. In Advances in Economic Theory: Fifth World Congress, pages 33-70. Cambridge University Press, 1987.
H. P. Young. Social choice scoring functions. SIAM Journal of Applied Mathematics, 28(4):824-838, 1975.
12

---

A
Randomized Rules
As mentioned in Section 2, the definition of distributional distortion (2) can extended to randomized voting rules by defining it to be the random variable
ddist(f.o) == [lsw(f(or) u)]
maxjEд sw (j, u)
where the expectation in the numerator is taken only over randomness in the voting rule f. In this paper we choose to only consider the deterministic rules because linearity expectation implies that any randomized voting rule is weakly worse than deterministic rule. Therefore, although the number of randomized rules infinite, considering the finite number of deterministic rules sufficient for finding an EDMR. Note that the same argument holds for EWMR as well. This result is formalized in the following lemma.
Lemma A.1 For any randomized voting rule, there exists a deterministic rule that has expected distortion as least as large as that of the randomized rule. The same result holds for expected welfare.
Proof. We will start by proving the result for expected distortion. The expected distortion of
randomized voting rule f can be written follows, where the inner expectation is over the randomness in the voting rule f and the outer expectation is over the random utilities up a. Note that the randomness in is over the alternatives that f can select.
E E[sw(f(o)) u)]
m j==1 Pr(f(o) j) sw(j.u)
E
E
upc a
MAXKEA sw(ku
uso
maxiE sw(k, u)
m Pr(f(o)= =)
Sw (..u)
E
usa
maxkEd sw(k,
sw(j.u)
Σ Pr(f(o)) = =)
E sw sw u max sw(k, u) 1)
mANKE A Sw (k;
< max j
uu
This completes the proof for expected distortion, as the final expression is a deterministic rule. For expected welfare, the result follows in similar manner:
[[|s([(())
u)]] = E
Pr(s(o)= =) sw sw(j. u)
u
up
Pr(f(o) = =) E [sw(i.u)
$ max E jsw u))) uub
B Infinite Expected Inverse Distributional Distortion
As mentioned in Section 2, we chose to define distributional distortion with the ratio in the opposite direction as worst-case distortion. Another possible definition would have been to define the inverse distributional distortion as follows, which is exactly the inverse of distributional distortion. Note that we have defined inverse distributional distortion using the more general definition for randomized voting rules introduced above, in (3).
13

---

Definition B.1 We define the inverse distributional distortion of a rule f under preference profile as
invddist(f,o) = max,cA Sw sw(j.u) u)
(4)
(
where the expectation over the the randomness of the voting rule.
As before, to a random u a. Unfortunately, even for relatively simple distributions supported on [0, 1]. the expectation of invddist or) can be infinite. This makes comparing rules more difficult when using expected inverse distortion as the metric.
consider the expectation of the random variable invddist with respect
Lemma B.2 Let m n and be symmetric preference profile. If 3(2, 1), then no deterministic rule f has finite Elinvddist(f.oo)
Proof. Let f(x) = 0.25x u.75 the pdf of D. Note that the joint pdf, denoted Xxx (x, v). of the minimum (1) and maximum ((2) of two i..d. draws from D is:
X (xr, v) (f)
2. each of the two voters is drawing two utilities from D, for total of ii.d. draws from D. Denote the utilities of voter as (w, z) and the utilities of voter 2 as (y. 2) respectively, and consider the case when preference profile is symmetric, and therefore the expected inverse distortions the two alternatives equal. We assume WLOG that alternative 1 has welfare of y w (ranked second by voter and first by voter 2) and alternative 2 has welfare of x + (ranked first by voter and second by voter 2). Using the joint pdf for the two sets of two draws, this allows calculate the expected inverse distortion of alternative 1 as follows:
Because
and y 2 2, with corresponding ranking
The
/
max(1
+ 2, w)
E[invddist (1, (1,
(() (() dz dw dy dx
dz du dy da
Jo
+ w
yV
x. + 2
2 4
Jo
Jo
J
Jo
y +
9 x +=
1
dz dw dy de J0 Jo Ju + (zyzw)0.77
64 Ju
co.
Therefore no deterministically chosen alternative has finite E[invddist o)].
C Randomization and Inverse Distributional Distortion
In Appendix A, we showed that a deterministic rule always achieves the highest expected distortion. For expected inverse distortion as defined in Appendix B, this is no longer the case. In fact, there exist distributions D supported on [0, 1] such that the best deterministic rule does arbitrarily worse than the best randomized rule.
Theorem C.1 For all > there exists distribution D and preference profile a such that the deterministic rule that maximizes expected inverse distortion has expected inverse distortion less than e fraction of that of the best random rule, i.e:
max E(invddist(j o)] sup Sunvddiidisst
Proof. To prove the desired result, we will show that there exist n, m. o, and D such that there is random rule that performs at least 1/c times better than the best deterministic rule. Let n = 100. Define D as follows for D.
w.p. 1
d
2nm
w.p.
nm
14

---

Consider the uniform preference profile where every alternative is ranked ith by exactly 1 voter for all E [1 nl]. First, note that the rule that chooses an alternative uniformly random achieves expected inverse distortion at most n7, as uniformly randomly selecting an alternative will choose the alternative with the maximum social welfare with probability 1/m. Therefore, the best randomized rule must have expected inverse distortion of at most m.
Define Nj to the total number of voters with utility 1 for alternative j. Define Niot Σi=1 Nz. By construction of D
1
Pr(Ntoo =0) 1
0.4
1um
and
1 "
Pr(Ny 0)
0.9
num
Now consider the deterministic voting rule that selects alternative j. By a union bound, the probability that Noot > 0 and Nj- 0 is at least
Pr [Not > 0 = 0] 2 - 0.4
0.5
If Noo 0 and N2 0, then alternative j has total social welfare of 2m and there is at least one alternative with social welfare greater than 1. Therefore, we can write
E[invddist(j. o)] 2 0.5
m
Because the preference profile or is symmetric across voters, the above inequality is true for all j. Therefore, the best deterministic rule gives expected inverse distortion that is factor of worse than that of the rule which selects an alternative uniformly at random.
The above result is especially disturbing if we allow ourselves to relax the independent and identically distributed assumption. For example, suppose that among the nm pairs of voters and alternatives, there is single voter that has value for single alternative, and every other voter/alternative pair has utility 2nm By symmetry, the best deterministic rule is choose an arbitrary alternative. This rule has expected inverse distortion at least
m
m
m
2m
In contrast, the randomized rule that chooses one the m alternatives uniformly at random has expected inverse distortion of at most Notice that the joint distribution of the social welfare of the chosen alternative and the maximum social welfare across all alternatives is the same for both rules. Therefore, one would expect them to have the same expected inverse distortion value. However, the random rule can have arbitrarily better inverse distortion as shown above. In contrast, these two rules will have the same expected distortion. This is another reason why chose to define distributional distortion with the ratio in the opposite direction as worst-case distortion.
D Proof of Theorem 3.1: Omitted Lemma
Lemma D.1 x 2 y 2 0, then for all 71, Zz 2 0, the following inequality holds:
Z1 + x
Z1 + y y, 42 +
max (Z1 + x, Za + y)
max
Proof. Consider the following two cases.
Case 1: If 71 + x 2 Z2 + then
Z1 +
Zi + y
12 max [71 U, 72 x)
max 21
x., 7o v)
Case 2: Z1 Zg + y. then since x: 2 y we have that
Z, +
7, 2
71 +
+ max Z1 2,, Zz + +
max Z1 + Zg +
Zg +
Zg +
15

---

E Proof of Theorem 4.1
Lemma E.1 For a 2 0 and integer b 2 such that ab 1 11/5,
1 ab - (1 a) 1 - ab + (ab)²
Proof. Expanding the binomial gives:
b b
(1 a)" =1 ab +
(
a)*
k
k=2
Examining the last terms, we have that
Σ (x a))
b²b(b-
11
+
Σ
-a)
k=3
a²b²
b
b
a)*
2
202²
(ab)*
2
a²b²
ab
I a²b?
Similarly,
d²b(b-
- 1)
b
a)*
(
-aa)
2
k.
3
a²6²
a²b
b
a)
2
2
k
k=
a
22b2
abb
(ab)*
2
2
k=
a²6
2²b3
a²b
2
ab
2
0.
Proof of Theorem 4.1. Let m 2 5. Choose any n > 1 such that 'D as follows: for un ~ D
v Ing(n)
2 m 2 2 log(nn) + 2. Define
m
w.p. n'm
w.p. p e log(m)
1
Uij
mm w.p. q == - log(m)/m
Draw m samples from D and denote them X())..., X (m)) in increasing order. The expectation of the largest sample is:
(()) = Pr(X (m) = + Pr (m) = n)) + Pr(X(m)) (m) = n²m)) n 4 m
9" + ((1 mm
m
q" + (1 -(1- nmm (") n2 'm
2 9" + ((1 nmm
9 m
n + (1 (1- n= 1/) n Am
9" + ((1 mm
n + n 2m m
> n. m m,
16

---

where we used Lemma E.1 and the fact that - 1/n2m 2 q.
For every l m, we have that
([X - E (m-))
(m-1)
(m-1) 1) (r(X(mm-1)
(m-1) =n) -n Pr(X(mm-1) (m-1) n''m) nn m
S Pr X (m-1) # n m)
Pr(Xpinn
1 - (1-n²m) m (1 7m
m=1 (nrmm) )
m
S n
m=1 mmm n'm
S n1 2m,
where again we used Lemma E.I.
Combining these two inequalities. we have that (m)) > n [[)) for every Therefore, one voter ranking a chosen alternative first has higher expected utility than all n voters ranking a chosen alternative second. This implies that if there is unique alternative that ranked first by the most voters, then that alternative is the unique expected welfare maximizing alternative.
We consider the following preference profile. Alternative is ranked first by - + 1 voters and ranked th by n - (-- + 1) = n /= voters. Alternative is ranked second by all n voters. Finally, other alternatives are ranked first by at most m-1 voters.
In this construction, alternative 1 has the most first place ranks and therefore is the unique expected welfare maximizing alternative. We now show that
E[ddist(2.
E[ddist(1, o)] [ s
m
Let E be the event that no voter has utility n'm for any alternative. By Lemma E. we have that
Pr(Ei) = - 21-4
Let &g be the event that every voter has utility at least n for alternative 2. Under event &2, the total welfare of alternative 2 is at least dsw(2, o) 2 n². We have that
Pr(E2) = Pr(X (m 2 n2)
Pr X (m- 1) = n))
(1 d"h mq m (1 -))"
q"h mm
log(m)
log(m)
m-
m
m
m
log(m)
(m) 1/ (m)
log(m)
m--1
1
2
n
n2
where we simplified using that S log(m) m 2 5, and m 2 log(n) +
We finally want to establish tighter upper bound the typical utility of alternative than event E alone provides. Let N₂ be the number of voters, among the m-2
m-1 voters that ranked alternative 1 in last place, who have utility strictly greater than for alternative Then let Eg be the event that:
N (n n= 1) + log(n)<To
17

---

We will show Eg is also likely. To calculate Pr(Es), note that by definition of the probability p.
(1( 1) (p + )mmm [ 1/m Therefore, N1 ~ Bin 72 m- 2 m-1 1). Applying Hoeffding's inequality to this random variable gives:
m
Pr(E3) Pr [ : (n m=7 1) log(n)
Pr (Ni - [ 2 log(n)vnz
2 exp( (n)(log()\//)//) m=1 1))
2 exp( (2(00((())
exp( (pp(-2lg?(())
#
Define : & &g. By inclusiinneexchuiion and a union bound,
Pr(E) =
U -Es) 2 Pr(EE) -P((EE))))( 2 3
We consider the social welfare of alternatives 1 and under event & to obtain bounds their respective expected distributional distortions.
Event Eg implies that the total number of voters that have utility greater than for alternative 1 (including the m-I voters who rank alternative first) is at most:
n2 - + (og(n)<n- - +1.
Under event ε,, no voter has utility greater than for any alternative. Therefore, every voter has utility either for alternative 1. Since we have an upper bound on the number of voters that have utility for alternative 1, and trivially at most n voters have utility for alternative 1, we upper bound the total social welfare for alternative by:
dsw(1, S n
m n m=? -1) + log(n) - +1) 1
n² in2 + log(n)n3/2
log(n) log(n)n3322 + 2n² +n
Combining this with the fact that dsw (2, 2 n² under event &g, we get that the distributional distortion under event most the following, using that m S log(n)
4n log(n) 3/2
log (n) 5
n²
m
m
Since Pr(E) 2 n2. the distributional distortion of alternative is upper bounded as follows:
E[ddist(1, .)) (1 - 3 m
Under event E, alternative 2 has total social welfare of n² and the max social welfare of any alternative is n This implies that alternative has distributional distortion 1. The expected distributional distortion of alternative 2 is thus lower bounded as follows:
3
3
E[ddist(2, σ)] >
1
1
0
Therefore,
Elddist(ewmr, o E(ddist (1,a)) a)]
< 10 E[ddist(2,
s 16 E/ddist(edmr,or) o)).
18

---

Note that while this distribution is not supported on [0. 11, simply scaling the values of the distribution by x to scaling the distribution, and therefore the result still holds.
_ will make the distribution supported on [0, 1]. Furthermore, expected distortion is invariant
F Proof of Theorem 4.2
Lemma F.1 Suppose the distribution 'D has mean and is supported on (0, Then the expected distributional distortion of the alternative selected by the expected welfare maximizing rule is least Furthermore, the expected welfare of the expected welfare maximizing alternative is at least ny.
Proof. First, note that we can add the expected distortion for all m players and apply linearity of expectation get that
Σ Bldsw(i.
Elugl = nmp.
j=1==1
Furthermore, the maximum expected social welfare alternative must have expected social welfare at least as large as the average expected social welfare across all alternaivess. This implies that there must exist some such that
E[dsw(jj, ()) 2 ny--
Therefore, the alternative selected by the expected welfare maximizing rule must have expected social welfare of least nyu. Therefore, using the fact that no alternative can have social welfare of greater than
dsw(ewmn) σ))
(iddist(ewmit r)) =
max, dsw dsw(jj))
dsw(ewmrr, σ7)
E
E (dswweewm,, o)
The below is purely technical lemma.
Lemma F2 If X1, .... Xm are i.i.d. draws from a continuously differentiable distribution with edf F. Suppose that dF(x) for all x. Then for every 82 > 0 there exists M such that for every M and for every j.
Var(X S s2
Proof. Let F' be the edf of D and let Fm be the empirical edf from samples. Let FF - Fmm = sup, [F(x) - (x)). The iterated logarithm law Smirnov (see Smirnov [1944], Chung [1949]) states that:
lim Fm F Pr
>00 (2 log log (m))m)) cs 1 -1.
consequence of this is that for any 8 0, there exists Mi such that for all m 2 M1:
(2 log log(m))
[Pnm F
> 1-8.
(5)
m
Since F is continuously differentiable it is continuous, and since increasing and its inverse F-1 is continuous and well-defined [0. also. Since F-1 is
dF 0 on (0, 1) F is strictly de
19

---

continuous and bounded on a closed interval, it is uniformly continuous: this means that for all > 0 there is some 8' such that for all [0, 11. if - < 8' then | (v) (v)-
E'.
Next, for given m, consider the order statistic Xj. We note that the j order statistic is equivalent ( (2). For quantiles of the form b 2 will suppose that Fm is well-defined and Fm (Fm (6)) For such point let a F (b) and let am := (b).
m FFF(((
We now introduce another condition on m. Given 8e, choose M2 such that (2 log(
vM2 S 8',
where 8' is the threshold given by the uniform continuity of F with the choice of Sg. (Since this is a decreasing function of M2, this incquality will hold for all M2.) By Equation (5) applied to the value ams we have that
(amm) Fm (am) S 8'
with probability at least - 8. If this is the case, then by uniform continuity,
F (F(am) (4'm (am) S (b) F (b) S $2,
where this last inequality follows by applying the definition of am-
Using the fact that XG) is supported on (0, 1]. this gives that the variance of ( can be bounded as
Var(X()) (2 log log(m))
+8 82
c/m
where we take o/ and sufficiently large m 2 M max.M,, M2).
Proof of Theorem 4.2. Recall that ewmr (a) is the expected welfare maximizing alternative. Let n 2 Al. where no is the solution to the equation log(n)
v/m Cp- By Lemma F.1, the expected welfare maxi- mizing alternative satisfies d'dsweewnee o)] 2 n.,.. Furthermore, note that the social welfare of any alternative j can be represented dsw(j. o) ables that are supported on (0, 1]. Therefore, we can apply Hoeffding 's theorem to get the following:
0i=1 U4 where u4y independent random vari-
(rddswwwwmr, o) S (1 =) E[dsw [eldsw(ewmm: a)))
= (o(dds((ewii σ) - E[dsw( (oddsw(ewni (ewmr, o]] < - Eldsw o)))
< Pr(dsw σ) Eldds(eewn)) o]] < -Enu)
< 2/een))//n /n
I e 2=²"
For any j # ewmr(a)), we must have Ejdsw ()) S (edsw o)). Therefore:
Pr(dsw(j, o) 2 (1 +) =) o))
< Pr(dsw(j. (j,o) 0) 2 E[dsw(j - -
Pr(dsw(j (j,o) E[dsw(j, =s]ds((eewr o)))
= E]dsw(ewmr.
Pr(dsw(j.r) (j,or σ) ( 2 emp)
2(enp)2/n /n
Se- 26?
Let be the event that the welfare of the ewmr(o) alternative is not too small, and that no other alternative has unusually large welfare; dsw(ewmr, ar) 2 (1 E E/dsw(ewmr, o)) and that for all
j * ewmr(ar), dsw (j. r) & (1 + E) E (dddswewwr, a)). Mathematically,
ε = (ewmr, σ 2 (1 e) E[dsw ]) [[ (fj dsw(j, σ) < (1+s) Eldsw }}}}-
Using the two results above, the probability of the event & can be lower bounded by the following:
Pr(E)= 2 1 -20²
ny² - 2e 2g
20

---

Fix any j. Under event E, the distributional distortion of this alternative satisfies the following inequality:
dsw o)
ddist(j,o)
max, dsw(j,o)
(1 + 8) Eldsw(ewmr, or]
max, o)
1+e dsw(ewmr, σ)
1 E max; dsw(j,
+ 1 -
dddisteewmr, or)
Under event -E, the distributional distortion j is at most by definition. Therefore, we can upper
bound the expected distributional distortion of j relative to the expected distributional distortion of ewmr(or) as follows:
(fddist o)) = Pr(E). [] P Pr(-E) [jddiss(j, -
- 1tc 1-8
Pr(E) Elddist(owmr, o 8] 2e 2n
< _ (Pr(E) Elddist(ewwrr or) E] + Pr(-E) E'ddist(ewmr, o) -E1) + 2e =2²np²
Itc Elddist(ewmr, ]r + 2e np² (dddis o)]
x 1-e
s 1+ + 2.. 2='mp) Elddist(ewmr, o))
Take == = < 2.
which is equal to
log(n)
by our choice of n. Then: 2/an
2e 26
2e 22
< 1 48
+ 2 V/ log(n)
< + te
2
< 1 Eo-
We have shown that for all j
E[ddist(j. < (1 + Eo) E(ddist(cwmr,cr))
and therefore,
(eddist o) = max E[ddist((j, o)) S (1 + 5o) [eddis o)).
We have shown that the expected social welfare maximizing rule is an e-approximation for the expected distributional distortion maximizing rule for sufficiently large We now show that the same holds for sufficiently large m when ' is continuous. The proof is very similar to the above, except that use Chebyshev's inequality instead of Hoeffding's inequality.
Note that dsw or) the sum independent random variables, and let s be an upper bound on the variance of any one of these random variables. We can use Lemma F.2 to find mg that is <ap"n
suitably large. Specifically, we choose mg such that m 2 mi implies o
256
Because the variance of sum of independent random variables is the sum of the variances, we can bound Var (ds((j o)) I ns?.. Applying Chebyshev's 's incquality then yiclds:
Pr(dsw o) s (1 =) E(dsw (ewmr, o)))
Pr(dss(ewmm: or) [eldsw(ewmmg rr < - FeEddss (ewmr,
< Pr(dsswewwur, σ) []dsw(ewmr, or] < -Snjj)
ns? 2
(snu))²
21

---

For any j ewmrr(o), we must have E/dsw (j. o)] - Bldsw(ewmr, or). and therefore:
Pr(dsw(j, σr) 2 (1 e r)])
Pr(dsw(j,o
([dsswwwwwr o o)]
Pr(dsw(j. (j.o) o Ejdsw(j. (1. 0-) 2 e BB]dsw(ewmr, r)))
Pr(dsw(() j. σ) [] σ 2 enf)
ns?
(emp))²
22
e2p2n
Using the same logic as in the first part of the proof, this means that we have
1 + 2. E2
E(ddist(j.o)]
Eeddist(ewmr, or)
1 -
We can upper bound this by taking = 5o to get:
1+E
2s
2s
S
48
1 E2Puôn
E2112n
80
+ 128s
2 EQPun
S + ED-
As in the first section of the proof, this implies that: Elddist(odmr, o]] max Ejddist(j, or] S (1 6o) (eddis)()
G Proof of Theorem 5.2
Lemma G.1 Let ~ Bern(p) for 0 < < <<ppp 1. For m i.i.d. draws from D. the expected welfare of order statistics satsify the following inequality:
For h S pm 8m,
([X S -20mm
For k 2 pm + 8mn
E[X(x)] 2 2m
Proof. Fix l: E pm 8m. By Hoeffding's inequality, the probability that X(k) is is bounded by: Pr(X(s) = 1) Pr(Bin(m, p) 2 pm + 8m)
Pr(Bin(m,,)) p) pm 2 8m)
25'm
The only two values that X()) can take 0 and 1, this implies that:
[[X S e 25 m
The other direction for k: 2 + dm follows from symmetric argument.
Proof of Theorem 5.2. Fix < a < 0.5. Let = and 6 = a² 4. Further let Dj = Bern( - 8)
and D: Bern(p). Choose m such that
2m88 < 6,
22

---

and let = (m 1). Define the preference profile o as follows. Let alternative have rank (1= 5)m for all voters. Let all the other rankings be evenly divided among the other voters. so that for every j [2 ml. alternative is ranked k by voters for every k E [1 ml] except for A = (1x 6)m.
By Lemma G.1, under distribution D1, alternative will have expected welfare of:
Eldsw(1, or] S ne 2m88
(6)
S nd,
by the choice m. By Lemma F.1 there exists at least one alternative j with expected social welfare of at least:
E(dsw(j, 2 np-.
Similarly for D2, by Lemma G.1 and the choice of m. the social welfare for alternative 1
[[dss(1,
2 (1 e 2mm² 22m6 )n
(8)
2 (1 - 8)n.
(9)
For # 1, let N, be the set of voters giving rank (μe 5)m or lower (better). Note that there are a total of (μ + 6)mm such rankings across all voters, and n of those positions are occupied by alternative
Furthermore, note that the social welfare of any alternative j can be represented
as dsw(j, o) = Σi=1 Uij where Uij are n i.i.d. random variables that are supported on [0, 1]. Therefore, for any j #1,
(p + 8)mm n
[N
S <n(u + 8).
m
Using this, we can then conclude that
E[dsw (i, o) = Elugl
E[uis] + Σ E[usyl
x N,
igN
$ 1 [4 + 2mm8
(n - |N5l)
N, + ne 2mm8
S n(p + 5) + no
= (μ + 25)
Under distribution D1, by (6) and (7) have that alternative has expected welfare most 5 fraction of the expected welfare of the expected welfare maximizing alternative. Under distribution D2, any alternative j # 1 has expected welfare at most (using that o, < 1/2)
# + 25
2μ
48 a
1 1-8
fraction of the expected welfare of the expected welfare maximizing alternative. Therefore, can conclude that under this preference profile, no alternative can be chosen that is an a-SWMR for both Dj and D2 simultaneously.
Corollary G.2 the distribution can depend on m, then every m there exists an n, a preference /log(m) 74
profile, and two distributions D and D such that rule is
SWMR for both distributions.
2 (Vllggm)
Proof. Take
This is valid as 8 satisfies the necessary inequality for this choice of
a.
23

---

H Proof of Theorem 5.4
Denote the mean and median of "D μs. Note that for any 22 [ the expectation of the kth order statistic from i..d. draws from a symmetric distribution satisfies the lower bound
[[X( 2
(10)
Similarly, for any & < <[2
([) S μ..
(11)
Among all voters and alternatives, there are at least mm 2 pairs of voters and alternatives where the voter ranked the alternative in the top 1 of alternatives, regardless of the preference profile Therefore, by the pigeonhole principle, there must exist at least one alternative that ranked in the top 7 by at least m! [ voters.
Define (op-Half as the alternative chosen by the Top-Hall approval scoring rule and let let be the number of voters that rank (op-Hal((or) in the top / By definition Top-Hall(o)) is the Using (10), the
alternative that is ranked in the top m by the most voters, and
expected welfare of Top-Half(o) can therefore be lower bounded by
o)] 2 2p1.
Note that because 'D is non-negative and symmetric with median 14, its support must lie within the range (0, 2q1). By construction, for all j * (op-Half(o)) alternative j is ranked in the top [m by at most voters. Furthermore, [[X(a) S for all k < [m] Then for any j * Top-Half(or)
[j. [) S = 2p + (n - 2) nu + zμ
Combining these two equations with the fact that > result:
> Z. we get the following desired
EJdsw(Top-Halff o]]
2/4
1
2
E Eldss σ)]
+ zμ
3
I Proof of Theorem 5.5
Proof of Theorem 5.5. Let Pi be the Onif(0, 1) distribution and let P3 be the Bernoulli distribu-
tion with probability 0.5. Fix 1 > au > O. Define a 4 Finally, take m, such that 2
2 llo(mm) mmm
log(m) 1e222ogg log(m))) Note that this is simply technical choice for this proof.
Define the preference profile a as follows, for constants (to be determined later) p, q satisfying S q < 1. Suppose alternative 1 is ranked m (og(m))/m by pn voters and ranked last (m (m* by all other voters. Suppose alternative is ranked first by gn voters and ranked m + log(m) v by the remaining (1 g)n voters. For simplicitly, we will assume that pn, qn, (m), /m, 7 are integers, and further that n, pn, gr are all divisible by m Suppose all other rankings are distributed as evenly as possible among the remaining voters.
Suppose that the true underlying distribution is P1. The expectation of the keth order statistic of uniform distribution is & m+I We then get the following lower bounds the expected social welfare for alternatives and 2:
m/2 + log(m) m
1
Eldsw(1 (1, o)] pn.
p)n.
m 1
m
pnm/22 + pm log (m) / + (1 p)n
+
(p+ + a)nm
(12)
2(m +
24

---

B(dsw(2. = gm m + + (1 - g)n 2 log(m)
m
m
m + 1
qum + - nmmm 2 (1 mm
(1+ a)mm
(13)
2(m 1)
We will now consider what happens when the true underlying distribution is Ps. Suppose that this the case. Then by applying Lemma G.I with 8 log(m)) vm we can bound the expected social welfare for alternative by:
(p- ain < pn(1 22lx0
I Eldsw(1, [),
< pn + (1 - p)re (m))
x (p+ an
(14)
and similarly for alternative by:
(g a)n S qm(1 e- 20gg(())
S E/dsw (2,
qm (1 g)ne -2 2mmg??mm
S (q + a)n.
(15)
For the remaining m 2 alternatives j & {1,2}, the remaining expected welfare is divided evenly among them. Note that by the divisibility assumptions stated the beginning, we can exactly evenly divide up the remaining rankings (and therefore expected welfare) among these - 2 alternatives. This allows us to upper bound the expected social welfare for the any alternative for j & [1,2) by:
E(dsw (j.
nm
2 E(dsw( (1, o)] Eldsw(2, 07l)
2
nm
(p + q)n 2an
2
2
nm
2 n + 2am
2
- 2
I (q + a)m,
(16)
since 2 1/2. Note a symmetric inequality shows that E(dsw(j.o)) σr] 2 (q a)n
If we select alternative 1, then comparing it to alternative 2 under P by combining (12) and (13), shows that the expected welfare is at most a I+q-a fraction of the expected welfare maximizing alternative.
p+o
If we select an alternative that is alternative 1, then by by combining (14), (15), and (16), see that the expected welfare is at most gta fraction of the expected welfare of the expected- wewetted-wlfarr-mmxiiiiie
p-a
alternative.
Therefore, we have construction such that for every alternative, under some distribution the alternative will be most a gia gta_EWWe -EWMR at most I+g-a p-a
_.t__.EWMRR From this, we can solve for p. g the following minimization make the social welfare approximation for either of these options as low as possible.
a+aa
p+a_)
p+a
p.q arg min P.q
max
p-a
1 q -
25

---

Solving this gives that the minimum is achieved at (p, q) = (v0.75, 0.5). For this choice of there no choice of alternative that achieves at least
0.5 + a
v0.75 S V 3
40 S
+
fraction of the maximum expected welfare alternative the underlying distribution can either P1 or P2. Therefore, we have shown that no rule can be better than (v + ao)-EW for all symmetric distributions, and taking the limit as oo - 0 gives the desired theorem result.
J Proof of Theorem 5.7
Lemma J.1 If (m+1-k) is the (m ki)ah order statistic of m draws from a distribution supported on [0, 1] with median u, then:
E[X (m+ 1)) 2 2-m
i
t=k
Proof. Note that random variable X D is greater than equal to the median with probability at least 3- Therefore the probability that the (m + 1 k-)th largest out of m draws is greater than the median is least:
Pr(X(m+1-N) 2 v) Pr(Bin(mm 1) N k)
2
t=k
m
2
t=
Therefore, lower bound the expectation of X (m++ kb) by
X (m+11
2)] 2 v Pr(X (m+1-1) (x 2 v)
m
2 22.2-0 2-
Proof of Theorem 5.7. Define Score(j) be the score of j under the Binomial Voting:
Score(j)
The scaled sum of the scores of all the alternatives can then be written as
2 Score(j) = m
2-
2
k= t=
k
2-m
1 m,
E
Bin
2
7um
2
where the second equality follows by expanding the inner sum. Let Binom(or the alternative that is chosen by the Binomial Voting. Then by the pigeonhole principle, the score of Binom(r) must satisfy
2 m Score Score (Binom (a)) 2
26

---

We next provide lower bound on the expected social welfare of an alternative based on the Binomial Voting, and use this to lower bound the expected social welfare of Binom(o)) Recall that if an alternative is ranked Pi.., In by the n voters, then Boutilier et al. [2015] tells us that:
Bldsw (j,
E|x (m
Applying Lemma J.1, we then find that
172
E[dsw( o ]] Σ
2- m
fmr;
V. 2 SSoorej).
For (inom((r) this yields
Fldss(Binom,, r 2 v. 2. Score(Binom(()) (o))
nv
2
V
I (edsw a));
2
as desired.
K Generalized Binomial Voting
Lemma K.1 If (m) is the (m + 1 - th order statistic of m draws from a distribution D supported on [0, 1}, where Q is value of the th quantile of D, then
B[X B[X 2 Q
m7
(1
p) nd
8
k=
Proof. As in the proof of Lemma J.1,
Pr Pr(X(m+1-H) 2 2Q) Pr(Bin(m, 1 1-p) 2 2k)
m
(1
p)
l
t=
Therefore, we can lower bound the expectation of X (m kk) by
[[[((m+1-x)) 2 Q Pr(X (m+11k) 2 Q)
2 Q
m1
(1 p) pm
t= 8
Proof of Corollary 5.9. If we define Ti,..,, the rankings of alternative and
Score(j)
é (1
p-
i=
then by Lemma K.1,
E|dsw( (j, v) = Σ B(X [(X(m+t-nn))
1=1
2
m
(1
mm
i
1=1
t=
= Q Score(i)-
27

---

The sum of the scores of all the alternatives can then be written as:
m
Score(j)
Σ
m m
m
pmppm-
= Y (m,, 1 p)]
mm(1 p).
The rest of the proof follows as in the proof of Theorem 5.7.
Lemma K.2 Let X be a random variable supported on [0, 1]. Choose T values in [0, 11, denoted 0 Q ... Qr 1. Define Qo 0 and Q4+1 = Then
T
E[
Σ
Q. Pr(Qi s < Q++1).
t=1
Proof. The expectation of X be written
X
Pr(X x)dr
T-1
Qr+i
Pr(X 2 x)dd
Σ
Pr(X 2 x)dr
Qr
1=0 Q.
Q++1
Pr(X 2 Qr+1)dx
QQ
(Q++1 - QQ)) ()))-P((X 2 Q++1)
Q. Pr(Q: X < Q(1)..
Proof of Theorem 5.11. Let X(m-++1) ++)) be the (m le + 1)th order statistic from m i.i.d. draws from distribution D. Consider the probability Pr(A S (m=++1) k+1) < B) for 0 S B 1. Define PA : Pr(X < A) and рB Pr(X < B). In order for A S (m-x-1) B, there must be least is draws greater than or equal to A, and at most k 1 draws greater than or equal to B. The probability that there are at least i draws greater than equal A is
m
Σ
(1 PA) (1-P
and the probability of having at least i draws that are greater than or equal to B is
Σ i (1
pB) p m-t
Now using the fact that the second event is a subset of the first event, we have that
Pr(A S ((m-x+1) < B) (000)~>0aa0 (1-
( --
m
m (1- P1-
PB)
m m-t
(17)
t=k
t=k
Therefore the score in Generalized Binomial Voting is a lower bound for the expectation of the (m - k + 1) th order statistic, as shown below. We start by applying Lemma K.2 to the order statistic X(m-k+1) k+1)- By combining this with (17) we get
T
X (m (oo)++1)]+
Q. 12-Pr(Qu S X ((m-k+1) < Q(+1))
1=1
T
Σ
Qi
Σ
m
(1 10))p))
pt) PT
Σ
m
(1 Ptt1) /' -
(18)
i
i
1=1
b=k
8mk k
28

---

Suppose alternative has rankings 7,.... In by the voters, and again define Score(j) as the total score of this alternative under the Generalized Binomial Voting rule. Then by linearity of expectation and the above inequality,
E(dsw( (j, σ-) =
Σ E (m+1-r))
Q:
m
(1
pt)
Pt
m
n-
Σ t=r
1 )1
m
(1
m- pe+1)
Pt+1
8
1=1 1=1
Score(j).
(19)
Now the last step to find a lower bound for the score of GBi the index chosen by Generalized Binomial Voting. Note that if we add all of the scores across all of the alternatives, we have that the value can written as sum of expectations of the order statistics Z(2). ((m))..((m))) of m draws from Multinomial distribution with T outcomes, with probabilities (pt+1 Pt \ and values 0, Q..-... Qr respectively, where we define Po O. This allows simplify the sum of scores as follows: In a manner similar to the proof of Theorem 5.7, we have
Scoro(j)
m pt)
(1
Pt
m
m (1 p(+1)ppet
Pt+1
m-
k=
t=1
1=k
8=
n
Qi
m
(1 pt)
m
(1 - -P(+1) Pc41
PT m-
L
t=1
A= 1 t=
Am R
Σ
Q
Pr[Bin(m, 1 pt) 2 k}
Pr Pr[Bin(m, P2+1) k))
= n
Qi (E,Bin(m, 1 - pc)l [mBin(m, 1 P(+1)))
T
mm
Qi (pt+1 - pt).
(20)
Finally, we conclude as in the proof of Theorem 5.7 that the score of GBinom can be bounded as
Eldsw (GBinom, r 2 Score (coro(GBBinom(r))
Qe(pe+1 - pc)
T
Qe(p++1 - pt) Bldsw(ewmr,
where we used (19), an averaging argument applied to (20), and that 2 E ('dss o. since D takes values in [0, 1].
Proof of Corollary 5.12. To prove this result, we need to show that the scores in Generalized Binomial Voting approach the expected values of the order statisties, which the scores in the ewmr.
Recall the above proof, the fact that there an inequality the equation E(dsw(j, a)] 2 Score(j) is because of the inequality in Lemma K.2. That inequality came from the fact that, for random
29

---

variable X,
E [
Pr(X 2 x) dr
T-1 Qi11
Pr(X 2 22) dx
Σ
Pr(X x) dr
00
T-1
Q+11 Pr(X 2 Q++1) dæ
Q:
other words, the score Generalized Binomial Voting can thought of as rectangular lower bound approximation of the integral of expectation of the order statistics of the underlying distribution. By the definition of the Riemann Integral, this rectangle approximation will exactly approach the true integral (making the inequality equality) T oc.
L Sampling
As mentioned in Section we can directly calculate an approximation the EDMR rule by sampling from the known underlying distribution D. We formalize this result below.
Consider the following sampling algorithm. Take T batches of nm i.i.d. samples each from distribution D. For each batch, assign m samples to each voter i, and denote the sorted samples as X3 (1) X( (m) Let ri....,?', rh be the rankings of alternative j under a. For each j. let
12
X
A 7/ 1 -
1
i=
(r))
max
> 1i=1 (rt)
X1
be the mean sample distortion of alternative j.
Theorem I..1 Let D be bounded on (0, 1] with mean p. For any E, 8 > 0, take T 2log( 2gg
Let
==*²*
jsampling = arg max, ūúg be the alternative with the highest mean sample distortion, as defined above. With probability 1 6, 6, JSampling is e-approximation of the EDMR:
Elddist o]] 2 (1 =) (lddist(cdmr,, o)].
Proof. By linearity of expectation, clearly [[, E[n = E[ddist(j o)) Applying the standard Hoeffding's 's inequality to μú gives:
P (lāg (j. IE|ddist (edmrr, r) < 2 exx (-Ts²
[[dddis(eddmr,rr]] (
< 2xxp (-Te2
5
Let be the event that for all E [1 m].
|Ā, [[ddist(j a ))] S (eddr, r)).
By a union bound, P(E) 2 8. By construction, jSampling satisfies fijsamptinn 2 Piaam Under
event E, this implies that
E[ddist(Sampling o)] + B[dddis((edmr,, a-] E[ddist(edmr, o]] - Elddist(edmr, o)).
This equation simplifies to Tiddist(SSmppiin の)) > 8) Elddist m)}
desired.
Note that each of the T' batches includes nm samples, so the total number of samples used this algorithm is Tnm nm log( )
30

---

M Benchmarks
In this section we elaborate on alternative benchmarks for our results, briefly mentioned in the discussion. While our results use the EDMR and EWMR as benchmarks, we can also rewrite the statements to instead compare to the actual expected values. restate Theorem 4.2 and Theorem 5.7 below as Corollary M.1 and Corollary M.2 respectively.
Corollary M.1 Assume D is supported on [0, 1] and has constant (relative to m) mean and variance s². Then for every Eo > 0, there exists such that if n 2 E (ewir,, o)] 2 - Eo.
Proof. Define & as in the proof of Theorem 4.2. Under event &, we have that
ddist, σ sw(ewmr, σ))
max; sw(i, or)
8) (/sswewmrr rr)
z
11 + E)
E E/sw(ewmlt r)]
1
1 1+5
We can then write
1-
[[ddiss(eem)),.r)] 2 Pr(E)
+ Pr((E))0
1+
2 (1 2e 2222 np²
+
2 (1 2e 2: np(n
28
- 1+
2 2e 26 npp
28
Eo
where the last inequality comes from taking suitably large and =00/3.
Corollary M.2 Let D be distribution supported on [0. whose largest median is v, iee. = y=suupyy y Procd(# S y) < }}. Then binomial voting achieves expected welfare of at least 2
Proof. In the last expression of the proof of Theorem 5.7, we exactly have
(Binom,, ] 2 v. 2- Score(Binom(()))
nv
2
N Total Variation Distance
desirable result would be that the EWMR for one distribution generalizes well similar distribu- tions. Unfortunately, this is not the case, and in fact the EWMR for one distribution can have arbitrarily bad expected welfare on an a second distribution that is arbitrarily close in total variation distance.
Theorem N.1 For every 0 8 < and
< 1 there exists n, m, a and distributions D1, D2 both supported on j0. 1] such that TV1 D2) S a and the social welfare maximizing rule on alternative D2 is not 8-E 5-EWMR for D2.
Proof. This follows directly from the construction in the proof of Theorem 5.2 in Appendix G.
31

---

N.1
Borda Count
Borda count has been previously shown be the scoring rule that maximizes expected welfare for the uniform distribution (which we also prove in Lemma N.2. Despite the negative result of Theorem N.I, somewhat surprising result is that Borda count also a (1 3>-EWMM for distributions close in total variation distance to the uniform distribution. We formalize this result in Theorem N.4.
Lemma N.2 (Weber [1978)) Define Borda count as the scoring rule that assigns scores (1, 21,2...., m) to the alternatives in rank order. Then Borda count is equivalent to the expected welfare maximizing rule when the underlying distribution Uniform[O,
Proof. Let X(1), ((m) be the order statisties from m i.i.d. draws from the Unif(O, 1) distribution.
Then [[X(a]] m-II For alternative j. let Ti,...Tn be the ranks of alternative j by voters I....,
and let Score(j) be the Borda count score of alternative j. Then by linearity of expectation,
Eldsw (j, σ) = E
X (m++-1))
E X (m+1-1a)
m + T3 m + 1=1
Score
m
Therefore, maximizing the expected social welfare is equivalent to maximizing the Borda count score Score(j).
Lemma N.3 Let Unif(0, 1) be the uniform distribution and P be a continuous distribution supported on [0, 1] with an invertible edf such that
(V,
PP(A) U(A) S. AC
sup
Define ((s)) as the the kth order statistic of m i.i.d. draws from P. Then
k
B[X
Se.
m
Proof. Let Fp and Fu be the edfs of P and respectively. Under the assumption, for all [0, 1]:
FF(x) (z)) [F((x) - x S.
Because the slope of is 1 and these distributions are supported on [0, 1), this implies that for all y E [0, 1]:
FF wl S.
The probability integral transform for order statistics gives that X(a) ~ FU where U(a is the kth order statistic from i..d. draws from U. Using that [[U m-I have the following
&
32

---

result for the expectation of (())-
k
k
E (()
B (U()))
m
m7 + 1
1 F (v)Ju (y) dy
k
m +
A:
(F [v) y) (v) dy + E(U(x))
m
//' (F (w) - y) (v) dy
|F ()-(()) vl Sesces (v) dy
efu (v) dy
E.
Theorem N.4 Let be a continuous distribution with invertible edf that is supported on [0, such that (V 1), P) S S 1. Let Score represent the Borda score. Then the Borda count winner a Se-approximation of the expected welfare maximizing rule.
E|dss (Borda, r (1 5e) E[dsw (ewmr, rr).
Proof. Recall that lemma N.2 shows that
Score(j)
m + 1 Σ i=1
=(m 1)
11
m
+
i=1
Define X (m++1-?) to be the (m+1-r;1) order statistic. Recall that Lemma N.3 states that for all r?.
r!
E X (m+1-r2))
SE.
+
Furthermore,
F(dsw(j (iaa((
Σ i=1
E (m+1-
Combining these two equations gives
E[dsw(j. [j, m + 1 r
S nE,
m +
or equivalently,
Score(j) m +
E]dsw(j, a]
< ne.
Because Borda(or) is the alternative that maximizes Score(j), we can apply this inequality twice get
Eldsw (Borda, σ) + ne Score(Borda(r))
m + 1 Score (T)
m +
E/dsw(ewmr, σ)] mE.
33

---

To relate ne to E[dss(ewmn) o ] we need to lower bound the expectation. If two distributions supported on [0, 1] have total variation distance then the means of the two distributions differ by at most e. Therefore, if /a is the expected value of P, then 0.5 c. This means Lemma F.1 implies:
Bldsw(ewmr, o) 2 np 2 n (0.5 - <).
Therefore, the two equations above combine to:
(Borda, r]] 2 (edds(eewmi σ)] 2ne
2ne
Eldsw (edwweemmr,o)) or]
Eldsw (ewmnr σr)
2na
Eldsw(ewmr, o))
ns
2 (1 55) Bldsw (ewmn, o)]
The last inequality comes from taking e S 10
Plurality
Theorem 0.1 For every value of n, m and every distribution D, plurality is an a-SWMR for
1
max
Proof. Define Plurality(ar) as the plurality winner. Then by definition, Plurality (or is the top-ranked alternative by at least [ voters. The maximum total expected welfare for an alternative is [E X (m))) where [[X(m)] is the expected value of the maximum from m i.idd draws from D. Therefore, the expected welfare of Plurality (ar) is lower bounded as follows:
E/dss(Phuraiity, o)] 2 m (()(
E[dsw(ewmr, o)]
max m 1) E(dsw(ewmr, o)).
34


Reviews:
[{"review_id": "ZwmDwnqJan", "reviewer": "Reviewer_Bk7r", "summary": "This paper studies the concept of expected distortion for voting rules, where distortion measures the worst-case ratio between the maximum social welfare and the rule's welfare. Expected distortion considers the expectation over consistent utility profiles drawn from an underlying i.i.d. distribution. The paper shows majority is optimal for two alternatives. For more alternatives, expected welfare maximization approximates expected distortion maximization for large electorates or alternatives. A novel voting rule called binomial voting is proposed and shown to approximate expected welfare maximization in a distribution-independent manner. Its guarantee depends on the median of the distribution.", "questions": "I got lost in the proof of Theorem 3.1.  In particular, could not see why a coupling argument was necessary (or sufficient).  I am not suggesting that the proof is wrong, rather (likely) unclear in its current condensed form (it could just be a me thing, but I am not a newbie to complex proofs).  \n\nCould you help me out here?\n", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Provides an interesting perspective by analyzing distortion in an average-case Bayesian setting rather than worst-case.\nEstablishes asymptotic equivalence between expected distortion and welfare maximization.\nBinomial voting is intuitive and has strong guarantees dependent on the median. Approaches expected welfare maximization.\nSolid theoretical analysis with proofs of key hardness and approximation results.  Does a good job exploring the space.\n", "weaknesses": "Assumption of i.i.d. utilities may be unrealistic for some domains like politics. Correlated utilities more reflective of reality.\nThe paper oversells itself.  In the abstract it works for “all distributions”; in the intro, i.i.d. distributions; and then in the main body consistent utility profiles drawn where each value is drawn from some  underlying i.i.d. distribution.\nI think I am in the minority on this, but I don’t love distortion as something to optimize.  It assumes truthful voting, which is very dubious in positional voting schemes (like is suggested in the paper).  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer comment:**\n\n> The paper oversells itself. In the abstract it works for “all distributions”; in the intro, i.i.d. distributions; and then in the main body consistent utility profiles drawn where each value is drawn from some underlying i.i.d. distribution. \n\n**Response:**\n\nThank you for letting us know this was unclear, and we are happy to augment the abstract with further details! The different wordings here are because we provide more specific details about the same model as the paper progresses, and not an attempt to oversell the paper. \n\nTo clarify, the use of the term \"all distributions\" in the intro refers to the fact that the underlying distribution D (from which i.i.d samples are drawn) can be any distribution. In addition, consistent utility profiles are necessary when conditioning on a preference profile, which we believe is a harder and more interesting setting than taking an expectation over all preference profiles. This is because without conditioning on a preference profile, all alternatives have roughly the same social welfare (especially in the large), which obviates the need for a good voting rule. If interested, we provide further discussion of this point in our response to reviewer gjAU.\n\n\n\n**Reviewer comment:**\n\n> I got lost in the proof of Theorem 3.1. In particular, could not see why a coupling argument was necessary (or sufficient). I am not suggesting that the proof is wrong, rather (likely) unclear in its current condensed form (it could just be a me thing, but I am not a newbie to complex proofs). Could you help me out here?\n\n**Response:**\n\nHere is a higher level overview of how we used a coupling argument in Theorem 3.1. Please let us know if there are any parts that are still unclear!\n\nIn Theorem 3.1, we want to show that the majority winner also has weakly higher expected distortion than the  majority loser. To do this, it is sufficient to show that the expected distortion of alternative 1 when it is ranked first $k$ times is weakly lower than the expected distortion of alternative 1 when it is ranked first $k+1$ times. This is exactly the equation on page 5 following the sentence beginning with \"Recall that...\". Showing this is sufficient because, by definition, the majority winner is ranked first at least as many times as the majority loser.\n\nThis brings us to the coupling argument itself. Define event $A$ as the event that alternative 1 is ranked first $k$ times, and define event $B$ as the event that alternative 1 is ranked first $k+1$ times. The only difference between these two events is that one voter prefers alternative 2 under event $A$ and prefers alternative 1 under event $B$. Therefore, because these two events only differ by a single voter, we can use a coupling argument to compare the expected distortion of alternative 1 under these two events. Assume WLOG that voter $n$ is the differing voter. Fixing the values of the utilities of the first $n-1$ voters (which are the same under both event $A$ and $B$), the only voter that changes the expected distortion is the $n$th voter. This allows us to use the law of total expectation to separate out the randomness of this $n$th voter from the randomness of the rest of the voters. Therefore, the coupling argument is that these first $n-1$ voters are coupled between the two events, with the only change coming from the $n$th voter. The proof concludes with the algebraic equations on the top of page 6, which show exactly the desired inequality between the expectation of the distortion under event $A$ versus event $B$."}, {"review_id": "fermZi8DCK", "reviewer": "Reviewer_J4Js", "summary": "This work introduces the notion of the expected distortion of voting rules. The setup involves n voters and m alternatives. Each voter $i$ has a utility $u_{ij}$ for alternative j, which induces a ranking $\\sigma_i$ of the alternatives, where $j$ is ranked higher than $k$ in $\\sigma_i$ only if $u_{ij} \\geq u_{ik}$. A deterministic voting rule $f$ only has access to the ordinal preferences profiles $\\boldsymbol{\\sigma}$ instead of the actual underlying utilities $\\mathbf{u}$. In the standard worst-case analysis, the distortion of a voting rule is defined as the social welfare incurred by the information loss, i.e.,$$\\sup_{\\boldsymbol{\\sigma}} \\sup_{\\mathbf{u}: \\mathbf{u} \\triangleright \\boldsymbol{\\sigma}} \\frac{\\max_{j \\in A} sw(j,\\mathbf{u})}{sw(f(\\boldsymbol{\\sigma},\\mathbf{u}))}.$$\nThis work considers a different setting. Given a preference profile $\\boldsymbol{\\sigma}$, a utility vector consistent with the preference profile $\\mathbf{u}$ is drawn from some distribution $D$ as follows: Each voter $i$ draws $m$ utilities i.i.d from $D$, and these $m$ utilities are assigned from highest to lowest to the $m$ alternatives according to the order of $\\sigma_i$. The paper then defines the distributional distortion of a voting rule $f$ for a given preference $\\boldsymbol{\\sigma}$ as a random variable $$ddis(f,\\boldsymbol{\\sigma}) = \\frac{sw(f(\\boldsymbol{\\sigma}), \\mathbf{u})}{\\max_{j \\in A} sw(j,\\mathbf{u})}.$$ Subsequently, the expected distortion of $f$ for a given $\\boldsymbol{\\sigma}$ is the expectation of this ratio, taken over the random process described above.\nSimilarly, it defines distributional social welfare $dsw(f, \\sigma) = sw(f(\\boldsymbol{\\sigma}), \\mathbf{u})$ and expected social welfare. Unlike the worst-case distortion, the benchmarks the paper considers is agnostic to the actual underlying utility profile, but rather the best voting rules that can know only to the distribution $D$ the utilities are drawn from. The best such rules are termed EDMR (expected-distortion-maximizing-rule) and EWMR (expected-welfare-maximizing-rule) for the expected distortion and expected social welfare objective, respectively.\n\nRegarding the results, for the two-alternative case, the paper shows that the Majority rule is both EDMR and EWMR. For multiple agents, by restricting attention to distributions that are independent of $n$ and $m$, and for sufficiently large $n$ or sufficiently large $m$, the expected distortion of an EWMR is a $1-\\epsilon$ approximation of the expected distribution of an EDMR. The paper then attempts to approximate the expected welfare which in terms to approximate the expected distortion of EDMR, under the stated conditions. To achieve this, they first present a negative result, demonstrating that it is impossible for a single voting rule to achieve any constant $\\alpha$ approximation of the expected social welfare for all distributions supported on $[0,1]$. To overcome this negative result, the paper shows that for symmetric distributions, a scoring rule that assigns a score of 1 to alternatives ranking in the highest half position and 0 to others, and outputs the alternative with the highest score, achieves an expected welfare 1/3 of the welfare of EWMR. IT also show that no voting rule can achieve a $\\sqrt{1/3}$ approximation for this setting. Another way to overcome the aforementioned negative result is by assigning a score of $\\sum_{\\ell = k}^{m} {m\\choose\\ell}$ to an alternative ranked $k$. The paper demonstrates that this smoother version of the top-half score rule is a $v/2$ approximation to the EWMR, where $v$ is the largest median. ", "questions": "Is there any results or intuition regarding how bad is the worst expected distortion for EDMR for different $D$? For example,for the special case of two alternatives, what's the worst expected distortion for majority for different $D$? \n\nIt seems like all the utilities i.i.d drawn from the same distribution is need for a lost of the concentration bounds to go through. Does the results still hold if voters are drawing the values for candidates i.i.d from $D_i$?\n\nRegrading the assumption that D is supported on [0,1], it is true that for the results to go through one only need the utilities to be bounded? Or the maximum of the distribution indeed affects the guarantees?", "limitations": "The assumptions are distributions for the positive results to hold are rather restricted. The results are not tight.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well organized. The high-level idea of moving beyond worst-case analysis for distortion is novel and of great interest. The observation of the connection between the optimal expected welfare and optimal expected distortion under different distributional assumptions is interesting. The distributional-independent adaptation of the scoring rule of Boutilier et al [2015] is intuitive (in a good way) and clever.", "weaknesses": "I find the benchmark to be relatively weak, and the positive results are somewhat marginal. Additionally, there are some correctness issues in the proofs.\n\nTo expand on the first point regarding the benchmarks, let us recall that the standard worst-case distortion measures the greatest difference between the social welfare of a voting rule that only has access to the ordinal preference and the optimal social welfare of the utilities that are consistent with the preference. This work relaxes the measure in two ways: First, the ratio is now measured in expectation, which aligns well with the idea of the paper. Second, the benchmarks are voting rules that are also agnostic to the underlying utilities but can have knowledge of the distributions from which the values are drawn (EDMR and EWMR). However, it is not clear to me why the second relaxation is needed or interesting, and no motivation is provided regarding the choice of such benchmarks. In fact, without the second relaxation, we can define the expected distortion of a voting rule for $D$ as follows:\n$$\\inf_{\\boldsymbol{\\sigma}} \\mathbb{E}\\left[\\frac{sw(f(\\boldsymbol{\\sigma},\\mathbf{u}))}{\\max_{j \\in A} sw(j,\\mathbf{u})}\\right].$$\nResults regarding the above evaluation seem to better capture the ''average-case analysis'' the paper refers to. To this end, it is unclear how well the EDMR (possibly distribution-dependent) performs with respect to the above benchmarks, which is also interesting and arguably a more natural question to tackle first before distribution-independent voting rules.\n\nRegarding the second point, please note that the positive results in section 5 are all with respect to the expected social welfare considered by Boutilier et al. [2015]. The results presented in this work are stronger since they are distribution-independent, but they are weaker since the distributions are assumed to be bounded (supported on [0,1]). As far as I know, no such restriction is needed for Boutilier et al.'s results to hold. To translate these expected social welfare results into expected distortion results, one needs to further restrict distributions to the ones that are independent with respect to both $n$ and $m$ and with sufficiently large $n$ or $m$, which weakens the positive results. Additionally, none of the bounds in section 5 are tight.\n\nThere are a few incorrect arguments in the proofs, the most important one I spotted being in the proof of Lemma F1. The first sentence states that by linearity of expectation, $\\mathbb{E}[dsw(j, \\sigma)] = \\sum^n_{i = 1} \\mathbb{E}[u_{ij}] = n\\mu$ for all $j$, where $\\mu$ is the mean of distribution $D$. The second equality seems to be incorrect. Consider a simple example with 2 alternatives and 2 agents with $D$ being Uniform$[0,1]$, and alternative $1$ is ranked second by any $i$. Then $u_{i1}$ will be the first-order statistic out of two draws for both agents, making $\\mathbb{E}[u_{ij}] = 1/3$ instead of $=\\mu = 1/2$. This, in turn, makes the proof of F1 invalid. With that said, I believe the statement of Lemma F1 is correct. A possible alternative proof is as follows: since $\\sum_{j} dsw(j,\\sigma) = \\sum_{j}\\sum_{i} u_{ij} = mn\\mu$, and the maximum $dsw$ is always weakly higher than the average $dsw = n\\mu$. Similarly, in the proof of theorem 4.2, the claim that the social welfare of any alternative $j$ can be represented as $dsw(j,\\sigma) = \\sum^n_{i=1} u_{ij}$, where $u_{ij}$ are $n$ i.i.d. random variables, is also incorrect since $j$ could be ranked in different positions for different voters $i$, and $u_{ij}$s are therefore only independent, not identical. This issue is again not major, as Hoeffding’s inequality only requires the variables to be independent and bounded. However, these false claims hinder my confidence in the rest of the proofs that I did not check to the same level of detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer comment:**\n\n> I find the benchmark to be relatively weak. [...] We can define the expected distortion of a voting rule for $D$ as follows: $$\\inf_{\\boldsymbol{\\sigma}} \\mathbb{E}\\left[\\frac{sw(f(\\boldsymbol{\\sigma},\\mathbf{u}))}{\\max_{j \\in A} sw(j,\\mathbf{u})}\\right].$$ Results regarding the above evaluation seem to better capture the ''average-case analysis'' the paper refers to. To this end, it is unclear how well the EDMR (possibly distribution-dependent) performs with respect to the above benchmarks, which is also interesting and arguably a more natural question to tackle first before distribution-independent voting rules.\n\n**Response:**\n\nTo paraphrase, you're asking why we aren't providing direct expected distortion (or expected welfare) bounds. This benchmark was indeed our starting point, but in the course of 9 months of working on this project (from September 2022 until May 2023) we shifted focus to approximating the EDMR and EWMR, where we could paint a much more complete picture. \n\nImportantly, our proofs can be adapted in order to restate our results in terms of direct bounds on expected distortion and welfare. For example, the following statements follow from our proofs:\n\n*Thm 4.2 restated:* For every $\\epsilon > 0$, there exists $n_0$ such that if $n \\ge n_0$, then the expected distortion of the EWMR is at least (1- $\\epsilon$).\n\n*Thm 5.7 restated:* Let $\\mathcal{D}$ be a distribution supported on $[0,1]$ whose largest median is $\\nu$. Then binomial voting achieves expected welfare of at least $\\nu n/2$.\n\nNote that both statements are true for all $\\sigma$, and therefore also hold when expected distortion is defined with an $\\inf$ as in your comment.\n\nIn light of your comment, we absolutely agree that more discussion of the benchmarks is needed. In our revision, we commit to adding 1-2 paragraphs about this to the paper, as well as including an appendix to elaborate on the technical connection between the benchmarks. We believe that such a revision would address your concern and would be well within the scope of a conference revision. \n\n**Reviewer comment:**\n\n> There are a few incorrect arguments in the proofs, the most important one I spotted being in the proof of Lemma F1. The first sentence states that by linearity of expectation, $\\mathbb{E}[dsw(j, \\sigma)] = \\sum^n_{i = 1} \\mathbb{E}[u_{ij}] = n\\mu$ for all $j$, where $\\mu$ is the mean of distribution $D$. The second equality seems to be incorrect. [...] Similarly, in the proof of theorem 4.2, the claim that the social welfare of any alternative $j$ can be represented as $dsw(j,\\sigma) = \\sum^n_{i=1} u_{ij}$, where $u_{ij}$ are $n$ i.i.d. random variables, is also incorrect since $j$ could be ranked in different positions for different voters $i$, and $u_{ij}$s are therefore only independent, not identical. \n\n**Response:**\n\nBoth issues are valid — thanks for catching them and kudos on reading Appendix F! The latter issue is a typo (\"i.i.d.\" should be \"independent\"), but the former issue is an embarrassing, albeit easily fixable, mistake. The correct argument is actually commented out in our LaTex file; it appears that in the last proofreading round, one of us introduced the mistake by attempting to slightly simplify the argument. The paper (including appendices) had been carefully proofread by multiple authors over several days before submission. We therefore hope that the minor mistake will be seen as a fluke that doesn't reflect on the soundness of our results. \n\n**Reviewer question:**\n\n> Is there any results or intuition regarding how bad is the worst expected distortion for EDMR for different $D$? For example,for the special case of two alternatives, what's the worst expected distortion for majority for different $D$?\n\n**Response:**\n\nThis question is partially addressed above. We do not know the answer your specific question about two alternatives, but not for lack of trying — we spent a while looking at regular and MHR distributions in this context. \n\n**Reviewer question:**\n\n> It seems like all the utilities i.i.d drawn from the same distribution is needed for a lot of the concentration bounds to go through. Do the results still hold if voters are drawing the values for candidates i.i.d from $D_i$?\n\n**Response:**\n\nRelaxing the i.i.d. assumption across either voters $i$ or alteratives $j$ are both interesting directions for future work. We suspect that we may be able to relax the i.i.d. assumption across voters (allowing each voter to have their own distribution for all candidates), as we may be able to leverage similar arguments regarding order statistics. Relaxing the i.i.d. assumption across candidates is likely much more difficult, as the expected utilities of a given voter can no longer be described by order statistics. \n\n**Reviewer question:**\n\n> Regarding the assumption that D is supported on [0,1], it is true that for the results to go through one only need the utilities to be bounded? Or the maximum of the distribution indeed affects the guarantees?\n\n**Response:**\n\nBounded utilities are sufficient for the results to go through — we chose to focus on $[0,1]$ to make the proofs clearer mathematically, that is, the assumption is made purely for ease of exposition. The maximum of the distribution does not affect our guarantees, as expected distortion is invariant to scaling of the distribution."}, {"review_id": "o8bzrWALIB", "reviewer": "Reviewer_TGPz", "summary": "The paper studies voting rules in the context of expected distortion and expected welfare. In more detail, one of the trending topics in social choice theory is the design of voting rules with low distortion. The underlying assumption for this is that voters have utilities over the alternatives, but only report ordinal preferences. Then, the distortion quantifies the loss of social welfare (=sum of the voters utilities) caused by not knowing the cardinal utilities. To this end, one typically investigates the utility profile (and induced preference profile), where the ratio between the social welfare of the optimal alternative and the alternative chosen by the voting rule is maximal. This is clearly a worst-case measure and allows, without additional assumptions, only for rather negative results. The paper at hand therefore analyzes expected distortion: given a preference profile, the authors assume that, for each voter, the utilities for the alternative are drawn i.i.d from some distribution, and then try to find alternatives that have in expectation a high social welfare (and therefore a good distortion). \n\nClearly, if we have knowledge about the distribution, it is theoretically possible to compute the alternative that maximizes the expected welfare. The authors thus rely on a model where the prior is not known (and we are thus not in the bayesian setting). In particular, while there is an underlying distribution, it is not known to the mechanism designer. In this setting, the authors then show that for 2 alternatives, the majority rule is the rule that optimizes the expected social welfare and the expected distortion for every underlying distribution. For more than 2 alternatives, the authors furthermore design a new rule called binomial voting (which is a scoring rule relying on the binomial coefficient for the score vector) which always chooses an alternative that has an expected welfare of at least v/2 times the expected welfare of the optimal alternative (where v is the median of the underlying, unknown distribution of utilities). For deriving this result, the authors establish a link between the maximization of expected social welfare and expected distortion. Finally, the authors also discuss several variants of their main result and the limitations of their approach.", "questions": "1) Can the authors say something about the expected distortion of known rules? This seems necessary to get some intuition about how strong the results are.\n2) Similarly, can the authors say more about upper bounds on expected distortion? Currently, Theorem 5.2 rules out the existence of voting rules with constant expected distortion, but can we, e.g., hope to find a voting rule which is v-EDMR (where v is the median of the distribution) rather than v/2-EDMR?\n3) The importance of the results hinges on some implicit assumption. For instance, the main result of the authors is only appealing if the median of the underlying (but unknown) distribution is not too small. Can the authors comment on whether there is some evidence that this might be the case? ", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is well-written and, despite its technical complexity, I found it easy to follow the main ideas of the paper. Furthermore, the paper opens an interesting new direction for going beyond the worst-case distortion in voting by studying the expected distortion. Since the worst-case distortion is known to be prohibitive and the new model seems reasonable, I find the approach quite attractive. Moreover, the results are interesting as they give first, clearly non-trivial bounds for this new setting. Finally, since distortion in voting is a topic that has appeared in NeurIPS before. \n", "weaknesses": "On the negative side, it should be mentioned that many of the main claims of the paper cannot be verified based on the paper itself (as all proofs are deferred to the appendix). (I also did not read the appendix and can therefore not vouch for the correctness of the given results; the proof of Theorem 3.1, which is the only one that is (almost completely) presented in the paper seems correct). Furthermore, I find the comparison to the literature somewhat lacking. For instance, Ebadian et al. (Optimized Distortion and Proportional Fairness in Voting, 2022) suggest several voting rules with close to optimal worst-case distortion and it seems interesting or even necessary to reason why these rules are not good in the given setting. In particular, the harmonic rule by Boutilier et al. (Optimal social choice functions: A utilitarian view, 2015) is also a scoring rule and it thus seems like an interesting question whether it also has a good expected distortion. However, I have to acknowledge that the paper is already quite dense and that the discussion of these results might be too much. \n\n\n\nFeedback: \n\n1) I am not a fan of the pun in the title.\n2) I think it should be better motivated why the authors use the distribution to draw utilities. This assumption is crucial for the results, not the only way to define expected distortion, and I am not entirely sure about how convincing this model is. In particular, the assumption implies that the preference intensities of voters are (in average) similar, which may not capture reality.\n3) Instead of Section 5.2 (which is certainly interesting, but rather dense and technical), one could think of introducing more detailed proof sketches or to discuss the expected distortion of known rules. In principle, I feel that this space is just not used in the most effective way (but the authors may disagree with me here, this is clearly subjective)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer question:**\n\n> Can the authors say something about the expected distortion of known rules? This seems necessary to get some intuition about how strong the results are.\n\n**Response:**\n\nSince expected distortion is defined with respect to a specific distribution and preference profile, we would need to know these parameters as well as the rule of interest. Given a specific distribution, preference profile, and voting rule, we can directly calculate or approximate the expected distortion using nested integrals or Monte Carlo sampling. \n\nThat being said, our results do connect back to some known rules. For uniform distributions (or distributions close to uniform), Borda Count is the expected welfare maximizing rule and therefore a good approximation of the expected distortion maximizing rule. For the two alternatives case, Theorem 3.1 also shows that plurality does maximize distortion. For more than two alternatives, Theorem N.1 shows that plurality is an $\\alpha$-EDMR rule for $\\alpha = \\max(\\frac{1}{n}, \\frac{1}{m})$.\n\nOne reasonable (and interesting!) question for future work could be, what is the *worst* distribution and preference profile for a specific rule, and how does the expected distortion compare to that of the EDMR in this setting? Our guess would be that for most rules, there is some distribution/preference profile pair for which the rule performs very poorly relative to the EDMR. If so, this would imply that our decision of whether or not to use a certain voting rule (e.g. harmonic) should depend on our hypothesis of the underlying distribution. This makes a lot of sense -- we might want to use Borda Count when the underlying distribution is approximately uniform, but not when the underlying distribution is approximately Bernoulli. We could also choose to use a voting rule with distribution independent guarantees such as binomial voting.\n\n\n**Reviewer question:**\n\n> Similarly, can the authors say more about upper bounds on expected distortion? Currently, Theorem 5.2 rules out the existence of voting rules with constant expected distortion, but can we, e.g., hope to find a voting rule which is v-EDMR (where v is the median of the distribution) rather than v/2-EDMR?\n\n**Response:**\n\nWe found proving upper bounds (such as no rule can achieve $\\nu$-EDMR) to be significantly harder than proving lower bounds. While we do not have a tight upper bound for the best $\\alpha$-EDMR rule, the example in the proof of Theorem 5.5 can give some insight into a possible upper bound. In that proof, the two distributions (which happen to be both symmetric) have medians of $0.5$ and $1$ respectively. The proof shows that it is impossible to achieve a $\\sqrt{1/3}$-EDMR for both of these distributions. Therefore, no rule can do better than a $1.14\\nu$-EDMR where $\\nu$ is the median. Clearly, this still does not rule out the possiblity of a $\\nu$-EDMR rule, but a more tailored example than the above would almost certaintly give stronger results.\n\n\n**Reviewer question:**\n\n>The importance of the results hinges on some implicit assumption. For instance, the main result of the authors is only appealing if the median of the underlying (but unknown) distribution is not too small. Can the authors comment on whether there is some evidence that this might be the case?\n\n**Response:**\n\nWhile the binomial voting rule does rely on the median being not too small, the generalized binomial voting rule can give stronger results that depend on higher quantiles. If the median is too low in a specific application for the binomial rule to give a strong result, then using higher quantiles in the generalized binomial voting rule will improve the guarantees. Therefore, one solution is to use a high enough quantile in the generalized binomial rule to get a useful guarantee. If even the higher quantiles are too small to give interesting guarantees, then the distribution has mass concentrated at $0$. A distribution with mass mostly concentrated at $0$ does require a substantially different approach, but this case may be \"easier\" because most voters have utility $0$ for most alternatives. "}, {"review_id": "V0jnjM7hs5", "reviewer": "Reviewer_3WoR", "summary": "This paper studies the distortion of voting rules, which is a measure of how well a voting rule performs with respect to optimal social welfare while having access to limited information about preferences. In particular, the focus is on expected distortion where the underlying utility vectors are drawn from an arbitrary prior distribution and the goal is to design a voting rule that doesn't use any information about such prior distribution, similar in spirit to the design of prior-independent auction mechanisms.\n\nThe main approach is to first design an approximate expected welfare maximizing rule (EWMR) and then derive conditions under which EWMR approximates expected distortion maximizing rule (EDMR). When there are only two alternatives ($m=2$), it turns out that the majority is rule is both an EDMR and EWMR. However, this is not true for $m>2$ and the authors consider scoring rule based methods.\n \nThe authors show that approving the top half is $1/3$-approximate EWMR for all symmetric distributions. For asymmetric distributions, the authors propose a new scoring called the Binomial voting rule which is $\\nu/2$-EDMR for any distribution with median $\\nu$. Furthermore, it is also shown that the voting rule can be adapted to incorporate partial knowledge about the underlying distribution e.g. various quantiles.", "questions": "1. If the assumption of symmetric distribution is violated, can you obtain $\\alpha$-EWMR for some distribution independent constant $\\alpha$? I understand that Theorem 5.2 provides a negative result but the distribution in the theorem needs to depend on $n$, and $m$. Is it still the case for asymmetric distributions independent of $n$, and $m$?\n\n2. Since the distortion of the binomial voting rule depends on the median of the prior distribution, a natural question is why median and why not some other statistic? In particular, if the median of the prior distribution is very small, should the distortion of any voting rule be small as well? Note that, mean can be large in this case as $E[X]$ can be as large as $\\textrm{Median}(X) + \\sqrt{\\textrm{Var}(X)}$.", "limitations": "The authors have addressed the limitations of the paper.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I think the notion of prior independent voting rules is quite interesting as the voting rules don't need to depend on the underlying distribution. Furthermore, the results show that prior independent voting rules can achieve constant expected distortion.\n\n2. The connection between EWMR and EDMR voting rules is non-trivial and might turn out to be an interesting approach to designing voting rules that aim to maximize welfare.\n\n3. Finally, the Binomial voting rule is quite interesting and I also liked the result showing that the voting rule can be adapted to incorporate additional information regarding the prior distribution.", "weaknesses": "1. The main weakness of the paper is that the utilities of the voters for the $m$ items are assumed to be i.i.d. from the prior distribution. In practice, the utilities of different alternatives are often correlated and this assumption excludes distribution like Gaussian with general covariance matrix. However, the authors have mentioned the limitations in the paper.\n\n2. I am also a bit concerned about the guarantees provided by prior-independent voting rules. Repeated auctions are quite frequent in online platforms and providing bound on performance in expectation makes sense. On the other hand, voting rules are used less frequently -- political elections happen every couple of years, and people's preferences change from one iteration to the next. In such a situation, providing instance dependent bound on distortion is more practical. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer comment:**\n\n> I am also a bit concerned about the guarantees provided by prior-independent voting rules. Repeated auctions are quite frequent in online platforms and providing bound on performance in expectation makes sense. On the other hand, voting rules are used less frequently -- political elections happen every couple of years, and people's preferences change from one iteration to the next. In such a situation, providing instance dependent bound on distortion is more practical.\n\n**Response:**\n\n\nIf we understand correctly, your concern is not about *prior-independent* voting rules, as infrequent elections make it unlikely that much information about the distribution would be available, which strengthens the case for prior independence. \n\nInstead, your concern seems to be about the very idea of optimizing *expected* distortion, and by \"instance-dependent bound\" you seem to be referring to the worst case over utilities consistent with the given profile. We believe we can provide some useful perspective. First, to say the obvious, this worst-case bound could be extremely bad; in fact, without the unit-sum assumption, there exist preference profiles for which no bound exists. Second, even when given a preference profile where the worst-case bound is reasonable, we would still prefer to optimize expected distortion (assuming these two measures disagree on the outcome), as it is *intuitively* (albeit not formally) likely to lead to an outcome with higher social welfare. (Formalizing this intuition is an interesting problem!) \n\n**Reviewer question:**\n\n> If the assumption of symmetric distribution is violated, can you obtain $\\alpha$-EWMR for some distribution independent constant $\\alpha$? I understand that Theorem 5.2 provides a negative result but the distribution in the theorem needs to depend on $n$, and $m$. Is it still the case for asymmetric distributions independent of $n$, and $m$?\n\n**Response:**\n\nThe distributions in the proof of Theorem 5.2 are both Bernoulli distributions that only depend on $\\alpha$. Therefore, if we consider all asymmetric distributions independent of $n$ and $m$, both of these distributions would be included. The proof in the theorem is dependent on $n,m$ because it required $m$ and $n$ to be sufficiently large. Therefore, Theorem 2 could be restated as \"For any $\\alpha$, there is no rule that is $\\alpha$-EWMR for all distributions if we allow $n$ and $m$ to be arbitrarily large, even if we restrict to distributions that are independent of $n,m$\". An interesting extension possibly related to your question is, if we restrict to $n,m < 100$ (or any constant), whether $\\alpha$-EWMR is possible for some constant $\\alpha$. The answer is yes (for example plurality will guarantee $\\frac{1}{100}$-EWMR in this case), but characterizing the exact constant is left for future work.\n\n\n**Reviewer question:**\n\n> Since the distortion of the binomial voting rule depends on the median of the prior distribution, a natural question is why median and why not some other statistic? In particular, if the median of the prior distribution is very small, should the distortion of any voting rule be small as well? Note that, mean can be large in this case as $E[X]$ can be as large as $\\textrm{Median}(X) + \\sqrt{\\textrm{Var}(X)}$.\n\n**Response:**\n\nYou are correct that the median is not inherently special. The binomial voting rule can be generalized to any quantile or combination of quantiles with the generalized binomial voting rule in Theorem 5.11. If the median of the prior distribution is very small, then using higher quantiles (75%, 95%, etc) would give stronger guarantees with the generalized binomial voting rule. As you point out, medians are not necessarily representative of the mean or higher moments of the distribution. Our results use medians and quantiles because the EWMR calculates the order statistics of the underlying distribution. Moments/means do not provide much information about order statistics, however, quantiles can be used to lower bound order statistics as in Theorems 5.7 and 5.11. This naturally leads to voting rules that use quantiles such as the generalized binomial rule. That being said, it is definitely possible that another rule could use information about moments of the underlying distribution to better approximate the order statistics."}, {"review_id": "O6Z4lKni6t", "reviewer": "Reviewer_M8Ee", "summary": "This paper studies the expected distortion of deterministic voting rules in a distributional setting proposed by Boutilier et al. in 2015. The setting assumes each voter has a random utility for each alternative drawn i.i.d. from a distribution $D$. Then for a given preference profile $\\sigma$, the expected welfare of a voting rule is defined as the expectation of winner's total utility conditioned on utilities are consistent with the preference profile $\\sigma$. The expected distortion of a voting rule $f$ for a fixed $\\sigma$: $ddist(f, \\sigma)$ is defined as the expected ratio between total utility of the winner determined by the voting rule and the total utility of the candidate with the highest utility. Note that although utilities are i.i.d. from a distribution, the preference profile can be arbitrary and considered in the worst case. \n\nThe first contribution is the authors' demonstration that the majority voting rule results in optimal expected distortion in cases where only two candidates are present. This finding aligns with extensive literature suggesting that majority (or plurality) is the sole \"reasonable\" voting protocol when faced with a two-candidate scenario. \n\nThe paper also explores the connections between expected social welfare and expected distortion. By some standard concentration bounds, the author prove that any voting rule that approximately maximizes expected social welfare also approximately achieves optimal   distortion under mild conditions on the distribution.\n\nFinally, Boutilier et al. [2015] identifies the optimal voting rule in terms of expected welfare. However, this optimal voting rule requires the knowledge of the utility distribution. The main contribution of this paper is that they propose a class of positional voting rules called binomial voting that has good guarantees on expected welfare/distortion for a wide range of distributions. In particular (generalized) binomial voting require no (or limited) information about the distribution.", "questions": "- Do authors know any results if utilities are still independent but from different distributions for different candidates?", "limitations": "The authors addressed all limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The distributional model considered in the paper is reasonable. Instead of resorting to questionable random ranking assumptions such as impartial culture, this paper only makes distributional assumptions for utilities but not preferences.\n\n- The new definition expected distortion under this model is well motivated and the authors provide diverse results under various assumptions on the distribution. \n\n- The binomial scoring rule proposed in the paper is novel. It is a nice result that a single voting rule achieves good expected welfare/distortion for a wide range of distributions.\n\n- This paper is very well-written.", "weaknesses": "- Though preferences are considered in the worst case, the assumption that all utilities are i.i.d. seems a bit strong. \n\n- The results for $m=2$ and connections between expected welfare and expected distortion are not very surprising and techniques involved are fairly straightforward.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer question:**\n\n> Do authors know any results if utilities are still independent but from different distributions for different candidates?\n\n**Response:**\n\nRelaxing the i.i.d. assumption across either voters $i$ or alteratives $j$ are both interesting directions for future work. We suspect that we may be able to relax the i.i.d. assumption across voters (allowing each voter to have their own distribution for all candidates), as we may be able to leverage similar arguments regarding order statistics. Relaxing the i.i.d. assumption across candidates is likely much more difficult, as the expected utilities of a given voter can no longer be described by order statistics. "}, {"review_id": "Vf5eXIdeaw", "reviewer": "Reviewer_gjAU", "summary": "The authors extend the notion of a distortion of a voting rule to a distributional setting. That is, given a distribution over utilities (that the voters have i.i.d. on the candidates), the authors replace the classic distortion with a random variable that depends on the distribution. The expected value of this random variable is the expected distortion. The authors mostly seek rules that have good expected distortion, as compared to a voting rule with the best one possible.\n\nThe two biggest issues with the paper are that the assumed model is highly unrealistic and, worse yet, that it does not seem to lead to any sort of robust conclusions. The assumption that each voter can have a arbitrary (and, possibly, correlated with other voters) preference order, but all the utilities come from the same distribution (i.e., there is a common distribution for each voter and each candidate, except that there is the hidden correlation that utilities that a voter generates for the candidates must respect their preference order) is highly artificial. Then, based on this highly artificial assumption, the authors claim that (under some further, arguably mild assumptions) some specific positional scoring rules (such as m/2-approval and the binomial rule from the title) perform particularly well (however, if I understand correctly, they do not perform _objectively_ well, but simply with respect to the best possible rule, which itself may or may not be very good---I missed if this is clarified in the paper). Now m/2-approval is well understood to be a poor rule because it can be very indecisivle (indeed, if all voters agree that the ranking of the candidates is a > b > c > ... then the rule would not realize that a is the best candidate). The binomial rule is certainly better, but---as argued by the authors---is not too far off m/2-approval. \n\nSo, all in all, the authors make a highly questionable assumption and conclude that some rules that do not look too attractive on the outset, optimize some criterion. This is far too weak a conclusion for a paper that expects to be competitive for NeurIPS.\n\nOn the positive side, the paper certainly includes high-quality mathematics. Still, I cannot really see it as more than an incremental addition  to the distortion literature (I mean incrementality in terms of conceptual contribution, which---I guess---the authors wanted to stress; on the technical level the paper is far from being incremental).", "questions": "Q1: You write that \"the metric assumption is arguably difficult to justify in most domains of interest\". Could you provide the arguments that you have in mind? \n\nQ2: Does your research lead to high-level conclusions beyond \"this rule performs well in our setting?\". The only thing I could think of is that---perhaps---using some sort of family of distributions that either are IID as yours, or become highly correlated (between the candidates) perhaps one could show that the closer we are to the IID setting, the more natural it is to use positional scoring rules, whereas the more highly correlated are the utilities the better are Condorcet-consistent rules. However, this just a guess and I am not sure how such a result could be obtained. However, generally, resolving the argument between Borda and Condorcet based on the correlations between voters' utilities would certainly be something I would be far more willing to recommend for NeurIPS.", "limitations": "The authors admit that their assumption is highly unrealistic, but argue that others make similar assumptions. I understand it is tempting to say so, but given that their work does not seem to give truly valuable conclusions, I think the argument is too weak.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The mathematics behind the results is certainly appealing.", "weaknesses": "The underlying assumption of drawing utilities IID is highly unnatural (especially when merged with the assumption that the  utilities still have to respect submitted preference orders, which creates a weird form of correlation).\n\nThe conclusions of the paper do not seem to have much practical meaning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reviewer comment:**\n\n> The assumption that each voter can have a arbitrary (and, possibly, correlated with other voters) preference order, but all the utilities come from the same distribution (i.e., there is a common distribution for each voter and each candidate, except that there is the hidden correlation that utilities that a voter generates for the candidates must respect their preference order) is highly artificial.\n\n**Response:**\n\nThis seems to be your main concern; we believe that it stems from a misunderstanding and that we can provide an effective rebuttal. \n\nWhen the utilities of the voters for alternatives are drawn i.i.d. from some distribution, the induced preference profile consists of rankings drawn independently and u.a.r. (as you may know, this is called \"impartial culture\" in social choice). One could define expected distortion with respect to the distribution over utilities, without conditioning on the preference profile. But this is a very \"easy\" setting for the analysis of distortion, because (especially in the large) all alternatives would have roughly equal social welfare. Therefore, this setting would not differentiate between different voting rules. \n\nWhen we condition on a preference profile, we are not making an assumption (nor imposing some hidden correlation). Rather, we are setting a tougher requirement. Think of it this way: in most cases, the voting rule would observe a preference profile that is almost symmetric, and then it doesn't really matter which alternative it chooses. But we are requiring the voting rule to do well in *every* situation, regardless of the preference profile it receives as input. This tougher requirement allows us to pinpoint voting rules that truly stand out in terms of their expected distortion (and expected welfare). \n\nTo be clear, we are not saying that i.i.d. utilities are not an assumption we'd like to see relaxed in future work — this is something we openly discuss in the paper. But we believe your concern about correlation (which is later referred to as a \"weird form of correlation\") is unfounded. \n\n**Reviewer comment:**\n\n> Now m/2-approval is well understood to be a poor rule because it can be very indecisivle (indeed, if all voters agree that the ranking of the candidates is a > b > c > ... then the rule would not realize that a is the best candidate).\n\n**Response:**\n\nWe do think binomial voting is more attractive, but let us say a few words in defense of m/2-approval. First off, the family of k-approval rules has received quite a bit of attention. A prominent member of the family is the veto rule, which corresponds to (m-1)-approval (each voter vetoes their bottom-ranked alternative). Veto would obviously have the same issue in your example. \n\nFrom a broader perspective, our model and results provide a novel way of evaluating voting rules. There are many other criteria, including axiomatic desiderata, maximum likelihood estimation under various noise models, distance rationalizability, etc. Your example shows that m/2-approval, without suitable tie-breaking, fails the unanimity axiom. Imposing such additional criteria narrows the search for suitable voting rules; in particular, binomial voting satisfies unanimity. In summary, the new criterion we propose should be seen as another tool in the social choice toolbox, which is meant to be used in conjunction with others. \n\n**Reviewer question:**\n\n> Q1: You write that \"the metric assumption is arguably difficult to justify in most domains of interest\". Could you provide the arguments that you have in mind?\n\n**Response:**\n\nWe note that you are asking us to justify that something is hard to justify :-) But let us respond by way of an anecdote. When one of us talked in 2014 with Elliot Anshelevich, who pioneered the metric view of distortion, the primary example he gave was voting over movies. But we are not convinced that there's a choice of dimensions that gives rise to metric preferences. For example, if the dimensions were quality of the script, quality of acting, etc., then all voters would be located in the same place: the maximum in each dimension. And if one adds dimensions where voters disagree, such as genre, then preferences are no longer single-peaked (imagine a voter who likes comedies and science fiction movies). \n\nAdmittedly, this example is a straw man. And don't get us wrong: we love the metric distortion literature and believe it's very valuable. But we also strongly believe in the importance of models that do not impose the metric assumption — especially when one is able to relax the common unit sum assumption, as we do. \n\n**Reviewer question:**\n\n> Q2: Does your research lead to high-level conclusions beyond \"this rule performs well in our setting?\". The only thing I could think of is that---perhaps---using some sort of family of distributions that either are IID as yours, or become highly correlated (between the candidates) perhaps one could show that the closer we are to the IID setting, the more natural it is to use positional scoring rules, whereas the more highly correlated are the utilities the better are Condorcet-consistent rules. \n\n**Response:**\n\nWe believe this question stems from the misunderstanding about correlation, which is addressed above. "}]

Author rebuttal:

Meta-review: This paper considers the distortion of voting schemes. Several reviewers have pointed out that distortion, without further justification, is not a very compelling metric --- in particular, the paper would greatly benefit from some important real-world examples where the proposed voting rule and metric would be of importance. The authors are encouraged to add a thorough discussion of applicability.

Still, many reviewers agree that the mathematical results are non-trivial and interesting --- in fact, a majority of the reviewers has a positive view of the paper.

In my assessment, the paper merits acceptance.
Decision: Accept (poster)