Algorithmic Redistricting: Elections made-to-order

[Music] okay [Music] so i am between workshops i mean garages i mean homes right now so today i have a computational project for you that doesn't require the workshop this map behind me right now is slowly rearranging itself according to a program that i wrote that uses a statistical technique called a markov chain monte carlo simulated anneal so you can see it's about to get real fuzzy there we go now it's going to get a little bit better i'll explain what all is going on here in a minute but basically this map is being gerrymandered if you've ever heard of gerrymandering it's the process of redrawing the maps that members of congress are elected to represent in order to heavily favor one party or the other as you could imagine this frequently leads to some really wacky shaped districts this is a proposed redistricting of the state of north carolina from a few years ago it was actually eventually thrown out by the courts but it would have given a very slightly red state a 10 to three republican majority in federal congressional seats you can tell that it's gerrymandered because it's got these weirdo districts all over it like this and this and this nothing like my map which produces an eleven to two majority with really normal looking districts on top of everything else politicians are actually really bad at gerrymandering [Music] okay so right off the bat i need to start and say that this is the first video that i've ever made that even approaches the topic of politics so i need everybody to behave in the comments that said the implications of using an algorithm like this are very interesting and making me very hesitant to just go you know drop my source code on github but the algorithm that allows this program to work is actually fascinating and it's this really cool dependent on random numbers thing that i love it and that's what i want to talk to you today about not the process and politics of gerrymandering but how we can draw these maps so efficiently i've made a bunch of videos about randomness being able to generate random numbers using random numbers to calculate mathematical constants using random numbers to form really ornate symmetric patterns but today i'm going to be drawing maps with random numbers but those maps are not going to be random you just need random numbers in order to make this algorithm work i can actually just turn that coefficient to zero we can see what happens to this process when no random numbers are chosen nothing happens the program literally grinds to a halt after a handful of iterations weird huh the core algorithm itself isn't overly complex but it all starts with an accurate map probably because they don't really just want everybody doing this it's actually quite a pain to produce an accurate map of a state with voting precinct data and population accurately represented geographically i found this site called open precincts that not only has election results by precincts but critically precinct maps across a state as relatively easily downloadable files and that is surprisingly difficult to locate but even the data they were able to collect is apparently sometimes lacking like these counties where only majority votes appear to be counted but their data for the 2018 state senate election in north carolina appears to be complete so that is the data set that i used to figure out where all the voters were but voting districts i mean in an ideal world don't represent voters they represent people so for actual population information i pulled u.s census data and combined these maps in matlab ah wait ah no that's not quite right i guess you can smash part of a round globe onto a flat screen in different ways so first i had to reproject both maps into the same coordinate system and then you can fuse them together and now we have a complete picture of where people red votes and blue votes live in the state of north carolina there are a few discrepancies where these maps disagree like how the mortar range at fort bragg has nobody living in it shocking but it is within a voting precinct so technically according to the map that i assembled it's just a big field full of craters with ballots sitting in them but no people the open ocean is actually the same way but in both cases it's not enough people that i'm going to bother to rewrite my map maker because i've already spent a long time literally just on the mapping part of this project and i'm not going to spend another week's worth of evenings to fix the mortar range voter anomaly now that we have a map it's the program's job to draw borders in such a way that each district contains roughly the same number of people the trick is that these borders also encapsulate some number of votes and a representative will be chosen from each district based on the majority vote within that district in a perfect world the proportion of elected representatives from both parties would match the popular vote of the state but we don't live in a perfect world and by cramming one district full of members from one party you can dilute that party's influence everywhere else it gets even more complicated when you have anomalies like in homogeneity in whether or not people vote if you have significant populations of non-voters you can use them to bias the results by including their population in a district but not including their votes to start finding our ideal map we need to start with a set of districts but they're going to be bad districts these can be any random set of borders drawn on our map but i used a technique called a voronoi tessellation where i basically drop a few random literally random points on the map and then each pixel on the map is assigned to the district of the closest point to it making this very polygonal set of district borders more mathematically speaking the borders of the districts are the perpendicular bisectors of the points that i randomly dropped on the map if we look at the populations and votes within the districts of this actually random map we see some districts are weirdly shaped they all contain different numbers of people i mean these population values are all over the place and there are some red majority and some blue majority districts no surprise they were actually random but now we need to make these districts better and the program does this incrementally one pixel at a time the program examines the entire map and randomly chooses one pixel on the boundary of an existing district then the algorithm makes a new map by flipping that pixel from one district to the other holds up both maps and says hmm it has to decide which of these two maps is better which one has equal population distributed across the districts which one has districts that are shaped normally and most importantly fair representation once this election were to take place frankly this scoring process is the hard part but we're going to skip it for right now if the program by its magical criterion decides that the new map is better it keeps that map and now we have an updated map we have incremented one step of the algorithm where one pixel has been changed relative to the previous map but if the program deems the new map inferior it rolls some dice and sometimes accepts the new map even though it's a worse fit than the map that it already had it's this willingness to take steps backwards that actually allows this code to work at the beginning when i said that removing the randomness from this algorithm made the algorithm fail this is the number that i was changing the fraction of bad maps that slip through and get accepted if we say that the program throws out every bad map and only accepts good maps that's the equivalent of turning this number to zero and then the code just stops running it sort of fiddles with all the borders a little bit and then from that moment forward every change every conceivable pixel that you would flip would make the map that you have worse than the map that you have that isn't to say that you then have the best map you just have the best map relative to all of the other maps that are related to your starting map by the fact that they only vary by a pixel this map is stuck the randomness has been turned to zero and it has stopped evolving it's not a good map i mean all of these maps are better but if you'll notice all of these maps are completely different than that map they need more stuff to change you can't get from here to anywhere over here by only changing a single pixel the algorithm has to sort of randomly stumble around until this starts to look like one of these and then the scoring and metrics thing takes over and really hones in the design i think that a fantastic analogy for this can be found in your pocket or at least it can be found in mine because my pocket still contains wired audio devices so this is the monte carlo method for untangling tangled headphones first you need to apply a driving force something that you want to have happen after you're done running the monte carlo simulation say i want this wire and this one those are actually the same one i want this wire and this wire to be very far from each other so i'm going to pull on these very slightly but if i pull on them too quickly obviously this is just going to not so what we need to do is increase the temperature of the system we need to add some randomness and after a minute the free energy of the system has decreased there's just one local minimum here at the end that is actually a knot that i need to get rid of there we go so believe it or not the monte carlo method for untangling headphones killed in the undergraduate physics lounge five years ago at nc state not sure that the joke will land quite as well on youtube but i told it anyway it's worth noting though most of the random jostling that you do isn't actually helping you to untangle your headphones but some of it is and on average the jostling combined with the fact that you're slowly pulling the wires apart will untangle the headphones and that's exactly what this algorithm is doing but to maps the random jostling is really necessary if you tried to write down all of the ways that these wires could overlap and then enumerate which ones were the least tangled you'd be here for a very long time likewise the state of north carolina as i've drawn it here has 27 921 pixels and each pixel can be in one of 13 different districts that means that there are 6.27 times 10 to the 57 possible maps that we could draw roughly we can't possibly sit here and look at and score all of those 10 to the 57 district 10 to the 57 yeah god that's a lot districts like it's computationally it's a non-starter so instead we do the next best thing we take a map that we know is a terrible map and then we sort of massage that map with statistics and with randomness making incremental changes one pixel at a time until we have a really good map that means that we aren't guaranteed to reach the best answer or even remotely similar answers these are maps that started from different initial tessellations and then evolved using the same set of rules in some places where the boundary conditions dominate the result we see these different simulations evolving almost to the exact same shape of district arriving at nearly identical solutions but in other places the initial conditions and the random numbers chosen along the way are significant and we see a wide variety of solutions while some are better than others all of these are generally good solutions to the same problem so what can we do with this program basically we can make election maps to order you select how weird shaped the districts can be specify your desired election results and then feed it an initial condition and wait god that's a weird phrase isn't it desired election results i mean even for fair maps where the representatives are proportional to the voters the program still has to sort of pick which districts are red and which districts are blue i mean it's the act of redistricting whether you're gerrymandering or not is almost like predestination it's kind of depressing in this case i have specified this sort of skewed sine curve as my ideal set of fair districts note that the curve crosses 50 at the same value as the actual popular vote in the state about a 47 to 53 percent split according to the data that i pulled this creates a few deep red districts a few deep blue districts and then a smooth grade in between with a couple districts that might flip year to year this reduces incumbent gerrymandering in a reasonable way by preserving some swing districts in the middle but is fair to the regions that are legitimately deep blue or deep red and in this case the map produced is sort of aggressively normal looking the centering metric and the perimeter to area ratio are very happy the districts all have similar populations and there are seven red districts and six blue districts in line with the actual popular vote if instead we wanted gerrymandered districts all we need to do is change that panel instead of a smooth curve that crosses 50 at the popular vote we set up this crazy skewed distribution that clusters one party into a few dense districts and the other party then just barely wins all the rest this is a relatively normal looking 11 to 2 red map giving a slight majority a significant majority and this is a pretty normal looking 8 to 5 blue map gerrymandering can even give a minority a significant victory granted you can't ask it for too much while still maintaining that all the districts need to be somewhat normally shaped it won't actually complete this is a simulation where i tried to give the blue minority 10 of 13 seats and it just didn't work you can see that it's trying to rearrange these districts and these numbers will just not go down if you wanted to incumbent gerrymander where you remove swing districts entirely but keep the party lines fair there's a map for that too in this map that looks pretty normal except for charlotte sorry charlotte the overall election results in a six blue seats seven red seats distribution just like it should but no individual race was decided by less than a landslide 13.2 percent at this point it's all pretty pointless so now we need to ask how does this program actually do what it does what are the magical metrics that i'm using to effectively tug on the wires while i shake the map not this metric not this metric either these metrics at the beginning i said that this program was basically drawing lines to partition people red votes and blue votes scattered around on a map in the code i can literally select a pixel and say within this pixel there are a certain number of people a certain number of red votes and a certain number of blue votes now in order to score the map the program looks at each district and basically runs an election it adds up all of the votes from all of the pixels that are in that district to see who wins and by how much and then adds that result to this plot at that point it runs a least squares fit to see how close the actual districts are to the desired election results again kind of a disturbing phrase desired election results but that's literally what we're doing the dots that i've circled in magenta here receive extra weight in the fit because i wanted to make the swing seats near 50 percent the most important to get right for population i want all the districts to have the same population so i initially added up all of the people in each district and then took the standard deviation in population across all the districts a small standard deviation meant that all of the districts have the same population however i found that this wasn't penalizing outliers quite enough and i ended up using a modified standard deviation with a fourth power in it instead of a square but that's sort of a minor correction district shape is much harder one of the most intuitive metrics would have been a surface area to volume ratio or here a perimeter to area ratio since we're in 2d clearly these two districts have different perimeter to area ratios this one has this weird little protrusion that adds a lot of perimeter but not very much area and we don't want that but to get from this shape to this shape we need to remove one pixel at a time unfortunately if you flip this pixel or you know the vast majority of these pixels on your way from this map to this map it actually makes the perimeter to area ratio worse so the program ends up favoring sort of round and hard to remove protrusions turns out in this case that the perimeter to area ratio while it is something that you want to optimize isn't a very useful metric it isn't an efficient way to pull on the wires because it's non-monotonic in configuration space to put it very abstractly the last metric that i added to the simulation before compiling this video is actually my favorite for how difficult it was to implement efficiently but i think i did it in an elegant way it does a much better job at eliminating protrusions by computing the center of population within each district and then measuring how far away each pixel in the district is from that center this makes weird protrusions sort of energetically expensive from the perspective of the simulation because they are far from the middle and therefore there's a significant weight to flipping these pixels and making these protrusions go away if you crank this metric's weight to the absolute max you basically end up with a fuzzy voronoi tessellation again that wiggles around it's kind of neat now i need to point out that there are some really good ways to implement an algorithm like this efficiently and there are some really bad ways to implement an algorithm like this no efficiency if the program literally looked at both maps and added up the population and the votes across the entire map to generate a score every time that it wanted to flip a single pixel it would take forever because you gotta add up so many numbers so instead of re-adding the entire map it just keeps a running tally of the population and vote count in each state and when it wants to flip a pixel it adds the population of that pixel to the new district's tally and then subtracts the population of that pixel from the original district so it doesn't have to add up the whole district again and as long as that journaling isn't corrupted it works great unfortunately some of my very early attempts at this algorithm screwed up the counting and inadvertently were adding and subtracting the wrong number of votes from adjacent districts inadvertently simulated extreme voter fraud because i had more people voting than actually existed in the simulation so i ended up fixing that as for the surface area and population centering metrics those were much more of a pain to make efficient for the centering for example i needed to be able to add and remove individual entries from a 2d weighted average location turns out it's a pretty concise equation it just you know takes a few minutes with a pen and then you've got to type it all into matlab without making a mistake the very first big problem that i had to solve was how to keep the district's whole how to prevent one district from growing a protrusion and then having another district grow into it and cut the first district into two i hoped that this wasn't going to be a problem and that statistics were going to save me but especially early on with very weird shaped districts statistics did not save me in the current simulation if flipping a pixel would break a district that pixel isn't even scored that new map is thrown away immediately and forgotten of course this would be really easy if you flipped that and then you looked at the map and you actually like ran an image recognition partition thing to determine if the district had been broken in half but that would be oppressively computationally intensive to execute an image recognition blob finding algorithm every time you wanted to flip a single pixel in order to do this efficiently i had to determine whether flipping a single pixel would cause any district around that region to be broken in half by only looking at the eight pixels that surrounded the pixel being flipped how did i even do that ah yeah yeah the thing with all the squares okay so it was complicated the most important metric in this simulation that sort of gives the districts regular shapes i ended up calling statistical surface tension basically pixels with more boundaries attempt to flip more frequently this pixel right here with three borders for example is more likely to get selected for a flip and then randomly accepted for that flip to make this a nice straight line as opposed to this pixel with only one border where we really don't want that one to flip and make this a bumpy line on average then all of the shapes kind of slowly equiaxed into nice rounded blobs when you put all of this together you get a really cool algorithm that is able to tune the shapes of districts on a map based on data within that map and guide those districts to specific criteria that you define using random numbers i don't have time to get that much into the fine minutia of hyper parameter tuning but there was an awful lot of it but basically i determined the fastest way to get a good result was to split this into three phases in phase one the centering and population metrics have very high weights so that the map basically gets all of the districts to have the same number of people in them and get them roughly normally shaped in phase two i significantly turn down the statistical surface tension and then increase the randomness so each district basically increases its surface area with these weird spider webbing fingers and then because each district has more surface area and can basically sense all of the possible regions around it that it could grow into it makes the next step a lot easier because in phase three you crank up the weight on voter selection and that's when you actually gerrymander the map you turn the surface tension back on which causes the districts to round back off into nice even shapes but the shapes are determined by where the voters are the fantastic thing is that this algorithm this statistical method of sampling the monte carlo markov chain simulated anneal when you put it all together can basically determine shapes for just about anything you don't have to use it for gerrymandering you could plug any data into a map like this and you could make it anneal into a particular shape and you can make it an optimal shape for whatever metrics you decide again maybe not the optimal shape but and optimal shape of course in this case where i'm trying to make maps it won't give me everything that i want if you ask it to make something that's too skewed your districts are going to end up with really weird shapes or it won't even finish solving but i have found that you can ask it for quite a lot and uh it will deliver i have spent way too many hours on this project because i think that algorithms like this are fantastically interesting and i hope that you do too if you're watching all the way at the end of the video you probably do there's so many things that i didn't have time to fully explain about implementing an algorithm like this so ask away in the comments and i will try to answer as many as i can thanks for watching and subscribe for more [Music] you

Channel: AlphaPhoenix

Views: 233,429

Rating: 4.955071 out of 5

Keywords: Alpha, Phoenix, Alpha phoenix, Alphaphoenix, Math, monte carlo, simulation, anneal, markov chain, voroni, tessellation, evolution, equilibration, fitting, algorithm, AI, computer, statistics, matlab, efficiency, optimization, pixel, image processing, Map, precinct, census, Politics, gerrymander, districts, congress, election

Id: Lq-Y7crQo44

Length: 26min 48sec (1608 seconds)

Published: Mon Jun 28 2021

Reddit Comments

[u/unagisongs]

The fact that Democrats aren't doing exactly this shows you little they give a shit about winning. Let's not even dink around with ethical concerns. Democrats are willing to go to Republican low of lows to ape conservative policy. Yet something like this won't touch with a 10ft pole because they'd actually be forced to govern.

[u/Sdl5]

Sort of a point to consider here:

IF a district created this way looks "perfectly normal" then is it not at least 50% odds that it DOES reflect the voters residing in an area?

I mean, locals would know if it drew a line down a major seeming division point that in reality split a cohort- and call out the linedrawers. But outside that...

[u/TheRazorX]

/u/martini-meow worthy of a pin?

[u/non-troll_account]

Now, I know this is a politics subreddit, but this guy's science content is TOP-TEIR stuff. He works in a lab with ultra-high vacuum chambers, and makes awesome educational content. This was just some stuff he came up with on the side.