Multi-Winner Elections: Complexity of Manipulation, Control and Winner-Determination

1 Introduction

Computational aspects of voting have been the focus of much interest, in a variety of fields. In multiagent systems, the attention has been motivated by applications of well-studied voting systems 1 as a method of preference aggregation. For instance, Ghosh et al. [1999] designed an automated movie recommendation system, in which the conflicting preferences a user may have about movies were represented as agents, and movies to be suggested were selected according to a voting scheme (in this example there are multiple winners, as several movies are recommended to the user). In general, the candidates in a virtual election can be entities such as beliefs or joint plans [Ephrati and Rosenschein, 1997].

Different aspects of voting rules have been explored by computer scientists. An issue that has been particularly well-studied is manipulation. The celebrated GibbardSatterthwaite Theorem implies that under any reasonable voting scheme, there always exist elections in which a voter can improve its utility by lying about its true preferences. Nevertheless, it has been suggested that bounded-rational agents may find it hard to determine exactly which lie to use, and thus may give up on manipulations altogether. The first to address this point were Bartholdi, Tovey and Trick [1989a]; Bartholdi and Orlin [1991] later showed that manipulating Single Transferable Vote (STV) is an NP-complete problem. Conitzer, Lang and Sandholm [2003] studied a setting where there is an entire coalition of manipulators. In this setting, the problem of manipulation by the coalition is NP-complete in a variety of protocols, even when the number of candidates is constant.

1 We use the terms "voting schemes", "voting rules", "voting systems", and "voting protocols" interchangeably.

Another related issue that has received some attention is the computational difficulty of controlling an election. Here, the authority that conducts the elections attempts to achieve strategic results by adding or removing registered voters or candidates. Bartholdi, Tovey and Trick [1992] analyzed the computational complexity of these (and other) methods of controlling an election in the Plurality and Condorcet protocols.

The above discussion implies that computational complexity should be considered when contemplating voting systems that are seemingly susceptible to manipulation or control. On the other hand, taking into account computational costs can also lead to negative results. Some sophisticated voting systems, designed to satisfy theoretical desiderata, may be too difficult to use in real-world settings. In other words, there are voting systems where even determining who won the election is an NP-complete problem. Previously known examples include voting schemes designed by Charles Dodgson 2 and Kemeny [Bartholdi et al., 1989b].

Settings where there are multiple winners are inherently different from their single-winner counterparts. A major concern when electing an assembly, for example, might be proportional representation: the proportional support enjoyed by different factions should be accurately represented in the structure of the assembly. In practice, this usually means that the percentage of votes secured by a party is roughly proportional to the number of seats it is awarded.

Some simple multi-winner rules do not guarantee proportional results; these rules include Single Non-Transferable Vote (SNTV), Bloc voting, Approval, and Cumulative voting. More recently, intriguing theoretical voting schemes have been devised with the goal of guaranteeing proportional representation. Two such schemes that have received attention were proposed, respectively, by Monroe [1995], and by Chamberlin and Courant [1983].

In this paper, we augment the classical problems of manipulation and control by introducing multiple winners, and study these problems with respect to four simple but important multi-winner voting schemes: SNTV, Bloc voting, Approval, and Cumulative voting; we find that Cumulative voting is computationally resistant to both manipulation and control. In addition, we characterize the computational complexity of winner determination in some of the intriguing voting schemes that have been suggested in recent years by political scientists.

2 Better known as Lewis Carroll, author of "Alice's Adventures in Wonderland".

2 Multi-Winner Voting Schemes

In this section we discuss several multi-winner voting systems of significance. Although the paper is self-contained, interested readers can find more details in [Brams and Fishburn, 2002].

Let the set of voters be V = {v1, v2, . . . vn}; let the set of candidates be C = {c1, c2, . . . cm}. Furthermore, assume that k ∈ N candidates are to be elected.

We first present four simple voting schemes; in all four, the candidates are given points by the voters, and the k candidates with the most points win the election. The schemes differ in the way points are awarded to candidates.

• Single Non-Transferable Vote (SNTV): each voter gives one point to a favorite candidate.
• Bloc voting: each voter gives one point to each of k candidates.
• Approval voting: each voter can approve or disapprove any candidate; an approved candidate is awarded one point, and there is no limit to the number of candidates a voter can approve.
• Cumulative voting: allows voters to express intensities of preferences, by asking them to distribute a fixed number of points among the candidates. Cumulative voting is especially interesting, since it encourages minority representation and maximizes social welfare [Brams and Fishburn, 2002].

2.1 Fully Proportional Representation

We now describe two theoretical voting schemes that attempt to achieve the ideal of fully proportional representation.

We begin by specifying Monroe's pure scheme [Monroe, 1995]. For each voter v and candidate c, a misrepresentation value μvc is known; 3 this value characterizes the degree to which candidate c misrepresents voter v.

Let S = {S ⊆ C : |S| = k}, the set of all possible subsets of k winners. Let S ∈ S, and let fS : V → S be a function that assigns voters to candidates in S. The misrepresentation score of voter v under fS is μvfS(v). The total misrepresentation of assignment fS is ∑v∈V μvfS(v).

Monroe requires that fS be restricted so that a similar number of voters be assigned to each candidate in S. In other words, each candidate in S must be assigned at least ⌊n/k⌋ voters. We say that such an assignment is balanced. The misrepresentation score of S is the misrepresentation score of fS, where fS : V → S is the assignment with the minimal misrepresentation, subject to the above restriction. The k winners are the set S ∈ S with the lowest misrepresentation score.

3 The misrepresentation values μvc may be naturally derived from ballots cast by the electorate, but we do not go into details as to exactly how this can be done. In any case, it is logical to assume that μvc ∈ {0, 1, . . . ,m}, and we make this assumption throughout the paper.

Chamberlin and Courant [1983] adopt a similar approach; as before, one considers sets S ∈ S and assignments fS. However, Chamberlin and Courant impose no restrictions on the assignments. Therefore, each set S is associated with the assignment fS : V → S that minimizes misrepresentation among all possible assignments. To maintain proportionality, Chamberlin and Courant compensate by using weighted voting in the assembly.

3 Manipulation

A voter is considered to be a manipulator, or is said to vote strategically, if the voter reveals false preferences in an attempt to improve its outcome in the election. Settings where manipulation is possible are to be avoided, as many voting protocols are designed to maximize social welfare, under the assumption that voters reveal their intentions truthfully. Therefore, computational resistance to manipulation is considered an advantage.

In the classical formalization of the manipulation problem [Bartholdi et al., 1989a], we are given a set C of candidates, a set V of voters, and a distinguished candidate p ∈ C. We also have full knowledge of the voters' votes. We are asked whether it is possible to cast an additional vote, the manipulator's ballot, in a way that makes p win the election.

When generalizing this problem for the k-winner case, several formulations are possible. For example, one can ask whether some candidate can be one of the k-winners, or whether it is possible to ensure that a complete set of k winners be elected. We adopt a more general formulation.

Definition 1. In the MANIPULATION problem, we are given a set C of candidates, a set V of voters that have already cast their vote, the number of winners k ∈ N, a utility function u : C → Z, and an integer t ∈ N. We are asked whether the manipulator can cast its vote such that in the resulting election: ∑c∈W u(c) ≥ t, where W is the set of winners, |W| = k.

Remark 1. We make the standard assumption that tiebreaking is adversarial to the manipulator [Conitzer and Sandholm, 2002; Conitzer et al., 2003], i.e., if there are several candidates that perform equally well in the election, the ones with the lower utility will be elected.

Proposition 1. MANIPULATION in SNTV, Bloc voting, and Approval is in P.

Proof. Simple and efficient algorithms exist for MANIPULATION in these three protocols; omitted due to lack of space.

Proposition 2. MANIPULATION in Cumulative voting is NP-complete.

The proof relies on a reduction from one of the most wellknown NP-complete problems, the KNAPSACK problem.

Definition 2. In the KNAPSACK problem, we are given a set of items A = {a1, . . . , an}, for each a ∈ A a weight w(a) ∈ N and a value υ(a), a capacity b ∈ N, and t ∈ N. We are asked whether there is a subset A′ ⊆ A such that ∑a∈A′ υ(a) ≥ t while ∑a∈A′ w(a) ≤ b.

Proof of Proposition 2. The problem is clearly in NP.

To see that MANIPULATION in cumulative voting is NPhard, we prove that KNAPSACK reduces to this problem. We are given an input 〈A, w, υ, b, t〉 of KNAPSACK, and construct an instance of MANIPULATION in Cumulative voting as follows.

Let n=|A|. There are 2n voters: V = {v1, . . . , v2n}, 3n candidates: C = {c1, . . . , c3n}, and n winners. In addition, each voter may distribute b points among the candidates. We want the voters in V to cast their votes in a way that the following three conditions are satisfied:

1. For j = 1, . . . , n, cj has b -w(aj) + 1 points.
2. For j = n+ 1, . . . , 2n, cj has at most b points.
3. For j = 2n+ 1, . . . , 3n, cj has exactly b points.

This can easily be done. Indeed, for i = 1, . . . , n, voter vi awards b -w(ai) + 1 points to candidate ci, and awards its remaining w(ai) - 1 points to candidate cn+i. Now, for i = 1, . . . , n, voter n + i awards all its b points to candidate 2n + i.

We define the utility u of candidates as follows:

The transformation is clearly polynomial, so it only remains to verify that it is a reduction. Assume that there is a subset A′ ⊆ A with total weight at most b and total value at least t. Let C = {cj : aj ∈ A′}. The manipulator awards w(aj) points to each candidate c ∈ C′ , raising the total score of these candidates to b+1. Since initially all candidates have at most b points, all candidates c ∈ C′ are among the n winners of the election. The total utility of these candidates is: ∑c∈C′ u(c) = ∑a∈A′ υ(a) ≥ t (since for all j = 1, . . . , n, u(cj ) = υ(aj )).

In the other direction, assume that the manipulator is able to distribute b points in a way that the winners of the election have total utility at least t. Recall that there are initially at least n candidates with b points and utility 0, and that ties are broken adversarially to the manipulator. Therefore, there must be a subset C′ ⊆ C of candidates that ultimately have a score of at least b + 1, such that their total utility is at least t. Let A′ be the corresponding items in the KNAPSACK instance, i.e., aj ∈ A′ iff cj ∈ C′ . The total weight of items in A′ is at most b, as only b points were distributed among the candidates in C′ by the manipulator, and each cj ∈ C′ initially has b - w(aj) + 1 points. It also holds that the total utility of the items in A′ is exactly the total utility of the candidates in C′ , namely at least t.

4 Control

Some voting protocols can be controlled by the authority conducting the election, which we refer to as the chairman, in the sense that the chairman can change the election's results. Some types of control available to the chairman are adding "spoiler" candidates, disqualifying candidates, registering new voters, or removing voters that were already registered. A study of these issues in the context of two wellknown voting protocols was reported by Bartholdi, Tovey and Trick [1992], who found that control by adding and deleting candidates is NP-hard even in the simple Plurality 4 protocol. Moreover, in most cases the complexity of deleting voters is identical to that of adding voters. Therefore, we focus hereinafter on control by adding voters.

The following formulation of the control (by adding voters) problem appeared in [Bartholdi et al., 1992]: we are given a set C of candidates and a distinguished candidate p ∈ C; a set V of registered voters, and a set V ′ of voters that could register in time for the election. We are also given r ∈ N, and have full knowledge of the voters' votes. We are asked whether it is possible to register at most r voters fromV ′ in a way that makes p win the election.

As in the case of manipulation, we generalize this definition for our multi-winner setting:

Definition 3. In the CONTROL problem, we are given a set C of candidates, a set V of registered voters, a set V ′ of unregistered voters, the number of winners k ∈ N, a utility function u : C → Z, the number of winners we are allowed to register r ∈ N, and an integer t ∈ N. We are asked whether it is possible to register at most r voters from V ′ such that in the resulting election, ∑c∈W u(c) ≥ t, where W is the set of winners, |W| = k.

Remark 2. Again, we assume that ties are broken adversarially to the chairman.

Proposition 3. CONTROL in Bloc voting, Approval, and Cumulative voting is NP-complete.

Proof. By reduction from MAX k-COVER; 5 omitted due to lack of space.

Proposition 4. CONTROL in SNTV is in P.

Proof. We describe an algorithm, CONTROL-SNTV, that efficiently decides CONTROL in SNTV. Informally, the algorithmworks as follows. It first calculates the number of points awarded to candidates by voters in V . Then, at each stage, the algorithm analyzes an election where the l top winners in the original election remain winners, and attempts to select the other k - l winners in a way that maximizes utility. This is done by setting the threshold to be one point above the score of the (l + 1)-highest candidate; the algorithm pushes the scores of potential winners to this threshold.

A formal description of CONTROL-SNTV is given as Algorithm 1. The procedure PUSH works as follows: its first parameter is the threshold thr, and its second parameter is the number of candidates to be pushed, pushNum. The procedure also has implicit access to the input of CONTROLSNTV, namely the parameters of the given CONTROL instance. PUSH returns a subset V ′′ ⊆ V ′ to be registered. We say that the procedure pushes a candidate c to the threshold

4 The Plurality protocol is identical to SNTV, when there is a single winner.

5 See [Feige, 1998] for a definition and analysis of this problem.

Algorithm 1 Decides the CONTROL problem in SNTV.

1: procedure CONTROL-SNTV(C, V, V ′ , k, u, r, t) 2: s[c] ← |{v ∈ V : v votes for candidate c}| 3: Sort candidates by descending score ▷ Break ties by ascending utility 4: Let the sorted candidates be {ci1 , . . . , cim } 5: for l = 0, . . . , k do ▷ Fix l top winners 6: V ′′ ←PUSH(s[cl+1] +1, k - l) ▷ Select other winners; see details below 7: ul ← utility from election where V ′′ are registered 8: end for 9: if maxl ul ≥ t then return true 10: else 11: return false 12: end if 13: end procedure

if exactly thr - s[c] voters v ∈ V ′ that vote for c are registered. In other words, the procedure registers enough voters from V ′ in order to ensure that c's score reaches the threshold. PUSH finds a subset C′ of candidates of size at most pushNum that maximizes ∑c∈C u(c), under the restriction that all candidates in C′ can be simultaneously pushed to the threshold by registering a subset V ′′ ⊆ V ′ s.t. V ′′ ≤ r. The procedure returns this subset V ′′ .

Now, assume we have a procedure PUSH that is always correct (in maximizing the utility of at most k - l candidates it is able to push to the threshold s[cl+1] + 1, while registering no more than r voters) and runs in polynomial time. Clearly, CONTROL-SNTV also runs in polynomial time. Furthermore:

Lemma 1. CONTROL-SNTV correctly decides the CONTROL problem in SNTV.

Proof. Let W = {cj1 , . . . , cjk } be the k winners of the election that does not take into account the votes of voters in V ′ (the original election), sorted by descending score, and for candidates with identical score, by ascending utility. Let W ∗ = {c∗j1 , . . . , c∗jk } be the candidates that won the controlled election with the highest utility, sorted by descending score, then by ascending utility; let s∗ [c] be the final score of candidate c in the optimal election. Let min be the smallest index such that cjmin /∈ W ∗ (w.l.o.g. min exists). It holds that for all candidates c ∈ W ∗ , s∗ [c] ≥ s[cjmin ]. Now, we can assume w.l.o.g. that if c ∈ W ∗ and s∗ [c] = s[cjmin ] then c ∈ W (and consequently, c = cjq for some q < min). Indeed, it must hold that u[c] ≤ u[cjmin ] (as tie-breaking is adversarial to the chairman), and if indeed c /∈ W even though c ∈ W ∗ , then the chairman must have registered voters that vote for c, although this can only lower the total utility.

It is sufficient to show that one of the elections that is considered by the algorithm has a set of winners with utility at least that of W ∗ . Indeed, let W ′ = {cj1 , . . . , cjmin-1 } ⊆ W; all other k - min + 1 candidates c ∈ W ∗ \ W ′ have s[c] ≥ s[cjmin ] + 1. The algorithm considers the election where the first min - 1 winners, namely W ′ , remain fixed, and the threshold is s[cjmin ]+1. Surely, it is possible to push all the candidates in W ∗ \ W ′ to the threshold, and in such an election, the winners would be W ∗ . Since PUSH maximizes the utility of the k -min + 1 candidates it pushes to the threshold, the utility returned by PUSH for l = min-1 is at least as large as the total utility of the winners inW ∗ .

It remains to explain why the procedure PUSH can be implemented to run in polynomial time. Recall the KNAPSACK problem; a more general formulation of the problem is when there are two resource types. Each item has two weight measures, w1 (ai) and w2 (ai), and the knapsack has two capacities: b1 and b2 . The requirement is that the total resources of the first type used do not exceed b1 , and the total resources of the second type do not exceed b2 . This problem, which often has more than two dimensions, is called MULTIDIMENSIONAL KNAPSACK. PUSH essentially solves a special case of the two-dimensional knapsack problem, where the capacities are b1 = r (the number of voters the chairman is allowed to register), and b2 = pushNum (the number of candidates to be pushed). If the threshold is thr, for each candidate cj that is supported by at least thr - s[cj] voters in V ′ , we set w1 (aj) = thr - s[cj ], w2 (aj) = 1, and υ(aj) = u(cj). The MULTIDIMENSIONAL KNAPSACK problem can be solved in time that is polynomial in the number of items and the capacities of the knapsack [Kellerer et al., 2004] (via dynamic programming, for example). Since in our case the capacities are bounded by m and |V ′ |, PUSH can be designed to run in polynomial time.

5 Winner Determination

Some complex voting schemes are designed to be theoretically appealing in the sense that they satisfy some strict desiderata. Unfortunately, it might be the case that an attractive voting scheme is so complicated that even identifying the winners is an NP-hard problem. This is a major issue, especially when one considers using such a protocol for real-life elections, as elections of this kind might always need to be resolved within a reasonable time frame. 6 Notice that in SNTV, Bloc Voting, Approval, and Cumulative Voting, it is clearly easy to tell who the winners are. In this section, however, we focus on the complex schemes introduced in Section 2.1.

Definition 4. In the WINNER-DETERMINATION problem, we are given the set of voters V , the set of candidates C, the number of winners k ∈ N, misrepresentation values μvc ∈ {0, 1, . . . ,m}, and t ∈ N. We are asked whether there exists a subset S ⊆ C such that |S| = k, with misrepresentation at most t.

Remark 3. Determining the set of winners is clearly harder than the above decision problem, as the set of winners minimizes misrepresentation.

6 Thus the negative repercussions of a winner determination scheme being NP-hard are even more pronounced than the positive repercussions of manipulation being NP-hard; in the latter case a voting scheme might, unacceptably, still be susceptible to manipulation in the average case [Procaccia and Rosenschein, 2006].

Remark 4. For ease of exposition, we shall assume that n/k is an integer. This does not limit the generality of our results, as otherwise it is possible to pad the electorate with voters v such that μvc = 0 for all c ∈ C.

Theorem 5. The WINNER-DETERMINATION problem in Monroe's scheme and in the Chamberlin-Courant scheme is NP-complete, even when the misrepresentation values are binary.

Proof. By reduction from MAX k-COVER; omitted due to lack of space.

Our hardness results relied on the implicit assumption that the number of winners k is not constant (in the previous sections as well). In the context of the WINNERDETERMINATION problem, we are also interested in a setting where the number of winners is constant, as this is sometimes the case in real-life elections: the electorate grows, but the size of the parliament remains fixed.

Proposition 6. When the number of winners satisfies k = O(1), the WINNER-DETERMINATION problem in Monroe's scheme and in the Chamberlin-Courant scheme is in P.

Proof. Clearly the WINNER-DETERMINATION problem in the Chamberlin-Courant scheme can be solved efficiently when k = O(1), as the size of the set S, the set of subsets of candidates with size k, is polynomial in m. For a given S ∈ S, finding the assignment fS that minimizes misrepresentation in this scheme is simple: each voter v is assigned to argminc∈C μvc.

In Monroe's scheme, by a similar consideration, it is sufficient to produce a procedure that efficiently computes the misrepresentation score of every S ∈ S, i.e., finds a balanced assignment that minimizes misrepresentation in polynomial time.

We analyze a procedure that maintains at each stage a balanced assignment, and iteratively decreases misrepresentation. 7 Changes in the assignment are introduced by cyclically right-shifting (c.r.s.) sets of voters: each voter in a set A = {vi1 , vi2 , . . . , vil } is shifted to the candidate that is assigned to its successor; the assignment remains balanced as the last voter is assigned to the first candidate. In more detail, if the current assignment is fS, the algorithm singles out a set of voters A = {vi1 , vi2 , . . . , vil }, l ≤ k, and modifies the assignment by defining the next assignment f ′S as follows:

The procedure is formally described in Algorithm 2. It terminates after at most nm repetitions of the iterative step: at each iteration, the total misrepresentation decreases by at least 1, since the μvc are integers. On the other hand, the total misrepresentation cannot decrease below 0, and is initially at most n · maxv,c μvc ≤ nm. Moreover, the iterative step of the algorithm can be calculated efficiently: since k is Algorithm 2 Finds a balanced assignment that minimizes misrepresentation.

7 It is also possible to derive an efficient algorithm by applying bipartite matching algorithms to an appropriate graph, but the solution given here is self-contained.

1: procedure ASSIGN(S) 2: fS ← arbitrary assignment of n/k voters to each candidate in S 3: loop 4: if ∃A ⊆ V s.t. |A| ≤ k ∧ c.r.s. A strictly decreases misrepresentation then 5: update fS by performing the shift ▷ According to Equation (1) 6: else 7: return fS 8: end if 9: end loop

• 10: end procedure

constant, the number of possible cycles of length at most k is polynomial in n. We have that the complexity of WINNERSELECTION in Monroe's scheme is polynomial - provided we are able to show that the procedure works!

Lemma 2. ASSIGN returns an optimal assignment.

Proof. Consider a scenario where the procedure reaches the iterative step, but the current assignment is not optimal. We must show that the algorithm does not terminate at this point. Indeed, let f ∗ S : V → S be a fixed optimal assignment. We consider the voters v such that fS(v) = f ∗ S (v) to be placed, and the other voters to be misplaced. Assume without loss of generality that f ∗ S minimizes the number of misplaced voters among all optimal assignments.

We claim that there is a set of l ≤ k voters that can be cyclically right-shifted in a way that places all l voters. Let vi1 be a misplaced voter. In order to place it, it has to be assigned to the candidate f ∗ S (vi1 ). Thus, one of the voters that fS assigns to f ∗ S (vi1 ) must be misplaced, otherwise fS is not balanced; call this voter vi2 . vi2 can be placed by uprooting a voter vi3 assigned to f ∗ S (vi2 ). Iteratively repeating this line of reasoning, there must at some stage be a voter vid′ , d′ ≤ k, such that f ∗ S (vid′ ) = fS(vid ) for some d < d′ ; this is true, since there are only k distinct candidates in S. Hence, the voters {vid , vid+1 , . . . , vid′ } can be cyclically right-shifted in a way that places all d′ - d + 1 = l ≤ k voters.

For any set of voters that can be placed by cyclic rightshifting, the shift must strictly decrease misrepresentation. Otherwise, by cyclically left-shifting the same set in f ∗ S , we can obtain a new optimal and balanced assignment, in which more voters are placed compared to f ∗ S ; this is a contradiction to our assumption that f ∗ S minimizes the number of misplaced voters.

It follows that there must be a set of at most k voters such that cyclically right-shifting the set strictly decreases the misrepresentation. Therefore, the procedure does not terminate prematurely.

The proof of Proposition 6 is completed.

6 Conclusions

Table 1 summarizes the complexity of manipulation and control, 8 with respect to four protocols: SNTV, Bloc voting, Approval voting, and Cumulative voting. Of the four protocols, the only one that is computationally resistant to both manipulation and control is Cumulative voting. This protocol also has other advantages: it allows voters to express the intensities of their preferences, and encourages proportional results (albeit, without guaranteeing them). Therefore, Cumulative voting seems especially suitable as a method to aggregate agents' preferences.

One must remember in this context that NP-hardness may not be a good enough guarantee of resistance to manipulation or control: an NP-hard problem has an infinite number of hard instances, but it may have many more easy instances. Indeed, Procaccia and Rosenschein [2006] show that a specific family of voting protocols is susceptible to coalitional manipulation in the average-case, although the problem is hard in the worst-case. Nevertheless, NP-hardness of manipulation or control should certainly be a consideration in favor of adopting some voting protocol.

While high complexity of manipulation or control in a voting scheme is interpreted positively, high complexity of winner determination is a major consideration against the scheme, and may in fact preclude its use in real-life settings. Winner determination is NP-complete with respect to the theoretical voting schemes proposed by Monroe, and by Chamberlin and Courant. Monroe's scheme has received some attention in recent years. In particular, it has been shown that an election can be resolved with integer programming [Potthoff and Brams, 1998]. Unfortunately, solving an integer program is still difficult; this formulation does not even guarantee an efficient solution when the number of winners is constant. Such a solution is, however, given by Proposition 6. This implies that it is perhaps possible to use the scheme in settings where the size of the assembly is very small compared to the size of the electorate.

7 Acknowledgment

This work was partially supported by grant #039-7582 from the Israel Science Foundation.