LSLG(V,n,d)
// B[i] is the iˆth column of B
1. B[i] ← ∅ for all 1≤i≤m
// B[d] is filled with n m-1's 2. B[d] ← {m-1,...,m-1}
// Each score is repeated n times in S
3. S ← {m-2,...,m-2,m-3,...,m-3,...,1,...,1,0,...,0}
4. *while* S 6= {}
// The column of B that contains fewer than n elements,
// with the lowest sum 5. c ← argmin i{sum(B[i]) + s(V,i) : |B[i]| < n}
6. B[c].push(S[0])
7. S ← S - S[0]
8. if sum(B[d]) + s(V,d) ≥ max i{sum(B[i]) + s(V,i)}
9. return B
10.*else* 11. return Failure Figure 3: The greedy algorithm based on placing the largest remaining score in the column of A
with the most room.

in Section 2. Each iteration of the *while* loop on lines 4-7 removes the first (largest) element of S
and pushes it (on line 6) into the column of B that has the lowest sum so far. Note that we use the notation |B(i)| to denote the current number of elements in the i th column of B. Once all elements of S have been assigned, the loop terminates and line 8 checks if a valid manipulation has been produced. If so, B is returned, and if not, the algorithm reports Failure.

The following proposition shows that this algorithm can sometimes find an optimal manipulation when REVERSE fails, and this is true for an infinite family of instances.

Proposition 1 Let E = (V, m) be an election such that m > 2 is even, d = m, s(*V, d*) = 0 and s(*V, i*) = m 2 +i for all i 6= d. Then LSLG finds an optimal 2-manipulation, but REVERSE produces a 3-manipulation.

## Proof

First, note that two non-manipulator votes are always sufficient to create such an election. Let σ =< 1, 2*, ..., m* − 1 > and let σ 0 =<
m 2
+ 1, m 2
+ 2, ...,
m 2
+
m 2
− 1, 1, 2, ...,
m 2
>
Then σ + σ 0 =
<
1 +
m 2
+ 1, 2 +
m 2
+ 2*, ...,* m 2
− 1 +
m 2
+
m 2
− 1
,
m 2
+ 1*, ...,* m − 1 +
m 2
>
which gives us m 2 + 2x for 1 ≤ x ≤
m 2 − 1 and m 2 + 2x − 1 for 1 ≤ x ≤
m 2
, or in other words, m 2 + i for all 1 ≤ i ≤ m − 1 (i.e. all i 6= d).

The first vote generated by REVERSE is r1 = m > 1 > 2 *> ... > m* − 1, after which s(V ∪ {r1}, i) = m 2 + m − 1 for all competing candidates, which is larger than the score of the distinguished candidate s(V ∪ {r1}, m) = m − 1. Therefore another manipulator is added, without loss of generality its vote is r2 = m > 1 > 2 *> ....m* − 1. The resulting scores of the competing