[EM] a democratic approach to intractable optimizations

[Simmons, Forest]

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 ahtarr at gmail.com 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.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/ms-tnef
Size: 7963 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20050820/a9986b28/attachment-0002.bin>