Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard

1 Introduction

In their recent overview on "AI's war on manipulation" Faliszewski and Procaccia [2010] write "An enigmatic open problem is the complexity of Unweighted Coalitional Manipulation under Borda." Here, we settle this open problem by showing NP-hardness for UNWEIGHTED COALITIONAL MANIPULATION UNDER BORDA, 1 which we subsequently refer to as BORDA MANIPULATION. Informally speaking, BORDA MANIPULATION asks whether under the Borda rule (see Section 2 for a formal definition) a distinguished candidate can be made a winner by adding a certain number of manipulative votes (called manipulators).

Previous work. There is a large amount of work for over two decades concerning the study of the computational complexity of manipulation in elections [Faliszewski and Procaccia, 2010; Faliszewski et al., 2010]. Hence, here we only highlight few previous publications related to BORDA MANIPULATION. For one manipulator, the problem can be easily solved in polynomial time [Bartholdi III et al., 1989]. Zuckerman et al. [2009] showed that for BORDA MANIPULATION a greedy algorithm can always find a set of x manipulators if the given input allows x - 1 manipulators to make a distinguished candidate win. In other words, this means that the optimization version of BORDA MANIPULATION is polynomial-time approximable with an additive error one. Regarding the computational complexity of UNWEIGHTED COALITIONAL MANIPULATION for scoring rules in general, there is only one NP-hardness result for an artificially constructed scoring rule [Xia et al., 2010]. Similarly to our NP-hardness result it is based on an NP-hard scheduling problem. By way of contrast, WEIGHTED COALITIONAL MANIPULATION UNDER BORDA is known to be NP-hard even for (at least) three candidates [Conitzer et al., 2007; Hemaspaandra and Hemaspaandra, 2007].

1 The same result was independently announced by Davies et al. [2011].

Regarding practical relevance, there is evidence that BORDA MANIPULATION "usually" is an easy-to-solve problem.This is justified by experimental work [Davies et al., 2010] as well as by considering some forms of average case analysis [Procaccia and Rosenschein, 2007; Xia and Conitzer, 2008].

Finally, we mention that BORDA MANIPULATION is fixedparameter tractable with respect to the number of candidates, that is, it can be solved in a running time whose exponential part only depends on a computable function in the number of candidates. This is a direct consequence of some integer linear programming formulation in combination with a result of Lenstra [1983] for more general problems (see e.g. [Betzler et al., 2009; Dorn and Schlotter, 2010]).

Our results. Our central result is to show that BORDA MANIPULATION is NP-hard even in case of three input votes and two manipulators. The key to prove this result is to devise a polynomial-time many-one reduction from a "close" NP-hard problem from scheduling theory. The problem is called 2-NUMERICAL MATCHING WITH TARGET SUMS and its NP-hardness has been proven by Yu et al. [2004]. Notably, Xia et al. [2010] used a general version of this problem for their already mentioned NP-hardness result for an "artificial" scoring rule. We also show that BORDA MANIPULATION remains NP-hard not only for three input votes but also for any other number greater than three. Moreover, we provide a close analysis of our reduction and reveal that it requires very special "settings" in order to work, partially explaining why attempts to prove NP-hardness have failed so far. In particular, our findings also make clear that the (worstcase) NP-hardness of BORDA MANIPULATION has little to say concerning the practical feasibility of manipulating Borda elections (also see Walsh [2010] for making this point in a more general way).

2 Preliminaries and basic observations

An election (V,C) consists of a multiset V of votes and a set C of candidates (or alternatives). A vote is a linear order (that is, a transitive, antisymmetric, and total relation) on C. The Borda voting rule determines a winner as follows. In every vote v, the best candidate is at position 1 and the leastliked candidate is at position |C|. For every vote v, the candidate at position i is assigned |C| - i points, that is, the score of c in v is

Each candidate with the highest total score is a Borda winner, that is, we mainly focus on the case that there may be several co-winners. Moreover, let s(V, c) := ∑v∈V s(v, c) denote the score of candidate c under all votes in V .

The UNWEIGHTED COALITIONAL MANIPULATION problem for Borda (BORDA MANIPULATION for short) is defined as follows.

Input: An election (V,C), a distinguished candidate c⋆ ∈ C, and a positive integer t. Question: Is there a multiset W (called coalition) consisting of t votes over C such that c⋆ is a Borda

winner of (V ∪W,C)?

We denote the votes from V as nonmanipulative and the votes fromW as manipulative votes. Without loss of generality, we assume that c⋆ takes the first position in every vote of W. Regarding the nonmanipulative votes, one is mainly interested in the scores of the candidates. To this end, we introduce the following notion (analogously to [Davies et al., 2010, Definition 1]):

For an election E = (V, C) with C := {c⋆ , c1, . . . , cm} and coalition size t, the gap of candidate ci, 1 ≤ i ≤ m, is

If the context is clear, we refer to the gap of candidate ci simply by gi. Intuitively, gi denotes the number of points that ci can make within W such that c⋆ is still a winner. Throughout the paper, we assume that g1 ≤ g2 ≤ . . . ≤ gm. Then, the following necessary condition for a yes-instance is easy to see [Davies et al., 2010, Observation 1]. In a yes-instance, for j ∈ {1, . . . ,m},

since the candidates assigned to the last j positions of a vote make together j(j - 1)/2 points.

A crucial concept used for our NP-hardness proof regards tightness with respect to an index j, that is, one has ∑ji=1 gi = t · j(j - 1)/2. This leads to the following easyto-verify observation.

Observation 2.1 If an instance is tight with respect to an index j ∈ {1, . . . ,m}, then, in every solution, the candidates c1, . . . , cj take the last j positions in every manipulative vote and s(W, ci) = gi for every i ∈ {1, . . . , j}.

3 The NP-hardness proof

In the first subsection, we show that BORDA MANIPULATION is NP-hard with two manipulative and three nonmanipulative votes. In the second subsection, we then discuss to which other settings this hardness proof can be extended.

3.1 Two manipulators and three input votes

Yu, Hoogeveen & Lenstra [2004, Theorem 23] provided a very sophisticated proof that the following special case of NUMERICAL MATCHING WITH TARGET SUMS is NPcomplete. 2

2-NUMERICAL MATCHING WITH TARGET SUMS (2NMTS)

Input: A sequence a1, . . . , ak of positive integers with ∑ki=1 ai = k(k + 1) and 1 ≤ ai ≤ 2k for 1 ≤ i ≤ k.

Question: Are there two permutations ψ1 and ψ2 of the integers 1, . . . , k such that ψ1(i) + ψ2(i) = ai for 1 ≤ i ≤ k?

Throughout the paper, we assume that a1 ≤ . . . ≤ ak. We devise a polynomial-time many-one reduction from 2NMTS to show that BORDA MANIPULATION is NP-hard in case of two manipulative and three nonmanipulative votes. We first describe the main idea based on specific gap values and the manipulative votes and then show how these gap values can be obtained by setting the nonmanipulative votes accordingly.

Consider an arbitrary instance a1, . . . , ak of 2NMTS. Assume that one can construct a BORDA MANIPULATION instance (V,C, c⋆ , 2) with C = {c⋆ , c1, . . . , ck} such that gap gi = 2k-ai for every i, 1 ≤ i ≤ k. Then, the constructed instance is a yes-instance of BORDA MANIPULATION if and only if the 2NMTS instance is a yes-instance: Given a solution for the 2NMTS instance, a solution for the BORDA MANIPULATION instance can be obtained as follows. Let c⋆ take the first positions in the manipulative votes. For every integer i, set the corresponding candidate ci to position ψ1(i)+1 in the first manipulative vote and to position ψ2(i) + 1 in the second manipulative vote. In this way, every candidate ci makes 2k + 2 - ai - 2 = gi points in W and c⋆ wins.

To see the reverse direction, first note that

Hence, the BORDA MANIPULATION instance is tight with respect to k, implying that every candidate ci makes exactly gi points in a solution (see Observation 2.1). Let p1(i) and p2(i) denote the positions of ci in the two manipulative votes, respectively. Since ci makes exactly gi points, p1(i) + p2(i) = ai + 2 and hence setting ψ1(i) := p1(i) - 1 and ψ2(i) := p2(i) - 1 results in a solution for 2NMTS.

2 Yu et al. used a slightly different problem notion which requires ψ1(i) + ψ2(i) + ui = e while we rephrase this by setting ai := e - ui (resulting in 1 ≤ ai ≤ 2k due to some side constraints in the definition of Yu et al.). Moreover, they denote the problem as RN3DM.

It remains to construct a set of nonmanipulative votes such that the gap gi for every candidate ci is realized, that is, the difference between the scores of c⋆ and ci in the nonmanipulative votes is set such that ci can make at most gi points in the manipulative votes without beating c⋆ . We show NPhardness even in case of having three nonmanipulative and two manipulative votes. To realize this, we will introduce a further set D of "dummy" candidates (described later) such that we end up with a new candidate set C ⊎ D with cardinality m + 1 (which will be specified later in the proof). The tightness with respect to k will ensure that the candidates from C \ {c⋆ } must be at the last k positions in the manipulative votes in every solution.

To define the three nonmanipulative votes we will first fix the positions of the candidates from C and then fill the remaining positions with dummy candidates from D. To assign positions to the candidates from C, we rename the candidates c1, . . . , ck as follows. In an instance, several candidates might have the same gap value. Let G1, . . . , Gh denote the different gap values. Consider a gap value Gj , 1 ≤ j ≤ h, that occurs sj times; that is, there are sj indices such that the corresponding gap values equal Gj . Denote the sj corresponding candidates by c1j , . . . , csj j . Let z be the maximum over all sj, that is, the maximum number of occurrences of one gap value. Then, let D consist of 8zk new candidates. This means that

and we end up with m+ 1 candidates in total. To ease the representation, we assume that m is divisible by four 3 . Then, the distinguished candidate c⋆ is assigned to position 3m/4 in every nonmanipulative vote.

Moreover, for candidate cxj , 1 ≤ j ≤ h, 1 ≤ x ≤ sj, we compute the number b(cxj ) of candidates with "smaller" indices as follows

Then, the positions of every candidate cxj in the three nonmanipulative votes are as follows.

• First vote: cxj is assigned to position m/4-2xk +Gj.
• Second vote: cxj is assigned to position b(cxj ) + 1.

· Third vote: cxj is assigned to position 2xk-(b(cxj )+1). We first show that every assigned position is within the range of 1 and m + 1. Let p denote the position assigned to cxj in the first vote. Since x ≤ z and m = 8zk + k, one has p > 0. Since there are at most k different gap values, one has Gj ≤ k, and hence x ≥ 1 implies p < m/4. Regarding the second and the third vote, the required range follows directly from the conditions 0 ≤ b(cxj ) ≤ k - 1 and x ≥ 1. More specifically, all assigned positions are even smaller than m/4.

3 This is no restriction. Since in the following we will also need that |D| = 8zk is divisible by three, we sketch how to construct an equivalent instance of 2NMTS such that k (and thus also m and |D|) are divisible by 12 as follows. Let p := k mod 12. Add the target sums ak+1, . . . , ak+p with ak+i = 2(k + i). Then, it is easy to verify that this results in a valid new instance. Moreover, the new instance is a yes-instance if and only if the old instance is a yes-instance. To establish the equivalence the crucial idea is that in solutions for the new and the old instance the old target sums correspond to the same positions while every new ak+i must correspond to position k + i in both permutations of the new instance. This is easy to observe for ak+p since the only possibility to build the target sum of 2(k + p) is to choose the position k + p twice and this can be inductively shown for every other ak+i with p > i ≥ 1.

Furthermore, we show that in one vote every position is assigned to at most one candidate from C. For the second and the third vote two candidates from C \ {c⋆ } do not coincide because of the order induced by the function b. Moreover, in all three votes, c⋆ appears at position 3m/4 while the other candidates take a position smaller than m/4 (see above). In the first vote, if two candidates from C have the same gap value, then they must have different x-indices and hence different positions. Two candidates with different gap values do clearly assume different positions when having the same xindex and every candidate with other x-index is more than 2k > Gj positions away (for all j). The score of cxj in the three nonmanipulative votes is

Since c⋆ makes 2m points in the manipulative votes and 3 · m/4 + 3 points in the nonmanipulative votes, the gap of candidate cxj is Gj, the gap value required for every candidate cxj .

Finally, we describe how to fill the remaining positions, that is, positions that are not already assigned to candidates from C, with the dummy candidates from D. To this end, we partition D into three subsets D1,D2, and D3 of equal size (assuming that |D| divisible by three; see second footnote). Then, in the first vote one has D1 > D2 > D3, in the second vote D2 > D3 > D1, and in the third vote D3 > D1 > D2, where Di > Dj means that every candidate di ∈ Di has a smaller position than every candidate dj ∈ Dj . Regarding the internal order of the candidates fromD1 := {d1, . . . , dl}, we assume that for every i ∈ {1, . . . , l - 1}, we have di > di+1 in the first vote and di+1 > di in the second vote, and an arbitrary order in the third vote. Since every di fromD1 in the first and the second vote together makes at most m+1 points (due to the reverse orders) and in the third vote the |D|/3 candidates from D3 have smaller positions, every candidate from D1 makes at most

points, using that |D| = m - k. The internal order of the candidates from D2 and D3 can be fixed analogously, resulting in the same upper bound for their scores. We show that every candidate d ∈ D can make at least m+ k points in the manipulative votes and is still beaten by c⋆ :

since k = m/(8z + 1) ≤ m/9 and hence 2k/3 ≤ 2m/27 < m/12. It follows that in the manipulative votes the candidates from D can assume all positions from 2 to |D| + 1

without beating c⋆ (by putting them in arbitrary order in the first vote and in the reverse order in the second vote). Moreover, because of the tightness with respect to k, the candidates c1, . . . , ck must be assigned to the last k positions in every possible solution (see Observation 2.1).

Altogether, since BORDA MANIPULATION clearly is in NP, one arrives at the following.

Theorem 3.1 BORDA MANIPULATION is NP-complete for three nonmanipulative and two manipulative votes.

Note that for the unique-winner case, that is, a candidate is a Borda winner only if it makes strictly more points than every other candidate, the construction can easily modified by setting c⋆ to position 3m/4 - 1 in the first nonmanipulative vote. Then, since c⋆ makes one point more in the nonmanipulative votes, the gap values remain the same and one can argue in complete analogy.

3.2 Other NP-hard cases

In the previous subsection, we showed NP-hardness for BORDA MANIPULATION in case of three nonmanipulative and two manipulative votes. In this section, we discuss further settings to which this result can be extended.

First, the NP-hardness reduction described in Subsection 3.1 can be extended to any number of nonmanipulative votes greater than three.

Proposition 3.2 For two manipulative and more than three nonmanipulative votes BORDA MANIPULATION remains NP-hard.

Proof. (Sketch) For four nonmanipulative votes one can modify the construction from Subsection 3.1 roughly as follows.

• In the second vote assign candidate cxj to position 2b(cxj ) + 2 while c⋆ remains at the old position.
• In the (new) fourth vote let c⋆ be at position k + 1 and cxj at position k - b(cxj ).

Then, the gap values for cxj remains the same since it "loses" b(cxj )+1 points against c⋆ in the second vote but wins b(cxj )+ 1 points against c⋆ in the fourth vote. The dummy candidates can be adapted to this case appropriately.

Moreover, every other number of manipulative votes can be achieved by adding pairs of any vote and its "reversal" without changing the relative scores. □

Second, we briefly discuss the case a coalition size greater than two. Yu [1996] was convinced to have a proof for the conjecture that the construction of Yu et al. [2004] can be adapted so that it yields NP-hardness of d-NUMERICAL MATCHING WITH TARGET SUMS for any fixed d ≥ 3 where d denotes the number of permutations. 4 If the conjecture holds, arguments analogous to the one in Subsection 3.1 would imply that for any fixed coalition size d ≥ 2, BORDA MANIPULATION is NP-hard.

4 Yu passed away in 2002 and so this conjecture was not proven until now. Since the construction used for 2NMTS is already very sophisticated, this seems to be a demanding task.

4 Amore refined look at the reduction

The NP-hardness of BORDA MANIPULATION stands in sharp contrast to the problem being easy to solve in practice [Davies et al., 2010]. Moreover, in probabilistic settings, it is provably often polynomial-time solvable [Procaccia and Rosenschein, 2007; Xia and Conitzer, 2008]. In contrast to study ways of assessing "average hardness", in the following we pursue the approach of "deconstructing intractability" [Niedermeier, 2010]. To this end, we investigate the structure of instances resulting from the NP-hardness reduction (going back to the NP-hardness proof of 2NMTS). We reveal that the instance resulting from the reduction does not resemble realistic settings. Clearly, this does not directly provide any information about instances that are not obtained by the reduction but nevertheless it helps on the way to identify and characterize "easy" instances. Moreover, this also helps to understand what makes the problem difficult and leads the way to interesting questions for future research.

The NP-hardness proof for BORDA MANIPULATION relies on a "series" of polynomial-time many-one reductions starting from the "classical" strongly NP-complete 3-PARTITION problem.

Input: A multiset of 3q positive integers X = {x1, . . . , x3q} and a positive integer b such that b < xj < 2b for j ∈ {1, . . . , 3q} and ∑3q j=1 xj = 4qb. Question: Is there a partition of X into k disjoint subsets X1, . . . ,Xq such that ∑xj∈Xi xj = 4b for i ∈ {1, . . . , q}?

More specifically, 3-PARTITION is reduced to a scheduling problem which in turn can be reduced to 2NMTS [Yu et al., 2004] and which then can be reduced to BORDA MANIPULATION (see the proof of Theorem 3.1).

A BORDA MANIPULATION instance resulting from the reductions is as follows. The number k of nondistinguished candidates is 4q2 b+4qb in the construction resulting from [Yu et al., 2004]. Herein, following Subsection 3.1, k denotes the number of integers of the 2NMTS instance. We omit the dummy candidates from further consideration (since they are only an auxiliary tool to show NP-hardness for a constant number of nonmanipulative votes). Moreover, the corresponding gap values are as follows. There are

• 4q2 b candidates with gap k + 4b + 1,
• 4qb - 3q candidates with gap k - 4qb - 2, and
• one candidate with gap k - 4qb - 2 + xj for every integer xj from the 3-PARTITION instance with xj < 2b.

In the constructed instance the gaps imply that the distinguished candidate has a strictly smaller score than every other candidate in the nonmanipulative votes. Note that, although very restrictive, this "requirement" in general does not lead to NP-hardness: An instance with 2k > gi ≥ k + 1 for every i ∈ {1, . . . , k} allows for a trivial solution although the distinguished candidate makes less points than every other candidate in the nonmanipulative votes (by setting the candidates in an arbitrary order in the first manipulative vote and the reverse order in the second vote). This observation leads to the following question. Call a candidate ci a strong opponent if gi < k + 1. Moreover, let ns denote the number of strong opponents. Now, the question arises whether BORDA MANIPULATION is fixed-parameter tractable with respect to ns.

Note that in the given construction the number of strong opponents exceeds the number of elements from the 3PARTITION instance and hence the reduction does not show "fixed-parameter intractability" with respect to ns.

In the remainder of this section, we discuss another property of the reduction that might be unlikely to hold in realistic settings and whose "relaxation" leads to a sufficient condition for an instance being a yes-instance.

Relaxing Tightness. One crucial property for showing the hardness of 2NMTS and BORDA MANIPULATION was that there is an index j of "unbounded" size such that ∑ji=1 gi = j(j - 1), while for almost all indices j ′ < j it holds that ∑j ′ i=1 gi > j ′ (j ′ - 1). An instance getting tight (only) for a large number of candidates seems unlikely for realistic settings. In the following, we discuss aspects of "relaxing" or "strengthening" the tightness requirements, ending up with cases for which BORDA MANIPULATION for two manipulative votes is easy to solve.

First, note that when an instance is tight for every index i, then it can be solved by simply putting ci to position |C| - i in every vote. This observation can be extended as follows. Let t1 ≤ . . . ≤ tx denote the x indices for which tightness holds.

Observation 4.1 BORDA MANIPULATION is fixedparameter tractable with respect to the parameter max1≤i<x{ti+1 - ti}.

Observation 4.1 follows directly from the fact that the candidates corresponding to the gaps between two tight indices must also be in the corresponding position range in every solution and for every such "range" one can apply a simple ILPformulation from which fixed-parameter tractability follows via a result from Lenstra [1983].

Second, we describe a condition relaxing the tightness for all indices that leads to a sufficient condition for a yesinstance of BORDA MANIPULATION. Recall that for the gaps we assume that gi ≤ gi+1 for i ∈ {1, . . . ,m- 1} and nondistinguished candidates c1, . . . , cm.

Proposition 4.2 For a BORDA MANIPULATION instance with ∑ji=1 gi ≥ 1.5 · j(j - 1) for all 1 ≤ j ≤ m, two manipulative voters can always make the distinguished candidate win.

Proof. We show that under the given condition a simple greedy strategy always leads to a solution: In the first manipulative vote, order the candidates according to their gap values in decreasing order (ties are broken arbitrarily). More specifically, the first position is assigned to c⋆ , the second position to cm, and so on (see Table 1). 5

We show by contradiction that there is a candidate cj such that cj can take the second position (that is, the next position after c⋆ ) in the second manipulative vote without beating c⋆ ; in other words, gj ≥ m + j - 2. Now, assume that such an index j does not exist. This implies gj < m+ j - 2 for every j. Then,

a contradiction to the condition of the proposition.

Now, the second manipulative vote can be "filled" as follows. Put a candidate cj with gj ≥ m+ j - 2 at position 2. Moreover, all positions up to position j in the second vote can be assigned to the candidates cj+1, . . . , cm in this order. This is true since gj ≤ gi for j < i and by this assignment every such candidate makes exactly the same score as gj . To fill the positions greater than m-j +2, we apply the described strategy again, that is, find a j ′ < j such that cj ′ can take position m- j +3 and so on. □

Summarizing, the condition ∑ji=1 gi ≥ j(j - 1) (see Inequality 1 in Section 2) provides a necessary condition for an instance being a yes-instance of BORDA MANIPULATION while ∑ji=1 gi ≥ 1.5 · j(j - 1) provides a sufficient condition (from Proposition 4.2). It is interesting to find stronger bounds for both cases, for example, what happens when ∑ji=1 gi ≥ j 2 for every j?

Finally, note that Proposition 4.2 may also apply to instances with strong opponents, that is, candidates with gap at most m. For example, there can be one candidate ci with gi = 0 or m/4 candidates each with gi = m (which are allowed to make m2 /4 > 1.5 · m/4 · (m/4 - 1) points).

5 Conclusion

We showed NP-hardness for BORDA MANIPULATION even for very restricted settings such as having constant numbers of input votes and manipulators. Our NP-hardness proof is of theoretical nature in the sense that it is a purely worst-case result with little impact on practical aspects of solving BORDA MANIPULATION. This also motivates the issue of parameterizing NP-hard problems such as BORDA MANIPULATION in the spirit of multivariate algorithmics [Niedermeier, 2010]. In this context, our results still leave a number of interesting challenges for future work. For instance, we still miss a combinatorial algorithm (not based on integer linear programming) to solve BORDA MANIPULATION efficiently 6 in case of few candidates and an "unbounded" coalition size. It is also of interest whether in case of two manipulators one can solve the problem in less than O(|C|!) time.

5 Iteratively applying this greedy algorithm provides an approximation algorithm with an additive error of one for the optimization problem of minimizing the size of a "winning coalition" [Zuckerman et al., 2009].

Moreover, with Inequality 1 (see Section 2) and Proposition 4.2 one now has one necessary and one sufficient condition for a BORDA MANIPULATION instance being a yesinstance. Besides improving the "gap" between the two corresponding bounds, it might be also interesting to "evaluate" the instances so far used for experimental studies or further realworld instances by answering the following question. What percentage of typically tested instances can not be decided based on the necessary or sufficient condition?

Furthermore, all our NP-hardness results rely on having a constant number of manipulative votes and an unbounded number of candidates. However, in many realistic voting scenarios one has only a small number of candidates but a large number of votes. Hence, it might be interesting to investigate whether BORDA MANIPULATION becomes "easy" when the coalition size is much larger than the number of candidates.

Finally, this paper explores a close connection between BORDA MANIPULATION and 2NMTS as well as the corresponding scheduling problem from [Yu et al., 2004] to show computational hardness. On the positive side, it seems interesting to investigate whether some of the algorithmic results from the scheduling or matching literature can also be applied to BORDA MANIPULATION or can be helpful to design algorithms for manipulation problems in general. Some results in this direction have already been obtained by Xia et al. [2010] but this still might be a fruitful field.

Acknowledgements. NB was supported by the DFG project "PAWS", NI 369/10. We are very grateful to the anonymous referees whose detailed and constructive feedback helped to significantly improve our presentation.