License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10101.4
URN: urn:nbn:de:0030-drops-25585
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2558/
Go to the corresponding Portal

Walsh, Toby

Manipulability of Single Transferable Vote

pdf-format:
10101.WalshToby.Paper.2558.pdf (0.1 MB)

Abstract

For many voting rules, it is NP-hard to compute a successful manipulation.
However, NP-hardness only bounds the worst-case complexity. Recent
theoretical results suggest that manipulation may often be easy in practice. We
study empirically the cost of manipulating the single transferable vote (STV) rule. This was one of the first rules shown to be NP-hard to manipulate. It also appears to be one of the harder rules to manipulate since it involves multiple rounds and since, unlike many other rules, it is NP-hard for a single agent to manipulate without weights on the votes or uncertainty about how the other agents have voted. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible. It remains an interesting open question if manipulation by a coalition of agents is hard to compute in practice.

BibTeX - Entry

@InProceedings{walsh:DagSemProc.10101.4,
  author =	{Walsh, Toby},
  title =	{{Manipulability of Single Transferable Vote}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2558},
  URN =		{urn:nbn:de:0030-drops-25585},
  doi =		{10.4230/DagSemProc.10101.4},
  annote =	{Keywords: Computational social choice, manipulability, STV voting, NP-hardness}
}

Keywords: Computational social choice, manipulability, STV voting, NP-hardness
Collection: 10101 - Computational Foundations of Social Choice
Issue Date: 2010
Date of publication: 20.05.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI