Unveiling the Truth in Liquid Democracy with Misinformed Voters
Becker, Ruben; D’Angelo, Gianlorenzo; Delfaraz, Esmaeil; Gilbert, Hugo (2021), Unveiling the Truth in Liquid Democracy with Misinformed Voters, in Fotakis, Dimitris; Insua, David Ríos, Algorithmic Decision Theory, Springer, p. 132-146. 10.1007/978-3-030-87756-9_9
TypeCommunication / Conférence
Conference title7th International Conference, ADT 2021
Book titleAlgorithmic Decision Theory
Book authorFotakis, Dimitris; Insua, David Ríos
Number of pages441
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)This 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.
Subjects / KeywordsLiquid democracy; Truth revelation; Approximation algorithms
Showing items related by title and author.
Angriman, Eugenio; Becker, Ruben; D'Angelo, Gianlorenzo; Gilbert, Hugo; van der Grinten, Alexander; Meyerhenke, Henning (2021) Communication / Conférence