
The Communication Burden of Single TransferableVote, in Practice
Ayadi, Manel; Ben Amor, Nahla; Lang, Jérôme (2018), The Communication Burden of Single TransferableVote, in Practice, in Elkind, Edith; Xia, Lirong, Seventh International Workshop on Computational Social Choice (COMSOC 2018), COMSOC Workshop Series
View/ Open
Type
Communication / ConférenceDate
2018Conference title
7th International Workshop on Computational Social Choice (COMSOC 2018)Conference date
2018-06Conference city
Troy, NYConference country
United StatesBook title
Seventh International Workshop on Computational Social Choice (COMSOC 2018)Book author
Elkind, Edith; Xia, LirongPublisher
COMSOC Workshop Series
Metadata
Show full item recordAuthor(s)
Ayadi, ManelLaboratoire de Recherche Opérationnelle de Décision et de Contrôle de Processus [LARODEC]
Ben Amor, Nahla
Laboratoire de Recherche Opérationnelle de Décision et de Contrôle de Processus [LARODEC]
Lang, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
Single Transferable Vote (STV) is of particular interest for voting, for cognitive reasons (it is easy to understand) and normative reasons (it is clone-proof). However, assuming that voters have to report full rankings sometimes makes it highly unpractical. We study single-winner STV from the point of view of communication. In the first part of the paper, we assume that voters give, in a single shot, their top k alternatives; we define a version of STV that works for such k-truncated votes, and we evaluate empirically (on randomly generated profiles, and on real data) the extent to which it approximates the standard STV rule. In the second part of the paper, we start from the protocol used by Conitzer and Sandholm (2005) for assessing the communication complexity of STV. We give an improvement of it, and then we study empirically the average communication complexity of these protocols, based on the one hand on randomly generated profiles, and on the other hand on real data. We also first give a polynomial-time computable characterization of possible winners at each step of this protocol. Our conclusion is that STV needs, in practice, much less information than in the worst caseSubjects / Keywords
vote; STVRelated items
Showing items related by title and author.
-
Ayadi, Manel; Ben Amor, Nahla; Lang, Jérôme (2018) Communication / Conférence
-
Ayadi, Manel; Ben Amor, N.; Lang, Jérôme; Peters, Dominik (2019) Communication / Conférence
-
Ben Amor, Imen (2010) Communication / Conférence
-
Jouirou, Manel (2003) Communication / Conférence
-
Bouveret, Sylvain; Blanch, Renaud; Baujard, Antoinette; Durand, François; Igersheim, Herrade; Lang, Jérôme; Laruelle, A.; Laslier, J.-F.; Lebon, Isabelle; Merlin, Vincent (2020) Document de travail / Working paper