  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 $\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.
