• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Single Transferable Vote: Incomplete Knowledge and Communication Issues

Thumbnail
View/Open
Single_Transferable.pdf (1.328Mb)
Date
2019
Dewey
Recherche opérationnelle
Sujet
Computational complexity; approximation
Conference name
18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 19)
Conference date
05-2019
Conference city
Montreal QC
Conference country
Canada
Book title
18th International Conference on Autonomous Agents and Multiagent Systems
Author
Veloso, Manuela; Elkind, Edith
Publisher
IFAAMAS
Year
2019
ISBN
978-1-4503-6309-9
URI
https://basepub.dauphine.fr/handle/123456789/20034
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Ayadi, Manel
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ben Amor, Nahla
88821 Laboratoire de Recherche Opérationnelle de Décision et de Contrôle de Processus [LARODEC]
Lang, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Peters, Dominik
98120 Oxford University
Type
Communication / Conférence
Item number of pages
1288-1296
Abstract (EN)
Single Transferable Vote (STV) is used in large political elections around the world. It is easy to understand and has desirable normative properties such as clone-proofness. However, voters need to report full rankings, which can make it less practical than plurality voting. We study ways to minimize the amount of communication required to use single-winner STV. In the first part of the paper, voters are assumed to report their top-k alternatives in a single shot. We empirically evaluate the extent to which STV with truncated ballots approximates STV with full information. We also study the computational complexity of the possible winner problem for top-k ballots. For $k=1$, it can be solved in polynomial time, but is NP-complete when $k\geq 2$. In the second part, we consider interactive communication protocols for STV. Building on a protocol proposed by Conitzer and Sandholm (2005), we show how we can reduce the amount of communication required in practice. We then study empirically the average communication complexity of these protocols, based on randomly generated profiles, and on real-world election data. Our conclusion is that STV needs, in practice, much less information than in the worst case.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.