The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality

1 Introduction

The notion of a Condorcet winner is among the most important ones in (computational) social choice [Arrow et al., 2002; Brandt et al., 2016a]. Consider a group of agents, each with a preference order over a given set of candidates. The Condorcet condition says that if there exists a candidate c that is preferred to every other candidate by a majority of agents (perhaps a different majority in each case), then this candidate c should be seen as the collectively best option. Such a candidate is known as the Condorcet winner.

In single-winner elections, that is, in settings where the goal is to choose one candidate (presidential elections are a prime example here, but in the context of AI one may want, e.g., to choose the best answer to a user's query based on a number of different criteria [Dwork et al., 2001]), there are strong arguments for choosing a Condorcet winner whenever it exists. For example, in case of presidential elections if a Condorcet winner existed but was not chosen as the country's president, a majority of the voters might revolt. If a particular response to a search query were better than every other response according to a majority of given criteria, then it would be a natural one to present to the user. (We note, however, that there are also arguments against rules that choose Condorcet winners whenever they exist: e.g., such rules suffer from the no-show paradox [Moulin, 1988; Brandt et al., 2016b] and fail the reinforcement axiom [Moulin, 1989].)

∗We are grateful to the anonymous IJCAI reviewers for their helpful comments. Haris Aziz was supported by a Julius Career Award. Edith Elkind, Martin Lackner, and Piotr Skowron were supported by the ERC grant number 639945 (ACCORD). Piotr Skowron was also supported by the Alexander von Humboldt Foundation. Piotr Faliszewski was supported by the National Science Centre, Poland, under project 2016/21/B/ST6/01509.

In this paper, we consider multiwinner elections, that is, settings where, instead of choosing a single winner (say, a president or a single best response to a search query), we choose a collective body of a given size (say, a parliament or a group of high-quality responses). The goal of our paper is to analyze generalizations of the concept of a Condorcet winner to multiwinner elections. There are several natural definitions of a "Condorcet committee" and we consider their merits and applications (we write "Condorcet committee" in quotes because several notions could be seen as deserving this term and, thus, eventually we do not use it for any of them).

First, we can take the approach of Gehrlein [1985] and Ratliff [2003], where we want the committee to be a collection of high-quality individuals who do not necessarily need to cooperate with each other (this is a natural approach, e.g., when we are shortlisting a group of people for a prize [Barber`a and Coelho, 2008; Elkind et al., 2017], or when we want to provide the user with a focused set of responses to a given query). In this case, each member of the "Condorcet committee" should be preferred by a majority of voters to all the nonmembers. We refer to such committees as Gehrlein-stable (see Remark 1 for some comments on our terminology).

Alternatively, there is the approach of Fishburn [1981a; 1981b] (also analyzed from an algorithmic perspective by Darmann [2013] and Sekar et al. [2017]), where a "Condorcet committee" is a committee that is preferred to every other committee by a majority of voters. If the voters only have preferences over the individual candidates, it is still possible to use this approach, but one has to lift the preferences to preferences over committees (e.g., by using a scoring function or another set extension). We do not pursue this approach here.

Finally, there is a middle-ground approach, proposed by Elkind et al. [2015], where the committee members focus on representing the voters (this is the case, e.g., in parliamentary elections, but also when we want to present the user with a broad, diverse set of answers to a given query; e.g., to include for each criterion a response ranked highly with respect to it). In this case, we compare committees against single candidates: We say that a voter i prefers committee W to some candidate c if there exists a candidate w in W (who can be seen as the representative of this voter) such that i prefers w to c. Now we could say that a "Condorcet committee" is one that is preferred to each candidate outside the committee by a majority of voters. Indeed, Elkind et al. [2015] refer to such committees as Condorcet winning sets.

Elkind et al. [2015] were unable to find an election with no Condorcet winning set of size three; their empirical results suggest that such elections are very unlikely. Thus, to use their approach in order to select large committees in a meaningful way, we should focus on committees that are preferred to unselected candidates by a large fraction of voters. In particular, we argue that when n voters select k candidates, the winning committee should be preferred to each non-member by roughly n - nk voters. Intuitively, if each voter has equal decision-making power, a group of nk voters should be able to influence the choice of one of the k candidates. In particular, such a group would be unhappy if there existed a candidate that they all prefer to each member of the selected committee. The resulting concept, which we call local stability, can be seen as a translation of the notion of justified representation [Aziz et al., 2017a] from the world of approval-based elections to that of ranked-ballot elections.

The goal of our work is to develop a better understanding of two generalizations of the Condorcet property to the multiwinner setting: the notion based on the ideas of Gehrlein [1985] and Ratliff [2003] (i.e., Gehrlein stability) and the notion based on Condorcet winning sets (i.e., local stability). We provide evidence that Gehrlein-stable committees are very well-suited for shortlisting (that is, when a Gehrlein-stable committee exists, then it is a natural choice for a shortlisting task 1 ), whereas locally stable committees are better at providing diverse results. We show that rules that output Gehrlein-stable or locally stable committees whenever such committees exist must be NP-hard (with the exception of one variant of Gehrlein stability, for which we show a polynomial-time computable rule).

2 Preliminaries

For each natural number p, we set [p] = {1, 2, . . . , p}. An election is a pair E = (C, V ), where C = {c1, . . . , cm} is a set of candidates and V = (v1, . . . , vn) is a list of voters; we write |V | to denote the number of voters in V . Each voter v ∈ V is endowed with a linear preference order over C, denoted by ≻v. For ℓ ∈ [m], topℓ(v) denotes the set of ℓ candidates most preferred by v. We write top(v) to denote the most preferred candidate of voter v, i.e., top(v) ≻v c for each c ∈ C \ top(v); note that top1(v) = {top(v)}. We write a ≻v b ≻v . . . to indicate that v ranks a first and b second, followed by all the other candidates in an arbitrary order. Given two disjoint subsets of candidates S, T ⊆ C, we write S ≻v T to indicate that v prefers each candidate in S to each candidate in T .

A single-winner voting rule is a function that takes an election E = (C, V ) and outputs a non-empty subset of candidates (the set of tied winners). A committee is a subset of C.

1 This idea is due to Barber`a and Coelho [2008], and we provide further supporting arguments. However, Barber`a and Coelho also show that rules that output Gehrlein-stable committees whenever they exist fail to satisfy an important criterion for shortlisting tasks. We offer a partial solution to this issue.

A multiwinner voting rule R takes an election E = (C, V ) and a positive integer k with k ≤ |C| as its input, and outputs a non-empty collection of size-k committees.

Given an election E = (C, V ) with |V | = n and two candidates c, d ∈ C, we say that c wins the pairwise election between c and d if more than n2 voters in V prefer c to d; if exactly n2 voters in V prefer c to d, we say that the pairwise election between c and d is tied. The majority graph of an election E = (C, V ) is a directed graph M(E) with vertex set C and the following edge set:

{(c, d) ∈ C 2 | c wins the pairwise election between c and d} .

Observe that if the number of voters n is odd, then M(E) is a tournament, i.e., for each pair of candidates c, d ∈ C exactly one of their connecting edges, (c, d) or (d, c), is present in M(E). We will also consider the weak majority graph of E, which we denote by W(E): this is the directed graph obtained fromM(E) by adding edges (c, d) and (d, c) for each pair of candidates c, d such that the pairwise election between c and d is tied. A candidate c is said to be a Condorcet winner of an election E = (C, V ) if the outdegree of c in M(E) is |C| - 1; c is said to be a weak Condorcet winner of E if the outdegree of c in W(E) is |C| - 1.

A single-winner voting rule is (weakly) Condorcet consistent if it outputs the Condorcet winner (the set of weak Condorcet winners) whenever it exists. Two prominent examples of Condorcet-consistent rules are the Copeland rule and the maximin rule. Under Copelandα (where α ∈ [0, 1] is a parameter), the score of each candidate c in election E is the outdegree of c in M(E) plus α times the number of candidates with whom c ties in their pairwise election. Under maximin, the score of candidate c in election E = (C, V ) is mind∈C\c |{v ∈ V | c ≻v d}|. In each case, the candidates with the highest score are the winners.

3 Gehrlein Stability and Local Stability

Gehrlein [1985] proposed a simple and natural extension of the notion of a weak Condorcet winner to the case of multiwinner elections, and a similar definition was subsequently introduced by Ratliff [2003]. We discuss Gehrlein's definition, and then put forward a different approach to defining winning committees, which is inspired by the recent work on Condorcet winning sets [Elkind et al., 2015] and on justified representation in approval-based model [Aziz et al., 2017a].

3.1 Gehrlein Stability

Gehrlein [1985] and Ratliff [2003] base their approach on the following idea: a committee is unstable if there exists a majority of voters who prefer a candidate that is not currently in the committee to some current committee member.

Definition 1 (Gehrlein [1985]; Ratliff [2003]). Consider an election E = (C, V ). A committee S ⊆ C is weakly Gehrlein-stable if for each committee member c ∈ S and each non-member d ∈ C\S it holds that c wins or ties the pairwise election between c and d. Committee S is strictly Gehrleinstable if for each c ∈ S and each d /∈ S the pairwise election between c and d is won by c.

We say that a multiwinner rule is weakly (strictly) Gehrlein-stable if it outputs the set of all weakly (strictly) Gehrlein-stable committees whenever this set is non-empty.

Remark 1. Unfortunately, there is no universally accepted terminology regarding what we call Gehrlein-stable committees. Gehrlein himself spoke of Condorcet sets (but we argued that this term is too broad). Barber`a and Coelho [2008] also spoke of Condorcet sets, but referred to rules that output 'Condorcet sets' as stable (this is also done by Kamwa [2017a; 2017b], even though he qualifies the term 'Condorcet set' more carefully). We believe that it is more natural to view stability as a property of committees rather than rules, and thus prefer to speak of Gehrlein-stable committees (and, to maintain consistency with the terminology of Barber`a and Coelho, we speak of Gehrlein-stable rules).

By definition, each strictly Gehrlein-stable committee is also weakly Gehrlein-stable, and the two notions are equivalent if the majority graph M(E) is a tournament. Further, a strictly (respectively, weakly) Gehrlein-stable committee of size one is simply a Condorcet winner (respectively, a weak Condorcet winner) of a given election. More generally, each member of a strictly (respectively, weakly) Gehrleinstable committee would be a Condorcet winner (respectively, a weak Condorcet winner) should the other committee members be removed from the election. Note also that given a committee S, it is straightforward to verify if it is strictly (respectively, weakly) Gehrlein-stable: it suffices to check that there is no candidate in C\S that ties or defeats (respectively, defeats) some member of S in their pairwise election.

Gehrlein-Stable Rules. Gehrlein stability has received some attention in the literature. In particular, Ratliff [2003], Coelho [2004], and, very recently, Kamwa [2017a; 2017b], proposed and analyzed a number of multiwinner rules that elect weakly Gehrlein-stable committees whenever they exist. We mention the following two rules [Coelho, 2004]. Let E = (C, V ) be an election and k the desired committee size; both rules output the committees with highest scores.

NED. Under the NED rule, the score of a size-k committee S is the number of edges in the graph W(E) that go from candidates in S to candidates in C \ S.

SEO. Under the SEO rule, the score of a size-k committee S is minc∈S,d∈C\S |{c ≻v d | v ∈ V }|.

NED and SEO can be seen as multiwinner analogues of Copeland1 and maximin, with weakly Gehrlein-stable committees in place of Condorcet winners. However, they are different from the rules that simply choose k candidates with the highest Copeland1 or maximin scores (we refer to these rules as k-Copeland1 and k-maximin). To understand why, let us consider the notion of committee monotonicity.

Gehrlein Stability and Committee Monotonicity. A rule R is said to be committee monotone if for each election E = (C, V ) and each committee size k (k < |C|), it holds that (a) every winning committee of size k is a subset of some winning committee of size k+1, and (b) every winning committee of size k + 1 is a superset of some winning committee of size k [Elkind et al., 2017]. For rules that always output a unique winning committee this property is known as enlargement consistency [Barber`a and Coelho, 2008]. Committee monotonicity is a natural requirement for rules used for shortlisting tasks; intuitively, it says that increasing the committee size never precludes a candidate from being shortlisted.

Barber`a and Coelho exhibited a profile where the unique weakly Gehrlein-stable committee of size 2 is disjoint from the unique weakly Gehrlein-stable committee of size 3, thereby establishing that no weakly Gehrlein-stable rule satisfies enlargement monotonicity (and hence committee monotonicity). As k-Copeland1 and k-maximin rules are committee monotone by definition, they are not weakly Gehrleinstable (and thus have to differ from the NED and SEO rules).

Barber`a and Coelho [2008] interpreted their result as saying that weakly Gehrlein-stable rules may not be appropriate for shortlisting tasks. This issue can be fixed by considering strictly Gehrlein-stable rules. In particular, our next result identifies a polynomial-time computable rule that is both strictly Gehrlein-stable and committee monotone.

Proposition 1. k-Copeland 0 is a strictly Gehrlein-stable rule that satisfies committee monotonicity.

Proof. Committee monotonicity follows from the definition. Strict Gehrlein stability follows because for an election E and committee size k, the rule outputs exactly committees of size k that include candidates with highest outdegrees inM(E); if a strictly Gehrlein-stable committee existed, then its members would have the highest outdegrees in M(E) and all the other candidates would have lower outdegrees.

3.2 Local Stability

An important feature of Gehrlein stability is that it is strongly driven by the majority opinions. Suppose, for instance, that a group of 1000 voters is to elect 10 representatives from the set {c1, . . . , c20}, and the society is strongly polarized: 501 voters rank the candidates as c1 ≻ · · · ≻ c20, whereas the remaining 499 voters rank the candidates as c20 ≻ · · · ≻ c1. Then the unique Gehrlein-stable committee of size 10 consists of candidates c1, . . . , c10, and the preferences of 499 voters are effectively ignored. While this is appropriate in some settings, in other cases we may want to ensure that candidates who are well-liked by significant minorities of voters are also elected.

Aziz et al. [2017a] formalize this idea in the context of approval voting, where each voter submits a set of candidates that she approves of (rather than a ranked ballot). Specifically, they say that committee S with |S| = k provides justified representation in an election (C, V ) with |V | = n, where each voter i is associated with an approval ballot Ai ⊆ C, if there is no group of voters V ′ ⊆ V with |V ′ | ≥ ⌈ nk ⌉ such that Ai ∩ S = ∅ for each i ∈ V ′ , yet there exists a candidate c ∈ C \ S approved by all voters in V ′ . Informally speaking, this definition requires that each 'cohesive' group of voters of size at least q = ⌈ nk ⌉ is represented in the committee. The choice of threshold q = ⌈ nk ⌉ (known as the Hare quota) is natural in the context of approval voting: it ensures that, when the electorate is composed of k equal-sized groups of voters, with sets of candidates approved by each group being pairwise disjoint, each group is allocated a representative.

Extending this idea to ordinal ballots (rankings) and to an arbitrary threshold q, we obtain the following definition.

Definition 2. Consider an election E = (C, V ) with |V | = n and a positive value q ∈ Q. A committee S violates local stability for quota q if there exists a group V ∗ ⊆ V with |V ∗ | ≥ q and a candidate c ∈ C \ S such that each voter from V ∗ prefers c to each member of S; otherwise, S provides local stability for quota q.

If a multiwinner rule always outputs locally stable committees for quota q (for some value of q) whenever they exist, then we say that this rule itself is locally stable for quota q.

Definition 2 requires some comments. First, there are many natural choices for the value of q, but for the sake of concreteness we fix the quota to be q = ⌊ n k+1 ⌋ + 1 (the Droop quota), and use the expression 'locally stable committee' to refer to locally stable committees for this value of the quota. Observe that for k = 1, a locally stable committee for the Droop quota q has the Condorcet winner-if it exists-as its only member. Hence local stability can also be seen as a generalization of the Condorcet criterion to the multiwinner setting. In the full version of the paper we provide a more detailed discussion of possible choices of quota.

Second, while in the context of approval voting the notion of group cohesiveness can be defined in absolute terms (a group is considered cohesive if there is a candidate approved by all group members), for ranked ballots a cohesive group is defined relative to a given committee (a group is cohesive with respect to S if all its members prefer some candidate to S). Another important difference between the two settings is that, while a committee that provides justified representation is guaranteed to exist and can be found in polynomial time [Aziz et al., 2017a], a committee that provides local stability may fail to exist (e.g., because for k = 1 the Condorcet winner does not always exist) and testing its existence is an NP-hard task (see Theorem 2).

Locally Stable Rules. Perhaps somewhat surprisingly (given that the definition of local stability is not necessarily the most obvious one), at least one locally stable rule was defined prior to our work. Specifically, Elkind et al. [2015] propose the following rule (we gave it a name, as Elkind et al. did not fix one; we explain its meaning below).

LSE-Maximin. A set of candidates S is a θ-winning set in an election E = (C, V ) for committee size k if for each candidate c ∈ C \S there are more than θ|V | voters who prefer some member of S to c. Elkind et al. [2015] define a voting rule that for a given election E and committee size k outputs a size-k θ-winning set for the largest possible value of θ. By definition, this rule outputs locally stable committees whenever they exist.

The name LSE-Maximin stands for 'locally stable extension of maximin.' Indeed, the maximin rule sets the score of each candidate c as the number of votes that c gets in the pairwise election against its toughest opponent. With local stability in mind, we do not compare candidates to candidates (as is natural if one is after Gehrlein stability or if one considers the single-winner case), and we do not compare committees to committees (as in Fishburn's [1981b] variant of multiwinner Condorcet consistency), but we compare committees to candidates. Under LSE-Maximin, the score of committee S can be interpreted as the number of voters who prefer S to its 'toughest opponent' among the candidates in C \ S.

We can define the 'locally stable extension of Copeland' (LSE-Copeland) in a similar way, by considering 'pairwise' comparisons of committees and candidates:

LSE-Copeland. The LSE-Copeland score of committee S in election E = (C, V ) (for committee size k) is the number of candidates d for whom at least n - ⌊ n k+1 ⌋ voters prefer some committee member to d. LSE-Copeland outputs the committees with the highest score.

As in the case of LSE-Maximin, LSE-Copeland outputs locally stable committees whenever they exist.

4 ACase Study: Single-Crossing Preferences

Intuitively, Gehrlein stability is a majoritarian notion, whereas local stability is directed towards voter representation. 2 In this section we reinforce this view by describing the structure of Gehrlein-stable and locally stable committees for single-crossing preferences. This allows us to obtain an intuitive understanding of how Gehrlein-stable and locally stable committees differ, and (to some extent) what sorts of behavior to expect from Gehrlein-stable and locally stable rules.

The following observation will be useful in our analysis. Consider an election E = (C, V ) for which M(E) is a transitive tournament, i.e., if (a, b) and (b, c) are edges of M(E) then (a, c) is also an edge of M(E). In such a case, the set of ordered pairs (a, b) such that (a, b) ∈ M(E) is a linear order on C and we refer to it as the majority preference order. Given a positive integer k, we let the centrist committee Scenter consist of the top k candidates in the majority preference order. We make the following simple observation.

Proposition 2. IfM(E) is transitive then for each committee size k, Scenter is strictly Gehrlein-stable.

The notion of single-crossing preferences was proposed by Mirrlees [1971] and Roberts [1977]. Informally speaking, an election is single-crossing if (the voters can be ordered in such a way that) as we move from the first voter to the last one, the relative order within each pair of candidates changes at most once. Saporiti and Tohm´e [2006] provide a number of examples where single-crossing preferences arise naturally.

Definition 3. An election (C, V ) with V = (v1, . . . , vn) is single-crossing 3 if for each pair of candidates a, b ∈ C such that v1 prefers a over b, {i | a ≻vi b} = [t] for some t ∈ [n].

Single-crossing elections have many desirable properties. In the context of our work, the most important one is that if E = (C, V ) is a single-crossing election with an odd number of voters, thenM(E) is a transitive tournament. Moreover if |V | = 2n′ + 1, the majority preference order coincides with the preferences of the (n′ +1)-st voter [Rothstein, 1991]. By Proposition 2, this means that for single-crossing elections with an odd number of voters the centrist committee exists, is strictly Gehrlein-stable, and consists of the top k candidates in the preference ranking of the median voter, which justifies the term centrist committee.

2 We should stress, however, that this is not proportional representation. Locally stable committees, when they exist, simply try to include the maximum possible number of views that are present in the society. Elkind et al. [2017] and Skowron et al. [2016] describe a number of settings where this form of representation is desirable.

3 Our definition assumes that the order of the voters is fixed. More commonly, an election is defined to be single-crossing if voters can be permuted so that the condition formulated in Definition 3 holds. For our results, this distinction is not important, but our approach simplifies presentation.

Locally stable committees turn out to be very different. Let E = (C, V ) be a single-crossing election with |V | = n, and let k be the target committee size; then the Droop quota for E is q = ⌊ n k+1 ⌋ + 1. We say that a size-k committee S is single-crossing uniform for E if for each ℓ ∈ [k] with ℓq ≤ n, it contains the candidate ranked first by voter vℓ·q. Note that a single-crossing uniform committee does not need to be unique: e.g., if all the voters rank the same candidate first, then every committee containing this candidate is singlecrossing uniform.

Example 1. Figure 1 shows a single-crossing election with 13 voters over the candidate set C = {a, b, c, d, e, f, g, h, i, j, k}. The first voter ranks the candidates in the alphabetic order, and the last voter ranks them in the reverse alphabetic order. For readability, we list the top four-ranked candidates only. For the target committee size 4, the centrist committee (marked with a rectangle) is {b, c, d, e}, and the unique single-crossing uniform committee is {b, d, g, j} (marked with dashed ellipses).

We will now argue that single-crossing uniform committees are locally stable.

Proposition 3. For every single-crossing election E = (C, V ) and for every k ∈ [|C|] it holds that every size-k single-crossing uniform committee for E is locally stable.

Proof. Fix a single-crossing election E = (C, V ) with |V | = n and a target committee size k; set q = ⌊ n k+1 ⌋ +1. Consider a committee S, |S| = k, that is single-crossing uniform with respect to E. We will show that S is locally stable.

Consider an arbitrary candidate c ̸∈ S. Suppose first that some voter vi with i < q ranks c above all candidates in S. Let a = top(vq). As a ∈ S and E is single-crossing, each voter vj with j ≥ q prefers a to c. Thus, there are at most q - 1 voters who prefer c to each member of S.

Now, suppose that some voter vi with ℓq < i < (ℓ + 1)q for some ℓ ∈ [k-1] ranks c above all candidates in S; let a = top(vℓ·q), b = top(v(ℓ+1)·q). By construction we have a, b ∈ S and by the single-crossing property a ̸= b (if a = b, then a and c would cross more than once). Also, by the singlecrossing property all voters vj with j ≤ ℓq rank a above c and all voters vj ′ with j ′ ≥ (ℓ + 1)q rank b above c. Thus, at most q - 1 voters prefer c to each member of S.

Finally, suppose that some voter vi with i > kq ranks c above all members of S; let a = top(vk·q). We have a ∈ S and by the single-crossing property all voters vj with j ≤ kq rank a above c. Thus, there are at most n - kq voters who may prefer c to a, and q > n k+1 implies n-qk < n- nk k+1 = n k+1 < q. In each case, the number of voters who may prefer c to all members of S is strictly less than q.

The following example shows that a single-crossing uniform committee can violate Gehrlein stability and, similarly, that the centrist committee can violate local stability.

Example 2. Let C = {a, b, c}. Consider the single-crossing election where three voters rank the candidates as a ≻ b ≻ c and four voters rank the candidates as c ≻ b ≻ a. Let k = 2. We have ⌊ n k+1 ⌋ + 1 = 3. The committee {a, c} is singlecrossing uniform for this election, yet four voters out of seven prefer b to a. The committee {b, c} is centrist, yet it is not locally stable since there are q = 3 voters who prefer a to both b and c.

We can reach similar conclusions for other restricted domains. E.g., for single-peaked preferences the locally stable committees are also uniformly distributed along the axis of societal preferences, while the Gehrlein-stable committees are concentrated around the center. For a detailed discussion of thse results, see the full version of the paper [Aziz et al., 2017b].

5 Computational Complexity

It is easy to test if a given committee is weakly/strictly Gehrlein-stable or locally stable, by directly applying the appropriate definition. We will now argue that finding stable committees can be computationally challenging, both for weak Gehrlein stability and for local stability. In contrast, we can test if a strictly Gehrlein-stable committee exists in polynomial time: it suffices to compute a k-Copeland0 winning committee and check if it is strictly Gehrlein-stable.

The results of this section imply that for all weakly Gehrlein-stable rules and for all locally stable rules finding a winning committee must be NP-hard. In particular, this applies to NED, SEO, LSE-Maximin, and LSE-Copeland.

Theorem 1. Given an election E = (C, V ) and a target committee size k with k ≤ |C|, it is NP-complete to decide if there exists a weakly Gehrlein-stable committee of size k for E.

Proof. It is immediate that this problem is in NP: given an election E and a committee S with |S| = k, we can check that S has no incoming edges in M(E).

To show hardness, we provide a reduction from PARTIALLY ORDERED KNAPSACK. An instance of this problem is given by a list of r ordered pairs of positive integers L = ((s1,w1), . . . , (sr,wr)), a capacity bound b, a target weight t, and a directed acyclic graph Γ = ([r],A). It is a 'yes'-instance if there is a subset of indices I ⊆ [r] such that ∑i∈I si ≤ b, ∑i∈I wi ≥ t and for each directed edge

(i, j) ∈ A it holds that j ∈ I implies i ∈ I. This problem is strongly NP-complete; indeed, it remains NP-hard if si = wi and wi ≤ r for all i ∈ [r] [Johnson and Niemi, 1983]. Note that if si = wi for all i ∈ [r], we can assume that b = t, since otherwise we obviously have a 'no'-instance. Furthermore, we assume that si = wi ≥ 3 for all i ∈ [r]; we can assure that, e.g., by multiplying all numbers by 3.

Given an instance 〈L, b, t, Γ〉 of PARTIALLY ORDERED KNAPSACK with L = ((s1,w1), . . . , (sr,wr)), si = wi, wi ≤ r for all i ∈ [r] and b = t, we construct an election as follows. For each i ∈ [r], let Ci = {c1i , . . . , cwi i } and set C = ⋃i∈[r] Ci. We construct the set of voters V and the voters' preferences so that the majority graph of the resulting election (C, V ) has the following structure: (1) for each i ∈ [r] the induced subgraph on Ci is a strongly connected tournament; (2) for each (i, j) ∈ A there is an edge from each candidate in Ci to each candidate in Cj; (3) there are no other edges. Using McGarvey's theorem [1953], we can ensure that the number of voters |V | is polynomial in |C|; as we have wi ≤ r for all i ∈ [r], it follows that both the number of voters and the number of candidates are polynomial in r. Finally, we let the target committee size k be equal to the knapsack size t. It can be shown that 〈L, b, t, Γ〉 is a 'yes'- instance of PARTIALLY ORDERED KNAPSACK if and only if there exists a weakly Gehrlein-stable committee of size t for (C, V ); we omit further proof details.

We obtain a similar result for locally stable committees.

Theorem 2. Given an election E = (C, V ) and a target committee size k with k ≤ |C|, it is NP-complete to decide if there exists a locally stable committee of size k for E.

Proof. It is easy to see that this problem is in NP: given an election (C, V ) together with a target committee size k and a committee S with |S| = k, we can check for each c ∈ C \ S whether there exist at least ⌊ n k+1 ⌋ + 1 voters who prefer c to each member of S.

To prove NP-hardness, we reduce from 3-REGULAR VERTEX COVER. Recall that an instance of 3-REGULAR VERTEX COVER is given by a 3-regular graph G = (N,E) and a positive integer t; it is a 'yes'-instance if G admits a vertex cover of size at most t, i.e., a subset of vertices N ′ ⊆ N with |N ′ | ≤ t such that {ν, ν ′ } ∩ N ′ ̸= ∅ for each {ν, ν ′ } ∈ E. This problem is known to be NP-complete [Garey and Johnson, 1979].

Consider an instance (G, t) of 3-REGULAR VERTEX COVER with G = (N,E), N = {ν1, . . . , νr}. Note that we have |E| = 1.5r, and we can assume that t < r -1, since otherwise (G, t) is trivially a 'yes'-instance. Given (G, t), we construct an election as follows. We set C = N ∪X ∪Y ∪Z, where X = {x1, . . . , x1.5r}, Y = {y1, . . . , y1.5r}, Z = {z1, . . . , z1.5r}. For each edge {ν, ν ′ } ∈ E we construct one voter with preferences ν ≻ ν ′ ≻ · · · and one voter with preferences ν ′ ≻ ν ≻ · · · ; we refer to these voters as the edge voters. Also, for each j ∈ [1.5r] we construct two voters with preferences xj ≻ yj ≻ zj ≻ · · · , two voters with preferences yj ≻ zj ≻ xj ≻ · · · , and two voters with preferences zj ≻ xj ≻ yj ≻ · · · ; we refer to these voters as the xyz-voters. We set k = t+3r. Note that the number of voters in our instance is n = 2|E| + 6 · 1.5r = 12r. Thus, using the fact that 0 < t < r -1, we can bound n k+1 as follows:

Thus the Droop quota is q = ⌊ n k+1 ⌋ + 1 = 4.

Now, suppose that N ′ is a vertex cover of size at most t; we can assume that |N ′ | is exactly t, as otherwise we can add arbitrary t-|N ′ | vertices to N ′ , and it remains a vertex cover. Then S = N ′ ∪ X ∪ Y is a locally stable committee of size |S| = t + 2 · 1.5r = t + 3r. Indeed, for each voter one of her top two candidates is in the committee (for edge voters this follows from the fact that N ′ is a vertex cover and for xyz-voters this is immediate from the construction), so local stability can only be violated if for some candidate c ̸∈ S there are at least q = 4 voters who rank c first. Yet, recall that each candidate is ranked first by at most three voters.

Conversely, suppose that S is a locally stable committee of size t + 3r. First note that |S ∩ {xj, yj, zj}| ≥ 2 for each j = 1, . . . , 1.5r, otherwise there would be 4 xyz-voters with a possible improvement and thus we would have a group of sufficient size to violate local stability. Hence, |S ∩N| ≤ t. Now, suppose that S∩N is not a vertex cover for G. Consider an edge {ν, ν ′ } with ν, ν ′ ̸∈ S. Since G is 3-regular, there are three edge voters who rank ν first; clearly, these voters prefer ν to each member of S. Moreover, there is an edge voter whose preference order is ν ′ ≻ ν ≻ . . . ; this voter, too, prefers ν to each member of S. Thus, we have identified four voters who prefer ν to S, a contradiction with the local stability of S. This shows that S ∩N is a vertex cover for G, and we have already argued that |S ∩ N| ≤ t.

6 Conclusions and Research Directions

We have considered two generalizations of the notion of a Condorcet winner to the case of multiwinner elections: the one proposed by Gehrlein [1985] and Ratliff [2003] and the one defined in this paper (but inspired by ideas of Aziz et al. [2017a] and Elkind et al. [2015]). Our analysis of singlecrossing elections provides evidence that the former approach is very majoritarian in spirit, while local stability may lead to diverse committees. Thus, it confirms the intuition that Gehrlein's approach is well-suited for shortlisting tasks; in particular, we have shown that the objection based on weakly Gehrlein-stable rules necessarily failing committee monotonicity does not apply to strictly Gehrlein-stable rules.

We have also shown that all rules that are weakly Gehrleinstable or locally stable must be NP-hard to compute (this does not apply to strictly Gehrlein-stable rules). While at first this may appear to be a serious disadvantage of these notions, in fact quite a few interesting multiwinner rules are NP-hard, and researchers seek various ways to work around this issue. Finding approximation algorithms, heuristics, and developing parameterized complexity approaches for these classes of rules is an immediate goal for future research.