review articles

Doi: 10.1145/1839676.1839696

Computational complexity may truly be
the shield against election manipulation.
By PiotR faLisze WsKi, eDith hemasPaanDRa,
anD Lane a. hemasPaanDRa
using
complexity
to Protect
elections

For ThouSaNDS oF years, people—and more recently, electronic agents—have been conducting elections. And surely for just as long, people—or more recently, electronic agents—have been trying to affect the outcomes of those elections. Such attempts take many forms. often and naturally, actors may seek to change the structure of the election, for example, by attracting new voters, suppressing turnout, recruiting candidates, or setting election district boundaries. Sometimes voters may even be bribed to vote a certain way. And a voter may try to manipulate an election by casting an insincere vote that may yield a more favorable outcome than would the voter’s sincere vote: not all people who preferred Ralph nader in the 2004 U.S. presidential election actually voted for him.

one might hope that by choosing a particularly
wonderful election system, one can perfectly block

such attacks. However, classic work from economics and political science proves that every reasonable election system sometimes gives voters an incentive to vote insincerely (see Duggan17 and the references therein). Reasonable election systems cannot make manipulation impossible. However, they can make manipulation computationally infeasible.

This article is a nontechnical introduction to a startling approach to protecting elections: using computational complexity as a shield. This approach seeks to make the task of whoever is trying to affect the election computationally prohibitive. To better understand the cases in which such protection cannot be achieved, researchers in this area also spend much of their time working for the Dark Side: trying to build polynomial-time algorithms to attack election systems.

This complexity-based approach to protecting elections was pioneered in a stunning set of papers, about two decades ago, by Bartholdi, Orlin, Tovey, and Trick. 2, 3, 5 The intellectual fire they lit smoldered for quite a while, but in recent years has burst into open flame. Computational complexity may truly be the key to defending elections from manipulation.

Preliminaries and the complexity
of the Winner Problem
In the introduction, we focused on

key;insights

algorithms can be used to seek attacks on elections, and complexity can serve to protect elections from attacks. for some election systems, manipulation has been proven nP-hard.

Dichotomy theorems pinpoint what it is about an election system that makes it computationally resistant to manipulation.

it is natural to consider an election system's computational weaknesses and strengths as one factor, among many, when selecting a system for a given task. in particular, one must consider which types of attacks one most needs to thwart.

ILLustratIon By meLVIn gaLapon