I have my own idea, but first I need to set it up so that it makes sense. As I see it, there are a number of competing, and possibly mutually exclusive, objectives when creating districts, and that is before even thinking about the political persuasion of the constituents. These objectives include:
- Equal population in each district
- District lines fall on county boundaries
- Non-gerrymandered
- Human Input into final decision (nobody likes to be told what to do by a computer)
There may be others, but I think these are a good start. It is almost guaranteed that optimizing for one will necessarily not be optimized for the others. As it is, we are currently optimized only on the last point, which we really can't assign an optimization function to anyway.
The first three, however, I think we can assign optimization values to. The first one is pretty easy, for a state of population P with N districts, where the ith district has a population pi then minimize the value of Sum(abs(pi - P/N)). You can use a squared value instead of abs if you want, that's just using the L2 norm instead of the L1 norm. Anyway, minimize that sum, and populations in each district will be equalized. For population data, use census data by precinct, assume that the population is uniform across the precinct (inaccurate, I know, but a good first guess).
The second one is a bit harder, but I think one way to express it mathematically is to minimize the the area which can be drawn between a district boundary and a county line. For a county that is split in such a way, count only the smaller area (otherwise the county could be cut any way you like). I'm sure others could come up with a way to optimize this as well that might make a bit more sense.
The third one could be mathematically imposed by minimizing the sum of the differences between the convex hull for a district and the district itself. If all of the districts are convex, then this sum will be 0. You will also have a non-gerrymandered state. For states such as Maryland, with its jagged southern border, it would probably be impossible to get this sum to 0, but that's still OK, we just want to minimize it for any given state.
Now, as I said before, these three cannot be complete optimized at the same time, and different people will put different weights on each of the objectives. Some people might believe that the population equality is most important, while others might believe that districts following county lines is paramount. This is almost where the human element comes in. See, even though people might disagree on what is most important, what can be done before assigning weights is to try to optimize over all of them. What will result is something called a Pareto frontier. Each point on the Pareto frontier represents a different weighting scheme. Some reasonable limits might also want to be enforced, maybe that every pi has to fall within 0.75 * P/N to 1.25 * P/N.
What would then happen is that a multiple objective optimization program can find a bunch of points on the Pareto frontier, in this case, each point is actually a specific map of the state in question. A set of these can then be handed off to a state legislature, or some other deciding body, and then they can select the one they like the most, bringing the human element back into it. They can then select the most optimal map for them if they like.
So there it is, a possible way to reduce gerrymandering while still leaving the final decision in the hands of people, possibly even state legislatures. I even think that this is a non-partisan idea. Also, I'd be happy to hear other (non-partisan) objectives that such a program might want to optimize for. It would be interesting if multiple states did this to see what the relative weights each state chose for it's given district mapping.
The second one is a bit harder, but I think one way to express it mathematically is to minimize the the area which can be drawn between a district boundary and a county line. For a county that is split in such a way, count only the smaller area (otherwise the county could be cut any way you like). I'm sure others could come up with a way to optimize this as well that might make a bit more sense.
The third one could be mathematically imposed by minimizing the sum of the differences between the convex hull for a district and the district itself. If all of the districts are convex, then this sum will be 0. You will also have a non-gerrymandered state. For states such as Maryland, with its jagged southern border, it would probably be impossible to get this sum to 0, but that's still OK, we just want to minimize it for any given state.
Now, as I said before, these three cannot be complete optimized at the same time, and different people will put different weights on each of the objectives. Some people might believe that the population equality is most important, while others might believe that districts following county lines is paramount. This is almost where the human element comes in. See, even though people might disagree on what is most important, what can be done before assigning weights is to try to optimize over all of them. What will result is something called a Pareto frontier. Each point on the Pareto frontier represents a different weighting scheme. Some reasonable limits might also want to be enforced, maybe that every pi has to fall within 0.75 * P/N to 1.25 * P/N.
What would then happen is that a multiple objective optimization program can find a bunch of points on the Pareto frontier, in this case, each point is actually a specific map of the state in question. A set of these can then be handed off to a state legislature, or some other deciding body, and then they can select the one they like the most, bringing the human element back into it. They can then select the most optimal map for them if they like.
So there it is, a possible way to reduce gerrymandering while still leaving the final decision in the hands of people, possibly even state legislatures. I even think that this is a non-partisan idea. Also, I'd be happy to hear other (non-partisan) objectives that such a program might want to optimize for. It would be interesting if multiple states did this to see what the relative weights each state chose for it's given district mapping.
