Election Tampering and Game Theory
In the aftermath of the 2016 presidential election and with 2018 midterms fast approaching, many people are concerned with how the United States should defend against election tampering. One of the most powerful and important tools for this is still manual auditing of individual districts votes. However, this is too labor intensive to do for every district. With this realization, you can start to see the problem as a game. One player is the government trying to minimize the effects of election tampering by choosing specific districts to audit. The other player is the tampering organization that needs to pick a subset of districts to attacks. With a framework like this, you can begin to intelligently ask and answer questions about what the attacker is most likely to do and how to most effectively respond.
This was the goal of Vanderbilt University’s Yevgeniy Vorobeychik and his collaborators in their paper Optimally Protecting Elections. His model allows the attacker to target individual districts so that their voters are effectively removed. The model also has a measure of the importance of a district based on the population and other factors of the district. Using their model, the team developed algorithms to find optimal behavior for defenders, attackers, as well as test election results to give a probability of tampering. Unfortunately, the attacker’s algorithm can be run in polynomial time, while finding the optimal defending strategy was proven to be NP Hard. In a large nation such as the US, this could mean that finding an optimal attacking strategy can be tractable while finding the optimal defense is not. They did, however, develop an efficient approximation algorithm for defense using linear programming, a common practice for estimating optimal solutions to such intractable problems. In coming years, such algorithms could prove vital in protecting the integrity of elections.