A Quantitative Analysis of Multi-Winner Rules

1 Introduction

A multi-winner rule is a voting method for selecting a fixedsize subset of alternatives, a so-called committee. More formally, it is a function that given a set of objects, preferences of a population of voters over these objects, and an integer k, returns a subset of exactly k objects. Ideally, a multi-winner rule should select the "best" committee, but the suitability of a chosen committee strongly depends on the specific context. For instance, if voters are experts (e.g., judges in a sport competition) whose preferences reflect their estimates of the objective qualities of candidates, then the goal is typically to pick k individually best candidates, e.g., those candidates who receive the highest scores from judges. Intuitively and somewhat simplified, in this and similar scenarios the quality of candidates can be assessed separately, and a suitable multi-winner rule should pick the k best-rated ones. On the contrary, if the voters are citizens and the goal is to choose locations for k public facilities (say, hospitals), then our goal is very different: assessing the candidates separately can result in building all the facilities in one densely populated area; yet, it is preferable to spread them in order to ensure that as many citizens as possible have access to some facility in their vicinity.

These two examples illustrate two very different goals of multi-winner rules, which can be informally described as follows [Faliszewski et al., 2017]: Diversity requires that a rule should select a committee which represents as many voters as possible; this translates to choosing a hospital distribution that covers as many citizens as possible. Individual excellence suggests picking those candidates that individually receive the highest total support from the voters; this translates to selecting a group of best contestants in the previous example. However, many real-life scenarios do not fall clearly into one of the two categories. For example, rankings provided by a search engine should list the most relevant websites but also provide every user at least one helpful link. In such cases, a mechanism designer would be interested in choosing a rule that guarantees some degree of diversity and individual excellence at the same time, putting more emphasis on either of them depending on the particular context.

Consequently, to properly match rules with specific applications, it is essential to understand to which degree committees chosen by established multi-winner rules are diverse or individually excellent. In this paper, we (1) develop a set of tools that allows a mechanism designer to better understand the nature of multi-winner rules and to assess the tradeoffs with respect to diversity and individual excellence, and (2) provide a classification that clarifies the behavior of wellknown rules with respect to the two criteria. We focus on the case where voters express their preferences by providing subsets of approved candidates (the approval-based model), yet our approach is applicable to other preference models as well.

1.1 Methodology and Contribution

In our approach, we choose two approval-based multi-winner rules, Chamberlin-Courant (CC) and Multi-winner Approval Voting (AV), as distinctive representatives of the principles of diversity and individual excellence, respectively. We measure how close certain rules are to AV and CC-we measure this distance by using the concept of the worst-case approximation. Thus, by investigating how well certain rules approximate AV or CC, we provide guarantees of how individually excellent or diverse these rules are; such guarantees can be viewed as quantitative properties of voting rules. This approach is fundamentally different from the traditional axiomatic approach, which is qualitative: a voting rule can either satisfy a property (axiom) or not. Our approach provides much more fine-grained information and allows us to estimate the degree to which a certain property is satisfied. With these methods, we understand voting rules as a compromise between different (often contradictory) goals.

There are several reasons for our choice of AV and CC: First, both AV and CC are well-known, well understood rules. Second, due to their different nature they are a good choice for a two-dimensional evaluation. Third, they can be characterized by properties that capture individual excellence and diversity [Lackner and Skowron, 2018a]. Finally, they embody the ideas of utility-maximization and egalitarian maximization (as in the classic works on collective utility functions), which in turn capture the spirit of excellence and diversity.

Our main contribution lies in developing a new method for evaluating multi-winner rules. Specifically, we provide two types of analyses for a selection of prominent multi-winner rules. In Section 3, we derive theoretical upper bounds on how much an outcome of the considered multi-winner rules can differ from the outcomes of CC and AV. We call these bounds CC-guarantee and AV-guarantee. These can be interpreted as worst-case (over all possible preference profiles) guarantees for diversity and individual excellence. Our guarantees are given as functions of the committee size k and return values between 0 and 1. Intuitively, a higher CCguarantee (resp. AV-guarantee) indicates a better performance in terms of diversity (resp. individual excellence), where 1 denotes that the rule performs as good as CC (resp., AV). Table 1 summarizes our results.

In Section 4, we complement the worst-case analysis from Section 3 with an experimental study yielding approximation ratios for actual data sets. In extensive experiments we estimate how on average the outcomes of the considered rules differ from the outcomes of CC and AV.

Our most important findings can be summarized as follows. Among the studied voting rules, Proportional Approval Voting (PAV) achieves the best compromise between AV and CC; this can be observed both from theoretical and experimental results. The sequential rules seq-PAV and Phragm´en's rule, however, achieve almost the same quality while being polynomial-time computable (in contrast to PAV, which is computationally intractable [Skowron et al., 2016; Aziz et al., 2015]). Also the 2-Geometric rule achieves a very good compromise, but is slightly leaning towards diversity. More generally, we show that the p-Geometric rule spans the whole spectrum from AV to CC, controlled through the parameter p. Hence, by adjusting the parameter p, one can obtain any desired compromise between AV and CC.

Finally, we show that while proportional rules tend to achieve a good compromise between individual excellence (AV) and diversity (CC), proportionality does not yield an optimal compromise: we find a non-proportional rule that outperforms any proportional rule with respect to both their AVand CC-guarantee.

1.2 RelatedWork

Our work is based on the idea of approximation algorithms, where computationally hard problems are solved by polynomial-time algorithms that can guarantee a certain (imperfect) solution quality. In our paper, we study how well popular multi-winner rules can approximate other, archetypical rules. The work of Brˆanzei et al. [2013] on the dynamic price of anarchy can be viewed in such a perspective: to which degree can the outcome of voting rules based on sincere preferences be approximated by the same voting rules with insincere preference (obtained via "selfish" best-response dynamics)? In a similar vein, Oren and Lucier [2014] study the performance of online social choice procedures in comparison to optimal (offline) procedures. Anshelevich et al. [2018] approximate an optimal social choice in a metric model with voting rules using rankings as input, i.e., using limited information.

The normative study of multi-winner election rules typically focuses on axiomatic analysis. For approval-based rules a number of axioms describing proportionality have been recently identified and explored, in particular in the context of the rules that we study in this paper [Aziz et al., 2017a; S´anchez-Fern´andez et al., 2017; Brill et al., 2017; Skowron et al., 2017; Aziz et al., 2018; Lackner and Skowron, 2018a]. For a survey on properties of multi-winner rules, with the focus on the ideas of individual excellence, diversity, and proportionality, we refer the reader to a survey by Faliszewski et al. [2017].

Another approach to understanding the nature of different multi-winner rules is to analyze how these rules behave on certain subdomains of preferences, where their behavior is much easier to interpret, e.g., on two-dimensional geometric preferences [Elkind et al., 2017], on party-list profiles [Brill et al., 2018], or on single-peaked and single-crossing domains [Aziz et al., 2017b]. Other approaches include quantifying regret and distortion in utilitarian models [Caragiannis et al., 2017], assessing their robustness [Bredereck et al., 2017], and evaluating them based on data collected from surveys [Rapoport et al., 1988; Van der Straeten et al., 2018].

2 Preliminaries

For each t ∈ N, we let [t] = {1, . . . , t}. For a set X, we write S(X) to denote the powerset of X, i.e., the set of all subsets of X. By Sk(X) we denote the set of all k-element subsets of X. Let C = {c1, . . . , cm} and N = {1, . . . , n} be sets of m candidates and n voters, respectively. Voters reveal their preferences by indicating which candidates they like: by A(i) ⊆ C we denote the approval set of voter i (that is, the set of candidates that i approves of). For a candidate c ∈ C, by N(c) ⊆ N we denote the set of voters who approve c. Given a set of candidates X ⊆ C, we write N(X) to denote the set of voters who approve at least one candidate in X, that is N(X) = {i ∈ N : X ∩ A(i) ̸= ∅}. We call the collection of approval sets A = (A(1),A(2), . . . ,A(n)), one per each voter, an approval profile. We use the symbol A to represent the set of all possible approval profiles.

We call the elements of Sk(C) size-k committees. Throughout the paper, we use the symbol k to represent the desired size of the committee to be elected. An approvalbased committee rule (in short, an ABC rule) is a function R that takes as an input an approval profile and an integer k ∈ N (the required committee size), and returns a set of size-k committees. Below, we recall the definitions of ABC rules which are the objects of our study.

Multi-winner Approval Voting (AV). This rule selects k candidates which are approved by most voters. More formally, for a profile A the AV-score of committee W is defined as scav(A,W) = ∑c∈W |N(c)|, and AV selects committees W that maximize scav(A,W).

Approval Chamberlin-Courant (CC). For a profile Awe define the CC-score of a committee W as sccc(A,W) = ∑i∈N min (1, |A(i) ∩ W|) = |N(W)|; CC outputs committees W that maximize sccc(A,W). In words, CC aims at finding a committee W such that as many voters as possible have their representatives in W (a representative of a voter is a candidate she approves of). The CC rule was first mentioned by Thiele [1895], and then introduced in a more general context by Chamberlin and Courant [1983].

Proportional Approval Voting (PAV). This rule [Thiele, 1895] selects committees with the highest PAV-scores, defined as scpav(A, W) = ∑i∈N H (|W ∩ A(i)|), where H(t) is the t-th harmonic number, i.e., H(t) = ∑ti=1 1/i. By using the harmonic function H(·), voters who already have more representatives in the committee get less voting power than those with fewer representatives; this leads to strong proportionality guarantees [Aziz et al., 2017a].

p-Geometric. This rule [Skowron et al., 2016] is defined analogously to PAV but uses an exponentially decreasing function instead of H(·). Formally, for a given parameter p ≥ 1 the p-geometric rule assigns to each committee W the score scp-geom(A, W ) = ∑i∈N ∑|A(i)∩W | j=1 1 pj , and picks the committees with the highest scores. Note that the 1-geometric rule is simply AV.

Sequential CC/PAV/p-Geometric. For each rule R ∈ {CC, AV, PAV, p-geometric}, we define its sequential variant, denoted as seq-R, as follows. We start with an empty solution W = ∅ and in each of the k consecutive steps we add to W a candidate c that maximizes scR(A,W ∪ {c}), i.e., the candidate that improves the committee's score most. We break ties lexicographically.

Monroe. Monroe's approval-based rule [1995], similarly to CC, aims at maximizing the number of voters who are represented in the elected committee. The difference is that Monroe additionally imposes that each committee member should represent roughly the same number of voters. Formally, a Monroe assignment of the voters to a committee W is a function φ: N → W such that each candidate c ∈ W is assigned roughly the same number of voters, i.e., that ⌊n/k⌋ ≤ |φ-1 (c)| ≤ ⌈n/k⌉. Let Φ(W) be the set of all possible Monroe assignments to W. The Monroe-score of W is defined as scMon(A,W) = maxφ∈Φ(W) ∑i∈N |A(i)∩{φ(i)}|; the rule returns all committees W that maximize scMon(A,W).

Phragm´en's Sequential Rule (seq-Phragm´en). This rule [Phragm´en, 1894; Brill et al., 2017] can be understood as a load distribution procedure. Each selected committee member c is associated with one unit of load that needs to be distributed among those voters who approve c. The rule proceeds in k steps. In each step it selects one candidate and distributes its load as follows: let ℓj(i - 1) denote the total load assigned to voter j just before the i-th step. In the i-th step the rule selects a candidate c and finds a load distribution {xj : j ∈ N} that satisfies the following three conditions: (1) xj > 0 implies that voter j approves c, (2) ∑j∈N xj = 1, and (3) the maximum load assigned to a voter, maxj∈N(ℓj(i - 1) + xj), is minimized. The new total load assigned to a voter j ∈ N after the i-th step is ℓj (i) = ℓj (i - 1) + xj .

3 Worst-Case Guarantees

In this section we analyze the multi-winner rules from Section 2 with respect to how well they perform in terms of diversity and individual excellence. In our study we use the established idea of approximation in a novel way: by estimating how well a given rule R approximates CC (resp., AV), we quantify how R performs with respect to diversity (resp., individual excellence). This differs from the typical use of the idea of approximation in the following aspects: (1) We do not seek new algorithms approximating a given objective function as well as possible, but rather analyze how well the existing known rules approximate given functions (even if it is apparent that better and simpler approximation algorithms exist, these algorithms might not share other important properties of the considered rules). (2) We are not approximating computationally hard rules with rules easier to compute. On the contrary, we will be even investigating how computationally hard rules (such as PAV, Monroe, etc.) approximate the algorithmically trivial AV rule.

Definition 1. Recall that for a profile A, scav(A,W) and sccc(A,W) denote the AV-score and CC-score of committee W, respectively. The AV-guarantee of an ABC rule R is a function κav : N → [0, 1] that takes as input an integer k, representing the size of the committee, and is defined as:

Analogously, the CC-guarantee of R is defined by

The AV and CC-guarantees can be viewed as quantitative properties of multi-winner rules. In the remaining part of this section we evaluate the previously defined rules against their AV- and CC-guarantees. Clearly, the AV-guarantee of Approval Voting and the CC-guarantee of the ChamberlinCourant rule are the constant-one function. We start by establishing the AV-guarantee of CC and vice versa. Due to space constraints, most proofs had to be omitted, but can be found in a longer version [Lackner and Skowron, 2018b].

Proposition 1. The CC-guarantee of AV is 1/k.

Proposition 2. The AV-guarantee of CC and seq-CC is 1/k.

Propositions 1 and 2 give a baseline for our further analysis. In particular, we would expect that "good" rules implementing a tradeoff between diversity and individual excellence should have AV and CC-guarantees better than 1/k.

We note that the CC-guarantee of seq-CC is 1 - (1 - 1/k)k (which approaches 1 - 1/e ≈ 0.63 for large k). This is the result of the fact that seq-CC is a (1- (1- 1/k)k )- approximation algorithm for CC [Lu and Boutilier, 2011].

Let us turn our attention to the Monroe rule, which is often considered a proportional rule (e.g., it satisfies proportional justified representation [S´anchez-Fern´andez et al., 2017]). Hence, one could expect that this rule offers a good compromise between AV and CC. Perhaps surprisingly, this is not the case: Monroe does not offer a better AV-guarantee than CC.

Proposition 3. The AV-guarantee of Monroe is 1/k, its CCguarantee is between 1 2 and 12 + 1 k-1 .

Let us now move to multi-winner voting systems offering asymptotically better guarantees than Monroe. As we will see, the examination of such rules requires a more complex combinatorial analysis. We start with PAV:

Theorem 1. The AV-guarantee of PAV is between 1 2+√k and 2 √k ; its CC-guarantee between 1 2 and 12 + 1 4k-2 .

Proof. To give a flavor of the proof techniques used in this paper, we show that the AV-guarantee of PAV is at least equal to 1 2+√k . Consider an approval profile A and a PAV-winning committee Wpav; let ¯n = |N(Wpav)| denote the number of voters who approve some member of Wpav. For each i ∈ N we set wi = |A(i)∩Wpav|. Let Wav be a committee with the highest AV-score. W.l.o.g., we can assume that Wav ̸= Wpav. Now, consider a candidate c ∈ Wav \ Wpav with the highest AV-score, and let nc = |N(c)| denote the number of voters who approve c. If we replace a candidate c′ ∈ Wpav with c, the PAV-score of Wpav will change by:

We know that for each c′ ∈ W we have ∆(c, c′ ) ≤ 0, thus k ∑i∈N(c) 1 wi+1 - ¯n ≤ 0 and ∑i∈N(c) 1 wi+1 ≤ ¯nk . We now use the inequality between the harmonic and arithmetic mean to obtain:

This can be transformed to:

Now, let us consider two cases. If ¯n ≤ nc√k, then we observe that:

On the other hand, if ¯n ≥ nc√k, then:

For sequential PAV we can prove an AV-guarantee qualitatively similar to the one for PAV. Concerning its CCguarantee, however, the gap between the lower and upper bounds is large; finding a more accurate estimate remains an interesting open question.

The following theorem states guarantees for the pgeometric rule. Let W(·) denote the Lambert W function, a function that increases asymptotically slower than log.

Theorem 3. The AV-guarantee of the p-geometric rule is between

The guarantees of Theorem 3 are visualized in Figure 1. We can see that p-geometric rules, for p ∈ [1,∞), form a spectrum connecting AV and CC (with p → 1 we approach AV and with p → ∞ we approach CC): by adjusting the parameter p one can control the tradeoff between the diversity and individual excellence.

Finally, we consider seq-Phragm´en, also a rule aimed at achieving proportional representation. It achieves guarantees similar to PAV.

Theorem 4. The AV-guarantee of seq-Phragm´en is between 1 5√k+1 and 2 ⌊√k⌋ - 1k ; its CC-guarantee is between 12 and 12 + 1 4k-2 .

Let us conclude Section 3 with an investigation on how proportionality relates to diversity and individual excellence. In an initial stage of this study we conjectured that proportionality can be characterized as a certain compromise between diversity and individual excellence. However, as we will argue below, proportionality should be rather viewed as a third, independent objective. Indeed, we will construct an ABC rule that is strictly better than any proportional rules with regard to both its AV- and CC-guarantee.

For each α ∈ [0, 1] we define α-CC-AV as a linear combination of CC and AV. For an approval-based profile A, αCC-AV first computes a size-⌈αk⌉ committee W1 that maximizes sccc(A,W1), and a size-⌊(1 - α)k⌋ committee W2 that maximizes scav(A,W2); then, the rule returns committee W = W1 ∪ W2.

Proposition 4. The CC-guarantee of α-CC-AV is at least α; its AV-guarantee is at least 1 - α - 1/k.

Let us now examine what AV- and CC-guarantees a proportional rule can achieve. We consider a very weak definition of proportionality, called lower quota [Balinski and Young, 1982]. Lower quota applies only to party-list profiles: approval profiles A in which for all voters i, j ∈ N it holds that either A(i) = A(j) or A(i) ∩ A(j) = emptyset; identical voters belong to "same party". Lower quota guarantees each group N ′ ⊆ N to receive at least min (∣∣⋂i∈N ′ A(i)∣∣ , ⌊ k|N ′ | |N| ⌋) representatives in any win-

ning committee, i.e., they receive a fair proportion of the committee seats (rounded down) as long as they have sufficient joint candidates. Lower quota is strictly weaker than proportionality axioms typically used for ABC rules (such as extended and proportional justified representation [S´anchezFern´andez et al., 2017; Aziz et al., 2017a]).

Proposition 5. The AV-guarantee of a rule that satisfies lower quota is at most 2 ⌊√k⌋ - 1k , its CC-guarantee is at most 34 + 3 8k-4 .

These bounds yield that α-CC-AV for α = 0.76 achieves a better AV- and CC-guarantee for all k ≥ 81. In particular, the AV-guarantee of α-CC-AV is superior: it guarantees a constant fraction of the optimal AV score. We conclude that proportional rules can achieve a desirable compromise between diversity and individual excellence (e.g., PAV), but this compromise is not optimal (as we have just seen) and not all proportional rules achieve good AV-guarantees (Monroe performs no better than CC).

4 Average Guarantees: An Experimental Analysis

To complement the theoretical analysis of Section 3, we have run experiments that aim at assessing AV-ratios and CC-ratios achieved by several voting rules. These two ratios are perinstance analogues of AV- and CC-guarantee and are defined as follows: Given an ABC rule R and a profile A, the AVratio for R(A, k) is defined as:

the CC-ratio is defined analogously. In the following experiments, we have calculated the AV- and CC-ratios for realworld and randomly generated profiles and compared them for different voting rules.

We have used two data sets: profiles obtained from preflib. org [Mattei and Walsh, 2013] and profiles generated via a uniform distribution. We restricted our attention to profiles where both the AV-ratio of CC and the CC-ratio of AV is at most 0.9. This excludes profiles where an (almost) perfect compromise between AV and CC exists. The uniform dataset consists of 500 profiles with 20 candidates and 50 voters, each. Voters' approval sets are of size 2-5 (chosen uniformly at random); the approval sets of a given size are also chosen uniformly at random. Experiments for the uniform dataset use a committee size of k = 5.

As preflib.org does not offer approval-based datasets, we extracted approval profiles from ranked ballots as follows: for each ranked profile and i ∈ {1, . . . , k - 1}, we generated an approval profile assuming that voters approve all candidates that are ranked in the top i positions. As before, we excluded profiles that allowed an almost perfect compromise between AV and CC. For the preflib dataset we considered k ∈ {3, . . . , 7}, obtaining a total number of 243 instances.

We considered the following ABC rules: AV, CC, seq-CC, PAV, seq-PAV, seq-Phragm´en, Monroe, and the 1.5-, 2-, and 5-Geometric rule. Our results are displayed as boxplots in Figure 2 for the preflib dataset; results for the random data set are largely similar. The top and bottom of boxes represent first and third quantiles, the middle red bar shows the median. The dashed intervals (whiskers) show the range of all values, i.e., the minimum and maximumAV- /CC-ratios.

The main conclusion from the experiments is that the classification obtained from worst-case analytical bounds also holds in our (average-case) experiments. PAV, seq-PAV, and seq-Phragm´en perform very well with respect to the AV-ratio, beaten only by 1.5-Geometric and AV itself. This is mirrored by our theoretical results as only PAV, seq-PAV, and seq-Phragm´en achieve a Θ(1/√k) AV-guarantee. Also the 2Geometric rule achieves comparable AV-ratios. Even better AV-ratios are achieved only by 1.5-Geometric and AV.

Considering the CC-ratio, we see almost optimal performance of seq-CC, Monroe, and 5-Geometric, and good performance of PAV, seq-PAV, seq-Phragm´en, and 2-Geometric. Minor variations within these groups seem to depend on the chosen dataset. We also observe that 5-Geometric is better than Monroe's rule and seq-CC according to both criteria.

When looking at the three Geometric rules considered here, we see the transition from AV to CC as our theoretical findings predict (cf. Figure 1): 1.5-Geometric is close to AV, whereas 5-Geometric resembles CC; 2-Geometric performs very similarly to PAV, slightly favoring diversity over individual excellence. To sum up, our experimental findings indicate that PAV is the best compromise between AV and CC among the considered rules. Yet, seq-PAV, seq-Phragm´en, and 2-Geometric achieve comparable ratios, and the former two are much cheaper to compute.

5 Conclusion and FutureWork

This work presents a new tool for assessing the level of diversity and individual excellence that multi-winner rules provide. Our results can help to understand the landscape of multi-winner rules, specifically how they behave with respect to two contradictory goals.

Our work can be extended in several directions. First, we have focused on approval-based multi-winner rules-a natural next step is to perform a similar analysis for multi-winner rules that take rankings over candidates as input. Second, we have excluded some interesting voting rules from our analysis, in particular reverse-sequential PAV [Skowron et al., 2017] and Minimax Approval Voting [Brams et al., 2007]; it is unclear how they compare to rules considered in this paper. Finally, we have chosen AV and CC as extreme notions that represent diversity and individual excellence. Another natural approach would be to take a proportional rule (such as PAV) as a standard and see how well others rules approximate it.

Acknowledgements

Martin Lackner was supported by the European Research Council (ERC) under grant number 639945 (ACCORD) and by the Austrian Science Foundation FWF, grant P31890. Piotr Skowron was supported by a Humboldt Research Fellowship for Postdoctoral Researchers and by the Foundation for Polish Science within the Homing programme (Project title: "Normative Comparison of Multiwinner Election Rules").