[math-fun] counter-gerrymandering
I looked into this problem back in the 1970's, but I was never able to come up with a good intuition about how districting should work. I considered various "greedy" algorithms for growing regions starting from "seeds", but there didn't seem to be any good criteria for selecting the initial seeds. The other intuition is that of a gas under pressure living in the district where the State boundaries are rigid and the district boundaries are flexible, and the boundaries move until the pressure "equalizes". The boundary itself could have a bending energy (analogous to a physical "spline") which would tend to keep the boundaries fairly smooth. Unfortunately, this intuition/analogy only helps once the basic district is defined, and you want to allow the system to "relax" into its lowest energy state. It doesn't help choose the initial configuration. I suppose that one could come up with a "soap bubble" analogy, wherein each district started with 1/N amount of gas, where N is the number of Representatives for that State. The boundaries of these soap bubbles could move. However, I didn't see any way to guarantee that the solution would be unique and/or stable. The other problem with the "soap bubble" analogy is that the population density is extremely non-uniform, looking a lot more like fractal dust than uniform air pressure. Moving the boundary a tiny bit in a very dense region produces very large changes in the population of the district, while moving the boundary a tiny bit in a very sparse region has almost no change in the population of the district. This fractal density effect essentially _guarantees_ a fractal-like boundary, even with relatively stiff spline boundaries. Most of the suggestions I read about to make a district "compact" ignored the existing boundaries of the State in which the district would have to live. For example, if a State is long and thin, then a district in the middle will necessarily disconnect the State into districts on one side of the selected district from districts on the other side. If the State is thin enough, the problem is essentially one-dimensional, and then the boundaries can be adjusted by some sort of "pressure equalization" method. If a State has disconnected portions -- e.g., Michigan -- is a district allowed to cross the disconnect?
Perhaps some pseudo-physical process could be used. If every person in a state or region had a repulsive force from every other, then you could diffuse people away from each other to form a thermodynamically uniform distribution within the boundary. Then, slice up the (now uniform) distribution, and transform the boundary back. On Jun 21, 2014, at 8:11 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I looked into this problem back in the 1970's, but I was never able to come up with a good intuition about how districting should work.
I considered various "greedy" algorithms for growing regions starting from "seeds", but there didn't seem to be any good criteria for selecting the initial seeds.
The other intuition is that of a gas under pressure living in the district where the State boundaries are rigid and the district boundaries are flexible, and the boundaries move until the pressure "equalizes". The boundary itself could have a bending energy (analogous to a physical "spline") which would tend to keep the boundaries fairly smooth.
Unfortunately, this intuition/analogy only helps once the basic district is defined, and you want to allow the system to "relax" into its lowest energy state. It doesn't help choose the initial configuration.
I suppose that one could come up with a "soap bubble" analogy, wherein each district started with 1/N amount of gas, where N is the number of Representatives for that State. The boundaries of these soap bubbles could move. However, I didn't see any way to guarantee that the solution would be unique and/or stable.
The other problem with the "soap bubble" analogy is that the population density is extremely non-uniform, looking a lot more like fractal dust than uniform air pressure. Moving the boundary a tiny bit in a very dense region produces very large changes in the population of the district, while moving the boundary a tiny bit in a very sparse region has almost no change in the population of the district.
This fractal density effect essentially _guarantees_ a fractal-like boundary, even with relatively stiff spline boundaries.
Most of the suggestions I read about to make a district "compact" ignored the existing boundaries of the State in which the district would have to live.
For example, if a State is long and thin, then a district in the middle will necessarily disconnect the State into districts on one side of the selected district from districts on the other side. If the State is thin enough, the problem is essentially one-dimensional, and then the boundaries can be adjusted by some sort of "pressure equalization" method.
If a State has disconnected portions -- e.g., Michigan -- is a district allowed to cross the disconnect?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I was trying to come up with such a physical model, more-or-less, with my "spline" analogy. Let's assume that every person in the state is nailed down to his/her address/GPS location. This means that no person's address can lie exactly _on_ a boundary. Each address can have an integer number of people having that address. Let's assume that each district is simply-connected. The spline boundary wants to be straight and resists being bent; the more and sharper the bending, the greater the stress & energy stored. If the State is allowed exactly N representatives, let's assume that the population is exactly divisible by N; let's say that exactly S people will populate each district. We still may have no solution if there are some addresses with too many people living there, because it may be impossible to find a boundary that puts exactly S people in each district while still keeping each district simply-connected. Perhaps we can approach the problem by considering N=1,2,3, etc. If N=1, the district is the entire State, so this case is trivial. If N=2, we can attempt to consider all combinations of address locations which partition the population into 2 exactly equal partitions. We now have to calculate the energy of the spline which separates these 2 groups. Since the boundary only has to separate the address locations, it isn't unique, but computing the lowest energy spline will dramatically reduce the number of possibilities. Presumably, such boundaries will "pin" the spline up against address locations on the boundary, so that the spline touches the address location. Nevertheless, for each such address location, it must be clearly labelled as on one "side" of the boundary. Alternatively, we can keep the boundary from actually touching any address location by providing a quite large repulsive force around each location; this force "repels" the boundary spline and increases the local stress. Presumably, the repulsive force is proportional to the number of people living at this particular location. Assume that we have chosen a boundary between the 2 districts and computed its energy. We can now consider every address location very near the boundary. If we move a particular address location from one side to the other, we have to pair that with another move from the second side to the first in order to keep the population in each district the same. So we can move along the boundary, considering exchanging pairs of address locations, and checking if the energy of the boundary goes up or down. However, there is no requirement that the two address locations in the pair be near one another; indeed, they could be at opposite ends of the State. My intuition is that the energy involved in trying to run a boundary through a densely populated area will so "crinkle" the spline that the lowest energy boundary spline will avoid densely populated areas, and hence keep the districts reasonably compact. At 07:14 AM 6/21/2014, Tom Knight wrote:
Perhaps some pseudo-physical process could be used. If every person in a state or region had a repulsive force from every other, then you could diffuse people away from each other to form a thermodynamically uniform distribution within the boundary. Then, slice up the (now uniform) distribution, and transform the boundary back.
On Jun 21, 2014, at 8:11 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I looked into this problem back in the 1970's, but I was never able to come up with a good intuition about how districting should work.
I considered various "greedy" algorithms for growing regions starting from "seeds", but there didn't seem to be any good criteria for selecting the initial seeds.
The other intuition is that of a gas under pressure living in the district where the State boundaries are rigid and the district boundaries are flexible, and the boundaries move until the pressure "equalizes". The boundary itself could have a bending energy (analogous to a physical "spline") which would tend to keep the boundaries fairly smooth.
Unfortunately, this intuition/analogy only helps once the basic district is defined, and you want to allow the system to "relax" into its lowest energy state. It doesn't help choose the initial configuration.
I suppose that one could come up with a "soap bubble" analogy, wherein each district started with 1/N amount of gas, where N is the number of Representatives for that State. The boundaries of these soap bubbles could move. However, I didn't see any way to guarantee that the solution would be unique and/or stable.
The other problem with the "soap bubble" analogy is that the population density is extremely non-uniform, looking a lot more like fractal dust than uniform air pressure. Moving the boundary a tiny bit in a very dense region produces very large changes in the population of the district, while moving the boundary a tiny bit in a very sparse region has almost no change in the population of the district.
This fractal density effect essentially _guarantees_ a fractal-like boundary, even with relatively stiff spline boundaries.
Most of the suggestions I read about to make a district "compact" ignored the existing boundaries of the State in which the district would have to live.
For example, if a State is long and thin, then a district in the middle will necessarily disconnect the State into districts on one side of the selected district from districts on the other side. If the State is thin enough, the problem is essentially one-dimensional, and then the boundaries can be adjusted by some sort of "pressure equalization" method.
If a State has disconnected portions -- e.g., Michigan -- is a district allowed to cross the disconnect?
Perhaps some pseudo-physical process could be used. ...
How about this? You select not the boundaries but the geometric centers of proposed populations. Now: anyone can register at any population center but that person's vote is reduced proportional to the distance from the center. Whit
Suppose there are N seats to be filled. Each person votes for their candidate, and all the votes go into a publicly accessible database. Voters can check the database and change their votes. The election is open for a long time, perhaps a year. At the close of the election, the top N candidates are elected. -- Gene
Implicit in all these schemes is the idea the people who are geographically localized have common interests and are best served by a common representative. Maybe when everybody in an area was a farmer that had some merit, but I see no merit in it now. Where I live the local congressional district contains a large military base, a lot of fruit and vegetable farms mostly worked by Mexican Americans (who rarely vote), some big oil operations, a university, and various small businesses. Would representative government work better if representatives were elected at large so that each of these factions could have their own representative - instead of having to hire a lobbyist to woo a guy elected to represent a geometric figure on a map? Brent Meeker On 6/21/2014 5:11 AM, Henry Baker wrote:
I looked into this problem back in the 1970's, but I was never able to come up with a good intuition about how districting should work.
I considered various "greedy" algorithms for growing regions starting from "seeds", but there didn't seem to be any good criteria for selecting the initial seeds.
The other intuition is that of a gas under pressure living in the district where the State boundaries are rigid and the district boundaries are flexible, and the boundaries move until the pressure "equalizes". The boundary itself could have a bending energy (analogous to a physical "spline") which would tend to keep the boundaries fairly smooth.
Unfortunately, this intuition/analogy only helps once the basic district is defined, and you want to allow the system to "relax" into its lowest energy state. It doesn't help choose the initial configuration.
I suppose that one could come up with a "soap bubble" analogy, wherein each district started with 1/N amount of gas, where N is the number of Representatives for that State. The boundaries of these soap bubbles could move. However, I didn't see any way to guarantee that the solution would be unique and/or stable.
The other problem with the "soap bubble" analogy is that the population density is extremely non-uniform, looking a lot more like fractal dust than uniform air pressure. Moving the boundary a tiny bit in a very dense region produces very large changes in the population of the district, while moving the boundary a tiny bit in a very sparse region has almost no change in the population of the district.
This fractal density effect essentially _guarantees_ a fractal-like boundary, even with relatively stiff spline boundaries.
Most of the suggestions I read about to make a district "compact" ignored the existing boundaries of the State in which the district would have to live.
For example, if a State is long and thin, then a district in the middle will necessarily disconnect the State into districts on one side of the selected district from districts on the other side. If the State is thin enough, the problem is essentially one-dimensional, and then the boundaries can be adjusted by some sort of "pressure equalization" method.
If a State has disconnected portions -- e.g., Michigan -- is a district allowed to cross the disconnect?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Eugene Salamin -
Henry Baker -
meekerdb -
Tom Knight -
Whitfield Diffie