Gerrymandering Problem: Variant on Set Partitioning

Question

I was recently helping a friend with homework from a dynamic programming class, and this was the question:

Given a set of n precincts P₁ ,... P_n , each containing m votes, with n being even. We want to divide each precinct into two districts, each consisting of $\frac{n}{2}$ of the precincts. For each precinct, we know the number of citizens who will vote for party A and B. A set of precincts is susceptible to gerrymandering if it is possible to perform a division into two districts s.t. the same party holds a majority in both districts. For a given set of precincts, return whether they are susceptible to gerrymandering.

Readers who have Kleinberg & Tardos' Algorithm Design, note that this is the following exercise in the book: Chapter 6, Exercise 24, "Gerrymandering". (Also here, problem #2.)

Of course, this is a classic DP-style question, and we arrived at a DP solution, but I was intrigued by an $O(n \log n)$ sorting approach.

Intuition and training suggests to me that this problem is NP-hard, so my $O(n \log n)$ sorting solution must be an approximation heuristic. Yet I cannot find or think of a counterexample to it.

My hope is that someone here can provide a counterexample of precincts such that my solution fails. And perhaps give me some intuition on the conditions for it to fail, how good of a heuristic it is, etc.

The basic strategy of my solution is this:

1. Sort the precincts in ascending order. (Precincts are expected to be in the form of an array of integers representing the delta of votes A - B for each precinct.)
2. Beginning with the right-most (highest) precinct, add it to the left district, popping it from our precinct collection.
3. While the left precinct sums to a greater number than the right precinct, add precincts from the left of the array (most negative precincts). If we would fill this district and put it to a sum below zero, we do not do so, and instead elect to place that precinct into the right district.
4. While there remains precincts, pop the rightmost precinct and add it to a district, preferring: "helping" the district with the lesser sum; the district with less precincts (maximizes future decision potential).
5. Do all of this above, with the same precincts' values multiplied by -1. (Effectively checking to see if it's possible to gerrymander for party A first, then party B.)

The general strategy is to always keep each district barely above a sum of zero. The underlying assumption is that if it is possible to gerrymander the precincts, it must be possible to do so in a way such that the maximum winning margin between the districts is minimized. Furthermore, one would expect that most non-trivial solutions involve minimizing the winning margins, otherwise you're "wasting" votes.

---

Here's the code:

from collections import deque


def left_is_greater(greater, precincts, n):
    return (
        greater
        and len(greater) < n / 2
        and (sum(greater) + precincts[0] > 0 or len(greater) < n / 2 - 1)
    )


def maximize(precincts):
    n = len(precincts)
    left, right = [], []
    while precincts:
        greater = left
        if sum(right) > sum(left):
            greater = right
        elif sum(right) == sum(left):
            greater = None

        if left_is_greater(greater, precincts, n):
            greater.append(precincts.popleft())
            continue

        p = precincts.pop()

        # if either of the districts is "full", we don't have a choice
        # and must select the opposite district
        if len(right) == n / 2:
            left.append(p)
        elif len(left) == n / 2:
            right.append(p)

        # we always prefer the lesser summed district. if gerrymandering
        # is feasible, we won't want to put all of our party's votes
        # into one district, but prefer to have each district barely win.
        elif sum(left) < sum(right):
            left.append(p)
        elif sum(right) < sum(left):
            right.append(p)

        # if the districts sum to the same amount, we prefer the district
        # with less precincts, as this maximizes future decision branches
        elif len(right) < len(left):
            right.append(p)
        elif len(left) < len(right):
            left.append(p)

        # we choose left as the default seed case, all else equal
        else:
            left.append(p)

    if sum(left) > 0 and sum(right) > 0:
        return True, left, right
    else:
        return False, left, right


def solve(precincts):
    maximized = deque(sorted(precincts))
    minimized = deque(sorted(x * -1 for x in precincts))
    for polarized_precincts in [maximized, minimized]:
        is_gerrymanderable, left, right = maximize(polarized_precincts)

        if is_gerrymanderable:
            print("It's gerrymanderable! Take a look: ", left, right)
            return

    print("Sorry, doesn't seem to be gerrymanderable.")


def main():
    test_cases = [
        [-10, -1, 0, 1, 2, 10],
        [-3, -3, -3, -1, 0, 1, 2, 9],
        [55 - 45, 43 - 57, 60 - 40, 47 - 53],
        [4, 5, 6, 7, 8, 9],
        [-1, -1, 0, 0, 1, 1],
        [-4, -1, -1, 1, 2, 6],
    ]
    for case in test_cases:
        solve(case)


if __name__ == "__main__":
    main()

Answer 1

As your intuition and training suggests, a simple greedy algorithm should not solve this seeming hard problem.

Here is a counterexample, [-3, -2, -2, 0, 4, 5]. This is probably the simplest counterexample. Your algorithm will return "Sorry, doesn't seem to be gerrymanderable". However, there is a division, [-2, -2, 5] and [0, -3, 4].

How can we beat this greedy algorithm? You probably have verified all cases of 4 precincts. Let us try making the first two greedy choices of 6 precincts a bad choice. Luckily there we have found it.