--- title: "Approval-Based Elections and Distortion of Voting Rules" authors: - "Grzegorz Pierczyński" - "Piotr Skowron" doi: "10.24963/ijcai.2019/77" url: "https://ijcai.org/proceedings/2019/77" pdf: "https://ijcai.org/proceedings/2019/0077.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "543-549" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Computational Social Choice" - "Agent-based and Multi-agent Systems: Voting" --- # Approval-Based Elections and Distortion of Voting Rules Grzegorz Pierczyński, Piotr Skowron *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 543-549. DOI: [10.24963/ijcai.2019/77](https://doi.org/10.24963/ijcai.2019/77) ## Abstract We consider elections where both voters and candidates can be associated with points in a metric space and voters prefer candidates that are closer to those that are farther away. It is often assumed that the optimal candidate is the one that minimizes the total distance to the voters. Yet, the voting rules often do not have access to the metric space M and only see preference rankings induced by M. Consequently, they often are incapable of selecting the optimal candidate. The distortion of a voting rule measures the worst-case loss of the quality being the result of having access only to preference rankings. We extend the idea of distortion to approval-based preferences. First, we compute the distortion of Approval Voting. Second, we introduce the concept of acceptability-based distortion---the main idea behind is that the optimal candidate is the one that is acceptable to most voters. We determine acceptability-distortion for a number of rules, including Plurality, Borda, k-Approval, Veto, Copeland, Ranked Pairs, the Schulze's method, and STV. ## Full text ## 1 Introduction We consider the classic election model: we are given a set of candidates, a set of voters-the voters have preferences over the candidates-and the goal is to select the winner, i.e., the candidate that is (in some sense) most preferred by the voters. The two most common ways in which the voters express their preferences is (i) by ranking the candidates from the most to the least preferred one, or (ii) by providing approval sets, i.e., subsets of candidates that they find acceptable. The collection of rankings (resp. approval sets), one for each voter, is called a ranking-based (resp. approval-based) profile. There exist a plethora of rules that define how to select the winner based on a given preference profile, and comparing these election rules is one of the fundamental questions of the social choice theory [Arrow et al., 2002]. One such approach to comparing rules, proposed by Procaccia and Rosenschein [2006], is based on the concept of distortion. Hereinafter, we explore its metric variant [Anshelevich et al., 2018]: the main idea is to assume that the voters and the candidates are represented by points in a metric space M called the issue space. The optimal candidate is the one that minimizes the sum of the distances to all the voters. However, the election rules do not have access to the metric space M itself but they only see the ranking-based profile induced by M: in this profile the voters rank the candidates by their distance to themselves, preferring the ones that are closer to those that are farther. Since the rules do not have full information about the metric space they cannot always find optimal candidates. The distortion quantifies the worstcase loss of the utility being effect of having only access to rankings. Formally, the distortion of a voting rule is the maximum, over all metric spaces, of the following ratio: the sum of the distances between the elected candidate and the voters divided by the sum of the distances between the optimal candidate and the voters. The concept of distortion is interesting, yet-in its original form-it only allows to compare ranking-based rules. In this paper we extend the distortion-based approach so that it captures approval preferences. In the first part of the paper we analyze the distortion of Approval Voting (AV), i.e., the rule that for each approval-based profile A returns the candidate that belongs to the most approval sets from A. To formally define the distortion of AV one first needs to specify, for each metric space M, what is the approval-based profile induced by M. Here, we assume that each voter is the center of a certain ball and approves all the candidates within it. We can see that each metric space induces a (possibly large) number of approval-based profiles-we obtain different profiles for different lengths of radiuses of the balls. This is different from ranking-based profiles, where (up to tie-breaking) each metric space induced exactly one profile. Thus, the distortion of AV might depend on how many candidates the voters decide to approve. Indeed, it is easy to observe that if each voter approves all the candidates, then the rule can pick any of them, which results in an arbitrarily bad distortion. On the other hand, by an easy argument we will show that for each metric space M there exists an approval-based profile A consistent with M, such that AV for A selects the optimal candidate. In other words: AV can do arbitrarily well or arbitrarily bad, depending on how many candidates the voters approve. Our first main contribution is that we fully characterize how the distortion of AV depends on the length of radiuses of approval balls. Specifically, we show that the distortion of AV is equal to 3, when the lengths of approval radiuses of the voters are all equal and such that the optimal candidate is approved by between 1/4 and 1/2 of the population of the voters (and this is the optimal distortion for the case of radiuses of equal length). The exact relation between the number of voters approving the optimal candidate and the distortion of AV is depicted in Figure 1. Figure 1: The relation between the fraction of voters approving the optimal candidate and the distortion of AV, for the case when the approval radiuses of the voters have all equal lengths. ![Image](https://ijcai.org/proceedings/2019/fulltext/77/image_000000_e07289812c7ca6a12b907e60164c487cb26ef6c8eb6fecb6b9a10f42d99909cc.png) In the second part of the paper we explore the following related idea: assume that the goal of the election rule is not to select the candidate minimizing the total distance to the voters, but rather to pick the one that is acceptable for most of them. E.g., AV perfectly implements this idea. A natural question is how good are ranking-based rules with respect to this criterion. To answer this question we introduce a new concept of acceptability-based distortion (in short, abdistortion). We assume that each metric space, apart from the points corresponding to the voters and candidates, contains acceptability balls-one for each voter (as before, each voter is the center of the corresponding ball). The optimal candidate is the one that belongs to the most acceptability balls, and the ab-distortion distortion measures the normalized difference between the numbers of balls to which the elected and the optimal candidates belong. The ab-distortion is a real number between 0 and 1, where 0 corresponds to selecting the optimal candidate and 1 is the worst possible value 1 . Among the ranking-based rules that we consider in this paper, the best (and the optimal) ab-distortion is attained by Ranked Pairs and the Schulze's method. It is an open question, whether Ranked Pairs is the only natural rule with this property. It is worth mentioning, that its ab-distortion is closely related to the size of the Smith set, so in case it is small (in particular, when the Condorcet winner exists) this rule has even better ab-distortion. We have found an interesting result for Copeland. Although in case of classic (distancebased) distortion most Condorcet rules are equally good, this is no longer the case when acceptability is the criterion we primarily care about. The ab-distortion of Copeland is equal to 1, which is the worst possible value. This rule is optimal only if the Condorcet winner exists (e.g. when the metric space is one-dimensional). The distortion of scoring rules (Plurality, Borda, Veto, k-approval) is significantly worse that that for Ranked Pairs. Another surprising result is the distortion of STV-while this rule is known to achieve a very good distance-based distortion, its ab-distortion is even worse than for Plurality (denoting the number of candidates as m, STV and Plurality achieve the ab-distortion of 2m-1 2m and m-1 m , respectively). In case of all these rules the worst-case instances were obtained in one-dimensional Euclidean metric spaces. Our results are summarized in Table 1. 1 The reader might wonder why we define the ab-distortion as a difference rather than as a ratio (as it is done for the classic definition of the distortion). Indeed, we first used the ratios in our definition, but then it was very easy to construct instances where any rule had the distortion of +∞. Further, we found that these results do not really speak of the nature of the rules but rather are artifacts of the used definition. Consequently, we found that the considering the difference gives more meaningful results. Table 1: The comparison of the distortion for various ranking-based rules. The results in the left column (for the distance-based distortion) are known in the literature. The results for ab-distortion are new to this paper; here, m denotes the number of the candidates and ℓ is the size of the Smith set. | Rule | Distance-based distortion ([1;+∞]) | Ab-distortion ([0; 1]) | |----------------|--------------------------------------|----------------------------------| | Each rule | ≥ 3 | ≥ ℓ-1 ℓ for ℓ > 1 ≥ 12 otherwise | | Plurality | 2m - 1 | m-1 m | | Borda | 2m - 1 | m-1 m | | k-approval | ∞ | 1 | | Veto | ∞ | 1 | | Copeland | 5 | 1 | | Ranked Pairs | 5 | ℓ-1 ℓ for ℓ > 1 12 otherwise | | Schulze's Rule | 5 | ℓ-1 ℓ for ℓ > 1 12 otherwise | | STV | O(ln m) | 2m-1-1 2m-1 | The motivation for studying the two types of distortion (the distance-based and the approval-based distortion) is the following. Very often it is not clear what should be the goal of an election. It has been argued that there is a tension between the desire to select a candidate judged "as highly as possible" and supported "by as many people as possible". Ideally, one would like to have a rule that works well with respect to the both criteria. Our goal is to examine whether such an ideal rule exists, and if not, to assess the tension between the two criteria, focusing on the well-known rules. Due to space constraints we redelegate all the proofs to the full version of the paper [Pierczynski and Skowron, 2019]. ## 2 Preliminaries For each set S by 2S and Π(S) we denote, respectively, the powerset of S and the set of all linear orders over S. By S∁ we denote the complement set of S, and by S∗-the set of all vectors with the elements from S. For each two sets S1, S2 and a function f : S1 → 2S2 by Rf : S2 → 2S1 we denote the function defined as follows: For convenience we assume that [-∞;+∞] denotes the affinely extended real number system (the set of real numbers R with additional symbols +∞, and -∞). We take the following convention for arithmetical operations: Expressions 0 0 , ±∞ ±∞ , 0 · ±∞ and ±∞ - ±∞ are undefined. ## 2.1 Our Metric Model An election instance is a tuple (N,C, d, λ), where N = {1, 2, . . . , n} is the set of voters, C = {c1, c2, . . . , cm}, is the set of candidates, d: (N ∪ C)2 → R is a distance function (d allows us to view the candidates and the voters as points in a pseudo-metric space), and λ: N → 2C is an acceptability function, mapping each voter i ∈ N to a subset of candidates that i finds acceptable. We assume that λ is nonempty 2 , i.e., for each i ∈ N, λ(i) ̸= ∅, and that is local consistent-for each i ∈ N, ca, cb ∈ C, if ca ∈ λ(i) and d(i, cb) ≤ d(i, ca), then cb ∈ λ(i). Often we will also require that λ satisfies a stronger condition, called global consistency-for each i, j ∈ N, ca, cb ∈ C, if ca ∈ λ(i) and d(j, cb) ≤ d(i, ca), then cb ∈ λ(j). Intuitively, local-consistency means that for each voter i ∈ N we can associate λ(i) with a ball with the center at the point of this voter. A voter i ∈ N considers a candidate cj to be acceptable for him, cj ∈ λ(i), if and only if cj lies within the ball. Such a ball will be further called the acceptability ball and its radius-the acceptability radius. Then, global consistency can be interpreted as an assumption that all the acceptability radiuses have equal lengths. We will sometimes slightly abuse the notation: by saying that an instance satisfies local (global) consistency we will mean that the acceptability function in the instance satisfies the respective property. By I, we denote the set of all election instances. Since issue spaces are often argued to be Euclidean spaces with small numbers of dimensions, we additionally introduce the following notation: for each k ∈ N let Ek denote the set of all the instances where the elements of N and C are associated with points from Rk , and d is the Euclidean distance. ## 2.2 Preference Representation In most cases, it is difficult for the voters to explicitly position themselves in the issue space, and often even the space itself is unknown. Therefore, we will consider voting rules that take as inputs preference profiles induced by election instances, instead of instances themselves. We consider two classic approaches to represent preferences. 2 We add this assumption to avoid pathological situations where some voters like no candidates. This way we avoid having somehow degenerated hard cases for the distortion. Ranking-based profiles. A ranking-based profile induced by an election instance I = (N,C, d, λ) is the function ≻I : N → Π(C), mapping each voter to a linear order over C such that for all i ∈ N and all ca, cb ∈ C if d(i, ca) < d(i, cb) then ca ≻i cb. 3 For each voter i ∈ N, the relation ≻I(i) (for convenience also denoted as ≻i, whenever the instance is clear from the context) is called the preference order of i. If for some cx, cy ∈ C it holds that cx ≻i cy, we say that i prefers cx over cy. Approval-based profiles. An approval-based profile of an election instance I = (N,C, d, λ) is a locally consistent acceptability function A: N → 2C . We say that a candidate cx is approved by a voter i ∈ N if cx ∈ A(i). We will say that the approval-based profile is truthful if for all i ∈ N it holds that A(i) = λ(i). Additional notation. Let us introduce some additional useful notation. Let P : C ∗ → N be a function mapping vectors of distinct candidates to sets of voters as follows: For convenience, we will write P(ci1 , ci2 , ..., cik ) instead of P((ci1 , ci2 , ..., cik ))4 . Note that for all ca, cb ∈ C we have P (ca, cb) ∩ P (cb, ca) = ∅ and P (ca, cb) ∪ P (cb, ca) = N. We say that ca dominates cb if |P(ca, cb)| > n2 and that ca weakly dominates cb if |P(ca, cb)| ≥ n2 . We say that a candidate cx Pareto-dominates a candidate cy if there holds that |P(cx, cy)| = n. A candidate cy is Pareto-dominated if there exists a candidate cx who Pareto-dominates cy. ## 2.3 Definitions of Voting Rules An election rule (also referred to as a voting rule) is a function mapping each preference profile to a set of tied winners. We distinguish ranking-based rules-taking ranking-based profiles as arguments, and approval-based rules-defined analogously. Among approval-based rules, we focus on Approval Voting (AV)-the rule that selects those candidates that are approved by most voters. In the remaining part of this subsection we recall definitions of the ranking-based rules that we study in this paper. Positional scoring rules. For a given vector ⃗s = (α1, α2, . . . , αm), the scoring rule implemented by ⃗s works as follows. A candidate ca gets αi points from each voter j who puts ca in the ith position in ≻j . The rule elects the candidates whose total number of points, collected from all the voters, is maximal. Some well-known scoring rules which we will study in the further part of this work are the following: 3 We allow for ties in the metric space-the voter ranks the equidistant candidates using a fixed tie-breaking rule. Allowing for ties gives somehow simpler hard-instances, yet they can be tweaked so that they do not depend on tie-breaking at all. Also, the positive results (the upper-bounds) work even for adversarial tie-breaking. 4 It will always be clear from the context whether in the inscription P(x), x should be interpreted as a vector or as a candidate. Copeland. The Copeland rule elects candidates cw who dominate at least as many candidates as any other candidate. More formally, a candidate cw is a winner if and only if: Ranked Pairs. Ranked Pairs works as follows: first we sort the pairs of candidates (ci, cj) in the descending order of the values |P(ci, cj)|. Then, we construct a graph G where the vertices correspond to the candidates. We start with the graph with no edges; then we iterate over the sorted list of pairsfor each pair (ci, cj) we add an edge from ci to cj unless there is already a path from cj to ci in G. If such a path exists, we simply skip this pair. Clearly, the so-constructed graph G is acyclic. The source nodes of G are the winners. Later on we will also use the well-known fact that Ranked Pairs always elects a subset of the Smith set. Recall that the Smith set of an instance I is the subset S of the candidates such that (i) every candidate from S dominates each candidate outside of S, and (ii) no non-empty proper subset of S satisfies the previous condition. The Schulze's Rule. The Schulze's rule works as follows: let the beatpath of length k from candidate ca to cb be a sequence of candidates cx1 , cx2 , . . . , cxk-1 such that ca dominates cx1 , cxk-1 dominates cb and for each i ∈ {1, . . . , k - 2}, cxi dominates cxi+1 . Let the strength of the beatpath be the minimum of values P(ca, cx1 ), P(cx1 , cx2 ), . . . , P(cxk-1 , cb). By p[ca, cb] we denote the maximum of strengths of all beatpaths from ca to cb. Candidate cw is the winner if and only if for each candidate c it holds that p[cw, c] ≥ p[c, cw]. STV. Single Transferable Vote (STV) works iteratively as follows: if there is only one candidate, elect this candidate. Otherwise, eliminate the candidate who has the least points according to the Plurality rule and repeat the algorithm. Note that the aforementioned rules are irresolute by definition. Further, we did not specify the tie-breaking rule used when sorting edges in Ranked Pairs and when eliminating candidates in STV. We will make all these rules resolute by using the lexicographical tie-breaking rule, denoted by ≻lex. ## 2.4 Measuring the Quality of Social Choice In this section we formalize the concept of distortion that, on the intuitive level, we already introduced in Section 1. Distance-based approach. A natural idea to relate the quality of a candidate c with the sum of the distances from this candidate to all the voters. The lower this sum is, the higher the quality. Following this intuition, the distortion of a voting rule ϕ in instance I ∈ I, is defined as follows (below, co denotes the optimal candidate for I): where PI is the set of profiles induced by I (either ranking or approval, depending on the domain of ϕ). D(ϕ) ∈ [1; +∞]. This approach can be applied to any rule discussed so far. For ranking-based rules it has already been widely studied in the literature, hence in the further part we will focus on AV. Acceptability-based approach. Now we present an alternative way to measure the quality of candidates, based on the acceptability function. Intuitively, the more voters a candidate c is acceptable for, the higher his quality. Besides, we would like the maximal possible quality not to depend on the number of voters. Therefore, we define the acceptabilitybased distortion (ab-distortion, in short) of a voting rule ϕ in instance I ∈ I as the following expression: where PI is the set of profiles induced by I (either rankingbased or approval-based, depending on the domain of ϕ). Clearly, the ab-distortion is always a value from [0; 1]. By definition, in truthful profiles Approval Voting always elects an optimal candidate in terms of ab-distortion. Thus, we will consider our acceptability-based measure only for rankingbased rules. Let E be a mathematical expression that can depend on some characteristics of an instance (e.g., on the number of candidates, or the size of the Smith set). We say that the (acceptability-based) distortion of a voting rule ϕ is E, if for each instance I, DI(ϕ) ≤ E and for each E and each ϵ > 0 there is a instance I with DI (ϕ) > E - ϵ. ## 3 Distortion of Approval Voting In this section we analyze the distance-based distortion of Approval Voting (AV)-hereinafter we denote AV by ϕAV . We start by showing that in the most general case, if we do not make any additional assumptions about the acceptability function, the distortion of AV can be arbitrarily bad. Proposition 3.1. There exists an instance I ∈ E1 such that DI (ϕAV ) = +∞. This result is rather pessimistic. However, one could ask a somehow related question-does there for each instance I always exist an approval profile consistent with I that would result in a good distortion? In contrast to Proposition 3.1, here the answer is much more positive. Proposition 3.2. For each instance I ∈ I, there is an approval based profile A of I such that ϕAV is the optimal candidate (minimizing the total distance to voters). Propositions 3.1 and 3.2 show that for each metric space M there always exists two approval profiles A1,A2 locally consistent with M such that for A1 AV selects the worst possible candidate, and for A2 it selects the optimal one-since A1 and A2 are both consistent with M, they only differ in the sizes of approval balls. This formally shows that the performance of AV strongly depends on how many candidates the voters decide to approve. Below, we provide our main result of this section-assuming that all the acceptability balls have radiuses of the same length, we show the exact relation between this length of approval radiuses and the distance-based distortion of AV. In particular, we show that the best approval radius is such that the optimal candidate is approved by between 1/4 and 1/2 fraction of all the voters. Definition 3.3. An approval-based profile A induced by an instance I is p-efficient for p ∈ [0; 1] if RA(co) = pn. In words, a profile is p-efficient if the number of voters who approve the optimal candidate is the p fraction of n. Theorem 3.4. For each globally consistent p-efficient instance I, we have the following results: The above function is depicted in Figure 1. All these bounds are attained for instances in E1 . The detailed construction is provided in the full version of the paper [Pierczynski and Skowron, 2019]. Finally, for completeness, we give an analogue of Proposition 3.2, but for globally-consistent instances. Proposition 3.5. For each instance I ∈ I, there exists an approval profile A globally consistent with I, such that ## 4 AB-Distortion of Ranking Rules Recall that the ab-distortion of a voting rule is a value from [0; 1], proportional to the difference between the number of voters accepting the optimal candidate and the number of voters accepting the winner. By definition, this value equals 0 for AV (provided the approval profile is truthful). In this section we analyze the ab-distortion of ranking-based rules. We start by proving the lower bound on the ab-distortion of any ranking-based voting rule. Theorem 4.1. For each ℓ ∈ N and each ranking-based rule ϕ, there exists a globally consistent instance I such that: 1. the size of the Smith set in the ranking-based profile induced by I equals ℓ, In the subsequent part of this section we will assess the distortion of specific voting rules, specifically looking for one that meets the lower-bound from Theorem 4.1. ## 4.1 Condorcet Rules We start by looking at Condorcet consistent rules. Note that the lower bound found in Theorem 4.1 is promising, as it depends on the size of the Smith set. In particular, if ℓ = 1, this bound equals 1 2 . Our first goal is to determine, whether Condorcet rules meet this bound. Theorem 4.2. Let I be an instance with a Condorcet winner and ϕ be a Condorcet consistent rule. Then, DI(ϕ) ≤ 12 . This bound is achievable for a globally consistent I ∈ E2 . Proof. Let cw be the winner and co be the optimal candidate. Since we assumed that the Condorcet candidate exists in I, we have that cw weakly dominates co. Then, we have: Thus, |P(co, cw)| ≤ n2 . Further, we have that: This completes the first part of the proof. For the hard instance, we have four candidates cx, cy, cz, and cc, placed in points (3, 3), (0, 0), (6, 0), and (3, 2), respectively. There are n2 - 1 voters in (3, 4) with preferences cx ≻ cc ≻ cy, cz, approving only cx, n4 + 1 voters in (1, 0) with rankings cy ≻ cc ≻ cx, cz, approving only cy, and n4 voters in (5, 0) with preferences cz ≻ cc ≻ cx, cy, approving only cz. Candidate cc is the Condorcet winner and the optimal candidate is cx. The distortion of each rule electing cc is 12 - 1n , which is arbitrarily close to 12 . From the above theorem, we get that for ℓ = 1 each Condorcet election method matches the lower bound from Theorem 4.1. Now we will prove that there exists election rules, namely Ranked Pairs and the Schulze's rule, which match this bound for each ℓ. Theorem 4.3. The ab-distortion of Ranked Pairs and of the Schulze's rule is equal to: - ℓ-1 ℓ for ℓ ≥ 2, - 1 2 for ℓ = 1 where ℓ is the size of the Smith set of considered instance. As we can see, there is no rule with a better ab-distortion than Ranked Pairs. Yet, it is not a feature of all the Condorcet methods. As we will see, even for the well-known Copeland rule, the possible pessimistic distortion is much worse. Theorem 4.4. The ab-distortion of Copeland is 1. This bound is achieved for globally consistent instances in E2 . ## 4.2 Scoring Rules Let us now move to positional scoring rules. Here, we obtain significantly worse results than for Ranked Pairs and the Schulze's rule. A general tight upper bound for the abdistortion of any scoring rule remains an open problem. Below we provide bounds that are tight for certain specific scoring rules. Theorem 4.5. For a scoring rule ϕ defined by vector ⃗s = (s1, . . . , sm) the ab-distortion of ϕ satisfies: The bound obtained in Theorem 4.5 is not tight in general. For example, for Plurality we have a tighter estimation. Theorem 4.6. The ab-distortion of Plurality is m-1 m . This bound is achieved for globally consistent instances in E1 . Yet, for a number of scoring rules the bound from Theorem 4.5 is tight. Below, we give some sufficient conditions. Proposition 4.7. The bound from Theorem 4.5 is tight for each scoring rule satisfying the following conditions: even for globally consistent instances in E1 . Theorem 4.5 combined with Theorem 4.7 imply the abdistortion for a number of scoring rules. Corollary 4.8. There exists a globally consistent instance I ∈ E1 , for which: 1. the ab-distortion of k-approval is 1 1+0 = 1, 2. the ab-distortion of Veto is 1 1+0 = 1, 3. the ab-distortion of Borda is m-1 m-1+1 = m-1 m . ## 4.3 Iterative Rules All scoring rules that we considered have poor ab-distortion, and in particular are considerably worse than Condorcet rules (especially for instances with Condorcet winners). Interestingly, STV in terms of acceptability, behaves worse even than Plurality. This is somehow surprising since for distance-based distortion, STV is better than any positional scoring rules, and only slightly worse than Condorcet rules. The above bound is tight even in one-dimensional Euclidean spaces. It is also tight if we restrict ourselves to global consistent instances. There, the hard instances that we found use (m - 2)-dimensional Euclidean space. Proposition 4.10. The bound from Theorem 4.9 is tight for locally consistent instances from E1 and globally consistent instances from Em-2 . ## 5 RelatedWork The spatial model of preferences is quite popular in the social choice and political science literature. For example seminal works studying spacial models we refer the reader to [Davis and Hinich, 1966; Plott, 1967; Enelow and Hinich, 1984; Enelow and Hinich, 1990; McKelvey and Ordeshook, 1990; Merrill and Grofman, 1999; Schofield, 2007]. The concept of distortion was first introduced by Procaccia and Rosenschein [2006]. In their work they did not assume the existence of a metric space, but rather used a generic cardinal utility model (where the voters can have arbitrarily utilities for candidates). This model was later studied by Caragiannis and Procaccia [2011] and Boutilier et al. [2015]. Recently, Benad´e et al. [2019] introduced the concept of distortion for social welfare functions, i.e., functions mapping voters preferences to rankings over candidates, and Benad´e et al. [2017] adapted and used the concept of distortion in the context of participatory budgeting to evaluate different methods of preference elicitation. The studies of the distortion in the metric model were initiated by Anshelevich et al. [2018], and then continued by Anshelevich and Postl [2017], Feldman et al. [2016], Goel et al. [2017], and Gross et al. [2017]. The analysis of the distortion forms a part of a broader trend in social choice stemming from the utilitarian perspective. For classic works in welfare economics that discuss the utilitarian approach we refer the reader to the article of Ng [1997] and the book of Roemer [1998]. This approach has also recently received a lot of attention from the computer science community. Apart from the papers that directly study the concept of distortion that we discussed before, examples include the works of Filos-Ratsikas and Miltersen [2013], Branzei et al. [2013], and Chakrabarty and Swamy [2014]. ## 6 Conclusion In this paper we have extended the concept of distortion of voting rules to approval-based preferences. This extension allows to compare rules that take different types of input: approval sets and rankings over the candidates. To the best of our knowledge, only very few formal methods are known that allow for such a comparison. We are aware of only one work that formally relates these two models: Laslier and Sanver [2010] proved that in the strong Nash equilibrium Approval Voting selects the Condorcet winner, if such exists. There are also some works that model elections in which voters cast both rankings and (consistent) approval ballots [Camps et al., 2014]. Our contribution is twofold. First, we have determined the distortion of Approval Voting, and explained how this distortion depends on voters' approval sets. Specifically, we have shown that the socially best outcome is obtained when the voters approve not too many and not too few candidates. If the lengths of voters' acceptability radiuses are all equal, the best distortion is obtained when the approval sets are such that between 14 and 1 2 of the voters approve the optimal candidate. Second, we have defined a new concept of acceptabilitybased distortion (ab-distortion). Here, we assume that the voters have certain acceptability thresholds; the ab-distortion of a given rule ϕ measures how many voters (in the worstcase) would be satisfied from the outcomes of ϕ. We have determined the ab-distortion for a number of election rules (our results are summarized in Table 1), and reached the following conclusions. The analysis of the classic and the acceptability-based distortions both suggest that Condorcet rules perform better than scoring and iterative ones. Further, our acceptability-based approach suggests that Ranked Pairs and the Schulze's rule are particularly good rules, in particular significantly outperforming the Copeland's rule. Thus, our study recommends Ranked Pairs or the Schulze's method as a rule that robustly performs well for both criteria (total distance, and acceptability). The question whether Ranked Pairs is the only natural ranking-based rule performing well for both criteria is open. Approval Voting is also a very good rule that can be considered an appealing alternative to Ranked Pairs, provided the sizes of the approval sets of the voters are appropriate. ## Acknowledgements The authors were supported by the Foundation for Polish Science within the Homing programme (Project title: "Normative Comparison of Multiwinner Election Rules"). ## References 1. [Anshelevich and Postl, 2017] E. Anshelevich and J. Postl. Randomized social choice functions under metric prefer- ences. Journal of Artificial Intelligence Research, 58:797- 827, 2017. 2. [Anshelevich et al., 2018] E. Anshelevich, O. Bhardwaj, E. Elkind, J. Postl, and P. Skowron. Approximating op- timal social choice under metric preferences. Artificial In- telligence, 264:27-51, 2018. 3. [Arrow et al., 2002] K. Arrow, A. Sen, and K. Suzumura, ed- itors. Handbook of Social Choice and Welfare, Volume 1. Elsevier, 2002. 4. [Benadé et al., 2017] G. Benadé, S. Nath, A. Procaccia, and N. Shah. Preference elicitation for participatory budgeting. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 376-382, 2017. 5. [Benadé et al., 2019] G. Benadé, A. Procaccia, and M. Qiao. Low-distortion social welfare functions. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019. To appear. 6. [Boutilier et al., 2015] C. Boutilier, I. Caragiannis, S. Haber, T. Lu, A. D. Procaccia, and O. Sheffet. Optimal social choice functions: A utilitarian view. Artificial Intelligence, 227:190-213, 2015. 7. [Branzei et al., 2013] S. Branzei, I. Caragiannis, J. Morgen- stern, and A. Procaccia. How bad is selfish voting? In Proceedings of the 27th AAAI Conference on Artificial In- telligence, pages 138-144, 2013. 8. [Camps et al., 2014] R. Camps, X. Mora, and L. Saumell. Social choice rules driven by propositional logic. Annals of Mathematics and Artificial Intelligence, 70(3):279-312, 2014. 9. [Caragiannis and Procaccia, 2011] I. Caragiannis and A. D. Procaccia. Voting almost maximizes social welfare despite limited communication. Artificial Intelligence, 175(9- 10):1655-1671, 2011. 10. [Chakrabarty and Swamy, 2014] D. Chakrabarty and C. Swamy. Welfare maximization and truthfulness in mechanism design with ordinal preferences. In Proceed- ings of the 5th Conference on Innovations in Theoretical Computer Science, pages 105-120, 2014. 11. [Davis and Hinich, 1966] O. A. Davis and M. J. Hinich. A mathematical model of preference formation in a demo- cratic society. In J. L. Bernd, editor, Mathematical Appli- cations in Political Science II, pages 175-208. Southern Methodist University Press, 1966. 12. [Enelow and Hinich, 1984] J. M. Enelow and M. J. Hinich. The spatial theory of voting: An introduction. CUP Archive, 1984. 13. [Enelow and Hinich, 1990] J. M. Enelow and M. J. Hinich. Advances in the spatial theory of voting. Cambridge Uni- versity Press, 1990. 14. [Feldman et al., 2016] M. Feldman, A. Fiat, and I. Golomb. On voting and facility location. In Proceedings of the 17th ACM Conference on Economics and Computation, pages 269-286, 2016. 15. [Filos-Ratsikas and Miltersen, 2013] A. Filos-Ratsikas and P. B. Miltersen. Truthful approximations to range vot- ing. In Proceedings of the 10th International Conference on Web and Internet Economics, pages 175-188, 2013. 16. [Goel et al., 2017] A. Goel, A. K. Krishnaswamy, and K. Munagala. Metric distortion of social choice rules: Lower bounds and fairness properties. In Proceedings of the 18th ACM Conference on Economics and Computa- tion, pages 287-304, 2017. 17. [Gross et al., 2017] S. Gross, E. Anshelevich, and L. Xia. Vote until two of you agree: Mechanisms with small dis- tortion and sample complexity. In Proceedings of the 31st Conference on Artificial Intelligence, pages 544-550, 2017. 18. [Laslier and Sanver, 2010] J.-F. Laslier and M. Sanver. The Basic Approval Voting Game, pages 153-163. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. 19. [McKelvey and Ordeshook, 1990] R. D. McKelvey and P. C Ordeshook. A decade of experimental research on spatial models of elections and committees. Advances in the spa- tial theory of voting, pages 99-144, 1990. 20. [Merrill and Grofman, 1999] S. Merrill and B. Grofman. A unified theory of voting: Directional and proximity spatial models. Cambridge University Press, 1999. 21. [Ng, 1997] Y.-K. Ng. A case for happiness, cardinalism, and interpersonal comparability. The Economic Journal, 107(445):1848-1858, 1997. 22. [Pierczynski and Skowron, 2019] G. Pierczynski and P. Skowron. Approval-based elections and distortion of voting rules. Technical Report arXiv:1901.06709 [cs.GT, arXiv.org, 2019. 23. [Plott, 1967] C. R. Plott. A notion of equilibrium and its pos- sibility under majority rule. The American Economic Re- view, 57(4):787-806, 1967. 24. [Procaccia and Rosenschein, 2006] A. D. Procaccia and J. S. Rosenschein. The distortion of cardinal preferences in vot- ing. In Proceedings of the 10th International Workshop on Cooperative Information Agents (CIA-2006), pages 317- 331, 2006. 25. [Roemer, 1998] J. E. Roemer. Theories of distributive jus- tice. Harvard University Press, 1998. 26. [Schofield, 2007] N. Schofield. The spatial model of politics. Routledge, 2007.