Show simple item record

The Communication Burden of Single TransferableVote, in Practice

hal.structure.identifierLaboratoire de Recherche Opérationnelle de Décision et de Contrôle de Processus [LARODEC]
dc.contributor.authorAyadi, Manel
hal.structure.identifierLaboratoire de Recherche Opérationnelle de Décision et de Contrôle de Processus [LARODEC]
dc.contributor.authorBen Amor, Nahla
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLang, Jérôme
dc.date.accessioned2019-06-17T17:04:04Z
dc.date.available2019-06-17T17:04:04Z
dc.date.issued2018
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18999
dc.language.isoenen
dc.subjectvoteen
dc.subjectSTVen
dc.subject.ddc003en
dc.titleThe Communication Burden of Single TransferableVote, in Practiceen
dc.typeCommunication / Conférence
dc.description.abstractenSingle 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 caseen
dc.relation.ispartoftitleSeventh International Workshop on Computational Social Choice (COMSOC 2018)en
dc.relation.ispartofeditorElkind, Edith
dc.relation.ispartofeditorXia, Lirong
dc.relation.ispartofpublnameCOMSOC Workshop Seriesen
dc.relation.ispartofdate2018
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.conftitle7th International Workshop on Computational Social Choice (COMSOC 2018)en
dc.relation.confdate2018-06
dc.relation.confcityTroy, NYen
dc.relation.confcountryUnited Statesen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-06-17T16:57:42Z
hal.identifierhal-02158158*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
AyadiEtAlCOMSOC2018.pdf
Size:
615.6Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record