Sometimes we will refer to a manipulation using n votes as an *n-manipulation*.

We define some additional notation that will be helpful in describing our greedy algorithms.

Definition 1 *Given an election* E = (V, m), a number of manipulators n*, the* gap *of candidate* 1 ≤ i ≤ m, is defined as gE,n(i) = s(*V, d*) + n(m − 1) − s(V, i)*. If the context is clear, we call the* gap of candidate i *simply* gi.

Intuitively, the gap of a candidate i is the difference between the score the distinguished candidate receives after the manipulators have voted, and the score of i before the manipulators vote. Without loss of generality, we assume that the manipulators always rank d first. Note that if giis negative for any i, then there is no n-manipulation.

Definition 2 *Given an election* E = (V, m), an n-manipulation matrix AE,n is an n × m matrix such that all elements of column d are equal to m − 1*, each row contains all numbers from* 0 to m − 1 and column i sums to at most gE,n(i) *for all* 1 ≤ i ≤ m.

It is easy to see that such a matrix represents an n-manipulation of the election, where each column represents a competing candidate, and each row corresponds to the vote of a distinct manipulator.

We will drop the parameters E and n and refer to matrix A when the context is clear. We use the notation A(i) to denote the i th column of A, and sum(A(i)) is defined to be the sum of the elements in A(i). Observation 1 *Given an election* E = (V, m) and a number of manipulators n*, if* Σ
m−1 i=1 gE,n(i) <
(n/2)(m − 1)(m − 2) then there is no n*-manipulation.*
This follows directly from Definition 2, since each of the n manipulator votes contributes a total of Σ
m−2 k=0 k = (1/2)(m − 1)(m − 2) score to the scores of the competing candidates. In other words, there must be enough difference between the original scores of the competing candidates and the achievable score of the distinguished candidate, otherwise an n-manipulation can not exist. We call the multiset containing n copies of each 0 ≤ k ≤ m − 2 Sn.

The greedy algorithm of Zuckerman et al. [19] is shown in Figure 1, and from now on will be referred to as REVERSE. The manipulation matrix A starts off empty, and is augmented row by row until enough manipulators have been added that the distinguished candidate wins. The sort procedure puts the distinguished candidate first, and then sorts the competing candidates in increasing order by their current score, in order to create the next manipulator's vote.

Example 1. Suppose E = (V, 5) where V contains the votes v1 = 1 > 2 > 3 > 4 > 5, v2 =
2 > 3 > 4 > 1 > 5, v3 = 3 > 4 > 1 > 2 > 5 and v4 = 4 > 1 > 2 > 3 > 5, and d = 5.

Then s(V, 5) = 0, and s(*V, i*) = 10 for all competing candidates i < 5. In order for candidate 5 to win the election, at least 4 manipulators are required since ΣigE,3(i) = 4 ∗ (4 ∗ 3 − 10) = 8 but (n/2)(m − 1)(m − 2) = 1.5 ∗ 4 ∗ 3 = 18. REVERSE will make the first manipulator vote w1 = 5 > 1 > 2 > 3 > 4 (ordering the competing candidates arbitrarily), at which point, e.g.,
s(V ∪ {w1}, 1) = 10 + 3 = 13. The candidates' scores are shown in Figure 2 after each iteration of the *while* loop. Since s(V ∪ {w1, w2, w3, w4}, 5) = 16, REVERSE finds the optimal manipulation.

## 3 Greedy Algorithms For Borda Manipulation

The definition of manipulation matrix from Section 2 is a useful abstraction, that suggests a connection to bin-packing or multiprocessor scheduling [4]. Intuitively, the elements of the manipulators