Some political mischief doesn’t need a bag of cash or a smoke-filled chamber. All you need is a map and a little perseverance. One of the oldest games in democratic politics is the manipulation of election district borders, which Americans have referred to as gerrymandering for more than 200 years.
What happens when mathematicians begin to examine the subject in greater detail is more recent and far more disturbing. What they discover is not comforting.
| Topic Overview: The Traveling Voter Problem & Electoral Districting | |
|---|---|
| Core Concept | The Traveling Voter Problem — designing voting districts where every voter goes to their nearest ballot box |
| Field | Computational Social Choice, Electoral Mathematics, Political Science |
| Key Term | Gerrymandering — manipulation of district boundaries to favor a particular party or candidate |
| Origin of “Gerrymandering” | Named after Massachusetts Governor Elbridge Gerry, who in 1812 approved a salamander-shaped district to benefit his party |
| Computational Complexity | Finding a geographic district division to guarantee a preferred winner is NP-complete |
| Algorithm Developed | A greedy algorithm capable of detecting possible electoral manipulations through spatial analysis |
| Elections Tested | 2015 Israeli General Election, 2015 UK General Election |
| Legal Milestone | U.S. Voting Rights Act of 1965 — required federal approval for district changes in states with documented voter suppression |
| Systems Affected | Electoral colleges, Westminster-style parliaments (UK, Canada, Australia), corporate divisional voting, sensor networks |
| Reference | Stanford Encyclopedia of Philosophy — Voting Methods |
The first infraction occurred in 1812 when Elbridge Gerry, the governor of Massachusetts, approved a state senate district that was so deformed that it was printed alongside a salamander graphic in a Boston newspaper. The name of the creature stuck. It’s easy to overlook the fact that Gerry’s technique involved more than just drawing unsightly lines; it also involved proximity, geography, and the voters who were ultimately counted together. A candidate who would lose under one plan becomes unassailable under another if you move a neighborhood here and cut a precinct there. Back then, the math was intuitive. It is now much more demanding.
In a fair district system, should every voter cast their ballot at the polling station nearest to their home? This issue sounds almost bureaucratic, but researchers investigating what they’ve called the “Traveling Voter Problem” are attempting to answer it. The answer seems clear: they should, of course. However, formalizing that idea proves to be extremely difficult, posing issues that lie awkwardly on the periphery of electoral theory and computer science.
It has been demonstrated that it is NP-complete to discover a geographic division that elects a chosen candidate while upholding the principle that voters always go to the closest polling place. That is not a small technical detail. It indicates that there isn’t a known effective algorithm to solve it in the best possible way. However, the problem is exploitable because of the same mathematical complexity.
The irony at play here is difficult to ignore. District systems were designed to provide communities with cohesive representation and a local voice. Canada, the United States, and the United Kingdom all inherited or created variations of the same system. Voters are part of districts, which send representatives to make choices. In theory, it’s clean enough. Political parties on both sides of the Atlantic have recognized and actively exploited the reality that whomever controls where the lines are drawn actually has a great deal of influence. Gerrymandering has been practiced by US parties for many years. As early as the 18th century, rotten boroughs in the UK infuriated the populace, which led to the introduction of reform legislation starting in 1832.
Recent computer research on this topic is noteworthy since it goes beyond historical study and into prediction. Researchers tested actual ballot box data from the 2015 general elections in Israel and the UK using a greedy algorithm, which is a workable but imperfect approach. The findings demonstrated that different winners would have been created by different geographic divisions of the same voter demographics. Theoretically, nothing is different. Actually, it’s different. Although the extent of such effects in current elections is yet unknown, the notion is no longer hypothetical.
While the computational side was catching up, the political science community seemed to have known this intuitively for years. In an effort to determine when and how gerrymandering had taken place, earlier scholarly research examined the practice using statistical modeling and historical vote data. However, formal computational research had mostly ignored spatial geography, which is the actual location of voters, ballot boxes, and district lines in relation to one another. Different types of solutions are possible when the problem is approached as a geometric and algorithmic one rather than just a political science one. Some of those responses are awkward.
The proposal for “rational districting”—a concept that the majority of democratic reformers would embrace right away—does not completely eradicate manipulation, as this study subtly shows. It simply alters its form. Even if voters are required to always go to the closest polling station, a skilled map-drawer can nonetheless work within that restriction and manipulate results. The issue is intricate enough to appear incidental, difficult enough to be disputed, and significant enough to alter the balance of power. In the past, no one has ever been deterred by that combination.
