Mapmatics by Paulina Rowińska

Author:Paulina Rowińska
Language: eng
Format: epub
Publisher: Macmillan

Because no computer can generate all possible districting maps even for the smallest of states, scientists build algorithms to sample just a fraction of them. Not just any fraction though, but a set of maps representative of all the possible divisions of a state into electoral districts. The simplest algorithm to generate electoral maps is called ‘random seed and grow’. It starts by randomly choosing a precinct, which will become a ‘seed’ of the first district. Then, it lets the seed ‘grow’ by attaching to it random adjacent precincts until the total number of voters in the resulting blob gets close to the target. Now that the first district is ready, the algorithm plants another seed, which will become the second district, and so on, until all precincts are assigned to electoral districts. Albeit quick and simple, this method isn’t reliable, as experiments have shown that the generated set of maps can be randomly biased towards one party, deeming any comparisons with the real map misleading. Aware of this problem, researchers have been working on developing alternative techniques.

Cho and colleagues, for example, developed a so-called evolutionary algorithm, which mimics the changes that happen in populations of animals or plants over time. In this case, instead, it’s the maps that ‘mutate’ and ‘mate’, creating offspring. First, the computer uses ‘random seed and grow’ to generate a few hundred initial maps, which are ranked according to a pre-defined quality criterion. Some maps ‘mutate’, which means that randomly selected precincts are moved to adjacent districts. Two maps of high quality – to mimic the survival of the fittest – ‘mate’, which involves overlapping them and merging some of the ‘children’ districts to obtain a new map. The worst maps ‘die’, that is, they are removed from the final set. And so, the population evolves, generation by generation, until the sample is large enough.

Evolutionary algorithms aren’t the only option. In 2014, a team of scientists at Princeton University generated electoral maps using a popular sampling method called Markov chain Monte Carlo (MCMC). To visualize how MCMC works, imagine that all possible maps are scattered across a hilly terrain. The ‘better’ a map is, according to a pre-defined criterion, the higher it will be placed. MCMC walks around the area, spending more time in places higher above the ground, and so collecting more plausible maps. At every step, the algorithm picks a random location, and if it’s higher than the current location, it moves there – otherwise, it stays put. After it finishes, we’ll have a list of locations it has visited and the corresponding maps, with the high-quality maps placed higher above the ground appearing on the list more often.

Like with the four-colour theorem, the key to applying MCMC to this problem is turning maps into graphs. This not only lets us communicate the problem to a computer but also offers the techniques from graph theory that let us prove that the method – under some conditions – will lead to a representative sample of maps.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.