Evaluating Committees for Representative Democracies: the Distortion and Beyond

1 Introduction

One of the fundamental goals that the (computational) social choice theory sets to itself is to evolve a set of tools that could help societies to improve the processes of making collective decisions. This includes developing frameworks that allow to formally reason about and to meaningfully compare election rules. Typically, such a comparison is done in a context-free manner-the criteria used for comparing rules are generic, not tailored to a specific scenario where the election rule is to be used (cf., the axiomatic approach [Arrow et al., 2002]). While such an approach has a natural appeal of generality, various applications differ substantially, and a rule which is considered perfect in one situation may be inappropriate in another one. This motivates comparing rules based on context-specific assumptions. In this paper we focus on indirect democracies-we study a framework for comparing rules for selecting committees (e.g., parliaments, representative boards, etc.), assuming that the elected committee will make a series of decisions on behalf of the society.

Our model can be informally described as follows (the formal definitions are provided in Sections 2 and 3). There are three types of objects: voters, candidates, and issues-an issue is an alternative with two possible outcomes: "yes" or "no". Each voter and each candidate has her preferred outcome for each issue-these preferred outcomes induce the preferences of the voters over the candidates-a voter examines how similar is her opinion on the issues to the opinions of the candidates, and ranks them accordingly 1 . Further, the preferred outcomes can be used to measure and to compare the qualities of committees: for a given committee W we can check what kind of decisions would be made by W if elected (we assume that the elected committee uses the majority rule to decide about each issue) and compare these decision with the voters' preferred outcomes. A committee whose decisions coincides with most preferred outcomes is called optimal.

∗Contact Author

Finding an optimal committee would be possible if we knew all the elements of the model. Yet, often the preferred outcomes of the voters (or even the issue space itself) remain unknown during elections, and winning committees are elected based on the preferences of the voters over the candidates. Since the voters' preference rankings only reflect the similarities between theirs and the candidates' preferred outcomes for the issues, it is not surprising that an election rule might not be able to choose an optimal committee since it has only access to partial information. In this paper we quantify this effect and we ask what is the loss of utility that a committee election rule can cause due to not knowing the issue space.

Our methodology and contribution are the following:

1. In Section 4 we assess the worst-case loss of utility of multiwinner rules-by an analogy to the literature [Procaccia and Rosenschein, 2006] we call this worst-case loss of utility the distortion. We prove that the distortion of any ordinal voting rule R equals to infinity. Thus, in the most general case, it is inevitable that an error made when selecting a committee based on the preferences of the voters over the candidates, can be arbitrarily bad.
2. Due to the aforementioned negative result, we further focus our theoretical analysis on a specific domain restriction inspired by works from political science on polarized division of ideologies. Under this domain restriction we assume that the societies are centered around two poles, i.e., that there are only two types of preferred outcomes that the voters and the candidates can have. It is quite sur-

1 The candidates' preferences are usually publicly known-e.g., politicians talk about their preferences over various issues during election campaigns. The voters know their own preferences and so they are able to construct their preferences over the candidates.

prising that already under this seemingly strong assumption the distortion of many known rules, such as SNTV, k-Borda, the Chamberlin-Courant rule, and the Monroe rule can be arbitrary bad once the parameters, such as the number of voters or candidates, are large. On the other hand, in this case the distortion of STV and k-Copeland are constant. In fact, the k-Copeland rule always selects an optimal committee when the societies are polarized.

1. Our negative results show certain limitations of the worstcase analysis when applied to the voting committee model. Consequently, the major (and the main) part of our study aims at understanding the average behavior of voting rules. To this end, we performed extensive computer simulations for several natural distribution of individuals' preferred outcomes. In particular, our distributions generalize and extend the polarized model, as described above.

If we judge the rules from the majoritarian perspective (a view that focuses solely on maximizing the total voters' satisfaction), our results show a dichotomy. In the two most extreme cases: (i) when a society is strongly polarized, or (ii) when the opinions with respect to various issues are uniformly and independently distributed in a society, multiwinner rules based on the Condorcet criterion, such as k-Copeland, are the best: this is confirmed both by our experiments and by the theoretical results. On the other hand, when the number of predominant views in a society is larger than two, then proportional rules such as STV select committees whose majoritarian decisions particularly well reflect the opinions of the voters (this is somehow unexpected, given the majoritarian approach to judging the rules). If we use a more proportional metric to assess qualities of voting rules (a metric that puts more emphasis on reducing the societal inequality), then the proportional rules such as STV are always superior.

Related Work

There is a vast literature that considers committees making series of decisions [Young, 1995; Feddersen and Pesendorfer, 1997; Feddersen and Pesendorfer, 1998; Magdon-Ismail and Xia, 2018]-this literature dates back to the 18th century, when Condorcet formulated his famous Jury Theorem. However, all these aforementioned works use the assumption that there exists a ground truth, and so, that each decision made by a committee is either objectively correct or wrong. Our model is different-here, the quality of a committee can be judged only with respect to the voters-a good committee is the one that well-represents (subjective) preferences of the society.

Scenarios where a committee makes a sequence of binary decisions were also considered in the context of Colonel Blotto games [Laslier and Picard, 2002], storable votes [Casella, 2005; Casella, 2011], and voting in multiattribute domains [Brams et al., 1998; Lacy and Niou, 2000; Xia et al., 2008; Xia et al., 2010]. None of these works, however, considers an indirect process of decision-making.

The voting committee model that we use in this paper was first introduced by Skowron [Skowron, 2015]; there, the author argued for the optimality of certain committee election rules, but under strong assumptions on the form of the voters' utility functions. The definition of the concept of the distortion in the voting committee model and its analysis is new to this paper.

Our model is closely related to the one by Koriyama et al. [Koriyama et al., 2013]. The difference is that Koriyama et al. consider the apportionment problem, i.e., a scenario, where the task is to divide a fixed number of parliamentary seats among political parties according to how the population votes-in our model, on the other hand, the voters vote for individual candidates rather than for political parties.

Recently, the ideas behind proxy voting [Miller, 1969; Green-Armytage, 2015; Cohensius et al., 2017] and liquid democracy [Behrens et al., 2014; Brill and Talmon, 2018; Kahng et al., 2018] have attained a considerable attention in the literature. These works consider scenarios where a sequence of decisions on certain issues is to be made through a referendum, but the voters are allowed to transfer their voting rights regarding selected issues to others; thus, for each issue an implicit committee is elected that (for this particular issue) votes on behalf of the whole population of the voters.

Our results allow to formulate conclusions saying how suitable are certain voting rules for electing representative committees. Thus, our research contributes to the vast literature that aims at comparing multi-winner election rules. For an overview of this literature we refer the reader to the paper by Elkind et al. [Elkind et al., 2017], and to the recent book chapter by Faliszewski et al. [Faliszewski et al., 2017].

The main measure that we use to compare voting rules in this paper is inspired by the popular concept of distortion (see, e.g., [Procaccia and Rosenschein, 2006; Caragiannis and Procaccia, 2011; Boutilier et al., 2015; Caragiannis et al., 2017; Anshelevich et al., 2018; Goel et al., 2017; Pierczynski and Skowron, 2019]). In these works, however, the unknown primitives are the utilities of the voters over the candidates, and the goal is to compare voting rules that do not have access to the utilities but only to the rankings or approval ballots that are consistent with these utilities. We study a more complex model where the utilities of the voters from the committees are inferred from the decisions made by these committees.

2 Preliminaries

For each n ∈ N by [n] we denote the set {1, . . . , n}. For a set X we use Sk(X) to denote the set of all k-element subsets of X; by S(X) we denote the set of nonempty subsets of X, i.e., S(X) = ⋃k∈[|X|] Sk(X). For a logical expression P the term 1P means 1 if P is true and 0 otherwise.

2.1 Elections, Preferences

Given a set of candidates C we call the elements of Sk(C) size-k committees (or simply committees, when k is clear). A multiwinner election (or, in short, an election) is a triplet E = (C, V, k), where C = {c1, . . . , cm} is a set of candidates, V = {v1, . . . , vn} is a set of voters and k is an integer representing the intended size of the committee to be elected. We will typically use n and m to represent the numbers of voters and candidates, respectively. We call the elements of C ∪ V (the voters and the candidates) individuals. For a voter vi ∈ V by ≻i we denote the preference relation of vi, which is a linear order over C; for example, if vi prefers a over b, then we write a ≻i b. By posi(c) we denote the position of candidate c in the vi's preference ranking; for instance, posi(c) = 1 if c is vi's most favorite candidate and posi(c) = m when c is the least preferred candidate for vi.

A voting rule R is a function that for each election E = (C, V, k) returns a nonempty set of size-k committees, i.e., R(E) ∈ S(Sk(C)). Throughout the paper we use the parallel-universes tie-breaking mechanism that allows us to obtain all committees that could possibly be built by means of the selected voting rules (see [Conitzer et al., 2009]).

2.2 Overview of Selected Voting Rules

Below we provide formal definitions of the voting rules that we study in this paper. First, though, let us recall the definitions of the Plurality and Borda scores. The Plurality score that a voter vi assigns to a candidate c, denoted by scP (vi, c), equals 1 if posi(c) = 1 and 0, otherwise. The Borda score that c gets from vi is scB(vi, c) = m- posi(c). Given an election E = (C, V, k), the Plurality score of a candidate c is the sum of the Plurality scores that c garners from all the voters, scP (c) = ∑vi∈V scP (vi, c). Analogously we define the Borda score: scB(c) = ∑vi∈V scB(vi, c).

Single nontransferable vote (SNTV). The SNTV rule returns k candidates with the highest Plurality scores, i.e., candidates that are ranked first by the most voters.

• k-Borda. It picks k candidates with highest Borda scores.
• k-Copeland. The Copeland score of a candidate c is the number of candidates c′ ̸= c such that c is preferred to c′ by a majority of voters. The k-Copeland rule selects k candidates with the highest Copeland scores.

Single transferable vote (STV). Let q = ⌊ nk ⌋ . STV is an iterative procedure that works as follows. In each iteration we check if there is a candidate with the Plurality score of at least q. If such a candidate exists, call it c, then we:

1. add c to the committee;
2. delete some q voters that rank c first, and
3. delete c from the rankings of the voters, i.e., the candidates that are ranked below c move one position up.

On the other hand, if all the candidates have their Plurality scores lower than q, then we delete the candidate with the lowest Plurality score from each voter's ranking.

The procedure repeats until k candidates are selected.

Chamberlin-Courant (CC). We call a function φ : V → C k-assignment if |φ(V )| = |{φ(v) | v ∈ V }| ≤ k. CC computes the assignment φ that maximizes ∑vi∈V scB(vi, φ(vi)) and returns φ(V ) as the winning committee. If |φ(V )| < k, then CC picks k-|φ(V )| arbitrary candidates to fill the missing slots in the committee.

Intuitively, a k-assignment specifies for each voter vi, who is vi's representative in the elected committee; CC finds the committee and the corresponding assignment so that the sum of the voters' happiness from their representatives (measured through Borda scores) is maximized.

Monroe. It works as CC, but puts an additional constraint on assignment functions-each candidate from the set φ(V ) must represent roughly the same number of voters, i.e., |φ-1 (c)| ∈ {⌊ nk ⌋ , ⌈ nk ⌉} for each c ∈ φ(V ). As for CC, Monroe first computes the (balanced) assignment Φ that maximizes ∑vi∈V scB(vi, φ(vi)), and then returns the committee implicitly induced by φ.

Greedy-Monroe. This is an iterative procedure. It starts with two empty sets V0 and W0. In the i-th iteration it chooses a pair-a candidate ci ∈ C \ Wi-1 and subset of voters V ′ ⊆ V \ Vi-1 with |V ′ | ∈ {⌊ nk ⌋ , ⌈ nk ⌉}-that maximizes ∑vj∈V ′ scB(vj, ci). The rule updates the two sets, Wi = Wi-1 ∪ {ci} and Vi = Vi-1 ∪ V ′ . It stops after k iterations and returns Wk as the winning committee.

3 The Voting Committee Model

An indirect election is a quadruple (C, V, I, k), where C and V are sets of candidates and voters, respectively, k is a size of a committee to be elected, and I = (I1, . . . , Ip) is a vector of p issues. Each individual i ∈ V ∪ C is represented as a p-dimensional binary vector (i[j])j∈[p], indicating her preferences over the issues-for each j ∈ [p] we set i[j] = 1 if individual i is for issue Ij and i[j] = 0 if i is against issue Ij. In indirect elections, similarly as in elections, the voters have preferences over the candidates. These preferences are consistent with the preferences of individuals over the issues-a voter v ranks the candidates according to the number of issues for which their preferences coincide. Formally,

for each vi ∈ V and c, c′ ∈ C we have that c ≻i c′ only if:

(if for a given voter v there are multiple candidates with the same numbers of issues on which they agree with v, the voter ranks them in an arbitrary order; intuitively, the voter breaks ties between these candidates according to the preferences over issues of secondary importance, which are not part of the model, according to her personal taste, or simply randomly). Consequently, each instance of indirect elections can be interpreted as a simple election, and so the voting rules from Section 2.2 naturally apply to indirect elections.

To assess the quality of a committee W, we assume that W uses the majority voting to make the decisions regarding the issues. Formally, we define the decision vector of W as a binary vector (W[j])j∈[p], where W[j] = 1 if |{c ∈ W | c[j] = 1}| > k2 and W[j] = 0 if |{c ∈ W | c[j] = 0}| > k2 . In order to avoid tie-breaking issues, hereinafter we assume that the size of the committee k is odd. Naturally, since the voters have preferences over the issues, the decision made by the committee W has an influence on voters' satisfaction. Here, we use perhaps the simplest measure, and define the utility of the voter vi from a committee W as the number of issues for which the committee's decision coincide with vi's preferences: ui(W) = ∑pj=1 1W[j]=vi[j]. The notion of the utility of an individual voter gives us a basis to define the utility of the whole set of voters; we use the following measures:

1. In the utilitarian approach we define the voters' utility from a committee W simply as: u(W) = ∑ni=1 ui(W).

1. In the proportional approach, we use an aggregation based on Nash Welfare: u(W) = ∑ni=1 log(1+ui(W)). Using the logarithm in the aggregation function is grounded in the broad literature on fair allocation (see, e.g. [Conitzer et al., 2017; Caragiannis et al., 2016]); intuitively, this metric puts less weight to the total satisfaction of the voters, and more to how the satisfaction is distributed among the voters (promoting reducing the societal inequality).

We will also use the concept of disutility of the voter, dui(W)-it is defined as the number of issues on which the voter disagree with the decisions of the committee. Analogously, for each committee W we define the utilitarian disutility of W as du(W) = ∑ni=1 dui(W). We will not be using proportional aggregations of the disutilities. 2

4 The Distortion: theWorst-Case Approach

In this section we employ the worst-case approach, formalized through the concept of distortion. Informally speaking, the distortion of a rule quantifies the worst-case loss of the utility being the effect of the rule not having access to all the information-here, our rules do not have access to information about issues, but rather choose the winning committees based on the preferences of the voters over the candidates.

This section focuses on the utilitarian distortion; even for this simple aggregation our results are mainly negative. Their primary purpose is to illustrate the limitations of the worstcase analysis when applied to the voting committee model.

Definition 1 (Distortion). The satisfaction-based distortion of a voting rule R wrt. a set of indirect elections E is:

where OPT(E) is a committee with the maximal utility in E, i.e., OPT(E) ∈ argmaxW∈Sk(C)u(W). Analogously, we define the dissatisfaction-based distortion of R as:

In the above definition we take the convention that 0/0 = 1. In Definition 1 the distortion is parameterized with a set of instances; this allows us, e.g., to explain how the distortion depends on certain structural properties of voters' preferences. Usually, the considered set of instances will be clear from the context-in such cases we will write distsat R (resp., distdis R ) as an abbreviation for distsat {R,E} (resp., distdis {R,E} ).

For k = 1 the dissatisfaction-based distortion boils down to the well-known concept of the metric distortion [Anshelevich et al., 2018] in pseudo-metric spaces where the voters and candidates are represented as vertices of hypercubes.

4.1 Universal Hardness of Distortion

We start our analysis by providing a negative result which says that in general, the distortion of any voting rule is arbitrarily bad. On the one hand, this result illustrates the possible inefficiency of the process of making decisions through a representative body, specifically if the committee is elected based on the voters' preferences over the candidates. On the other hand, it justifies introducing additional assumptions to the model-in the subsequent sections we will consider certain restricted (but realistic) structures of voters' preferences.

2 We are not aware of any formula for aggregating disutilities that would share strong fairness properties of the Nash Welfare.

Theorem 1 (Universal Hardness Theorem). For each voting rule R and for each committee size k ≥ 3:

1. the satisfaction-based distortion of R equals to∞.
2. the dissatisfaction-based distortion of R equals to∞.
3. there exists an instance E where du(W)/du(OPT(E)) = ∞, and u(OPT(E))/u(W) ≥ (k+1)/2 - ε, for each ε > 0.

Proof. We provide the proof of (3) - the construction for (1) is analogous. Statement (2) follows from (3).

Fix a rule R, a committee size k, and m = k + k+1 2 . Assume that for a single voter, with the preference ranking c1 ≻ c2, . . . , cm, the rule picks the committee W = {ci1 , . . . , cik }. Fix a constant L and an instance E with p = L · k+1 2 issues. We have one voter represented as the vector of p ones, and

the following three classes of candidates:

1. C1: in this class we have k-1 2 candidates, each represented as the vector of p ones;
2. C2: this class contains k+1 2 candidates. The i-th candidate is represented as a vector of (i - 1)L zeros, followed by L ones, followed by ( k+1 2 - i)L zeros.
3. C3: here we have k+1 2 candidates, each represented by L ones followed by ( k+1 2 -1)L zeros.

Each candidate in C2 ∪C3 is equally liked by the voter (their preferences coincide for L issues). Now, we slightly perturb the instance, to enforce that the voter will use a particular tiebreaking for the candidates in C2∪C3. For that, for each candidate in C2 ∪C3, we change at most k +1 zeros to ones. We do that in a way that the candidates fromC3 will be put in the voter's preference ranking in the positions from {i1, . . . , ik}. We give the names to the candidates so that the candidates ranked in the positions from {i1, . . . , ik} are ci1 , . . . , cik , and the remaining candidates have names from {c1, . . . , cm}\W.

For this instance, the rule picks a committee containing C3. This committee will make the decision "one" for at most L+ k+1 issues. On the other hand, the committee C1∪C2 would make the decision "one" for all p issues. Thus, we have that:

4.2 Distortion for Polarized Society

We next study a model where the society is centered around two points in the issue space. Formally, we say that an indirect election (C, V, I, k) is centered around two poles if there exists two binary p-dimensional vectors, p1 and p2, such that each individual from V ∪ C is represented as either p1 or p2. When determining the distortion of a rule R for two poles, we assume that the set of instances E from Definition 1 consists of all elections that are centered around two poles.

Due to space constraints, here we only present our results very briefly. We summarize them in the following theorem:

Theorem 2. For societies centered around two poles, the satisfaction-based distortion:

1. of the k-Copeland rule equals to 1.
2. of STV is 3, but for large n/k and k it approaches 1.
3. of SNTV and CC is Θ(n), of k-Borda is Θ(m/k), of Monroe is Ω(n) even if k = 3, and of greedy-Monroe is Ω(k).

5 Beyond theWorst-Case Analysis

Our theoretical results illuminate particular limitations of the worst-case analysis when applied to the voting committee model. Already Theorem 1 provides a certain barrier to deriving meaningful conclusions that would allow to reason about voting rules and that would apply more broadly. Further, even under a seemingly strong assumption of the society being completely polarized the distortion of some known voting rules is arbitrarily bad in limit. This motivates us to extend our analysis beyond the worst-case and to assess the average qualities of the studied rules for certain natural distributions.

In this section we consider a probabilistic model-we assume that the preferences of the individuals are drawn randomly from a given distribution. For each voting rule R we run a series of experiments in order to assess the qualities of the outcomes produced by R for elections drawn from several different distributions. In our experiments we focussed on instances with n = 500 voters, m = 100 candidates, and where the total number of issues is p = 100. We consider the following distributions of individuals' preferences:

Impartial Culture. For each individual i and issue Ij the i's preferred outcome on Ij is drawn uniformly at random.

(ξ1, ξ2)-Polarized Balanced Society ((ξ1, ξ2)-PBS). Here we assume that the individuals come from two equal-size groups-each containing 250 voters and 50 candidates. For each group we choose a vector of preferred outcomes, which we call the center of the group. Specifically, the center of the first group is the vector with all 'ones'; for the second group this is the vector of all 'zeros'. For each individual i from group t ∈ {1, 2} we sample a value ξ(i) uniformly at random from [ξt, 1]. Intuitively, ξ(i) describes how close is i (with respect to her preferences) to the center of his or her group. Formally, for each issue Ij the probability that i's preferred outcome for Ij is consistent with the center of her group equals to ξ(i).

(ξ1, ξ2)-Polarized Imbalanced Society ((ξ1, ξ2)-PIS). This model is similar to (ξ1, ξ2)-PBS; the difference is that the two groups do not have equal sizes. There are 150 voters and 50 candidates in the first group; the second group contains 350 voters and 50 candidates.

(t, ξ)-Poles. In the (t, ξ)-Poles distribution the society is divided into t groups, the sizes of which are derived as follows: We first sample t integers, x1, x2, . . . , xt, i.i.d., uniformly at random from [0, 1]. Next, for each i ∈ [t] we set the size of the i-th group-both the number of candidates and the number of voters-to be proportional to xi. The total number of voters and candidates must be equal to 500 and 100,

• (a) utilitarian aggregation
• (b) proportional aggregation

Figure 1: Comparison of voting rules for elections drawn from the (ξ1, ξ2)-PBS for ξ1 = ξ2 and k = 31. The plots depict the average (normalized) utility of committees returned by different voting rules.

respectively; we round up or down the number of individuals within each group when necessary. Second, we sample t central points for the groups-each central point is a pdimensional binary vector whose coordinates were sampled independently, uniformly at random from {0, 1}. Finally, for each group z ∈ [t] and each individual i from the z-th group we derive the preferred outcomes of i as follows. First, we sampled ξ(i) uniformly at random from [ξ, 1]. For each issue Ij the individual i will have a preferred outcome consistent with the central point of its group (i.e., equal to the j-th coordinate of the central point) with probability equal to ξ(i).

In our simulations we covered a wide range of possible values of the parameters of the distributions (we give details below). For each distribution with a fixed set of parameters we ran 500 experiments; each experiment was performed as follows. We drew an indirect election and computed the winning committees according to different voting rules. For each such a committee W we computed the vector of decisions made by W, compared these decisions to the preferred outcomes of the voters, and calculated the utility value u(W). We normalized these values, dividing them by n · p-for the utilitarian aggregation, or by n · log(1+p)-for the proportional aggregation (the best possible utility that would be obtained if each voter were perfectly satisfied with every decision made by the committee; an alternative approach would be to divide u(W) by the utility of the optimal committee-cf., Definition 1but finding such a committee is NP-hard), and we computed the average of these normalized utilities over the 500 runs.

For the sake of clarity, in all the figures in this section we plot only the results for STV, k-Copeland, and SNTV. The plots for greedy Monroe are almost indistinguishable from the plots for STV; similarly, the plots for k-Borda are almost the same as the plots for k-Copeland.

The results of our simulations for (ξ1, ξ2)-PBS for ξ1 = ξ2 and k = 31 (recall that we use an odd size of the committee to avoid tie-breaking in the decision-making process) are depicted in Figure 1. The results for (ξ1, ξ2)-PBS with fixed ξ2 = 0.85 and ξ1 ranging from 0.5 to 1, and for (ξ1, ξ2)- PIS with ξ1 = ξ2 lead to the same conclusion, so we do not present the corresponding plots. Further, for all these distributions we also run the experiments for k = 11, and obtained results consistent with the ones presented in Figure 1. We also do not include plots for the Impartial Culture model since the results obtained in this model were similar to those obtained

(a) utilitarian aggr., t = 3

(b) utilitarian aggr., t = 5

(c) proportional aggr., t = 3

(d) proportional aggr., t = 5

• (a) utilitarian aggregation

(b) proportional aggregation

Figure 3: Average qualities of voting rules for elections drawn from (ξ1, ξ2)-PBS (ξ2 = 0.85) for the binary distribution of weights.

for (ξ1, ξ2)-PBS when values of ξ1 and ξ2 were close to 1/2. The results of our experiments performed for the (t, ξ)-Poles distribution are summarized in Figure 2. Due to space constraints, we only present the results for t ∈ {3, 5} and k = 31, but we also performed experiments for t = 10 and k = 11; the results are consistent with those presented.

Our interpretations of the results are as follows: For the utilitarian aggregation we observe a dichotomy. In the two most extreme cases: (i) when the society is strongly polarized, or (ii) when the opinions in the society are uniformly distributed with no correlations (the Impartial Culture model), k-Copeland is the best, and performs better than the proportional rules; this conclusion is consistent with our theoretical results (see Theorem 2). SNTV is the worst out of the considered rules. For the proportional aggregation of the utilities the proportional rules, specifically STV, perform better, even when the society is strongly polarized. On the other hand, for societies with more than two predominant opinions, or when the predominant opinions are less extreme, the proportional rules perform better, even for the utilitarian aggregation of the voters' satisfactions; this effect is yet magnified when we look at the proportional aggregation of the utilities.

Finally, since in real-life it is often the case that the voters consider some issues more important than the others, we extended our experimental setting in order to capture this intuition. For each voter i and each issue Ij we assume that there is a weight wi,j that measures how important voter i perceives issue Ij. The definition of the utility that a voter i assigns to a committee W changes accordingly (cf., Section 3):

We consider three different distributions of weights:

Uniform. For each voter and each issue the weight is sampled uniformly at random from [0, 1].

Exponential. We sample the weight a voter assigns to an issue from the exponential distribution with λ = 1.

Binary. For each voter we randomly pick 10% of issues that she considers important, and for these issues we set the weight to 1. The weights for the remaining issues are 0.

The results of our simulations for (ξ1, ξ2)-PBS for the binary distribution of weights for k = 31 are depicted in Figure 3we do not include plots for the remaining distributions, as the results are very similar. Our main conclusion is that adding weights does not change the overall picture-the rules that performed well (resp., badly) in settings without weights still perform well (resp., badly) in the same settings with weights (independently of the distribution from which the weights are drawn).

6 Conclusion

We studied a model, where the voters and the candidates have preferences over a certain set of issues. The preferences of the voters over the candidates are inducted by the individuals' preferred outcomes for the issues. We assumed that the issue space is unknown and the selection of the winning committee is purely based on the preferences of the voters over the candidates. We measured the quality of committees by looking at the majoritarian decisions made by them and by comparing those decisions with the voters' preferred outcomes.

In the most general case, the distortion of any voting rule can be arbitrarily bad. This motivated us to look at special cases inspired by works from political science, where the voters' preferences have certain structure. If the society is extremely polarized or when there is no predominant view in the society, then k-Copeland is the best according to the majoritarian perspective. If we look at the proportional aggregation of voters' utilities, or in the intermediate cases (when there are more predominant views in the society, or when the predominant views are not extreme)-both for the proportional and for the majoritarian aggregation-STV performs much better.

Acknowledgements

The authors were supported by the Foundation for Polish Science within the Homing programme (Project title: Normative Comparison of Multiwinner Election Rules). We are very grateful to IJCAI reviewers for their thorough remarks.