Committee Scoring Rules: A Call to Arms

1 Introduction

rules, introduced by Elkind et al. [2017b] 1 as multiwinner analogues of the well-known single-winner positional scoring rules. Our goal is to encourage further researchers to study this class of rules. To this end, we suggest a number of research challenges, ranging from very high-level ones (such as finding principled ways of deciding which committee scoring rules are most appropriate for particular applications), through mid-level ones (such as characterizing some specific subclasses of committee scoring rules), to very specific ones (such as finding good algorithms for concrete rules).

The problem of selecting a set of individuals based on a given set of criteria is ubiquitous. For example, in various competitions it is often necessary to select a group of finalists based on their performance, Internet stores need to decide which products to show on their homepages to advertise their offer, and democratic societies need to choose parliaments to represent them. While these scenarios are very different from each other in many ways, they all fit within the framework of multiwinner voting: Our goal is to select a fixed-size committee of candidates, based on the preferences of a group of voters. For the case of choosing the finalists in a competition, the candidates are the participants and the voters' preferences correspond to means of evaluating these participants (for example, in ski-jumping each "vote" would describe a single series of jumps, ordering the competitors from the most to the least successful one; in other types of competitions, the votes would reflect the opinions of the judges or would be derived in some other ways). For the case of an Internet store, the candidates are the products on offer and the voters model the customers the store expects to see. Finally, in the case of parliamentary elections, the voters are simply the members of the society participating in electing their leaders. (The examples given above are based on the discussions provided by Lu and Boutilier [2011], Elkind et al. [2017b], and Skowron et al. [2016a].)

There are many multiwinner voting rules, based on many different ideas and principles (e.g., multiwinner rules inspired by Condorcet consistency recently attracted some attention in the AI literature [Sekar et al., 2017; Aziz et al., 2017b]). In this paper we focus on the family of committee scoring

∗ Piotr Faliszewski was supported by the National Science Centre, Poland, under project 2016/21/B/ST6/01509.

2 Committee Scoring Rules

The idea of single-winner positional scoring rules is to assume that each voter ranks the candidates from the most to the least appealing one and to associate each position in a ranking with a score value; the final score of a candidate is the sum of the scores he or she obtains from the voters and the candidates with the highest total score win. Committee scoring rules follow the same approach, but for a generalized notion of a position. We provide formal definitions below.

2.1 Definitions

An election E = (C, V ) consists of a set C = {c1, . . . , cm} of candidates and a collection V = (v1, . . . , vn) of voters, where each voter is endowed with a preference order, i.e., a ranking of the candidates from the most to the least appealing one. The position of candidate c in the preference order of voter v is denoted by posv(c) (the position of the most preferred candidate is 1, the position of the next one is 2, and so on). For a positive integer t, by [t] we mean the set {1, . . . , t} (in particular, we use [m] to denote the set of all possible candidate positions, but we will use this notation in other contexts as well). A single-winner scoring function γm: [m] → R associates each position in a preference order with a score. The γm-score of candidate c in election E = (C, V ) is defined as γm-scoreE(c) = ∑v∈V γm(posv(c)). We require scoring functions to be nonincreasing (i.e., if i < j then f(i) ≥ f(j)). Examples of scoring functions include the Borda scoring function, βm(i) = m-i, and, for each positive integer t, the t-Approval scoring function, αt(i) = [i ≤ t]

1 The notion was introduced in 2014, in the conference paper corresponding to the 2017 journal paper we cite here.

(we use the Iverson bracket here; for a logical expression P, by [P] we mean 1 if P is true and 0 if P is false).

In the multiwinner setting, our goal is to select a committee of candidates (i.e., a set of candidates) of a given size. Formally, a multiwinner rule R is a function that given an election E = (C, V ) and a positive integer k, outputs a family of size-k committees that tie as winners. For an election E = (C, V ), we define the position of a committee S in the preference order of voter v (denoted by posv(S)) to be the increasing sequence obtained from sorting the set {posv(c) | c ∈ S}. For two positive integers m and k, k ≤ m, we write [m]k to denote the set of all increasing length-k sequences of numbers from [m] (intuitively, [m]k is the set of all possible positions of size-k committees in elections with m candidates). Given two committee positions, I = (i1, . . . , ik) and J = (j1, . . . , jk), we say that I weakly dominates J (denoted I ⪰ J) if for each t ∈ [k] we have it ≤ jt. A committee scoring function fm,k : [m]k → R is a function that associates each committee position with a score, so that for each two committee positions I and J such that I ⪰ J it holds that fm,k(I) ≥ fm,k(J). The fm,kscore of a committee S in election E = (C, V ) is defined as fm,k-scoreE(S) = ∑v∈V fm,k(posv(S)).

Definition 1 (Elkind et al. [2017b]). We say that a multiwinner rule R is a committee scoring rule if there exists a family of committee scoring functions f = (fm,k)k≤m such that for each election E = (C, V ) with m candidates and each committee size k (k ≤ m), the set R(E, k) of winning committees consists exactly of those size-k committees S for which the value fm,k-scoreE(S) is the highest.

2.2 Examples of Committee Scoring Rules

One of the greatest strengths of the framework of committee scoring rules is that it allows one to express a remarkably diverse set of rules, including many rules previously studied in the literature, in a simple and uniform way. Below we provide several examples (we let k be the committee size):

Single Non-Transferable Vote (SNTV). The SNTV rule is defined via committee scoring functions of the form f SNTV m,k (i1, . . . , ik) = α1(i1) + · · · + α1(ik) = α1(i1). In other words, under the SNTV rule a committee gets a point for each voter that ranks some member of the committee on the top position.

Bloc. Under the Bloc rule, we use scoring functions of the form f Bloc m,k (i1, . . . , ik) = αk(i1) + · · · + αk(ik). This can be interpreted as saying that under the Bloc rule each voter lists his or her ideal committee members and the score that a voter assigns to a committee is the number of ideal candidates this committee includes.

k-Borda The k-Borda rule uses scoring functions of the form f k-Borda m,k (i1, . . . , ik) = βm(i1) + · · · + βm(ik). That is, k-Borda chooses k candidates with the highest Borda scores. Debord [1992] offers an axiomatic analysis of k-Borda.

Chamberlin-Courant (β-CC). Under the β-CC rule, we use scoring functions of the form f β-CC m,k (i1, . . . , ik) = βm(i1). Given a committee S and a voter v, we refer to the highest-ranked member of S as the representative of v in S. The score of a committee is the Borda score of its representative. The β-CC rule was introduced by Chamberlin and Courant [1983], but currently other variants of the rule are studied as well. For example, if we replace the Borda scoring function with the k-Approval one, we obtain the αk-CC rule [Procaccia et al., 2008; Betzler et al., 2013]. The SNTV rule can be seen as the α1-CC rule.

Proportional Approval Voting (αk-PAV). Under the αkPAV rule, we use scoring functions of the form f αk-PAV m,k (i1, . . . , ik) = αk(i1) + 12 αk(i2) + 13 αk(i3) + · · · + 1k αk(ik). PAV was introduced by Thiele [1895] and rediscovered by Simmons (see the overview of Kilgour [2010]).

These five rules have very different properties and are used in very different settings. For example, SNTV and Bloc are sometimes used in political elections (SNTV is used, e.g., in Puerto Rico, and Bloc is used, e.g., for some local elections in the United States and in the United Kingdom), kBorda seems to be very fitting for the problem of choosing finalists in a competition (indeed, similar rules are used, e.g., in Formula 1 racing, ski-jumping, and the Eurovision song contest), β-CC seems to select the most diverse committees (we are not aware of real-life applications of the rule, but this conclusion is both intuitive and supported by several recent studies [Skowron, 2016; Faliszewski et al., 2016a; Elkind et al., 2017a]), and PAV is best-suited for electing parliaments (in particular, the surprising-at-first use of the harmonic sequence in its definition guarantees that it naturally extends the d'Hondt method of apportionment, used for electing the parliaments of many countries [Brill et al., 2017]).

2.3 Approval-Based Elections

Instead of considering ordinal elections, where voters submit rankings of candidates, it is often more practical to consider approval-based elections, where voters indicate which candidates they find acceptable. Indeed, the cognitive burden of choosing a few candidates to approve, among many available ones, is much lower than ranking all these options (however, we should bear in mind that in some applications approvalbased votes do not provide sufficient information).

Fortunately, many multiwinner rules that were originally defined in the context of approval elections can also be cast in the framework of committee scoring rules. One of the most typical ways of doing so is to convert preference orders to sets of approved candidates, e.g., by assuming that each voter approves his or her k highest-ranked candidates (where k is the size of the committee). Indeed, the PAV rule was originally defined in the context of approval elections and we converted it to the αk-PAV rule in the just-described way.

For more details on approval-based multiwinner rules, we point the readers to the overview of Kilgour [2010] and to the recent works of Aziz et al. [2017a; 2015] (which also include computational results). Two other papers that link committee scoring rules and approval-based elections are those of Skowron et al. [2016a] and Lackner and Skowron [2017].

3 Challenge: Which Rules to UseWhen?

In Section 2.2 we have provided several examples of committee scoring rules and discussed the settings where they are (or could be) used. However, it is not always clear which committee scoring rule is most suitable to which task. Indeed, if one were simply presented with the definition of the αk-PAV rule, it would not be immediately clear that the rule selects committees that represent the voters in a proportional way.

Challenge A. Find axiomatic properties that should be satisfied by rules suitable for respective applications, test which well-known committee scoring rules have these properties, and find ways of synthesizing new committee scoring rules that satisfy them.

Next we discuss some results inspired by this challenge, and outline more specific challenges.

3.1 Properties of All Committee Scoring Rules

One of the most spectacular results regarding single-winner scoring rules is their axiomatic characterization, due to Young [1975]. This characterization says that positional scoring rules are the only single-winner rules that are symmetric, continuous, and consistent. (Informally put, a rule is symmetric if it treats equally all candidates and all voters, it is continuous if it is possible to ensure a candidate's victory by adding sufficiently many copies of an election where he or she wins, and it is consistent if merging two elections that have the same winner w gives an election where w still wins). Since symmetry and continuity are satisfied by most of the practical voting rules, Young's characterization says that if one cares about the rules' consistency, one's choice is limited to scoring rules.

Skowron et al. [2016b] obtained a characterization of committee scoring rules that is analogous to that of Young, but in the setting where multiwinner rules not only output the winning committees, but also allow one to compare two committees (their setting is analogous to that of social welfare functions from the world of single-winner elections 2 ). Thus the following challenge remains.

Challenge A.1. Provide an axiomatic characterization of committee scoring rules for the case where multiwinner rules are viewed as outputting families of winning committees (as in the model presented in this paper).

In addition to the characterization of Skowron et al. [2016b], there are also several other properties possessed by all committee scoring rules. For example, all committee scoring rules satisfy candidate monotonicity [Elkind et al., 2017b] (i.e., if a candidate c belongs to some winning committee and we shift him or her forward in some preference order, then c still belongs to some winning committee) and all of them satisfy nonimposition [Faliszewski et al., 2016a]

2 The characterization of single-winner scoring functions holds both if we view voting rules as providing winners only [Young, 1975] and if we view them as providing rankings of candidates [Smith, 1973; Young, 1974].

(for every committee W there exists an election where W is the unique winning committee). 3

Challenge A.2. Seek further axiomatic properties satisfied by all committee scoring rules.

3.2 Classification of Committee Scoring Rules

The class of committee scoring rules is so diverse that to obtain interesting results one often has to consider its subclasses. So far, the following ones attracted most attention (see the work of Faliszewski et al. [2016a] for a more detailed discussion):

(Weakly) Separable Rules. A rule is weakly separable if it can be defined through a scoring function of the form fm,k(i1, . . . , ik) = γm,k(i1) + · · · + γm,k(ik), where γm,k are single-winner scoring rules. If additionally the functions γm,k do not depend on k, then the rule is separable. SNTV and k-Borda are separable, whereas Bloc is only weakly separable. The class of (weakly) separable rules was introduced by Elkind et al. [2017b].

Representation-Focused Rules. A rule is representationfocused if it can be defined through a scoring function that (for a given number of candidates and a given committee size) depends only on the position of the mostpreferred committee member. SNTV and β-CC are examples of representation-focused rules. This class was introduced by Elkind et al. [2017b].

Top-k-Counting Rules. A rule is top-k-counting if it can be defined using a scoring function that (for a given number of candidates and a given committee size) depends only on the number of committee members ranked on the top k positions. Bloc, αk-CC, and αk-PAV are examples of top-k-counting rules. This class was introduced by Faliszewski et al. [2016b].

OWA-Based Rules. OWA-Based rules are defined using scoring functions of the form fm,k(i1, . . . , ik) = λm,k 1 γm,k(i1) + · · · + λm,k k γm,k(ik), where γm,k are single-winner scoring functions and λm,k t are coefficients; sequences (λm,k 1 , . . . , λm,k k ) are referred to as OWA operators. This class was introduced by Skowron et al. [2016a].

Decomposable Rules. Decomposable rules are defined using scoring functions of the form fm,k(i1, . . . , ik) = γm,k,1(i1)+γm,k,2(i2)+· · ·+γm,k,k(ik), where γm,k,t are single-winner scoring functions. This class was introduced by Faliszewski et al. [2016a].

Faliszewski et al. [2016b; 2016a] have pointed out that all weakly-separable, representation-focused, and topk-counting rules are OWA-based, and that all OWA-based rules are decomposable. Further, they characterized weaklyseparable rules within the class of committee scoring rules as the only ones that satisfy non-crossing monotonicity 4 and they discovered the class of top-k-counting rules while characterizing committee scoring rules that satisfy the fixedmajority criterion. 5 In their presentations (but not in the papers themselves, since the results were not available sufficiently early), they also announced similar characterizations of separable rules and representation-focused rules. Finally, they also suggested a variant of the non-crossing monotonicity property such that if a committee scoring rule satisfies it, then the rule must be decomposable. Thus, as far as characterizing important subclasses of committee scoring rules goes, the most pressing challenge is as follows.

3 Interestingly, there are committee scoring rules that fail the 2nonimposition property. That is, there is a committee scoring rule R and two committees W1 and W2 (of the same size k) such that for every election E we have that R(E, k) ̸= {W1,W2} [Lackner and Skowron, 2017]. On the other hand, every single-winner scoring rule satisfies 2-nonimposition.

Challenge A.3. Characterize OWA-based and decomposable rules within the class of committee scoring rules.

Using their characterizations, Faliszewski et al. [2016b; 2016a] also characterized the Bloc rule: It is the only committee scoring rule that is non-crossing monotone and fixedmajority consistent. Providing further such characterizations (and seeking to understand the meaning of particular axiomatic properties in the context of particular applications) would be a way to solve one part of our Challenge A.

Challenge A.4. Provide characterizations of specific rules within the class of committee scoring rules.

Finding new subclasses of committee scoring rules with desirable properties would provide a way for synthesizing new interesting committee scoring rules.

3.3 Experimental Verification

Another approach to tackling our Challenge A is to perform experimental evaluation of particular rules. For example, Elkind et al. [2017a] generated elections using the 2D Euclidean model and visualized their aggregated results.

4 Challenge: How to Compute the Rules?

It turns out that many interesting committee scoring rules are NP-hard to compute (weakly separable rules are a notable exception), but there are many ways to circumvent these hardness results. For example, even though computing winning committees under Chamberlin-Courant rules is NPhard [Procaccia et al., 2008; Lu and Boutilier, 2011], there are good approximation algorithms [Lu and Boutilier, 2011; Skowron et al., 2015a], there are fixed-parameter tractable algorithms [Betzler et al., 2013], and there are polynomial-time algorithms that work correctly provided the input votes satisfy appropriate restrictions [Betzler et al., 2013; Skowron et al., 2015b; Peters and Elkind, 2016; Cornaz et al., 2012].

4 A rule is non-crossing monotone if the following holds: If c is a member of some winning committee W and we shift c forward, but without passing any other member of W, then W is still winning.

5 The fixed-majority criterion requires that if a strict majority of voters rank members of some committee W on their top positions (not necessarily in the same order), then W is the unique winning committee.

Challenge B. Seek approximation, FPT, and heuristic algorithms for computing as wide a class of committee scoring rules as possible, as well as algorithms for computing these rules' results under restricted domains.

4.1 Approximation Algorithms

Below we focus on polynomial-time approximation algorithms. Currently there is a polynomial-time approximation scheme for the β-CC rule [Skowron et al., 2015a], but for most other committee scoring rules either inapproximability results are known [Skowron et al., 2016a] or the standard greedy algorithm of Nemhauser et al. [1978] for optimizing submodular set functions, achieving the 1- 1e approximation ratio, is the best known. Finding efficient algorithms, with better approximation guarantees, for a wide class of committee scoring rules is a major challenge. One possible way of tacking this challenge would be to consider OWA-based rules based on the Borda scoring function.

Challenge B.1. Seek efficient approximation algorithms for OWA-based rules with scoring functions of the form fm,k(i1, . . . , ik) = λ1β(i1) + · · · λkβ(ik), where the OWA operators (λ1, . . . , λk) are nonincreasing. One particularly interesting OWA operator to consider is the sequence of k/2 ones followed by k/2 zeros. Another one is sequence (1, 1 - 1k , 1 - 2k , . . . , 1 - k-1 k ).

We ask about the rules based on the Borda scoring functions because other well-known functions (such as kApproval) often lead to hardness of approximation [Skowron et al., 2016a] (but there are counterexamples, such as the surprising result of Byrka et al. [2017] regarding the PAV rule).

4.2 Fixed-Parameter Tractability

It is also interesting to seek FPT algorithms for committee scoring rules. While parametrization by the number of candidates leads to immediate FPT results and there are results that suggest that parametrization by the committee size would typically lead to W[1]-hardness results [Betzler et al., 2013], parametrization by the number of voters seems promising (indeed, Faliszewski et al. [2016b] already obtained some encouraging results for the case of top-k-counting rules).

Challenge B.2. Seek FPT algorithms for committee scoring rules, parametrized by the number of voters.

5 Summary

We have presented some of the current work on committee scoring rules and suggested avenues for future work. We believe that committee scoring rules are an exciting topic and hope that more researchers would join the force!