Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/50841
Title: Essays on the complexity of voting manipulation
Authors: Obraztsova, Svetlana
Keywords: DRNTU::Science::Mathematics
Issue Date: 2012
Source: Obraztsova, S. (2012). Essays on the complexity of voting manipulation. Doctoral thesis, Nanyang Technological University, Singapore.
Abstract: In their groundbreaking paper, Bartholdi, Tovey and Trick [6] argued that many well-known voting rules, such as Plurality, Borda, Copeland and Maximin are easy to manipulate. Following the direction proposed by this paper we examine the influence of features to which attention was not paid previously, namely, tie-breaking rules, and additional constraints, namely, the distance to the manipulator’s true preferences, on the complexity of manipulating elections. In Chapter 3 we show that all scoring rules, (simplified) Bucklin and Plurality with Runoff are easy to manipulate if the winner is selected from all tied candidates uniformly at random. This result extends to Maximin under an additional assumption on the manipulator’s utility function that is inspired by the original model of [6]. In contrast, we show that manipulation under randomized tie-breaking is hard for Copeland, Maximin, STV and Ranked Pairs. In Chapter 4 we demonstrate that Plurality, Maximin, Copeland and Borda, as well as many families of scoring rules, become hard to manipulate if we allow arbitrary polynomial-time deterministic tie-breaking rules. In Chapter 5, we investigate the complexity of optimal manipulation, i.e., finding a manipulative vote that achieves the manipulator’s goal yet deviates as little as possible from her true ranking. We study this problem for three natural notions of closeness, namely, swap distance, footrule distance, and maximum displacement distance, and a variety of voting rules, such as scoring rules, Bucklin, Copeland, and Maximin. For all three distances, we obtain polynomial-time algorithms for all scoring rules and Bucklin and hardness results for Copeland and Maximin.
URI: https://hdl.handle.net/10356/50841
DOI: 10.32657/10356/50841
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Theses

Files in This Item:
File Description SizeFormat 
Tspmsg0802680e.pdf448.93 kBAdobe PDFThumbnail
View/Open

Page view(s) 50

408
Updated on Jun 26, 2022

Download(s) 20

161
Updated on Jun 26, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.