Computing Pareto Optimal Committees

1 Introduction

Pareto optimality is a central concept in economics and has been termed the "single most important tool of normative economic analysis" [Moulin, 2003]. An outcome is Pareto optimal if there does not exist another outcome that all agents like at least as much and at least one agent strictly prefers. Although Pareto optimality has been considered extensively in single-winner voting and other social choice settings such as fair division or hedonic games, it has received only little attention in multiwinner voting, in which the outcomes are sets of alternatives. Multiwinner voting applies to selecting a set of plans or a committee, hiring team members, movie recommendations, and more. For convenience, we use the terminology "committee" even if our results have an impact far beyond committee elections.

In single-winner voting setting, agents express preferences over alternatives and a single alternative is selected. Pareto optimality in this context is straightforward to define, achieve, and verify. In multiwinner voting, a well-known difficulty is that it is unrealistic to assume that agents will report preferences over all possible committees, since there are an exponential number of them. For this reason, most approaches

J´erˆome Lang and J´erˆome Monnot

LAMSADE, Universit´e Paris-Dauphine Paris, France ¶lang, jerome.monnot♦@lamsade.dauphine.fr

assume that they only report a small part of their preferences, and that some extension principle is used to induce a preference over all possible subsets from this 'small input' over single alternatives [Barber`a et al., 2004]. Such preference extensions are also widely used in other social choice settings such as fair division or matching. The most two widely used choices of 'small inputs' in multiwinner voting are rankings (linear orders) over alternatives and sets of approved alternatives. In this paper we make a choice that generalizes both of them: agents report weak orders over single alternatives. Then we consider four prominent preference extension principles: the responsive extension, where a set of alternatives S is at least as preferred as a set of alternatives T if S is obtained from T by repeated replacements of an alternative by another alternative which is at least as preferred; the optimistic, or 'best' (respectively pessimistic, or 'worst') extension, which orders subsets of alternatives according to their most (respectively, least) preferred element; and the leximax extension, a lexicographic refinement of the optimistic extension.

The responsive extension [Barber`a et al., 2004; Roth and Sotomayor, 1990] can be seen as the ordinal counterpart of additivity. The leximax extension has been considered in various papers [Bossert, 1995; Lang et al., 2012; Klamler et al., 2012]. The 'best' set extension has been considered in a number of approaches such as full proportional representation [Chamberlin and Courant, 1983; Monroe, 1995] and other committee voting settings [Elkind et al., 2015]. The 'worst' set extension, also used by Klamler et al. [2012] and Skowron et al. [2015b], captures settings where the impact of a bad alternative in the selection overwhelms the benefits of good alternatives: for instance, when the decision about a crucial issue will be made by one of the members of the committee but the agent ignores which one and is risk-averse; or the case of a parent's preferences over a set of movies to be watched by a child. The 'best' and 'worst' set extensions have been used in coalition formation [Aziz and Savani, 2016; Cechl´arov´a, 2008].

Although set extensions have been implicitly or explicitly considered in multiwinner voting, most of the computational work has dealt with specific voting rules (see the related work section). Instead, we concentrate on Pareto optimality, consider the computation and verification of Pareto optimal committees, as well as the existence of a polynomial-time and strategyproof algorithm that returns Pareto optimal outcomes.

Contributions We consider Pareto optimality with respect to the four aforementioned preference set extensions. We present various connections between the Pareto optimality notions. For each of the notions, we undertake a detailed study of complexity of computing and verifying Pareto optimal outcomes. Table 1 summarizes the complexity results.

An important take-home message of the results is that testing Pareto optimality or obtaining Pareto improvements over status-quo committees is computationally hard even though computing some Pareto optimal committee is easy. For responsive and leximax extensions we give a complete characterization of the complexity of testing Pareto optimality when preferences are dichotomous and the size of top equivalence class is two: unless P = NP, Pareto optimality can be tested in polynomial time if and only if the size of the first equivalence classes is at most two. For the 'best' extension, we show that even computing a Pareto optimal outcome is NP-hard. Another interesting contrast with the responsive set extension is that even when preferences are dichotomous and the size of top equivalence class is two, testing Pareto optimality is coNP-complete. In contrast to the other extensions, for the 'worst' extension, both problems of computing and verifying Pareto optimal outcomes admit polynomial-time algorithms.

We also consider the requirement of strategyproofness on top of Pareto optimality. We show that there exist linear-time Pareto optimal and strategyproof algorithms for committee voting even for weak preferences for three of the four set extensions. The algorithms can be considered as careful adaptations of serial dictatorship for committee voting.

2 RelatedWork

A first related stream of work involves studying specific committee elections rules from a computational point of view (generally with little or no focus on Pareto optimality). Our focus on determining whether a committee is Pareto optimal or on finding a Pareto optimal committee, is in some sense orthogonal to the study of committee election rules. The simplest (and most widely used) rules for electing a committee, called best-k rules, compute a score for each alternative based on the ranks, and the alternatives with the best k scores are elected [Elkind et al., 2014; Faliszewski et al., 2016]. Scoring-based extension principles have also been used by Darmann [2013]. Note that the output of a best k-rule is obviously Pareto-optimal for the preferences induced by this scoring function, but not necessarily with respect to other set extensions.

Klamler et al. [2012] compute optimal committees under a weight constraint for a single agent (therefore optimality is equivalent to Pareto optimality), using several preference extensions including 'worst', 'best', and leximax.

The 'best' (B) extension principle has been used in a number of papers on committee elections by full proportional representation, starting with [Chamberlin and Courant, 1983] and studied from a computational point of view in a long series of papers (e.g., [Procaccia et al., 2008; Lu and Boutilier, 2011; Betzler et al., 2013; Skowron et al., 2015a; Elkind and Ismaili, 2015]. These rules obviously output Pareto optimal committees for B, but not necessarily for other extensions.

Some works are based on the Hamming extension. Each agent specifies his ideal committee and he prefers committees with less Hamming distance from the ideal committee. The Hamming distance notion can be used to define specific rules such as minimax approval voting [Brams et al., 2007], which selects the committee minimizing the maximum Hamming distance for the agents. Although the output of minimax approval voting is not always Pareto-optimal for the Hamming extension, there are good Pareto-optimal approximations of it [Caragiannis et al., 2010]. Note that for dichotomous preferences, the Hamming extension coincides with the responsive and the leximax extensions, therefore our computational results for responsive set extension for dichotomous preferences also hold for the Hamming and leximax extensions.

A second line of work concerns understanding the classes of rules that result in Pareto optimal outcomes. Most works along this line bear on a different type of committee elections, called designated-seat voting, where candidates must declare the seat they contest [Benoˆıt and Kornhauser, 2010]. 1 Results about the existence or non-existence of Pareto optimal rules have been presented [ ¨Ozkal-Sanver and Sanver, 2006; Benoˆıt and Kornhauser, 2010; Cuhadaroˇglu and Lain´e, 2012].

3 Setup

We consider a set of agents N = ¶1↪ ▷ ▷ ▷ ↪ n♦, a set of alternatives A = ¶a1↪ ▷ ▷ ▷ ↪ am♦ and a preference profile %= (%1 ↪ ▷ ▷ ▷ ↪%n) such that each %i is a complete and transitive relation over A. We write a %i b to denote that agent i values a at least as much as b and use ≻i for the strict part of %i, i.e., a ≻i b iff a %i b but not b %i a. Finally, ⇠i denotes i's

indifference relation, i.e., a ⇠i b iff both a %i b and b %i a. The relation %i results in equivalence classes E1 i ↪E2 i ↪ ▷ ▷ ▷ ↪Eki i for some ki such that a ≻i a0 if a 2 El i and a0 2 El0 i for some l < l0 . We will use these equivalence classes to represent the preference relation of an agent as a preference list i : E1 i ↪E2 i ↪ ▷ ▷ ▷ ↪Eki i . For example, we will denote the preferences a ⇠i b ≻i c by the list i : ¶a↪ b♦↪ ¶c♦. An agent i's preferences are strict if the size of each equivalence class is 1. An agent i's preferences are dichotomous if he partitions the alternatives into just two equivalence classes, i.e., ki = 2. Let Topwidth(%) be the maximum size of the most preferred equivalence class, i.e., Topwidth(%) = maxin ♣E1 i ♣. For any S ✓ A, we will denote by max%i (S) and min%i (S) the alternatives in S that are maximally and minimally preferred by i respectively. Thus, if q and r are respectively the smallest and the largest indices such that Eq i \ S 6= ; and Er i \ S 6= ;, then max%i (S) = Eq i \ S and min%i (S) = Er i \ S. For k  m, let Sk(A) = ¶W ✓ A : ♣W♣ = k♦.

1 If there are exactly two candidates per seat, then designated voting is equivalent to multiple referenda, where a decision has to be taken on each of a series of yes-no issues.

4 Set Extensions and Pareto Optimality

Set Extensions Set extensions are used for reasoning about the preferences of an agent over sets of alternatives given their preferences over single alternatives. For fixed-size committee voting, the responsive extension is very natural and has been applied in various matching settings as well [Barber`a et al., 2004; Roth and Sotomayor, 1990]. For all V↪ W 2 Sk(A), we say that W %RS i V if and only if there is an injection f from V to W such that for each a 2 V , agent i weakly prefers f(a) to a, i.e. f(a) %i a.

We define the 'best' set extension and the 'worst' set extension which are denoted B and W respectively. For all W↪ V 2 Sk(A), W %Bi V if and only if w %i v for w 2 max%i (W) and v 2 max%i (V ). On the other side, W %Wi V if and only if w %i v for w 2 min%i(W) and v 2 min%i (V ).

In the leximax (LX) extension, an agent prefers a committee that selects more alternatives from his most preferred equivalence class, in case of equality, the one with more alternatives for the second most preferred equivalence class, and so on. Formally, W ≻LX i V iff for the smallest (if any) l with ♣W \ El i ♣ 6= ♣V \El i ♣ we have ♣W \ El i ♣ > ♣V \El i ♣. 2

Efficiency based on Set Extensions With each set extension E, we can define Pareto optimality with respect to E. A committee W 2 Sk(A) is Pareto optimal with respect to E, or simply E-efficient, if there exists no committee W 0 2 Sk(A) such that W 0 %Ei W for all i 2 N and W 0 ≻Ei W for some i 2 N. Note that for each of our set extensions, E-efficiency coincides with standard Pareto optimality when k = 1. An outcome is a Pareto improvement over another if each agent weakly improves and at least one agent strictly improved.

In Figure 1, we illustrate the relations between the different efficiency notions. In one case, The inclusion relation follows from the fact that %LX i is a refinement of %RS i . Most of the other observations can be proved by small examples consisting of two or three agents.

We also make the following general observation.

Lemma 1. If there is a polynomial-time algorithm to compute a Pareto improvement over a committee, then there exists a polynomial-time algorithm to compute an E-efficient committee under set extensions E 2 ¶RS↪ LX↪W↪ B♦.

2 One could define in a similar way a leximin refinement of %W . For the sake of brevity we do not consider such a refinement here.

Proof. Here, we start from any committee and we recursively apply Pareto improvement until we reach a Pareto optimal committee. For the 'best' and 'worst' extensions, there can be at most mn Pareto improvements because for one agent there can be at most m improvements. Since an RS-improvement implies an LX-improvement, let us bound the number of LX-improvements. The maximum number of improvements is when we start from the set of worst alternatives and move to the set of best alternatives. The number of movements for the best alternative in the set is at most m, and similarly for other alternatives. Thus there can be at most m2 improvements and in total there can be nm2 Pareto improvements.

We end this section by observing that, under any of the set extensions we consider, a set of Pareto optimal alternatives may be Pareto dominated. Consider the following example.

Example 1.

1 : a↪ c↪ b↪ d

3 : b↪ c↪ a↪ d

2 : a↪ d↪ b↪ c

4 : b↪ d↪ a↪ c

The set ¶c↪ d♦ consists of Pareto optimal alternatives but is Pareto dominated by ¶a↪ b♦ under any of our set extensions.

5 Responsive Set Extension

There is a trivial way to achieve Pareto optimality under the responsive set extension by taking any decreasing scoring vector consistent with the ordinal preferences, finding the total score of each alternative and returning the set of k alternatives with the maximum scores. For instance, on Example 1, the outcome of the rule that outputs the alternatives with the best k Borda scores is ¶a↪ b♦.

Theorem 1. A Pareto optimal committee under the responsive set extension committee can be computed in linear time.

In many situations, one may already have a status-quo committee and one may want to find a Pareto improvement over it. This problem of testing Pareto optimality and finding a Pareto improvement under the responsive set extension turns out to be a much harder task. Note that if there exists a polynomial-time algorithm to compute a Pareto improvement, then it means that testing Pareto optimality is also polynomial-time solvable.

Theorem 2. Checking whether a committee is Pareto optimal under the responsive set extension is coNP-complete, even for dichotomous preferences and T opwidth(%) ≥ 3, or for strict preferences.

Proof. We only present the case where Topwidth(%) = 3. The reduction is from the NP-complete problem VERTEX COVER [Garey and Johnson, 1979]. Given a simple graph G = (V↪E), the MINIMUM VERTEX COVER problem consists in finding a subset C ✓ V of minimum size such that every edge e 2 E is incident to some node of C. Its decision version VERTEX COVER consists, given a simple graph G = (V↪E) and an integer k, of deciding if there exists a vertex cover C ✓ V of G with ♣C♣  k.

Let h(V↪E)↪ ki be an instance of VERTEX COVER, with [x↪ y] being one arbitrary edge in E. We build the following instance of Pareto optimality under RS:

• ÷ N = [e2ENe [ ¶a♦, where for each edge e 2 E, Ne is a set of k agents, and a is a special agent.
• ÷ A = V [ D, where D = ¶d1↪ ▷ ▷ ▷ ↪ dk♦.
• ÷ For each e = [u↪ v] 2 E, the preferences of agent ei , for i = 1↪ ▷ ▷ ▷ ↪ k, and of agent a, are

The reduction is clearly done within polynomial time and preferences are dichotomous. We can check easily that committee D (of size k) is not Pareto optimal under RS if and only if there exists a vertex cover of G of size at most k.

For strict preferences, in the previous reduction we replace ¶u↪ v↪ di♦↪ ▷ ▷ ▷ by ¶u♦↪ ¶v♦↪ ¶di♦↪ ▷ ▷ ▷ in the preferences of ei . It is easy to see that the proof is similar.

Using a similar reduction from the HITTING SET problem, we can also prove Theorem 3 that concerns a parametrized complexity intractability result [Downey and Fellows, 2013]. HITTING SET is defined as follows: given a ground set X of elements, and a collection C = ¶C1↪ ▷ ▷ ▷ ↪ C`♦ of subsets of X, does there exist a H ⇢ X such that ♣H♣  k and H \ C 6= ; for all C 2 C?

Theorem 3. Checking whether a committee is Pareto optimal under the responsive set extension is W[2]-complete under parameter k, even for dichotomous preferences.

For dichotomous preferences we present a complete characterization of the complexity according to the T opwidth(%) parameter. If Topwidth(%) = 1, then in any Pareto improvement over committee D, any alternative in D that is most preferred by some agent needs to be remain selected, and therefore the problem of checking RS-efficiency is easy. If Topwidth(%) ≥ 3, from Theorem 2, the problem is hard. Remains the case Topwidth(%) = 2.

Theorem 4. For dichotomous preferences, a Pareto improvement over a committee with respect to the responsive set extension can be computed in polynomial time when T opwidth(%)  2.

Proof. Consider a preference profile %= (%1↪ ▷ ▷ ▷ ↪%n) where each %i is dichotomous and verifies Topwidth(%) = 2, and let D 2 Sk(A). For each i 2 N, let (E1 i ↪E2 i ) be the partition associated with %i.

First, if for all i 2 N, E1 i ✓ D, then D is obviously RSefficient. Assume it is not the case, that is, (1) for some i 2 N, E1 i ∩D 6= ;. Let

• ÷ N 0 = ¶i 2 N : E1 i \ D = E1 i ♦, W 0 = [i2N 0E1 i (by construction, W 0 ✓ D), and k0 = ♣W 0 ♣.
• ÷ N 00 = ¶i 2 N ∩ N 0 : E1 i \ (D ∩ W 0 ) 6= ;♦ and A00 = [i2N 00E1 i .

Now, we build a graph G = (V↪ E) with V = ¶v1↪ ▷ ▷ ▷ ↪ vr♦ isomorphic to A00 , and [vp↪ vq] 2 E iff E1 i = ¶ap↪ aq♦ for some i 2 N 00 : each edge of G corresponds to the top two alternatives of some agent, provided one of them is in D∩W 0 . Let ⌧(G) be the size of an optimal vertex cover of G.

We first claim that there is a Pareto improvement over D if and only if one of follows two conditions is satisfied:

• (i) ⌧(G) < k -k0 , or
• (ii) ⌧(G) = k - k0 , and there is an optimal vertex cover of G containing either at least an element of E1 i for some i ◁2 N 0 [N 00 , or two elements of E1 i for some i 2 N 00 .

We first show that (i) and (ii) are sufficient. If (i) holds then take a committee corresponding to a minimum vertex cover of G, add to it the k0 alternatives of W 0 , and add (k-k0 )-⌧(G) alternatives, with at least one in [i(E1 i ∩ D); this is possible because of (1). If (ii) holds, then take a committee corresponding to a minimum vertex cover of G, and add to it the k0 alternatives of W 0 . In both cases, the obtained committee contains E1 i for all i 2 N 0 , contains at least one element of E1 i for all i 2 N 0 , and contains either two elements of E1 i for some i 2 N 00 , or an element of E1 i for some i ◁2 N [ N 00 . Therefore it is a Pareto-improvement over D.

Now, we show that (i) and (ii) are necessary. Let W 2 Sk(A) be a Pareto improvement of D containing a maximum number of alternatives from D. We have the following two properties: W 0 ✓ W and W ∩ W 0 is a vertex cover of G. W 0 ✓ W holds, since otherwise there would be an i 2 N 0 such that W 0 %RS i W does not hold. For similar reasons, C 0 = (W ∩W 0 ) \A00 is a vertex cover of G. If ♣(W ∩W 0 ) \ A00 ♣ < ⌧(G), then by adding to it any set of D∩C 0 of size kk0 -⌧ (G) we obtain a set of size k which constitutes a Pareto improvement of D because now, E1 i ✓W for some i 2 N 00 . If ♣(W ∩W 0 )\A00 ♣ = ⌧(G), then (W ∩W 0 )\A00 =W ∩W 0 and necessarily either E1 i \C 6= ; for some i ◁2 (N 0 [N 00 ) or E1 i ✓ C for some i 2 N 00 .

It remains to be shown that (i) and (ii) can be checked in polynomial time. (i) can be done in polynomial-time because G is bipartite: indeed, by construction, G is two-colorable with color sets A00 \ D and A00 ∩ D, and by K¨onig's theorem, for bipartite graphs, the problem of finding the minimum vertex cover is equivalent to computing a maximum matching, hence solvable in polynomial time. As for (ii), if ⌧(G) = k - k0 , we have to check whether for some optimal vertex cover C of G, either (ii.1) E1 i \C 6= ; holds for some i ◁2 (N 0 [N 00 ), or (ii.2) E1 i ✓ C for some i 2 N 00 . In order to check (ii.1), for each i ◁2 (N 0 [N 00 ) such that there exists x 2 E1 i \A00 , we transform G into a new bipartite graph G¶x♦ where we add a new vertex x0 and an edge [x↪ x0 ]. In order to check (ii.2), for each i ◁2 N 00 , let E1 i = ¶x↪ y♦; we transform G into a new bipartite graph G¶x↪y♦ where we add two new vertices x0 and y0 , and two edges [x↪ x0 ] and [y↪ y0 ]. Finally, we test if ⌧(G) = ⌧(G¶x♦) or if ⌧(G) = ⌧(G¶x↪y♦) for one of these graphs, because all optimal vertex covers of G¶x♦ (respectively G¶x↪y♦) must contain x (respectively ¶x↪ y♦).

Example 2. We illustrate the algorithm in the proof of Theorem 4. Let k = 2 and consider the dichotomous profile, where we specify only the top equivalence class of each agent:

Let D = ¶a↪ b♦. We have N 0 = W 0 = ;, k0 = 0, D ∩ W 0 = ¶a↪ b♦, N 00 = ¶1↪ 2↪ 3♦, and A00 = ¶a↪ b↪ c↪ d♦. We construct the graph G = (V↪E): V = ¶va↪ vb↪ vc↪ vd♦ and E = ¶¶va↪ vc♦↪ ¶vb↪ vc♦↪ ¶vb↪ vd♦♦. We have ⌧(G) = 2 = k-k0 . Now we consider the four graphs G¶d♦, resulting from the addition to G of a new vertex vd0 and edge [vd↪ vd0 ], and G¶a↪c♦, G¶b↪c♦ and G¶b↪d♦: G¶a↪c♦ results from the addition to G of two new vertices va0 ↪ vc0 and edges [va↪ va0 ] and [vc↪ vc0 ], etc. Two of these graphs have an optimal cover of size 2: G¶d♦, with optimal cover ¶vc↪ vd♦, and G¶b↪c♦, with optimal cover ¶vb↪ vc♦. Therefore, ¶c↪ d♦ and ¶b↪ c♦ are RS-Paretoimprovements over ¶a↪ b♦, and ¶a↪ b♦ is not RS-efficient.

G¶d♦

G¶b↪c♦

Note that finding an algorithm that computes a Pareto improvement over a committee can be used to decide whether a given a committee D of size k, is Pareto optimal under the responsive set extension.

Pareto optimality and Strategyproofness We now try to achieve both RS-efficiency and strategyproofness simultaneously. A mechanism is strategyproof if no agent can get a more preferred outcome by misreporting his/her preference.

A naive way of achieving RS-efficiency and Pareto optimality is to enumerate the list of possible winning sets and implement serial dictatorship over the possible outcomes as is done in voting [Aziz et al., 2013b]. However, the number of possible outcomes is exponential and responsive preferences result in a partial order over the possible winning sets and not a complete and transitive order. This problem is solved by Algorithm 1 which can be viewed as a computationally efficient serial dictatorship.

Theorem 5. There exists a linear-time and strategyproof algorithm that returns a committee that is Pareto optimal under the responsive set extension.

Proof. Consider Algorithm 1. We show that at each stage i0 , agent ⇡(i0 ), implicitly refines the set of feasible committees to the maximal set of most preferred outcomes from the set by providing additional constraints. This is true for the base case i0 = 1. Now assume it holds from 1 to i0 . Note that L contains all those alternatives that are strictly less preferred by agents in ¶⇡(1)↪ ▷ ▷ ▷ ↪ ⇡(i0 )♦ than the ones they respectively fixed. Moreover, each agent in ¶1↪ ▷ ▷ ▷ ↪ ⇡(i0 )♦ is indifferent between the alternatives in L. As for ⇡(i0 + 1), he fixes the

Input: (N↪A↪%↪ k↪ permutation ⇡ of N) Output: W 2 Sk(A). 1 L (last set to be refined) -A 2 r (number of alternatives yet to be fixed) - k; W - ; 3 i0 (index of the permutation ⇡) - 1 4 while r 6= 0 or i0 6= n do 5 Agent i = ⇡(i0 ) selects first t equivalence classes such that ♣ Stj=1 Ej i \L♣ ≥ r and ♣ St-1 j=1 Ej i \L♣ < r. 6 W - W [ (St-1 j=1 Ej i \ L) (we say agent i fixes the alternatives in St-1 j=1 Ej i ); 7 r - ♣ Stj=1 Ej i \L♣ - ♣ St-1 j=1 Ej i \L♣ 8 L -Et i ; ri0 - r 9 Increment i0 by one 10 if r > 0 then 11 pick any r alternatives from L and add them to W 12 return W

best ♣ St-1 j=1 Ej⇡(i0+1) \L♣ alternatives in L where t is the value such that ♣(Stj=1 Ej⇡(i0+1) ) \L♣ ≥ ri0 and ♣ St-1 j=1 Ej⇡(i0+1) \ L♣ < ri0 . For Et⇡(i0+1) , the agent only requires that ri0+1 = ♣(St-1 j=1 Ej⇡(i0+1) ) \ L♣ - ♣(St-1 j=1 Ej⇡(i0+1) ) \ L♣ alternatives are selected from his equivalence class Et⇡(i0+1) which is ensured by the definition of the algorithm. It follows from the argument that the returned set is Pareto optimal under the responsive set extension. For strategyproofness, when an agent ⇡(i0 ) turn comes, it only has a choice over fixing the alternatives in L and requiring ri0 alternatives from his equivalence class Et⇡(i0 ) . In this case the algorithm already chooses one of the best possible committees for the agent.

Note that for k = 1, the algorithm is equivalent to serial dictatorship as formalized by Aziz et al. [2013a]. Note that a committee that is Pareto optimal under the responsive set extension may not be a result of serial dictatorship. This holds even for k = 1 and the basic voting setting.

The problem with the serial dictatorship algorithm formalized is that it overly favours the agent that is the first in the permutation. One way to limit his power is to let him choose only dk◁ne alternatives. We note that this attempt at having a fairer extension of serial dictatorship comes at an expense because strategyproofness is compromised. Consider the profile in which 1 has preferences a↪ b↪ c and 2 has preferences a↪ c↪ b. For k = 2, and permutation 12, the outcome is ¶a↪ c♦. But if agent 1 reports b↪ a↪ c, then the outcome is ¶a↪ b♦.

6 Leximax Set Extension

We point out that for dichotomous preferences, the responsive set extension coincides with the leximax set extension. Hence we get a corollary of our results for responsive preferences:

Corollary 1. Checking whether a committee is LX-efficient is coNP-complete, even for dichotomous preferences and T opwidth(%) ≥ 3.

Note that Algorithm 1 returns a LX-efficient committee.

Theorem 6. There exists a linear-time and strategyproof algorithm that returns a LX-efficient committee.

7 'Best' Set Extension

Next, we consider Pareto optimality with respect to B, which has been used for defining many rules (see Section 2).

Theorem 7. Unless P=NP, there is no polynomial-time algorithm to compute a Pareto improvement over a committee with respect to B, even for dichotomous preferences and T opwidth(%) = 2.

Proof. We show that if it is not the case, then we can solve polynomially the vertex cover decision problem. Consider an instance of VERTEX COVER given by a simple graph G = (V↪ E) with V = ¶v1↪ ▷ ▷ ▷ ↪ vq♦ and E = ¶e1↪ ▷ ▷ ▷ ↪ er♦, and an integer k. Assume the existence of a polynomial-time algorithm Algo that computes a Pareto improvement over a committee with respect to B when Topwidth(%)  2: given a profile % and a set of k alternatives W, Algo(%↪W) returns, in time polynomial in ♣ % ♣, Yes if W is Pareto optimal with respect to B, and otherwise returns a k-set U of alternatives which Pareto dominates W. We will now prove by applying at most n times Algo with different inputs that we can decide in polynomial if G has a vertex cover C ✓ V of G with ♣C♣  k. We construct the following profile P :

• ÷ The set of agents is N = ¶1↪ ▷ ▷ ▷ ↪ q+r-k♦, where agent i  r corresponds to edge ei 2 E.
• ÷ Let ei = [u↪ v] 2 E be an edge of G; the preferences of agent i for i = 1↪ ▷ ▷ ▷ ↪ r are:
• ÷ The set of 2q - k alternatives is A = V [ D where D = ¶d1↪ ▷ ▷ ▷ ↪ dq-k♦.

The preferences of the last set of q - k agents ¶r + 1↪ ▷ ▷ ▷ ↪ q + r - k♦ are given by: for i = 1↪ ▷ ▷ ▷ ↪ q - k↪

The reduction is clearly done within polynomial time and the set of preferences given by % are dichotomous.

Consider the following inductive procedure: W0 = V and for i ≥ 1, Wi = Algo (%↪Wi-1) if Wi-1 is not Pareto optimal with respect to B, otherwise we return Wi-1. Let W = Wn-k be the solution output after n - k calls. Because Algo is polynomial, the whole procedure is polynomial.

We claim that G has a vertex cover of size k iff D ✓ W. We will first prove by induction that at each step i, Wi ∩ D is a vertex cover of G. For the initial step, it is valid because V is a vertex cover of G. Assume that it is true for i < n - k and let us prove that Wi+1 ∩ D is a vertex cover of G. If it is not the case, some edge ej = [u↪ v] 2 E is not covered. By assumption, ej is covered by Wi ∩ D. This implies Wi ≻Bj Wi+1, which is a contradiction. Hence, Wi+1 %Bj Wi. From this hypothesis, we deduce D ∩ Wi+1 %Bj D ∩ Wi for j = n + 1↪ ▷ ▷ ▷ ↪ 2n - k with a strict preference for some agent. Equivalently, D∩Wi ⇢ D∩Wi+1. In conclusion, after n-k recursive calls, ♣W ∩D♣  k if and only if D ✓ W.

Theorem 8. Computing a B-efficient committee is NP-hard, even for dichotomous preferences.

Proof. We give a reduction from HITTING SET. Let N = ¶1↪ ▷ ▷ ▷ ↪ `♦, A = X and for each i 2 N, i's dichotomous preferences are i : Ci↪ (X ∩ Ci)▷ If there exists a polynomialtime algorithm to compute a B-efficient committee, it will return a committee in which each agent gets a most preferred alternative if such a committee exists. But such a committee corresponds to a hitting set of size k.

8 'Worst' Set Extension

In contrast to all the other set extensions considered in the paper, Pareto optimality with respect to the 'worst' set extension can be checked in polynomial time.

Theorem 9. There exists a polynomial-time algorithm that checks whether there a committee is W-efficient and computes a Pareto improvement over it if possible.

Proof. Let W 2 Sk(A). For each i 2 N, let Eti i be the least preferred equivalence class such that Eti i \W 6= ;. We want to check whether there is a k-set D of alternatives in which at least some agent i 2 N gets a strictly better outcome and all the other agents get at least as preferred an outcome. We check this as follows. For i 2 N, let Bi = A ∩ (Ski `=ti E` i ) [ Sj2N∩¶i♦ Skj `=tj+1 E` j ). We check whether ♣Bi♣ ≥ k or not. If ♣Bi♣ ≥ k, we know that there exists a subset of Bi, that is strictly more preferred by i 2 N and at least as preferred by each agent. If ♣Bi♣ < k, then this means that a Pareto improvement with i strictly improving is only possible if the

size of the winning set is less than k which is not feasible.

We now consider strategyproofness together with Wefficiency. We first note that Algorithm 1 may not return a W-efficient outcome. However, we construct a suitable strategyproof and W-efficient by formalising an appropriate serial dictatorship algorithm for the worst set extension.

Theorem 10. There exists a linear-time and strategyproof algorithm that returns a W-efficient committee.

Proof. Consider the agents in a permutation ⇡. The set of alternatives A0 is initialized to A. We reduce the set A0 while ensuring that it of size at least k. The next agent i in the permutation comes and deletes the maximum number of least preferred equivalence classes from his preferences and the corresponding alternatives in A0 while ensuring that ♣A0 ♣ ≥ k. Each successive agent in the permutation gets a most preferred outcome while ensuring that agents before him in the permutation get at least as preferred an outcome as before. Thus the algorithm is strategyproof and Pareto optimal with respect to the 'worst' set extension.

9 Conclusions

We considered Pareto optimality in multi-winner voting with respect to a number of prominent set extensions. We presented results on the relations between the notions as well as complexity of computing and verifying Pareto optimal outcomes. Further directions of future work include considering Pareto optimality with respect to other set extensions [Brandt and Brill, 2011].

Acknowledgments

Data61 (formerly known as NICTA) is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program. The authors thank Felix Brandt for useful pointers and comments. J´erˆome Lang and J´erˆome Monnot thank the ANR project CoCoRICo-CoDec.