Show simple item record

Unveiling the Truth in Liquid Democracy with Misinformed Voters

dc.contributor.authorBecker, Ruben
dc.contributor.authorD’Angelo, Gianlorenzo
dc.contributor.authorDelfaraz, Esmaeil
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGilbert, Hugo
dc.date.accessioned2022-02-22T11:02:37Z
dc.date.available2022-02-22T11:02:37Z
dc.date.issued2021
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22698
dc.language.isoenen
dc.subjectLiquid democracyen
dc.subjectTruth revelationen
dc.subjectApproximation algorithmsen
dc.subject.ddc006en
dc.titleUnveiling the Truth in Liquid Democracy with Misinformed Votersen
dc.typeCommunication / Conférence
dc.description.abstractenThis paper investigates the so-called ODP-problem that has been formulated by Caragiannis and Micha. This problem considers a setting with two election alternatives out of which one is assumed to be correct. In ODP, the goal is to organise the delegations in a social network in order to maximize the probability that the correct alternative is elected. While the problem is known to be computationally hard, we strengthen existing hardness results and show that the approximation hardness of ODP highly depends on the connectivity of the social network and the individual accuracies. Interestingly, under some assumptions, on either the accuracies of voters or the connectivity of the network, we obtain a polynomial-time 1/2-approximation algorithm. Lastly, we run extensive simulations and observe that simple algorithms relying on the abilities of liquid democracy outperform direct democracy on a large class of instances.en
dc.identifier.citationpages132-146en
dc.relation.ispartoftitleAlgorithmic Decision Theoryen
dc.relation.ispartofeditorFotakis, Dimitris
dc.relation.ispartofeditorInsua, David Ríos
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpages441en
dc.relation.ispartofurl10.1007/978-3-030-87756-9en
dc.subject.ddclabelMéthodes informatiques spécialesen
dc.relation.ispartofisbn978-3-030-87755-2en
dc.relation.conftitle7th International Conference, ADT 2021en
dc.relation.confdate2021-11
dc.relation.confcityToulouseen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-87756-9_9en
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2022-02-22T10:59:32Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
Unveiling_Becker.pdf
Size:
852.0Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record