A number of recent theoretical results suggest that manipulation may often be computational easy [5, 10, 15, 16]. Brelsford et al. [3] showed that weighted (and unweighted) Borda manipulation has a FPTAS, which means that finding a very close to optimal manipulation can be done in polynomial time. Along these lines, Zuckerman et al. [19] gave a simple greedy algorithm to calculate a manipulation, that in the unweighted case uses at most one more manipulator than is optimal. In addition, even Borda himself appears to have recognised that his rule was susceptible to manipulation, having retorted that:
"My scheme is intended only for honest men", quoted on page 182 of [2]
More recently, strategic voting was identified in the 1991 presidential candidate elections in the Republic of Kiribati (where a variant of the Borda rule is used) [11]. This suggests that the manipulability of the Borda rule is not just a theoretical possibility but a practical reality.

The manipulability of voting rules has also been studied empirically [13, 14]. For example, Walsh studied the Single Transferable Vote rule, which is theoretically NP-hard to manipulate.

However, he provided ample evidence that in practise, elections using this rule are easy to manipulate [14]. We provide further empirical evidence that the Borda rule provides little defense to manipulation, by showing that in many elections, an optimal manipulation can be found (and often verified) in polynomial time. Our starting point is the greedy algorithm of Zuckerman et al. [19], which decides the vote of each manipulator in turn by reversing the candidates ordered by current score. Although this algorithm provides a guarantee that in the worst case it only uses one more manipulator than is optimal, the theoretical analysis does not extend to answer the question of how frequently it uses this extra manipulator. Perhaps another greedy algorithm exists that finds the optimal manipulation much more frequently. If so, it could be used in conjunction with that of Zuckerman et al. to provide a verified optimal solution whenever it finds a solution using one fewer manipulator. We introduce two new greedy algorithms, based on intuitions from the bin-packing and multiprocessor scheduling domains, and provide theoretical and empirical comparison between their performance and that of Zuckerman et al.'s greedy algorithm. The new algorithms result in a significant improvement over Zuckerman et al.'s algorithm, allowing the optimal manipulation to be found and verified quickly on 99% of more than 60,000 randomly generated elections.

The paper continues with the definitions and background in Section 2, followed in Section 3 by our new greedy algorithms. Section 4 presents the experimental results and we conclude in the last section.

## 2 Background In This Section We Introduce Notation And Definitions That Will Be Used Throughout The Paper.

An *election* is a pair E = (*V, m*) where m is the number of candidates. We refer to the distinguished candidate who the manipulators want to win the election as candidate 1 ≤ d ≤ m; the other m − 1 candidates are then the *competing* candidates. V is a set of *votes*, where a vote is an ordering of the candidates v = c1 > c2 *> ... > c*m such that Scj = {1*, .., m*}. Given a vote v, the *score* of a candidate i under the Borda rule, denoted s(*v, i*), equals m − k where ck = i. If V is a set of votes, then the score of a candidate i given by these votes is s(*V, i*) = Σv∈V s(*v, i*).

Given an election E = (*V, m*), the *winners* are defined as those candidates 1 ≤ i ≤ m such that s(*V, i*) is maximal. A *manipulation* of an election E = (*V, m*) is a set of manipulator votes M
such that s(V ∪ M, d) ≥ s(V ∪ *M, i*) for all i 6= d. We assume that ties are broken in favour of the manipulators. The manipulation problem is to find a manipulation such that |M| = n is minimized.