
## Manipulation Matrices

We can view REVERSE as greedily constructing a manipulation matrix. A *manipulation matrix* is an n by m matrix, A where A(*i, j*) = k iff the ith manipulator adds a score of k to candidate j. A manipulation matrix has the properties that each of the n rows is a permutation of 0 to m − 1, and the sum of the jth column is less than or equal to g(j), the maximum score candidate j can receive without defeating d.

REVERSE constructs this matrix row by row.

Our two new approximation methods break out of the straightjacket of constructing a manipulation matrix in row wise order. They take advantage of an interesting result that relaxes the constraint that each row is a permutation of 0 to m − 1. This lets us construct a *relaxed manipulation matrix*. This is an n by m matrix that contains n copies of 0 to m − 1 in which the sum of the jth column is again less than or equal to g(j). In a relaxed manipulation matrix, a row can repeat a number provided other rows compensate by not having the number at all.

Theorem 2 Suppose there is an n by m relaxed manipulation matrix A. Then there is n by m *manipulation matrix* B
with the same column sums.

Proof: By induction on n. In the base case, n = 1 and we just set B(1, j) = A(1, j) for j = 1 *. . . , m*. In the inductive step, we assume the theorem holds for all relaxed manipulation matrices with n − 1 rows. Let h(i) be the sum of the ith column of A. We use a perfect matching in a suitable bipartite graph to construct the first row of B and then appeal to the induction hypothesis on an n − 1 by m relaxed manipulation matrix constructed by removing the values in the first row from A.

We build a bipartite graph between the vertices Vi and Wj for i ∈ [0, m − 1] and j ∈ [1, m]. Vi represent the scores assigned to the first row of B, whilst Wj represent the columns of A from where these will be taken. We add the edge (Vi, Wj ) to this bipartite graph for each i ∈ [0, m−
1],j ∈ [1, m] and k ∈ [1, n] where A(*k, j*) = i. Note that there can be multiple edges between any pair of vertices. By construction, the degree of each vertex is n.

Suppose we take any U ⊆ {Vi|i ∈ [0, m − 1]}. By a simple counting argument, the neighborhood of U must be at least as large as U. Hence, the Hall condition holds and a perfect matching exists (Hall 1935). Consider an edge
(Vi, Wj ) in such a perfect matching. We construct the first row of B by setting B(1, j) = i. As this is a matching, each i ∈ [0, m − 1] occurs once, and each column is used exactly one time. We now construct an n − 1 by m matrix from A
by removing one element equal to B(1, j) from each column j. By construction, each value i ∈ [0, m − 1] occurs n − 1 times, and the column sums are now h(j) − B(1, j).

Hence it is a relaxed manipulation matrix. We can therefore appeal to the induction hypothesis. This gives us an n by m manipulation matrix B with the same column sums as A. ✷
We can extract from this proof a polynomial time method to convert a relaxed manipulation matrix into a manipulation matrix. Hence, it is enough to propose new approximation methods that construct *relaxed* manipulation matrices. This is advantageous for greedy methods like those proposed here as we have more flexibility in placing later entries into good positions in the manipulation matrix.

## Largest Fit

Our first approximation method, LARGEST FIT is inspired by bin packing and multiprocessor scheduling. Constructing an n by m relaxed manipulation matrix is similar to packing n objects into m bins with a constraint on the capacity of the different bins. In fact, the problem is even similar to scheduling nm unit length jobs on n different processors with a constraint on the total memory footprint of the n different jobs running at every clock tick. Krause et al. have proposed a simple heuristic for this problem that schedules the unassigned job with the largest memory requirement to the time step with the maximum remaining available memory that has less than n jobs assigned (Krause, Shen, & Schwetman 1975). If no time step exists that can accommodate this job, then the schedule is lengthened by one step.

LARGEST FIT works in a similar way to construct a relaxed manipulation matrix. It assigns the largest unallocated score to the largest gap. More precisely, it first assigns n instances of m − 1 to column d of the matrix (since it is best for the manipulators to put d in first place in their vote).

It then allocates the remaining (n − 1)m numbers in reverse order to the columns corresponding to the candidate with the current smallest score who has not yet received n votes from the manipulators. Unlike REVERSE, we do not necessarily fill the matrix in row wise order.

Example 2 Consider again the last example. We start with the score vector h3, 4, 5, 0i. One manipulator alone cannot increase the score of candidate 4 *enough to beat* 2 or 3*. Therefore, we need at least two manipulators.*
LARGEST FIT first puts two 3s in column 4 *of the relaxed* manipulation matrix. This gives the score vector h3, 4, 5, 6i.

The next largest score is 2. LARGEST FIT puts this into column 1 *as this has the larger gap. This gives the score vector* h5, 4, 5, 6i*. The next largest scores is again* 2. LARGEST FIT
puts this into column 2 *giving the score vector* h5, 6, 5, 6i.

The two next largest scores are 1. LARGEST FIT puts them in columns 1 and 3 giving the score vector h6, 6, 6, 6i. Finally, the two remaining scores of 0 *are put in columns* 2 and 3 so all columns contain two scores. This gives a relaxed manipulation matrix corresponding to the manipulating votes: 4 > 2 > 1 > 3 and 4 > 1 > 3 > 2. With these votes, 4 *wins based on the tie-breaking rule. Unlike* REVERSE, LARGEST FIT *constructs the optimal manipulation with just two manipulators.*

## Average Fit

Our second approximation method, AVERAGE FIT takes account of both the size of the gap and the number of scores still to be added to each column. If two columns have the same gap, we want to choose the column that contains the fewest scores. To achieve this, we look at the average score required to fill each gap: that is, the size of the gap divided by the number of scores still to be added to the column. AVERAGE FIT puts the largest unassigned score possible into the column which will accommodate the largest