Strategic Manipulation in Voting Systems

Abstract

In this thesis, we are going to study the strategic manipulation of voting rules, mostly scoring rules. In the first part, we focus on naive manipulation, where we have a coalition of manipulators and the other voters vote sincerely. In Section 1.4 we introduce a new measure of manipulability of voting rules, which reflects both the size and the prevalence of the manipulating coalitions and is adaptable to various concepts of manipulation. We place this measure in a framework of probabilistic measures that organizes many results in the recent literature. We discuss algorithmic aspects of computation of the measures and present a case study of exact numerical results in the case of 3 candidates for several common voting rules. In Section 1.5 we study manipulability measures as power indices in cooperative game theory. In Chapter 2, we study the asymptotic behaviour of a model of manipulation called safe manipulation for a given scoring rule under the uniform distribution on voting situations. The technique used is computation of volumes of convex polytopes. We present explicit numerical results in the 3 candidate case. In the second part of the thesis, we adopt a game-theoretic approach to study strategic manipulation. We try to explore more behavioural assumptions for our voters. In Chapter 3, we have an introduction to voting games and different factors such as the available amount of information, voters’ strategies and ability to communicate . In Chapter 4, we consider best-reply dynamics for voting games in which all players are strategic and no coalitions are formed. We study the class of scoring rules, show convergence of a suitably restricted version for the plurality and veto rules, and failure of convergence for other rules including k-approval and Borda. In Chapter 5,We discuss a new model for strategic voting in plurality elections under uncertainty. In particular, we introduce the concept of inertia to capture players’ uncertainty about poll accuracy. We use a sequence of pre-election polls as a source of partial information. Under some behavioural assumptions, we show how this sequence can help agents to coordinate on an equilibrium outcome. We study the model analytically under some special distributions of inertia, and present some simulation results for more general distributions. Some special cases of our model yield a voting rule closely related to the instant-runoff voting rule and give insight into the political science principle known as Duverger’s law. Our results show that the type of equilibrium and the speed of convergence to equilibrium depend strongly on the distribution of inertia and the preferences of agents. This thesis is based on the results of the following papers [1], [2], [3], [4] and [5].