Re: [EM] Geographically proportional ballots
Juho wrote: On Aug 29, 2008, at 15:51 , Kristofer Munsterhjelm wrote: One more approach to semi-computerized voting. A computer displays the personal alternatives and then prints a ballot. This solution hides the personalized nature of the ballot and still avoids the problem of voter voting for candidates that he/she should not vote. One could augment the semi-computerized voting by making it print all candidates That could be thousands, so maybe a subset in many cases. Just enough to hide the data. One could print out to the nearest candidate that's, say, a tenth of the population away from the voter. Here I say that a candidate is N voters away from a voter if it's not possible to make a compact region that includes both the voter and the candidate, yet has fewer than N voters in it. For simplicity, the region might be a circle. One should maybe avoid the possibility of someone deriving the location of the voter based on the distribution of all the candidates on the ballot. (Also picking fully random candidates may reveal the location since there will be one concentration of nearby candidates.) This could happen if the voter has a compact region significantly different from the rest. For instance, vote-buyers may (theoretically) advertise that they're just in range to candidate x, so that x will be on his ballot whereas x won't be on all the others in his region. But if that's not the case, then the only way your deduction will work is statistically, and when doing so, it'll be hard to separate a single person from the rest of the mass you know is in the close vicinity. If you tell A to rank yourself in first place, and you then find out that one of the ballots from this area has yourself in first place, you still don't know if it's A or not (absent intentional ballot fingerprinting by the voter). Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] A computationally feasible method (algorithmic redistricting)
On Sep 1, 2008, at 7:28 AM, Kristofer Munsterhjelm wrote: A simpler algorithm, though one that doesn't give any worst-case bounds, is Lloyd's algorithm. Start with random center points, then calculate the centroids for the current Voronoi cells. Move the center points towards the centroid (shifting the Voronoi cell somewhat) and repeat. Do so until they settle. This can get stuck in a local optimum. I have implemented essentially that, and it pretty quickly gets pretty good results as measured by the distance per person to land-area- center test. I added one thing to deal with variations in population density. Each district center also has an associated weight. Each 'voronoi cell'/district contains the people with a weighted distance closest to that district center. So, a district center in a high population density area doesn't have to reach very far to gather its allotment of people. There are some states where this doesn't work very well (CA, TX, NV, and a couple others) and a more exhaustive solving method is needed. I think one of the weaknesses of the voronoi method is that population is not continuous, but in discrete census blocks of dozens to thousands of people. The voronoi method can't necessarily tweak to swap a block here and a block there to get within a reasonable margin of equal-population. I think it's worth repeating that I'd prefer to write the law with a way of measuring what a good district mapping is, rather than writing the law with a specific procedure for creating the district mapping. Specific procedures get really complex, and I don't think in this case that a fair procedure ensures a fair outcome. I used the voronoi technique as just one possible way of writing a solver to get the desired result. It could even wind up that the best way to solve for the desired goals is to have a computer do 99% of the work and have a human come back and clean up the edges. Since it's subject to the same scoring in the end, the human couldn't deviate too far from the ideal mapping. Brian Olson http://bolson.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] A computationally feasible method (algorithmic redistricting)
On 9/2/08, Brian Olson [EMAIL PROTECTED] wrote: I have implemented essentially that, and it pretty quickly gets pretty good results as measured by the distance per person to land-area-center test. I added one thing to deal with variations in population density. Each district center also has an associated weight. Each 'voronoi cell'/district contains the people with a weighted distance closest to that district center. So, a district center in a high population density area doesn't have to reach very far to gather its allotment of people. Your maps don't look like voronoi diagrams (edges aren't lines). Do you assign based on Assign voter to district with minimum distance to district centre - Cd Where Cd is some coefficient for the district d. Cd is set so as to give equal populations. If so, have you considered using squared distance instead of distance? Assign voter to district with min (distance to centre)^2 - Cd This gives straight district edges (I think). You might need to change your rule to The best district map is the one where people have the lowest average *squared* distance to the center of their district. There are some states where this doesn't work very well (CA, TX, NV, and a couple others) and a more exhaustive solving method is needed. I think one of the weaknesses of the voronoi method is that population is not continuous, but in discrete census blocks of dozens to thousands of people. The voronoi method can't necessarily tweak to swap a block here and a block there to get within a reasonable margin of equal-population. When I was writing the software to implement the shortest splitline for Rangevoting.org, my solution was to split the border block. (or at least that was my plan ... I don't think I actually implemented it). This page has all the states (v1 of the software) http://rangevoting.org/SplitLR.html This page has the entire 'lower 48' all in one go (v2 of the software) http://rangevoting.org/USsplitLine.png Basically, the algorithm picks a slope to test and then sorts all the blocks based on which line with that slope goes through them. e.g. sort by Cn = Yn - m*Xn It then finds the median block. This means that approx half the population is on one side and half the population is on the other side of the line. (Blocks that have equal Cn are differentiated by Dn = m*Yn + Xn, this means that there is only ever one block) The block itself can be placed on one side or the other. If it worked out population above line: 649,700 population of block: 1000 population below line: 649,300 These blocks would be split into 2 sub-blocks of population 300 and 700. These blocks would still be considered to occur at the same point. The 300 would be assigned to the above the line district and the 700 to the below the line district. The result from the algorithm could be District A: list of blocks that are 100% in district partial blocks 300 of 1000 from tract X 100 of 800 from tract Y 150 of 1050 from tract Z Unless the blocks are massive, there should only be a few partial blocks, accounting for only a small fraction of the district's population. The boundaries could be drawn by a judge or other group by hand. If you really wanted to be strict, they could be automatically split, but I don't think it is worth the effort. They would be unlikely to make much difference and thus it wouldn't be worth the effort corrupting them. I also added a rule which auto-split blocks prior to starting the algorithm, based on a limit. For example, 650k blocks might be converted into 750k by splitting the largest blocks. If the limit was 500, then a 2250 block would be auto split into 5 blocks, 500, 500, 500, 500, 250. I think it's worth repeating that I'd prefer to write the law with a way of measuring what a good district mapping is, rather than writing the law with a specific procedure for creating the district mapping. Specific procedures get really complex, and I don't think in this case that a fair procedure ensures a fair outcome. Sounds reasonable. However, people don't really like randomness. There is considerable resistance to using randomness in elections and people might consider a system where the solution isn't well defined as somewhat random. You mean that the best solution mightn't be picked because nobody could find it? Also, there could be issues if a better solution is found after the deadline, especially, if it favoured one party over another. I used the voronoi technique as just one possible way of writing a solver to get the desired result. It could even wind up that the best way to solve for the desired goals is to have a computer do 99% of the work and have a human come back and clean up the edges. Since it's subject to the same scoring in the end, the human couldn't deviate too far from the ideal mapping. Well a person is going to be unlikely to be able to beat a computer, if the algorithm is reasonably optimised. You
Re: [EM] A computationally feasible method (algorithmic redistricting)
On Sep 2, 2008, at 6:00 PM, Kristofer Munsterhjelm wrote: Your reference to a Cd variable to get population proportionality is interesting. I think part of the problem that you're trying to fix here comes from that clustering (such as by Lloyd's algorithm) optimizes for energy instead of mass. Or in other words, it finds districts so that the average distance for each voter to the closest center is minimized (energy) rather than to find districts that have equal proportions of people within their borders (analogous to equal mass, if each voter is a point of unit mass). Unless I'm mistaken, your generalization of Voronoi cells (with weights linked to the center nodes) is called power diagrams. Not long ago, I stumbled across a paper (draft?) about automatic redistricting involving power diagrams. It's here: http://www.stat.columbia.edu/%7Egelman/stuff_for_blog/fryer.pdf . The authors state that for a certain given compactness measure, the optimally compact district map will consist of power diagrams. They also give an algorithm for finding these optimal (or near- optimal, since the compactness measure is computationally intensive) power diagrams, but it's a bit too complex for my understanding. I'm looking at fryer.pdf and maybe the notation is a little thick for me but it looks like the pi(V_s) equation number 1 in section 3.2 is summing, for each district, the distance between every voter in the district and every other voter in that district. This is a little counterintuitive to me since for so long I've been summing the distance of voters to the center of their district. On the other hand, it does kinda make sense too. Anyway, what my pseudo-voronoi solver does is this: Initialization: • Assign district centers to random points (block coordinates). • Assign census blocks to nearest district center. Repeat until done: • Move district centers towards center of population they were actually assigned. • Adjust district weight, nudging weight up or down if there are too few or two many people assigned to it. • (optional) Nudge district centers away from underpopulated district centers and towards overpopulated district centers. • For each census block, assign census block to the district with the lowest ((distance to block from district center) * weightd) • Fixup district contiguity (because straight-line-nearest can jump across water and other gaps in odd ways) (That's now enshrined here: http://code.google.com/p/redistricter/wiki/NearestNeighborSolver ) Oh, and when it's done (an hour or two for most states), start it over again with a different random starting state because it may have gotten stuck in a local optimum. I think it's worth repeating that I'd prefer to write the law with a way of measuring what a good district mapping is, rather than writing the law with a specific procedure for creating the district mapping. Specific procedures get really complex, and I don't think in this case that a fair procedure ensures a fair outcome. Sounds reasonable. However, people don't really like randomness. There is considerable resistance to using randomness in elections and people might consider a system where the solution isn't well defined as somewhat random. You mean that the best solution mightn't be picked because nobody could find it? Also, there could be issues if a better solution is found after the deadline, especially, if it favoured one party over another. Perhaps the randomness complaint could be diminished by having a default map drawn according to some rules set in law. The redistricting law could refer to that rule, where the rule is very simple - perhaps splitline? Then a state commission or similar could draw the default map so that one is ensured that the results won't be too bad if the redistricting fails. As long as the rule is neutral, the state can't rig the default map, either. I guess my time in Computer Science land has left me pretty comfortable with the idea that there are lots of problems that are too hard to ever reliably get the best solution. I don't know if there's a short-short popularizing explanation of how finding a good solution is Hard while measuring the quality of a solution is pretty quick. If anybody asks and it's not the time, place, or audience for discussing NP Hard problems, I will wave my hands and say, Hey, look over there! Good results, on my one puny computer! With more it'd only get better! Brian Olson http://bolson.org/ Election-Methods mailing list - see http://electorama.com/em for list info
