| Voting and elections are at the core of democratic societies. People vote to elect leaders, decide policies, and organize their lives, but elections also have natural applications in computer science. For example, agents in multiagent systems often need to work together to complete some task, but each agent may have its own set of beliefs, preferences, and goals. Voting provides agents with a natural way to reach decisions that take all their preferences into account. With elections playing such an important role both in real-life political settings and in computer science, it is natural to ask about their resistance to misuse.;Two particular types of election misuse are manipulation and bribery. In manipulation, a group of voters chooses to misrepresent its preferences in order to obtain a more desirable outcome, and in bribery an outside agent, the briber, asks (possibly at a cost) a group of voters to change its votes, to obtain some outcome desirable for the briber. Classical results from political science show that, for any reasonable election system, there are scenarios where at least some voters have an incentive to attempt manipulation.;In this thesis we seek to protect elections from manipulators and bribers by making their computational task of finding good manipulations/bribes prohibitively expensive. When this is not possible, we seek to better understand (and even improve) the algorithmic attacks that manipulators and bribers can employ. In doing so, we develop new models of manipulation and bribery, and provide new approaches to studying the computational complexity of bribery and manipulation in elections. |
