# When Can Liquid Democracy Unveil the Truth?

arXiv: https://arxiv.org/abs/2104.01828 · HTML: https://mlsanity.com/paper/2104.01828/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 5 Apr 2021.

## Builds on (most cited first, 11 of 11)

- [The Fluid Mechanics of Liquid Democracy](https://mlsanity.com/paper/1808.01906/) (2018)
- [On Rational Delegations in Liquid Democracy](https://mlsanity.com/paper/1802.08020/) (2018)
- [Binary Voting with Delegable Proxy: An Analysis of Liquid Democracy](https://mlsanity.com/paper/1707.08741/) (2017)
- [Power in Liquid Democracy](https://mlsanity.com/paper/2010.07070/) (2020)
- [Incentivising Participation in Liquid Democracy with Breadth-First Delegation](https://mlsanity.com/paper/1811.03710/) (2018)
- [Iterative Delegations in Liquid Democracy with Restricted Preferences](https://mlsanity.com/paper/1809.04362/) (2018)
- [Voting Behaviour and Power in Online Democracy: A Study of LiquidFeedback in Germany's Pirate Party](https://mlsanity.com/paper/1503.07723/) (2015)
- [Flexible Representative Democracy: An Introduction with Binary Issues](https://mlsanity.com/paper/1811.02921/) (2018)
- [On Parameterized Complexity of Liquid Democracy](https://mlsanity.com/paper/2011.14192/) (2020)
- [Tracking Truth by Weighting Proxies in Liquid Democracy](https://mlsanity.com/paper/2103.09081/) (2021)
- [Popular Branchings and Their Dual Certificates](https://mlsanity.com/paper/1912.01854/) (2019)

## Built on by (most cited first, 2 of 2)

- [Towards Group Learning: Distributed Weighting of Experts](https://mlsanity.com/paper/2206.02566/) (2022)
- [Liquid Democracy for Low-Cost Ensemble Pruning](https://mlsanity.com/paper/2401.17443/) (2024)

## Abstract (arXiv)

In this paper, we investigate the so-called ODP-problem that has been formulated by Caragiannis and Micha [10]. 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 α ≥ (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.