Therefore, |*nbhd*(P)| is not less than |P|. Since the Hall condition holds [8], there is a perfect matching in G that assigns each value from 0 to m − 1 to a position in the first row of B, as follows.

Let M = {e1, ..., em} ⊆ E be the set of edges in the matching. For each e = (*i, j*)k ∈ M, let A(1, j) = i. Since M is a matching, each i, 0 ≤ i ≤ m−1 appears in exactly one column, and each column is assigned exactly one element. Therefore, the first row of A is well defined. Also note that for each column j, A(1, j) appears in the j th column of B.

Let B0 be the matrix defined by taking B and removing one element equal to A(1, j) from each column j. Then B0is an n − 1 × m matrix containing exactly n − 1 elements equal to i for each 0 ≤ i ≤ m − 1, since the elements removed were one of each value. The column sums for B0are gj −A(1, j) for all columns j. By the induction hypothesis, there exists an n−1×m matrix A0such that A0contains the same elements as B0and the same column sums, but each row of A0contains exactly one element equal to i, for 0 ≤ i ≤ m − 1. Given that we've already defined the first row of A, let the remaining n − 1 rows be A0. Then A contains the same set of values as B, with the same column sums A(1, j) + (gj −A(1, j)) = gj , and every row of A contains exactly one element equal to i, for each 0 ≤ i ≤ m − 1.

Therefore, by induction, the theorem holds for all n. ✷
If a matrix B exists whose column sums are at most the value of the candidates' gaps, and sum(B[d]) = gd, then matrix A gives a manipulation, where each row of A defines the vote of one of the manipulators. Therefore, we can devise algorithms to discover B and be assured that A exists.

However, the manipulation problem has two additional differences to bin-packing. First, the number of objects in each bin must be exactly n, while bin-packing has no such constraint.

Secondly, each of our bins has a different maximum capacity gi. The former constraint has been studied in the multiprocessor scheduling domain, where the problem is to schedule jobs on a set of n processors such that the memory resources are never exceeded and the time to complete all jobs is minimized [9]. Our problem corresponds to the case where each job takes a unit of processing time. For each element a ∈ Sn, there is a job with memory requirement equal to a. The number of processors is equal to the number of manipulators n, and the amount of available memory resource at time step i is equal to gi. We wish to find a schedule that uses m − 1 time steps, which will be possible if an n-manipulation exists. Krause et al. consider the case where the memory resource remains constant over time, and present theoretical analysis of a simple scheduling algorithm that assigns the jobs one at a time to particular time steps. Their scheduler takes the unassigned job with largest memory requirements and assigns it to a time step (with at least one processor free), that has the maximum remaining available memory. If no time step exists that can accommodate this job, a new time step is added.

Our first greedy algorithm is based on this same intuition, where it translates to giving the largest scores to the competing candidates that have the least score so far. In this it is similar to REVERSE,
but we are now free to pursue this heuristic strictly, while REVERSE for example decides which candidate the second voter's m − 2 should be assigned to *after* the smaller scores of the first manipulator are assigned. This can sometimes be an advantage, but it may also lead the algorithm to make more serious mistakes, as we will show.

## 3.1 Largest Score In Largest Gap

Our first greedy algorithm, LSLG is shown in Figure 3. LSLG takes the number of manipulators as an argument and returns the matrix B (from Theorem 3.1) if it is able to find an n-manipulation. On line 1, the matrix B (represented as an array of vectors) is initialized so that every column vector is empty. On line 2, the column corresponding to the distinguished candidate is filled with the maximum value, m − 1. On line 3, the array S is initialized with the sorted elements of Sn defined