Unveiling the Truth in Liquid Democracy with Misinformed Voters.

Ruben Becker, Gianlorenzo D'Angelo, Esmaeil Delfaraz, Hugo Gilbert
ADT 2021

Abstract : Liquid democracy is a voting paradigm that allows voters that are part of a social network to either vote directly or delegate their voting rights to one of their neighbors. The delegations are transitive in the sense, that a voter who decides to delegate, delegates both her own vote and the ones she has received through delegations. The additional flexibility of the paradigm allows to transfer voting power towards a subset of voters ideally containing the most expert voters on the question at hand. It is thus tempting to assume that liquid democracy can lead to more accurate decisions. This claim has been investigated recently, maybe most importantly, by Kahng, Mackenzie, and Procaccia (AAAI'18) and Caragiannis and Micha (IJCAI'19), who provide however mostly negative results using a model similar to the uncertain dichotomous choice model. In this paper, we provide new insights on this question. In particular, we investigate the so-called ODP-problem that has been formulated by Caragiannis and Micha. Here, we are in 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 the social network in order to maximize the probability that the correct alternative, referred to as ground truth, is elected. While the problem is known to be computationally hard, we strengthen existing hardness results by providing a novel strong approximation hardness result: For any positive constant C, we prove that, unless P = NP, there is no polynomial-time algorithm for ODP that achieves an approximation guarantee of \alpha \ge (ln n)^{−C}, where n is the number of voters. The reduction designed for this result uses poorly connected social networks in which some voters suffer from misinformation. Interestingly, under some hypothesis on either the accuracies of voters or the connectivity of the network, we obtain a polynomial-time 1/2-approximation algorithm. This observation proves formally that the connectivity of the social network is a key feature for the efficiency of the liquid democracy paradigm. Lastly, we run extensive simulations and observe that simple algorithms (working either in a centralized or decentralized way) outperform direct democracy on a large class of instances. Overall, our contributions yield new insights on the question in which situations liquid democracy can be beneficial.