Egalitarian Committee Scoring Rules

1 Introduction

We study the problem of selecting a committee based on preferences of a group of agents (the voters). We assume that there is a set of candidates and each agent ranks them from the most to the least desirable one. Given such preferences and a size k of the committee to be selected, a multiwinner rule outputs a set of k candidates (the winning committee) that is meant to reflect the voters' preferences in the best possible way.

Many multiwinner rules are utilitarian in the sense that for each possible committee and each voter they provide the utility that this voter is supposed to derive from having this committee elected (typically this utility is referred to as the committee's score) and output the committee that maximizes the sum of these utilities. Indeed, this is exactly how committee scoring rules operate [Elkind et al., 2017b] (see also the approval-based setting [Aziz et al., 2017; 2015; Kilgour, 2010; Lackner and Skowron, 2018]). For example, the score that a voter associates with a committee under the k-Borda rule is the sum of the Borda scores of the committee members 1 ; the rule outputs the committee with the highest sum of such voter scores (which happens to be the committee of k candidates with the highest individual Borda scores). On the other hand, under the Chamberlin-Courant rule (β-CC) the score that a voter associates with a committee is the Borda score of the highest-ranked committee member (referred to as the representative of the voter [Chamberlin and Courant, 1983]). Again, the rule outputs the committee with the highest sum of voter scores (it is, however, NP-hard to compute [Procaccia et al., 2008; Lu and Boutilier, 2011; Betzler et al., 2013]).

1 The Borda score that a voter v assigns to candidate c is the number of candidates that v ranks below c.

The two rules mentioned above are quite different in spirit and thus applied in different situations. For example, k-Borda and similar rules are often used to choose finalists of competitions, and β-CC seems to be well-suited for choosing collective bodies, such as university senates or advisory boards (in which case the committee's diversity is particularly important; to provide multifaceted opinions, members of an advisory board should represent as varied points of view as possible; see also recent works on selecting diverse committees [Bredereck et al., 2018; Aziz and Lee, 2018]). The differences between the rules are presented graphically by Elkind et al. [2017a] (see also our experimental section).

The utilitarian approach is well-justified for choosing individually excellent candidates, but has some disadvantages for diverse committees. Indeed, if the goal is to find a committee representing a diverse set of opinions, then the level of support of various candidates may be less important than the number of truly different candidates included in the committee. For example, consider the following election (with many candidates, including a, b, and c): 60% voters have preferences : a ≻ b ≻ · · · ≻ c, 30% voters have preferences: b ≻ a ≻ · · · ≻ c, 10% voters have preferences: c ≻ · · · ≻ a ≻ b. If we were to choose a committee of size k = 2, then β-CC would output the committee {a, b}, but intuitively {a, c} would be closer to covering the views of the society (indeed, a and b are clones, in the sense that all voters rank them consecutively, whereas c is different).

To implement the idea of focusing on the number of different opinions present in the society, without regard to the number of voters with each opinion, we consider egalitarian variants of committee scoring rules. Egalitarian committee scoring rules are defined in the same way as their utilitarian counterparts, but instead of finding a committee that maximizes the sum of scores that a committee gets from individual voters, they find one that maximizes the lowest score that the 'worst-off' voter gives to the committee (in technical terms, we replace the summation operator with the minimum operator).

Our goal is to explore the nature of such egalitarian scoring rules, establish their computational and axiomatic properties, and to evaluate them experimentally. More precisely:

• We study the computational complexity (classic and parametrized) of five egalitarian rules (egalitarian variants of k-Borda, β-CC, SNTV, Bloc, and the Pessimist rule; see Section 2 for definitions). We find that the intuitions acquired for the utilitarian setting often do not work for the egalitarian case (for example, k-Borda is computationally easy, but its egalitarian variant is hard).
• We consider axiomatic properties of egalitarian rules. We discuss the consequences of the fact that egalitarian rules disregard the number of voters with any particular type of preferences (and, thus, are incompatible with properties such as the fixed majority property of Debord [1993]), and we also study their monotonicity properties.
• Following Elkind et al. [2017a], we evaluate our rules on the 2D Euclidean domain and present the results graphically. To our surprise, we find that sometimes egalitarian rules behave very similarly to utilitarian ones, defined using different scoring functions (in our experiments this happens, e.g., for k-Borda and egalitarian-Pessimist).

Egalitarian rules suffer from several drawbacks. Perhaps the most obvious ones are that they may not be as decisive as the utilitarian ones, and that they may perform poorly in the presence of outliers (or manipulators). Indeed, under egalitarian rules, a single voter has as much power as a large group of voters with the same preferences; this is both their strength and a weakness: On the one hand, we argued that it is very useful when looking for a diverse committee. On the other hand, if the committee is genuinely too small to represent the very different opinions of the society, egalitarian rules cannot distinguish between opinions with larger and smaller support.

To some extent such issues can be addressed, e.g., by using the leximin operator (instead of the minimum), or by following the approach of Elkind and Ismail [2015], who showed a continuum of options between fully utilitarian and fully egalitarian rules. We focus on the simple egalitarian setting, so that we evaluate our rules under the most basic conditions. Rules that turn out to be appealing should then be studied further. Omitted proofs are available upon request.

2 Preliminaries

For an integer m, we write [m] to denote the set {1, . . . ,m}. By R+ we mean the set of nonnegative real numbers.

An election E = (C, V ) consists of a set of candidates C = {c1, . . . , cm} and a collection of voters V = (v1, . . . , vn), where each voter ranks the candidates from the most to the least desirable one (the ranking provided by voter v is called v's preference order and is denoted as ≻v). A multiwinner rule R is a function that given an election E = (C, V ) and a committee size k, outputs a family of size-k subsets of C, i.e., the size-k committees that tie as winners of this election.

Committee Positions. Let v be some voter with preference order ≻v over candidates from the set C. For c ∈ C, we denote c's position in ≻v by posv(c) (the top-ranked candidate has position 1, the next one has position 2, and so on). For an integer t ∈ [|C|], by topv(t) we mean the set of t top-ranked candidates according to voter v. For a committee S of size k, S ⊆ C, we write posv(S) to denote the sequence (i1, . . . , ik) obtained by sorting the set {posv(c) | c ∈ S} in the increasing order; we say that posv(S) is the committee position of S in the preference order of v. We write [m]k to denote the set of all such increasing sequences of length k with elements from the set [m]. Let I = (i1, . . . , ik) and J = (j1, . . . , jk) be two committee positions. We say that I weakly dominates J, denoted I ⪰ J, if for each t ∈ [k] it holds that it ≤ jt.

Scoring Functions. A committee scoring function for elections with m candidates and committees of size k is a function fm,k : [m]k → R+ such that for each I, J ∈ [m]k, if I ⪰ J then fm,k(I) ≥ fm,k(J). In other words, a committee scoring function associates score values with committee positions, while respecting a basic monotonicity condition.

We refer to committee scoring functions for k = 1 as singlewinner scoring functions and typically denote them using Greek letters. By a slight abuse of notation, we use [m] instead of [m]1 as their domain. Two best-known examples of singlewinner scoring functions include the Borda family of functions, βm(i) = m-i, and the t-Approval functions, αt(i) = [i ≤ t] (where [·] is the Iverson bracket, which evaluates to 1 if the condition inside is true, and evaluates to 0 otherwise). The 1-Approval function is known as the Plurality scoring function.

Committee Scoring Rules. Let f = (fm,k)k≤m be a sequence of committee scoring functions, with one function for each number m of candidates and each committee size k. The committee scoring rule Rf is a multiwinner rule that, given an election E = (C, V ) and committee size k, outputs all the size-k committees S that maximize the value f-scoreE(S) = ∑v∈V f|C|,k(posv(S)). Examples of committee scoring rules with their corresponding scoring functions are in Table 1. SNTV, Bloc, and k-Borda, are polynomialtime computable: It suffices to output a committee consisting of k candidates with the highest Plurality, k-Approval, or Borda scores, respectively. The Chamberlin-Courant rule and the Pessimist rule are NP-hard (formally, the problem of deciding if there is a committee with at least a given score is NP-complete for these rules; see the works of Procaccia et al. [2008] and Lu and Boutilier [2011] for the case of the Chamberlin-Courant rule, and the work of Skowron et al. [2016] for the Pessimist rule). As opposed to all the other rules from Table 1, the Pessimist rule has not received much attention in the literature and is not a well-known rule (but the pessimistic way of comparing committees has been considered as the 'worst set extension' [Aziz et al., 2016]).

OWA-Based Rules. The committee scoring rules of Table 1 belong to the class of OWA-based rules. An OWA (ordered weighted average) operator Λ of dimension k is a sequence (λ1, . . . , λk) of numbers from R+. A committee scoring rule is OWA-based if its scoring functions are of the form:

where γm,k are single-winner scoring functions and (λm,k 1 , . . . , λm,k k ) are OWA operators. Table 1 provides the families of OWA operators used by the respective rules.

Complexity Theory. We assume familiarity with basic concepts of (parametrized) complexity theory. When we say that a multiwinner rule is polynomial-time computable, we mean that, given an election E = (C, V ) and committee size k, it is possible to check in polynomial time if a given set S, S ⊆ C and |S| ≤ k, can be extended to a winning committee (if |S| = k then it means testing if S is a winning committee). Thus, if a committee scoring rule is polynomial-time computable, then we can also compute the scores of winning committees in polynomial time. When we say that a given committee scoring rule is NP-hard, we mean that deciding if there is a committee with at least a given score is NP-hard. Analogously, we speak of multiwinner rules being computable in FPT-time or being W[1]- or W[2]-hard.

3 Egalitarian Committee Scoring Rules

We present the class of egalitarian committee scoring rules and our computational, axiomatic, and experimental results.

3.1 Definition and Examples

Committee scoring rules are utilitarian because they choose committees that maximize the sum of scores provided by the voters. Egalitarian rules aim at maximizing the welfare of the worst-off voters.

Definition 1. Let f = (fm,k)k≤m be a sequence of committee scoring rules. The egalitarian variant of the committee scoring rule Rf , denoted egalitarian-Rf , is a multiwinner rule that, given an election E = (C, V ) and committee size k, outputs all the size-k committees S that maximize the value egal-f-scoreE(S) =minv∈V f|C|,k(posv(S)).

So far, egalitarian rules have not received much attention in the literature; e.g., Aleskerov et al. [2010] introduced the egalitarian variant of the single-winner Borda rule and Betzler et al. [2013] introduced the egalitarian variant of the ChamberlinCourant rule (and of the Monroe rule [Monroe, 1995]; we discuss the egalitarian Minimax Approval Voting rule later). We focus on the egalitarian variants of the rules from Table 1.

Example 1. Let us consider election E = (C, V ) with candidate set C = {a, b, c, d, e, f, g} and with the following voters:

v1 : d≻b≻f≻a≻e≻g≻c, v5 : e≻c≻f≻d≻a≻b≻g,

v2 : d≻b≻a≻c≻e≻g≻f, v6 : e≻c≻f≻d≻a≻b≻g,

v3 : d≻b≻a≻f≻e≻c≻g, v7 : e≻c≻f≻d≻a≻b≻g,

v4 : f≻b≻e≻c≻a≻g≻d, v8 : f≻c≻e≻d≻a≻b≻g.

We consider committees of size two. Under SNTV, committee {d, e} wins because these candidates are ranked first three times each (so the committee has SNTV score 6). On the other hand, egalitarian-SNTV elects all possible committees, each with score 0 because for each committee there is some voter that ranks both its members below the first place. Committee {d, e} also wins under β-CC, but egalitarian-β-CC chooses {b, c} (the former committee has higher sum of β-CC scores, but voters v4 and v8 rank both its members on or below the third position, whereas all voters rank either b or c on the second position, so the egalitarian-β-CC score of {b, c} is higher). More tedious calculations show that k-Borda chooses committee {e, f} with score 63, whereas its egalitarian variant selects {d, f} with score 6 (voter v4 assigns k-Borda score 6 to {d, f}; every other committee receives score at most 5 from some voter). Pessimist outputs {c, e} (with score 24) while egalitarian-Pessimist gives {a, e} (these are the only two candidates that are never ranked on the two bottom positions). Finally, both Bloc and egalitarian-Bloc output {b, c}.

By αk-CC, we mean a variant of β-CC which uses kApproval scores instead of the Borda ones. If a size-k committee S has nonzero score under egalitarian-Bloc then every voter ranks at least one member of S among top k positions and, so, this committee also wins under egalitarian-αk-CC (and, indeed, under αk-CC). Somewhat surprisingly, egalitarian-Bloc can also be seen as a special case of the Minimax Approval Voting (MAV) rule of Brams et al. [2007]. Under MAV, each voter v submits a set Av of candidates that he or she approves; the MAV-score of a committee W in election E = (C, V ) is maxv∈V d(W, Av), where d(W, Av) = |W \Av|+|Av \W|; and MAV returns the size-k committees with the lowest MAVscores. Given an election E = (C, V ), egalitarian-Bloc returns the same committees as MAV would, if for each voter v we would set Av = topv(k).

3.2 Computational Complexity

In this section we analyze the computational complexity of our rules. The case of egalitarian-β-CC has already been resolved by Betzler et al. [2013]. Utilitarian OWA-based committee scoring rules which use OWA operators (1, . . . , 1) are polynomial-time computable (provided that their scoring functions are polynomial-time computable). In the egalitarian setting this is not the case. While egalitarian-SNTV indeed is polynomial-time computable (via a trivial algorithm), both egalitarian Bloc and egalitarian-k-Borda are NP-hard.

Theorem 1. Egalitarian-SNTV is in P, but the problem of deciding if there exists a committee with at least a given score is NP-hard both for egalitarian-Bloc and egalitarian-k-Borda.

NP-hardness for egalitarian-Bloc follows via a simple reduction from the SET COVER problem, but FPT algorithms exist. For parametrization by the number of voters and the number of candidates, we inherit the algorithms for the MAV rule [Misra et al., 2015]. For parametrization by the committee size, we use the ideas of Gramm et al. [2003] (interestingly, MAV is W[2]-hard for the parametrization by the committee size [Misra et al., 2015], so egalitarian-Bloc is indeed easier than MAV); it is interesting if we can inherit approximation properties of MAV [Byrka and Sornat, 2014].

Corollary 1. Egalitarian-Bloc is computable in FPT-time for parametrizations by the number of candidates, the number of voters, and the committee size.

For egalitarian-k-Borda we only have the trivial FPT algorithm for the parametrization by the number of candidates.

Theorem 2. The problem of deciding if there is a committee with a given score for egalitarian-k-Borda is W[1]-hard when parametrized either by the number of voters or by the committee size. The rule is in FPT for the number of candidates.

Proof sketch. We reduce from MULTICOLORED CLIQUE (MCC) which, given a positive integer k and a graph G = (V (G), E(G)) where each vertex has one of k colors, asks if there are k vertices of different colors, all connected to each other; MCC parametrized by k is W[1]-hard. Let I = (G, k) be an instance of MCC. For each i ∈ [k], by V (i) we mean the set of vertices with color i, and for each i, j ∈ [k], by E{i,j} we mean the set of edges connecting vertices of color i with those of color j. Let N = |V (G)| + |E(G)| be the total number of vertices and edges. We form the set of candidates C = V (G)∪E(G)∪A′∪A′′∪B, where A′ , A′′ , and B are sets of dummy candidates with |A′ | = |A′′ | = N 10 and |B| = N 7 . We set the desired committee size to be K = k + (k2), and ask if there is a committee with egalitarian-k-Borda score at least T = 2KN 10 . We introduce the following voters.

Voters ensuring that dummies are not selected. We form the voters u1, u2, and u3 (when we put a set in a preference order, we mean listing its members in some easy to compute order):

Due to these voters, there is no size-K committee that includes members of A′ ∪ A′′ ∪ B and has total score at least T .

Choice voters. For each color i ∈ [K], we have a voter ranking the non-dummy candidates so that they have the following individual Borda scores (the dummies are ranked arbitrarily):

1. Every non-dummy candidate not in V (i) has individual Borda score 2N 10 + 1 K-1 N 7 + x, where x is between 0 and N, selected so that the score is an integer and is different for every candidate in (V (G) ∪ E(G)) \ V (i) .
2. Each candidate in V (i) has individual score 2N 10 -N 7 + x, where x is an integer in [N] chosen so that every candidate in V (i) has distinct score.

These voters ensure that a size-K committee with total score at least T does not contain more than one candidate from V (i) . We introduce analogous voters for each pair of colors i, j ∈ [k], to ensure that no such committee contains two candidates fromE{i,j} . In consequence, if a committee has score at least T, then it must include one vertex candidate for each color and one edge candidate for each pair of colors.

Voters ensuring consistency. For each ordered pair of distinct colors (i, j) we introduce two voters that jointly ensure that the committee members from V (i) and E{i,j} correspond to a vertex and an edge that are incident. We assume that candidates in V (i) are ordered, so for ℓ ∈ [|V (i) |] we can speak of the ℓ-th vertex of color i. We create voter u(i,j) 1 that ranks the non-dummy candidates so that they have the following individual Borda scores:

1. Every non-dummy candidate that is neither in V (i) nor in E{i,j} gets individual score 2N 10 +x, where x ∈ [N] is chosen so that all such candidates have different scores.
2. For each ℓ ∈ [|V (i) |], the ℓ-th vertex candidate from V (i) has individual score 2N 10 + ℓN 4 .
3. For each ℓ ∈ [|V (i) |], the candidates from E{i,j} that correspond to the edges connected to the ℓ-th vertex from V (i) have scores of the form 2N 10 - ℓN 4 + x, where x ∈ [N] is such that these candidates have distinct scores.

We also create voter u(i,j) 2 , defined in the same way, but for the reversed order of vertices from V (i) . If a committee includes the ℓ-th vertex from V (i) and a candidate from E{i,j} that corresponds to an edge connected to the ℓ′ -th vertex from V (i) , with ℓ′ > ℓ, then voter u(i,j) 1 gives such a committee score at most (K-2)(2N 10+N)+2N 10+ℓN 4+2N 10-ℓ′N 4+N = 2KN 10 +(K-1)N+(ℓ-ℓ′ )N 4 < T . If it were the case that ℓ′ < ℓ, then voter u(i,j) 2 would assign score lower than T to the committee. On the other hand, if a committee contains some vertex from V (i) and an edge from E{i,j} that is connected to this vertex, then both voter u(i,j) 1 and voter u(i,j) 2 assign score at least T to this committee. Thus, there is a committee with score at least T if and only if (G, k) is a yes-instance. This completes the proof as the number of voters that we introduced and the committee size are both functions of k only.

The next result is surprising as utilitarian rules with OWA vector (0, . . . , 0, 1) are NP-hard even to approximate [Skowron et al., 2016]; however, see the results regarding the Pessimist rule based on k-Approval scoring [2018].

Proposition 3. Egalitarian-Pessimist is in P.

3.3 Axiomatic Properties

We now consider axiomatic properties of egalitarian committee scoring rules, starting with their most characteristic feature.

Independence of Cloning Voters. Let E = (C, V ) be an election. Let core(V ) be obtained from V by removing voters so that if v is in V , then core(V ) contains exactly 1 voter with v's preference order. We define core(E) to be (C, core(V )).

Definition 2. A multiwinner rule R is independent of cloning voters if for each election E = (C, V ) and each committee size k it holds that R(E, k) = R(core(E), k).

Proposition 4. Every egalitarian committee scoring rule is independent of cloning voters.

This property motivated us to study egalitarian rules in the first place, as it seems to be important for electing diverse committees (however, it is certainly possible to define rules that are not egalitarian in our sense and have the property as well). Not surprisingly, independence of cloning voters is incompatible with majoritarian notions, such as the fixedmajority property of Debord [1993], which requires that if more than half of the voters rank members of some committee on the their top positions (possibly in different orders), then this committee wins. As egalitarian rules are indifferent to replacing a voter with copies of it, we get the following.

Proposition 5. There are no fixed-majority consistent egalitarian committee scoring rules.

(See the work of Faliszewski et al. [2018] for a discussion of fixed-majority consistent committee scoring rules.)

The fixed-majority property is a consensus-type notion, in the sense that it specifies which committee should "obviously" win in certain situations (see also the works of Nitzan [1981] and Elkind et al. [2015]). While egalitarian rules fail fixedmajority, they satisfy other consensus-type properties. For example, the narrow-top property [Faliszewski et al., 2017] requires that if there is a committee such that every voter ranks a member of it on top, then this committee shall win. The narrow-top property is very useful in the context of selecting diverse committees as it describes a situation where each voter's opinion can be catered for. In particular, utilitarian SNTV and β-CC have the property [Faliszewski et al., 2017].

Proposition 6. Both egalitarian-β-CC and egalitarian-SNTV satisfy the narrow-top property, but neither of egalitarian-Bloc, egalitarian-k-Borda, and egalitarian-Pessimist does.

Egalitarian-Bloc fails the narrow top property, but it does so quite gracefully: If there is a size-k committee such that each voter ranks one of its members on top, then either egalitarianBloc outputs this committee, or it outputs one where each voter ranks at least two of its members on top k positions.

(Strong) Candidate Monotonicity. Candidate monotonicity requires that if a candidate belongs to some winning committee and we shift him or her forward by one position in some vote, then this candidate still belongs to some winning committee (but possibly to a different one). All committee scoring rules have this property [Elkind et al., 2017b] and the same holds for all egalitarian committee scoring rules. In fact, our five egalitarian rules satisfy a stronger variant of candidate monotonicity: If a committee with the shifted candidate ceases to win, then no new committee comes in its place.

Proposition 7. Every egalitarian committee scoring rule is candidate-monotone.

Noncrossing Monotonicity. Elkind et al. [2017b] introduced the noncrossing monotonicity property, which requires that if we shift forward a member of some winning committee W (without passing any other members of W), then W still wins. Faliszewski et al. [2016] characterized noncrossingmonotone committee scoring rules as exactly those that are OWA-based, with OWA-vectors of the form (1, . . . , 1). Unfortunately, neither of our rules is noncrossing-monotone.

Proposition 8. Neither of the egalitarian variants of SNTV, Bloc, k-Borda, β-CC, and Pessimist is noncrossing monotone.

Faliszewski et al. [2016] also discuss top-member monotonicity, which requires that shifting forward the top-ranked member of a winning committee (in some vote) cannot prevent the committee fromwinning, and argue that this is a desirable property for rules that seek diverse committees. They show that, e.g., β-CC is top-member monotone. Unfortunately, neither egalitarian-β-CC nor egalitarian-Bloc, two of our rules that seem best suited for choosing diverse committees, has the property. Yet, egalitarian-Pessimist is top-member monotone.

Proposition 9. Neither of the egalitarian variants of SNTV, Bloc, k-Borda, and β-CC is top-member monotone, but egalitarian-Pessimist is.

If we compare β-CC and its egalitarian variant in terms of their (axiomatic) suitability for electing diverse committees, we see that both rules satisfy narrow-top, and β-CC is topmember monotone, whereas egalitarian-β-CC is independent of cloning voters. Thus neither comes out as clearly preferable (and in our experiments they give very similar results).

Committee-Enlargement Monotonicity. We conclude our discussion of axiomatic properties by considering the notion of committee-enlargement monotonicity [Barber`a and Coelho, 2008; Elkind et al., 2017b]. Intuitively, it requires that if we extend the size of the committee, then we obtain the larger winning committees from the smaller ones, by adding new members (without removing any of the old ones).

Definition 3 (Elkind et al. [2017b]). A multiwinner rule R is committee-enlargement monotone if for each election E with m candidates holds: (i) For each k ∈ [m- 1], if W ∈ R(E, k) then there is a committee W ′ ∈ R(E, k + 1) such that W ⊆ W ′ . (ii) For each k ∈ [m-1], if W ′ ∈ R(E, k+1) then there is a committee W ∈ R(E, k) such that W ⊆ W ′ .

Committee enlargement monotonicity is useful if one is interested in committees of individually excellent candidates (if a candidate is among the k best ones, this candidate should still be among k + 1 best!). As egalitarian rules do not seem fit for choosing individually excellent candidates, it is not surprising that they fail committee-enlargement monotonicity.

Proposition 10. The egalitarian variants of SNTV, Bloc, kBorda, β-CC, and Pessimist all fail the committee-enlargement monotonicity property.

3.4 Experiments

To better understand our rules, we computed their histograms for 2D Euclidean elections and three distributions of candidates and voters (using the technique of Elkind et al. [2017a]).

In the 2D Euclidean model, each candidate and each voter is represented as a point on a 2-dimensional plane (in our case, on the [-3, 3] × [-3, 3] square). Each voter-point forms its preference order by sorting the candidate-points in increasing order of their Euclidean distance from the voter. We considered the following ways of generating the points:

1. In the uniform disc setting, the candidate and voter points are selected uniformly at random from a disc with radius 3, centered at point (0, 0).
2. In the 2-Gaussians setting, candidate points are selected uniformly at random from the [-3, 3] × [-3, 3] square, while 90% (resp., 10%) of the voter points are selected from a Gaussian centered at (0, 0) (resp., (2, 0)) with standard deviation 0.25 (resp., 0.1).
3. In the overlapping squares setting, candidate points are selected uniformly at random from the square [-3, 1] × [-3, 1], and voter points are selected uniformly at random from the square [-1, 3] × [-1, 3].

The uniform disc setting is provided for basic comparison, as it was used by Elkind et al. [2017a]. The other two settings model situations where there are various groups of voters, with different sizes (in the 2-Gaussian case) and different properties (in the overlapping squares case, for some voters there are good representatives and for some there are none).

For each of the settings and for each of our rules (both utilitarian and egalitarian), we drew 10,000 elections with 100 candidates and 100 voters each, and computed the winning committees of size 10 (breaking ties uniformly at random; for NP-hard rules we used the ILP formulations of Skowron et al. [2016], adapted to the egalitarian setting, if needed (we omitted utilitarian Pessimist as it was particular difficult to compute). Then, for each scenario, we partitioned our [-3, 3] × [-3, 3] square into 120 × 120 equal-sized cells, and computed how many winners end up in each cell. We present the obtained histograms in Figure 1 (the darker a given point is, the more winners landed there; see the work of Elkind et al. [2017a] for details on drawing the histograms).

Our results are somewhat surprising. First, we note that for the uniform disc setting, where candidate and voter points are distributed in the same way, there is very little difference between utilitarian and egalitarian rules (the only really visible one is between Bloc and egalitarian-Bloc, which can be explained by that fact that egalitarian-Bloc is closer in spirit to αk-CC than to Bloc). Another surprise is that the egalitarianPessimist rule behaves quite similarly to the k-Borda rule (this is striking in the uniform disc setting, and is somewhat visible in the other settings). It is also quite intriguing that the histograms for β-CC and for its egalitarian variant are nearly indistinguishable (the same holds for SNTV, but, as observed by Elkind et al. [2017a], for SNTV this is a statistical artifact).

The results for egalitarian-Bloc are also very interesting. As the rule is a variant of MAV and can be seen as a refinement of αk-CC, it is very appealing that it seems to be very good at choosing diverse committees (in particular, for the 2-Gaussians setting, the sizes of the peaks near the centers of the Gaussians are much more similar to each other than in the β-CC case).

An important observation is that the egalitarian rules (except for egalitarian-SNTV) gave meaningful results and ties were a smaller problem than one might expect (to some extent this is because our elections did not contain true outliers).

4 Conclusions

Egalitarian voting rules are based on the Rawlsian idea of justice, saying that the election result is 'behind a veil of ignorance' and nobody knows how good or bad the result will be for any voter; hence a social contract should be concluded to maximise the welfare of the worst off voter. For singlewinner elections this approach has limited applicability due to non-decisiveness of egalitarian rules but it can be useful for multiwinner ones. We attempted to combine egalitarian idea with committee scoring rules. The results obtained, especially through modelling, are encouraging: The complexity of egalitarian version of some rules may be very different from that of their utilitarian versions. We also looked at axiomatic properties of egalitarian rules. It will be interesting to consider other approaches to egalitarian committees that do not fall under the framework of egalitarian committee scoring rules, and to provide mathematical motivation for the egalitarian approach (as inspired, e.g., by the work of Feld and Grofman [1988]).

Acknowledgments H. Aziz is supported by a Julius Career Award. P. Faliszewski was supported by the National Science Centre, Poland, under project 2016/21/B/ST6/01509. B. Grofman is indebted to research support from the Jack W. Peltason (Bren Foundation Endowed) Chair of Democracy at the University of California, Irvine. A. Slinko was supported by the Royal Society of NZ Marsden Fund grant 3706352.