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 | Schools: | School of Physical and Mathematical Sciences | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SPMS Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Tspmsg0802680e.pdf | 448.93 kB | Adobe PDF | View/Open |
Page view(s) 50
517
Updated on Mar 18, 2024
Download(s) 20
219
Updated on Mar 18, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.