In a recent message, partly quoted below, Adam Tarr outlined an NP hard optimization approach to redistricting. He suggested that a genetic optimization algorithm might be used for practical purposes. It has been suggested before that in such cases anybody with a proposal found by any means (genetic or not) should be allowed to submit it in some standard format, in this case as a partition of census blocks. The feasible partition that minimized the weight of the cut set would be adopted. I would like to mention two other applications of this approach to overcoming intractability. 1. Proportional Approval Voting (PAV) proceeds by considering all possible candidate sets of the appropriate cardinality, and electing the set with the maximum PAV score. This is computationally intractable in a twenty winner election when there are a reasonable number of candidates. But why not maximize over proposals submitted by any and all? Included among the proposals would be STV solutions with Droop and other quotas, as well as the results of genetic algorithms. 2. It is probably intractable in general to find the "best" lottery of the type that Jobst and I have been considering lately, i.e. the lottery that minimizes the maximum number of votes that any candidate would get over it in a head-to-head contest. Again, the practical approach is to allow any and all to submit their proposed lotteries, and then minimize over this set of proposals. Do you wonder how the winning lottery would be used? I thought you'd never ask! If the best lottery is unbeaten by any candidate, then that lottery is used to pick the winner. Else the candidate that beat the best lottery by the greatest margin is the winner. How would this be done in practice? The simplest way is through Asset Voting. Each voter votes for one candidate (write-ins allowed, including self). The candidates, including write-ins, cast their range or ordinal ballots, each replicated according to the number of voters represented. This ballot set is used to evaluate the lottery proposals. As explained above, if the best lottery is unbeaten, then it picks the winner, else the candidate that beats the best lottery by the greatest margin is the winner. A slight variation allows an erstwhile write-in to submit a cardinal or ranked ballot immediately, instead of voting for a candidate or writing in self. This is a method that I wouldn't mind having my name attached to. Of course, at least half of the credit goes to Jobst. If it becomes very successful, we'll call it the Jobst/Simmons method, otherwise Forest's Folly. Forest
On Fri, 19 Aug 2005 09:14:24 -0600, Adam Tarr [EMAIL PROTECTED] wrote (under the subject heading Re: [RangeVoting] Ballot Initiative feedback from Lomax) ... Warren, As with many topics, this has been covered extrensively before in the EM archives. As far as non-partisan districting goes, an idea that has gotten a lot of mileage is some sort of specific algorithm that is used to determine districts. I'll try to describe one approach below: -------------------- The "atoms" of districts are census blocks. Census blocks are drawn up in a nonpartisan fashion, and since they are much, much smaller than congressional districts, it is extremely difficult to manipulate the process by re-drawing them. Consider the census blocks in a given state to be the nodes of a graph. There are links between all nodes where the census blocks are geographically adjacent. The nodes have weights equal to the population therein. The links have weights equal to the number of lanes of transportation connecting the two nodes. A single lane of surface road is worth one. Limited access highway lanes can be made to count double or triple. Railroad and subway lines can be weighted more heavily than a single lane, and sidewalks less heavily. If the border between two census blocks is formed by a road, then any lanes that "T" into that road count half as much as usual. (So a road that cuts through counts regular.) (Note that natural boundaries such as rivers and mountains tend to have few ways to cross them, so they will naturally end up as boundaries.) If the state is to be divided into N districts, then the graph must be divided into N unconnected sub-graphs by severing links in the graph. The problem is: minimize: total weight of severed links subject to: total node weight of each of the N sub-graphs must be within 5% (or some small acceptable error) of one another. I beleive this is an NP problem, but a good genetic algorithm could come up with an acceptable solution given enough time to crank away.
<<winmail.dat>>
---- Election-methods mailing list - see http://electorama.com/em for list info