# The Complexity Of Manipulating K**-Approval Elections** ∗

Andrew Lin Department of Computer Science Rochester Institute of Technology Rochester, NY 14623, USA
apl8378@cs.rit.edu

## Abstract

An important problem in computational social choice theory **is the complexity of undesirable behavior**
among agents, such as control, manipulation, and bribery in **election systems. These kinds of voting** strategies are often tempting at the individual level but disastrous for the agents as a whole. Creating election systems where the determination of such strategies is difficult is thus an important goal.

An interesting set of elections is that of scoring protocols. Previous work in this area has demonstrated the complexity of misuse in cases involving a fixed number of candidates, and of specific election systems on unbounded number of candidates such as Borda. In contrast, we take the first step in generalizing the results of computational complexity of election misuse **to cases of infinitely many scoring protocols**
on an unbounded number of candidates. Interesting families of systems include k-approval and k**-veto**
elections, in which voters distinguish k **candidates from the candidate set.**
Our main result is to partition the problems of these families based on their complexity. We do so by showing they are polynomial-time computable, NP-hard, or polynomial-time equivalent to another problem of interest. We also demonstrate a surprising connection between manipulation in election systems and some graph theory problems.

## 1 Introduction

Elections are a means for choosing one or more candidates given the **preferences of individuals to arrive at a**
decision that attempts to maximize the collective welfare of the individuals (see also [47]). A voting system contains both rules for valid voting, and how one yields a final outcome given the preferences of individual voters. The choice of which rule one uses to choose the winner(s) may affect both the outcome of the election and the behavior of each voter. Voters may be unweighted or weighted, and need not count equally toward the final result.

The computational theory behind voting, as well as systems beyond that of the obvious majority and plurality, were first studied during the French Revolution. Two notable early theorists in this field were Jean-Charles de Borda [?] and Marquis de Condorcet [78]. Borda introduced the system used **for electing**
members to the French Academy of Sciences in 1770. The Borda system favors candidates that are somewhat liked by a lot of voters. Condorcet believed the winner should be one who fares well in pairwise comparisons of the candidates, a concept that is poorly captured by the Borda **election, as it does not view pairs of** candidates.

∗Supported in part by NSF grant IIS-0713061. This work has also appeared in the 3rd International Conference on Agents and Artificial Intelligence [104]
arXiv:1005.4159v3 [cs.AI] 19 Apr 2012