Committee Scoring Rules: Axiomatic Classification and Hierarchy

1 Introduction

We study axiomatic properties of classes of committee scoring rules (some previously known, and one introduced in this paper), and clarify the relations between these classes.

In our multiwinner voting setting, we are given a set of candidates and a collection of voters, each with a preference order ranking the candidates, and the goal, for a given k, is to select a committee (a set) of exactly k candidates that reflects the voters' preferences in the best possible way. Committee scoring rules, introduced by Elkind et al. [2014], are multiwinner analogues of the classic single-winner scoring rules. They form a remarkably rich class that includes both very simple rules, such as SNTV, Bloc, or k-Borda, and rather complicated ones, such as the rule of Chamberlin and Courant [1983] or variants of the proportional approval voting rule [Kilgour, 2010]. In effect, it is quite natural to focus on various classes of committee scoring rules instead of studying only general properties of the whole class.

So far, researchers have identified the following classes of committee scoring rules (see Sections 2 and 3; here we

⇤ Piotr Faliszewski was supported by AGH University grant 11.11.230.124 (statutory research). Arkadii Slinko was supported by the Royal Society of NZ Marsden Fund UOA-254. Piotr Skowron was supported by ERC-StG 639945. Nimrod Talmon was supported by a postdoctoral fellowship from I-CORE ALGO.

Piotr Skowron

University of Oxford Oxford, United Kingdom p.k.skowron@gmail.com

Nimrod Talmon

Weizmann Institute of Science Rehovot, Israel nimrodtalmon77@gmail.com

give intuitions only). Weakly separable rules, introduced by Elkind et al. [2014], are those rules where we compute a separate score for each candidate (using a single-winner scoring rule) and then pick k candidates with top scores (for example, using the plurality scoring leads to the single nontransferable vote rule, SNTV). Representation-focused rules, also introduced by Elkind et al. [2014], model rules which are similar to the Chamberlin-Courant rule, which ensures that each voter ranks his or her most preferred committee member (his or her representative) as high as possible. On the other hand, top-k-counting rules, introduced by Faliszewski et al. [2016], capture rules where each voter judges the quality of a committee by the number of its members that he or she ranks among k top ones (notably, among committee scoring rules, only members of this class can satisfy the fixedmajority property of Debord [1993]; Bloc is a prime example of a top-k-counting rule). Finally, the class of OWA-based rules-introduced by Skowron et al. [2015], but also studied by Aziz et al. [2015a; 2015b]-includes all the previously mentioned classes, and is based on summing ordered weighted averages (OWAs) of the (per vote) scores of the candidates (see the original work of Yager [1988] for a general discussion of OWAs, and, e.g., the works of Kacprzyk et al. [2011] or Goldsmith et al. [2014] for their other applications in voting).

Our goal is to establish relationships between these classes and to study their axiomatic properties. Our main results are:

1. Regarding classes of top-k-counting, representationfocused, and weakly separable rules, for each two of these we show that their intersection contains exactly one nontrivial rule and we identify this rule (in each case, it is a natural, previously-studied rule).
2. We introduce the class of decomposable committee scoring rules that strictly contains all the OWA-based rules and appears to be easier to work with axiomatically. Since weakly separable rules, representation-focused rules, and top-k-counting rules are all OWA-based, we obtain a hierarchy of classes of committee scoring rules.
3. We characterize weakly separable rules as exactly those committee scoring rules that satisfy the noncrossing

monotonicity property of Elkind et al. [2014]. Then we refine the notion of noncrossing monotonicity to obtain a family of its variants, including one satisfied by all representation-focused rules (top-member monotonicity), and one satisfied by a natural class of decomposable rules (prefix monotonicity).

In addition, we show that there are decomposable rules that are not OWA-based, but nonetheless interesting from a practical point of view. Due to limited space, we omit most of our proofs (the proofs are available upon request).

2 Preliminaries

For each positive integer t, we write [t] to mean ¶1↪ ▷ ▷ ▷ ↪ t♦. Multiwinner Elections. An election is a pair E = (C↪ V ), where C = ¶c1↪ ▷ ▷ ▷ ↪ cm♦ is a set of candidates and V = (v1↪ ▷ ▷ ▷ ↪ vn) is a collection of voters. Each voter vi has a preference order ≻i, expressing his or her ranking of the candidates, from the most desirable one to the least desirable one. Given a voter v and a candidate c, by posv(c) we mean the position of c in v's preference order (the top-ranked candidate has position 1, the next one has position 2, and so on).

A multiwinner voting rule is a function R that, given an election E = (C↪ V ) and a committee size k, 1  k  ♣C♣, returns a family R(E↪ k) of size-k subsets of C, i.e., the set of committees that tie as winners of the election (we use the nonunique-winner model). We provide a few examples of multiwinner rules a bit later. (We focus on rules based on scoring functions, but there are other rules, e.g., those based on the Condorcet principle [Barber`a and Coelho, 2008; Fishburn, 1981; Darmann, 2013], or those which take approval ballots as input [Kilgour, 2010]).

Single-Winner Scoring Functions. Most of the multiwinner rules we study are based on single-winner scoring functions. A single-winner scoring function for m candidates is a nonincreasing function γ, γ : [m] ! R+, that assigns a score value to each position in a preference order. Given a preference order ≻i and a candidate c, by the γ-score of c (given by voter vi) we mean the value γ(posvi (c)). The two most commonly used scoring functions are the Borda scoring function, βm(i) = m-i, and the t-approval scoring function, ↵t, where ↵t(i) = 1 for i  t, and ↵t(i) = 0 otherwise.

Committee Scoring Rules. Let m and k be two positive integers, k  m (intuitively, m is the number of candidates and k is the committee size). We write [m]k to denote the set of all length-k increasing sequences of numbers from [m]. Given two sequences, I = (i1↪ ▷ ▷ ▷ ↪ ik) and J = (j1↪ ▷ ▷ ▷ ↪ jk), we say that I (weakly) dominates J, I ⌫ J, if for each t 2 [k], it holds that it  jt.

Let E = (C↪ V ) be an election with C = ¶c1↪ ▷ ▷ ▷ ↪ cm♦ and V = (v1↪ ▷ ▷ ▷ ↪ vn), and let k be a positive integer. For a committee S and voter vi, by posvi (S) we mean the sequence that we obtain by sorting the set ¶posvi (c) ♣ c 2 S♦ in the increasing order. Naturally, posvi (S) is in [m]k.

Definition 1 (Elkind et al. [2014]). A committee scoring function for m candidates and committee size k is a function h: [m]k ! R+ such that, for each two sequences I↪ J 2 [m]k, if I dominates J then h(I) ≥ h(J).

Let f = (fm↪k)km be a family of committee scoring functions, where each fm↪k is a function for m candidates and committee size k. We define the score of a size-k committee S in an election E with m candidates to be scoreE(S) = Pvi2V fm↪k(posvi (S)). The committee scoring ruleRf outputs those committees that have the highest score under f.

Many well-known multiwinner rules are, indeed, committee scoring rules. Below, we provide some examples:

1. Under the single nontransferable vote rule (SNTV), we output those k candidates that are ranked first by the largest numbers of voters; i.e., SNTV uses functions f SNTV m↪k (i1↪ ▷ ▷ ▷ ↪ ik) = Pkt=1 ↵1(it) = ↵1(i1).
2. k-Borda outputs k candidates whose sums of Borda scores are highest. That is, k-Borda uses committee scoring functions f k-Borda m↪k (i1↪ ▷ ▷ ▷ ↪ ik) = Pkt=1 βm(it).
3. Bloc operates under the assumption that each voter ranks the members of his or her ideal committee on top k positions, and outputs those k candidates that belong to the highest number of ideal committees. That is, Bloc uses functions f Bloc m↪k (i1↪ ▷ ▷ ▷ ↪ ik) = Pkt=1 ↵k(it).
4. Under the Chamberlin-Courant rule (the β-CC rule), the score that a voter v assigns to committee S depends only on how v ranks his or her favorite member of S (referred to as v's representative in S). The Chamberlin-Courant rule seeks committees in which each voter ranks his or her representative as high as possible. Formally, the rule uses functions f CC m↪k (i1↪ ▷ ▷ ▷ ↪ ik) = βm(i1).

Naturally, there are many other committee scoring rules, some of which we discuss throughout the paper. The trivial committee scoring rule that for every election and committee size k returns the set of all size-k subsets of candidates is defined by a family of constant functions.

3 Hierarchy of Committee Scoring Rules

In this section we describe the classes of committee scoring rules that were studied to date, introduce our new class-the class of decomposable rules-and argue how all these classes relate to each other, forming a hierarchy.

(Weakly) Separable Rules. We say that a family of committee scoring functions f = (fm↪k)km is weakly separable if there exists a family of (single-winner) scoring functions (γm↪k)km with γm↪k : [m] ! R+ such that for every m 2 N and every sequence I = (i1↪ ▷ ▷ ▷ ↪ ik) 2 [m]k we have:

A committee scoring rule Rf is (weakly) separable if it is defined through a family of (weakly) separable scoring functions f. If for all m we have γm↪1 = · · · = γm↪m, then we say that the function is separable, without the "weakly" qualification (separable rules have some axiomatic properties that other weakly separable rules lack [Elkind et al., 2014]).

The notion of (weakly) separable rules was introduced by Elkind et al. [2014]; they pointed out that SNTV and k-Borda are separable, whereas Bloc is only weakly separable. 1

1 In the AAMAS version of their paper, Elkind et al. [2014] used the term "additively separable" instead of "separable."

Representation-Focused Rules. A family of committee scoring functions f = (fm↪k)km is representation-focused if there exists a family of (single-winner) scoring functions (γm↪k)km such that for every m 2 N and every sequence I = (i1↪ ▷ ▷ ▷ ↪ ik) 2 [m]k we have:

A committee scoring rule Rf is representation-focused if it is defined through a family of representation-focused scoring functions f. The notion of representation-focused rules was introduced by Elkind et al. [2014]; β-CC is the archetypal example of a representation-focused committee scoring rule.

SNTV is both separable and representation-focused rule, and it is the only nontrivial rule with this property.

Proposition 1. SNTV is the only nontrivial rule that is (weakly) separable and representation-focused.

Top-k-Counting Rules. A committee scoring rule Rf , defined by a family f = (fm↪k)km, is top-k-counting if there exists a sequence of nondecreasing functions (gk)k2N, with gk : ¶0↪ ▷ ▷ ▷ ↪ k♦ ! R+, such that:

That is, the value fm↪k(i1↪ ▷ ▷ ▷ ↪ ik) depends only on the number of committee members that the given voter ranks among his or her top k positions. We refer to the functions gk as the counting functions. Top-k-counting rules were introduced by Faliszewski et al. [2016].

Faliszewski et al. mention three notable examples of topk-counting rules: the Bloc rule (with counting functions gBloc k (i) = i), the Perfectionist rule (with counting functions gPerf k such that gPerf k (i) = 1 if i = k and gPerf k (i) = 0 otherwise), and the ↵k-CC rule (with counting functions gCC k such that gCC k (0) = 0 and gCC k (i) = 1 for i ≥ 1). ↵k-CC is also representation focused and is one of many approvalbased variants of the Chamberlin-Courant rule.

Bloc is the only nontrivial rule that is both weakly separable and top-k-counting, and ↵k-CC is the only nontrivial rule that is both representation-focused and top-k-counting.

Proposition 2 (Follows from the results of Faliszewski et al. [2016]). Bloc is the only nontrivial rule that is weakly separable and top-k-counting.

Proposition 3. ↵k-CC is the only nontrivial rule that is representation-focused and top-k-counting.

OWA-Based Rules. Skowron et al. [2015] introduced a class of multiwinner rules based on ordered weighted average (OWA) operators (a variant of this class was studied by Aziz et al. [2015a; 2015b]; Elkind and Ismaili [2015] use OWA operators to define a different class of multiwinner rules). While they did not directly consider elections based on preference orders, their ideas also apply to committee scoring rules.

An OWA operator ⇤ of dimension k is a sequence ⇤ = (λ1↪ ▷ ▷ ▷ ↪ λk) of nonnegative real numbers.

Definition 2. Let ⇤ = (⇤k)k2N be a sequence of OWA operators such that ⇤k = (λk1 ↪ ▷ ▷ ▷ ↪ λkk ) has dimension k. Let γ = (γm↪k)km be a family of (single-winner) scoring functions for elections with m candidates (γm↪k : [m] ! N).

Then, γ and ⇤ define a family f = (fm↪k)km of committee scoring functions such that for each (i1↪ ▷ ▷ ▷ ↪ ik) 2 [m]k we have:

We refer to committee scoring rules Rf defined through f in this way as OWA-based.

It is known that weakly separable, representation-focused, and top-k-counting rules are OWA-based (one uses OWA operators (1↪ ▷ ▷ ▷ ↪ 1) for weakly separable rules, and OWA operators (1↪ 0↪ ▷ ▷ ▷ ↪ 0) for representation-focused rules; the argument for top-k-counting rules is due to Faliszewski et al [2016] and is a bit more involved). As a corollary to the preceding propositions, we get the following observation.

Corollary 4. Each of the classes of separable, top-kcounting, and representation-focused rules is strictly contained in the class of OWA-based rules.

Naturally, there are also OWA-based rules that do not belong to any of the above-mentioned classes. For example, by t-PAV (t-approval based variant of proportional approval voting; see the work of Kilgour [2010]) we mean the OWAbased rule that uses ↵t as the single-winner scoring functions and OWA operators of the form ⇤k = (1↪ 12 ↪ 13 ↪ ▷ ▷ ▷ ↪ 1k ).

Proposition 5. For some constant t, t-PAV is neither weakly separable, representation-focused, nor top-k-counting.

For other examples of OWA-based rules, see the works of Skowron et al. [2015] and Aziz et al. [2015a; 2015b].

Decomposable Rules. We introduce the following class that naturally generalizes the class of OWA-based rules.

Definition 3. Let γ (t) m↪k : [m] ! N, t 2 [k], be a family of (single-winner) scoring functions for elections with m candidates (t  k  m). These functions define a family of committee scoring functions f = (fm↪k)km such that for each (i1↪ ▷ ▷ ▷ ↪ ik) 2 [m]k we have:

We refer to committee scoring rules Rf defined through f in this way as decomposable.

At first glance, decomposable rules seem very similar to the weakly separable ones. The difference is that for fixed m and k and two different values t and t0 , for decomposable rules the functions γ (t) m↪k and γ (t0 ) m↪k can be completely different. This implies that OWA-based rules are decomposable. In fact, the containment is strict.

Proposition 6. The class of OWA-based rules is strictly contained in the class of decomposable rules.

While the containment is immediate to see, proving that it is strict requires more care. We first give an intuition for a practical decomposable rule that is not OWA-based and then show that indeed such rules are not OWA-based.

Example 1. Consider a clothing store that specializes in shirts. Let C be the set of m shirts that the store can order from its suppliers. However, the store can put on display only k different shirts, and it wants to pick them in a way that would maximize its revenue (i.e., the number of shirts sold). We assume that every customer ranks all the possible shirts from the best one to the worst one. 2 Let us say that a customer considers a shirt to be "good enough" if, from his or her point of view, it is among the top 20% of all shirts and to be "very good" if it is among top 5%. A customer buys two "very good" shirts, or one "at least good enough" shirt (if there are no two "very good" shirts). Naturally, the customer picks the best shirt(s) he can find (respecting the above constraints). If i1↪ ▷ ▷ ▷ ↪ ik are the positions (in the customer's preference order) of the shirts that the store puts on display, then the number of shirts he or she buys is given by function:

Thus, to maximize its revenue, the store should find a winning committee for the election where the shirts are the candidates, the voters are the customers, and where we use committee scoring rule Rf based on f = (fm↪k)km.

We refer to decomposable rules defined through committee scoring functions of the form

where ⇤k = (λk1 ↪ ▷ ▷ ▷ ↪ λkk ) are OWA operators and tm↪k↪1↪ ▷ ▷ ▷ ↪ tm↪k↪k are sequences of integers from [k], as multithreshold rules (we put no constraints on tm↪k↪1↪ ▷ ▷ ▷ ↪ tm↪k↪k; both increasing and decreasing sequences are natural).

Proposition 7. The committee scoring rule defined through the multithreshold function fm↪k(i1↪ ▷ ▷ ▷ ↪ ik) = ↵p1 (i1) + ↵p2 (i2), for p1↪ p2 2 ¶2↪ ▷ ▷ ▷ ↪m - k - 2♦, p1 > p2 + 1, is not OWA-based.

Proof. Let us fix the number of candidates m to be sufficiently large (as will become clear throughout the proof) and the committee size k to be sufficiently small (e.g., k = 2 would suffice). For the sake of contradiction, let us assume that Rf is OWA-based, i.e., in particular, that there exists f 0 such that Rf = Rf 0 (for elections with m candidates and committee size k) and such that f 0 (i1↪ ▷ ▷ ▷ ↪ ik) = λ1γ(i1)+λ2γ(i2)+· · ·+λkγ(ik), where γ is a single-winner

Let E1 be an election obtained from E by shifting c1 one position forward in v. According to fm↪k, in E1 the score of committee C1 increases by one point (as compared to E),

scoring function and the coefficients λi are all nonnegative. Let E = (C↪ V ) be an election with candidate set C = ¶c1↪ ▷ ▷ ▷ ↪ cm♦ and voter collection V = (v1↪ ▷ ▷ ▷ ↪ vm!), with one voter for each possible preference order. By symmetry, each size-k subset W of C is a winning committee of E under Rf . Let v be an arbitrary fixed voter and let b be the candidate that v ranks on top, c1 be the candidate that v ranks on position (p1 + 1), and c2 be the candidate that v ranks on position (p2 + 1). Note that v prefers b to c2 to c1. Let Dk-1 and Dk-2 be, respectively, the sets of candidates that v ranks on bottom k - 1 and k - 2 positions. We define three committees: C1 = Dk-1 [ ¶c1♦, C1↪2 = Dk-2 [ ¶c1↪ c2♦, and Cb↪2 = Dk-2 [ ¶b↪ c2♦.

2 We use this order to define natural concepts, such as a "good enough" shirt. A customer certainly knows if a shirt is good enough.

and the score of C1↪2 does not change. Since every other committee gains at most one point, we get that C1 is a winner in E1 and that C1↪2 is not. However, this means that also under f 0 the score increase of C1 must have been greater than the score increase of C1↪2 and, so, we get λ1(γ(p1) - γ(p1 + 1)) > λ2(γ(p1)-γ(p1 +1)). It must be that γ(p1)-γ(p1 + 1) > 0 (otherwise the above inequality would not hold) and we conclude that λ1 > λ2.

Next, let E2 be an election obtained from E by shifting c2 one position forward in v: In E2 the committee Cb↪2 gains one point and by the same reasoning as above we infer that Cb↪2 is a winner in E2. Similarly, C1↪2 does not gain the additional point and, so, it is not a winner in E00 . Under f 0 the score increase of Cb↪2 must be greater than that of C1↪2, so λ2(γ(p2) - γ(p2 + 1)) > λ1(γ(p2) - γ(p2 + 1)). This implies that λ2 > λ1, which gives a contradiction.

Example 2. We continue the shirt store example. Now the store does not want to maximize its direct revenue (i.e., the number of shirts sold), but the number of happy customers (in hope of increased future revenue). Let us say that a customer is happy if he finds at least two very good shirts or at least one excellent shirt (one among top 1% of the shirts). Then the store should use the committee scoring function fm↪k(i1↪ ▷ ▷ ▷ ↪ ik) = max(↵0▷01m(i1)↪ ↵0▷05m(i2))▷

We refer to multithreshold rules with summation replaced by the max operator as max-threshold rules.

Proposition 8. There is a max-threshold rule that is not decomposable.

We show the relations between the classes discussed in this section, with examples of notable rules, in Figure 1.

4 Axiomatic Properties

We now focus on axiomatic properties of committee scoring rules. The choice of properties we study was led by the desire to understand (and separate) our classes of rules.

Nonimposition Property. Nonimposition is among the most basic properties of voting rules. A single-winner rule R

is said to satisfy the nonimposition property if for each candidate there is an election where this candidate is the unique winner. We generalize this definition to the case of multiwinner rules in the natural way.

Definition 4. Let R be a multiwinner rule. We say that R has the nonimposition property if for each candidate set C and each subset W of C, there is a collection of voters V over C, such that for election E = (C↪ V ) we have R(E↪ ♣W♣) = W.

We show that all nontrivial committee scoring rules have the nonimposition property, through a somewhat intricate proof. For single-winner scoring rules, it suffices to consider an election where a fixed candidate is on top in all preference orders and all the other candidates are ranked in all possible ways. We use a similar approach, but the proof is more complicated because we need to take care of committees that share some members with the committee that we want to win.

Theorem 9. Let Rf be a committee scoring rule defined by a family of committee scoring functions f = (fm↪k)km. The rule Rf satisfies the nonimposition property if and only if every committee scoring function in f is nontrivial.

So far we do not know if for every committee scoring rule there is an election where exactly two (a'priori given) committees tie as winners. This is unfortunate since if we had such a result, we would have a fairly general mechanism for showing that two committee scoring functions (for given m and k) define the same rule (for these m and k) only if they are linearly related. This would give a semiautomatic mean of proving results such as Proposition 7.

Variants of Noncrossing Monotonicity. Elkind et al. [2014] introduced two monotonicity notions for multiwinner rules: candidate monotonicity and noncrossing monotonicity. In the former one, we require that if we shift forward a candidate from a winning committee in some vote, then this candidate still belongs to some winning committee after the shift (possibly a different winning committee). Elkind et al. [2014] show that all committee scoring rules have this property.

For noncrossing monotonicity, we require that if we shift forward a member of a winning committee W (without him or her passing another member of W) then W is still winning.

Definition 5 (Elkind et al. [2014]). A multiwinner rule R is noncrossing monotone if for each election E = (C↪ V ) and each k 2 [♣C♣] the following holds: if c 2 W for some W 2 R(E↪ k), then for each E0 obtained from E by shifting c forward by one position in some vote without passing another member of W, we have that W 2 R(E0 ↪ k).

Elkind et al. [2014] have shown that weakly separable rules are noncrossing monotone, and we will now show that these are the only such committee scoring rules.

Theorem 10. Let Rf be a committee scoring rule defined through a family f = (fm↪k)km of scoring functions fm↪k : [m]k !N. Rf is noncrossing monotone if and only if Rf is weakly separable.

Proof. Due to the results of Elkind et al. [2014], it suffices to show that if Rf is noncrossing monotone then it is weakly separable. So let us assume that Rf is noncrossing monotone.

Consider an arbitrary number of candidates m and committee size k 2 [m]. For each t 2 ¶2↪ ▷ ▷ ▷ ↪m♦, let Pm↪k(t) be the set of sequences from [m]k that include position t and do not include position t-1. (For example, if m = 5 and k = 2, then P5↪2(4) = ¶(1↪ 4)↪ (2↪ 4)↪ (4↪ 5)♦.) Intuitively, Pm↪k(t) is a collection of positions a committee of size k may take, in which it is possible to shift the committee member from position t to position t - 1 without passing another member.

Consider an arbitrary integer t 2 ¶2↪ ▷ ▷ ▷ ↪m♦, two arbitrary (but distinct) sequences I = (i1↪ ▷ ▷ ▷ ↪ ik) and J = (j1↪ ▷ ▷ ▷ ↪ jk) from Pm↪k(t), and an arbitrary vote v from the election. Let C(I) be the set of candidates that v ranks at positions i1↪ ▷ ▷ ▷ ↪ ik, and let C(J) be defined analogously for J. Let E0 be the election obtained by shifting in v the candidate currently in position t one position up. Finally, let I 0 and J 0 be sequences from [m]k, obtained from I and J by replacing the number t with t-1 (recall that I and J are from Pm↪k(t)).

Let E = (C↪ V ) be an election with candidate set C = ¶c1↪ ▷ ▷ ▷ ↪ cm♦, and voter collection V = (v1↪ ▷ ▷ ▷ ↪ vm!), with one voter for each possible preference order. By symmetry, any size-k subset W of C is a winning committee under Rf .

Since, by assumption, Rf is noncrossing monotone, it must be the case that C(I) and C(J) are winning committees under Rf also in election E0 . The difference of the scores of committee C(I) in elections E0 and E is fm↪k(I 0 )-fm↪k(I), and the difference of the scores of committee C(J) in E0 and E is fm↪k(J 0 ) - fm↪k(J). Clearly, it must be the case that: fm↪k(I 0 ) - fm↪k(I) = fm↪k(J 0 ) - fm↪k(J). However, since the choice of t, and the choice of I and J within Pm↪k(t), were completely arbitrary, it must be the case that there is a function hm↪k such that for each t 2 ¶2↪ ▷ ▷ ▷ ↪m♦, each sequence U 2 Pm↪k(t), and each sequence U 0 obtained from U by replacing position t with t - 1, we have hm↪k(t - 1) = fm↪k(U 0 ) - fm↪k(U).

We define a single-winner scoring function γm↪k as follows. For each t 2 ¶2↪ ▷ ▷ ▷ ↪m♦, we set γm↪k(t - 1) - γm↪k(t) = hm↪k(t - 1). We choose γm↪k(m) so that γm↪k(m) + γm↪k(m - 1) + ▷ ▷ ▷ + γm↪k(m - (k - 1)) = fm↪k(m- (k - 1)↪ ▷ ▷ ▷ ↪m- 1↪m) (so that γm↪k indeed correctly describes the score of the committee ranked at the k bottom positions as a sum of the scores of the candidates).

We fix some arbitrary sequence (`1↪ ▷ ▷ ▷ ↪ `k) from [m]k; our goal is to show that fm↪k(`1↪ ▷ ▷ ▷ ↪ `k) = γm↪k(`1) + γm↪k(`2) + · · · + γm↪k(`k). We know that, due to the choice of γm↪k(m), for R = (r1↪ ▷ ▷ ▷ ↪ rk) = (m- k + 1↪ ▷ ▷ ▷ ↪m) it does hold that fm↪k(r1↪ ▷ ▷ ▷ ↪ rk) = γm↪k(r1)+· · ·+γm↪k(rk). Now we can see that this property also holds for R0 = (r1 - 1↪ r2↪ ▷ ▷ ▷ ↪ rk). The reason is that γm↪k(m-k)-γm↪k(m-k+ 1) = hm↪k(m- k) = fm↪k(R0 ) - fm↪k(R)▷ Thus, for R0 , we have fm↪k(R0 ) = γm↪k(r1 - 1) + γm↪k(r2) + · · · + γm↪k(rk). Clearly, we can proceed in this way, shifting the top member of the committee up by sufficiently many positions, to obtain R00 = (`1↪ r2↪ ▷ ▷ ▷ ↪ rk) and (by the same argument as above) have fm↪k(R00 ) = γm↪k(`1) + γm↪k(r2) + · · · + γm↪k(rk)▷ Then we can do the same to position r2, and keep decreasing it until we get `2. Then the same for the third position, and so on, until the k-th position. Finally, we get fm↪k(`1↪ ▷ ▷ ▷ ↪ `k) = γm↪k(`1) + · · · + γm↪k(`k). We conclude by noting that γ is a nonincreasing function, because it defines a noncrossing monotone rule.

Based on the idea of noncrossing monotonicity, we can define many other similar notions. Consider a multiwinner rule R, committee size k, and let M = ¶m1↪ ▷ ▷ ▷ ↪mt♦ be a subset of [k], where t  k and m1 < m2 < · · · < mt. Consider a vote v (over a candidate set C, ♣C♣ ≥ k) and a committee W = ¶w1↪ ▷ ▷ ▷ ↪wk♦ (we assume that v ranks w1 ahead of w2, ranks w2 ahead of w3, and so on). By an Mshift of W in v, we mean shifting by one position forward wm1 , then wm2 , and so on, until wmt . We say that a given M-shift is legal in v with respect to W if executing it is possible (i.e., wm1 is not ranked first) and the shifted members of W do not overtake other members of W.

Definition 6. Let M = (Mk)k≥1 be a sequence of sets, where each Mk is a family of subsets of [k]. We say that a multiwinner rule R is M-monotone if for each election E = (C↪ V ) and each k 2 [♣C♣], the following holds: For each W 2 R(E↪ k), each M 2 Mk, and each E0 obtained from E by applying in some vote a legal M-shift (with respect to W), we have that W 2 R(E0 ↪ k).

We can use M-monotonicity to define the standard noncrossing monotonicity and several other interesting notions:

1. Consider a sequence Mnc = (Mnc k )k≥1, where each Mnc k consists of all the singleton subsets of [k]. Then Mnc -monotonicity is simply noncrossing monotonicity.
2. Consider a sequence Mpre = (Mpre k )k≥1, where each Mpre k is of the form ¶¶1♦, ¶1↪ 2♦, ▷ ▷ ▷ ↪ ¶1↪ ▷ ▷ ▷ ↪ k♦♦. We refer to Mpre -monotonicity as prefix monotonicity.
3. Consider a sequence Mtop = (Mtop k )k≥1, where each Mtop k is equal to ¶¶1♦♦. We refer to Mtop - monotonicity as top-member monotonicity.

Intuitively, if a rule satisfies the prefix monotonicity criterion, then shifting forward some top members of a winning committee, within a given vote, never prevents this committee from winning. Top-member monotonicity is a refinement of prefix monotonicity, where we are restricted to shifting only the top-ranked member of a winning committee.

Naturally, all noncrossing monotone rules (i.e., all weakly separable rules) satisfy all types ofM-monotonicity.

Corollary 11. If a multiwinner rule is noncrossing monotone then it isM-monotone for every choice ofM.

Thus it is impossible to use M-monotonicity notions to characterize classes of rules that do not contain weakly separable ones. Yet, it is possible to show that some such classes do satisfy specific types of M-monotonicity.

Proposition 12. Every representation-focused rule is topmember monotone.

On the other hand, only decomposable rules can be prefixmonotone (and mostly, though not only, those based on convex functions; see also the explanations below Theorem 14).

Theorem 13. Let Rf be a committee scoring rule. If Rf is prefix-monotone then it must be decomposable.

Theorem 14. Let Rf be a decomposable committee scoring rule defined through a family of scoring functions fm↪k(i1↪ ▷ ▷ ▷ ↪ ik) = γ (1) m↪k (i1) + γ (2) m↪k (i2) + · · · + γ (k) m↪k (ik), where γ = (γ (t) m↪k )tkm is a family of single-winner scoring functions. A sufficient condition for Rf to be prefix-monotone is that for each m and each k 2 [m] we have that:

• (i) for each i 2 [k] and each p↪ p0 2 [m-1], p < p0 , it holds that γ (i) (p)-γ (i) (p+1) ≥ γ (i) (p0 )-γ (i) (p0 +1), and
• (ii) for each i↪ j 2 [k], j > i, and each p 2 [m], j  p < m - (k - i), it holds that γ (i) (p) - γ (i) (p + 1) ≥ γ (j) (p) - γ (j) (p + 1).

Intuitively, condition (i) says that functions in the γ family are convex, and condition (ii) says that, for each m and k, if i < j then γ (i) m↪k decreases at least as rapidly as γ (j) m↪k .

Example 3. ↵k-CC is a decomposable rule that is not prefixmonotone. Consider k = 2 and an election that includes the vote v : a ≻ b ≻ c ≻ d. Let us say that in the whole election the winning committees are W = ¶b↪ c♦ and W 0 = ¶c↪ d♦. If ↵k-CC were prefix-monotone, then shifting b and c by one position forward in v (to obtain b ≻ c ≻ a ≻ d) should keep W winning. However, doing so does not change the score of W and increases the score of W 0 , so W no longer wins.

5 Computational Remarks

Many committee scoring rules are NP-hard to compute. Procaccia et al. [2008], Lu and Boutilier [2011], and Betzler et al. [2013] show hardness of winner determination for various representation-focused rules, Skowron et al. [2015] and Aziz et al. [2015b] show strong hardness results for large families of OWA-based rules, and Faliszewski et al. [2016] do the same for many top-k-counting rules. (On the other hand, weakly separable rules are polynomial-time computable.)

Fortunately, many of the above-cited papers also provide means to go around their hardness results. We add the following result to this literature.

Theorem 15. Let Rf be a decomposable committee scoring rule defined through a family of scoring functions fm↪k(i1↪ ▷ ▷ ▷ ↪ ik) = γ (1) m↪k (i1) + γ (2) m↪k (i2) + · · · + γ (k) m↪k (ik), where γ = (γ (t) m↪k )tkm is a family of polynomial-time computable single-winner scoring functions. If for each m, each k 2 [m], each i 2 [k - 1] and each p 2 [m], it holds that γi-1(p) ≥ γi(p), then there is a polynomial-time algorithm that, given an election E = (C↪ V ) and a committee size k, outputs a committee W such that scoreE(W) ≥ (1 - 1e ) maxS✓C↪♣W♣=k scoreE(S).

6 Summary

We have provided an axiomatic study of committee scoring rules, focusing mostly on the hierarchy formed by its subclasses (including that of decomposable rules, introduced in this paper) and on properties of monotonicity. There is a number of follow-up directions for this research. For example, whole-committee monotonicity (where all the members of the committee are shifted forward) is an interesting property.