Skip to main content
SpringerLink
Log in

Unveiling the Truth in Liquid Democracy with Misinformed Voters

  • Conference paper
  • First Online:
Algorithmic Decision Theory (ADT 2021)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 13023))

Included in the following conference series:

  • 677 Accesses

Abstract

This paper investigates the so-called ODP-problem that has been formulated by Caragiannis and Micha [8]. 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 69.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    The choice of a set voter can be done arbitrarily when several choices are possible.

  2. 2.

    We use that \(n\le 4^{N}\), whose proof is available in a long version of the paper [2].

  3. 3.

    This method uses a parameter \(\alpha \) set to 1 and a cap function \(C: x\rightarrow 10\log (x)^{1/3}\).

References

  1. Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)

    Google Scholar 

  2. Becker, R., D’Angelo, G., Delfaraz, E., Gilbert, H.: When can liquid democracy unveil the truth? arXiv preprint arXiv:2104.01828 (2021)

  3. Behrens, J., Kistner, A., Nitsche, A., Swierczek, B.: The principles of LiquidFeedback. Interaktive Demokratie (2014)

    Google Scholar 

  4. Berend, D., Chernyavsky, Y.: Effectiveness of weighted majority rules with random decision power distribution. J. Publ. Econ. Theory 10(3), 423–439 (2008)

    Article  Google Scholar 

  5. Bloembergen, D., Grossi, D., Lackner, M.: On rational delegations in liquid democracy. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, 27 January– 1 February 2019, pp. 1796–1803 (2019)

    Google Scholar 

  6. Brill, M.: Interactive democracy. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, 10–15 July 2018, pp. 1183–1187 (2018)

    Google Scholar 

  7. Brill, M., Talmon, N.: Pairwise liquid democracy. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, Stockholm, Sweden, 13–19 July 2018, pp. 137–143 (2018)

    Google Scholar 

  8. Caragiannis, I., Micha, E.: A contribution to the critique of liquid democracy. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, 10–16 August 2019, pp. 116–122 (2019)

    Google Scholar 

  9. Christoff, Z., Grossi, D.: Binary voting with delegable proxy: an analysis of liquid democracy. In: Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2017, Liverpool, UK, 24–26 July 2017, pp. 134–150 (2017)

    Google Scholar 

  10. Colley, R., Grandi, U., Novaro, A.: Smart voting. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 1734–1740 (2020)

    Google Scholar 

  11. De Condorcet, N., et al.: Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. Cambridge University Press (1785)

    Google Scholar 

  12. Dey, P., Maiti, A., Sharma, A.: On parameterized complexity of liquid democracy. In: Mudgal, A., Subramanian, C.R. (eds.) CALDAM 2021. LNCS, vol. 12601, pp. 83–94. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-67899-9_7

    Chapter  Google Scholar 

  13. Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th ACM Symposium on Theory of Computing, STOC 2014, New York, NY, USA, 31 May– 03 June 2014, pp. 624–633 (2014)

    Google Scholar 

  14. Erdös, P., Rényi, A.: On random graphs I. Publ. Math. Debrecen 6(290–297), 18 (1959)

    MATH  Google Scholar 

  15. Erwig, M.: The graph Voronoi diagram with applications. Networks 36(3), 156–163 (2000)

    Article  MathSciNet  Google Scholar 

  16. Escoffier, B., Gilbert, H., Pass-Lanneau, A.: The convergence of iterative delegations in liquid democracy in a social network. In: Fotakis, D., Markakis, E. (eds.) SAGT 2019. LNCS, vol. 11801, pp. 284–297. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30473-7_19

    Chapter  Google Scholar 

  17. Escoffier, B., Gilbert, H., Pass-Lanneau, A.: Iterative delegations in liquid democracy with restricted preferences. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA, 7–12 February 2020, pp. 1926–1933 (2020)

    Google Scholar 

  18. Gölz, P., Kahng, A., Mackenzie, S., Procaccia, A.D.: The fluid mechanics of liquid democracy. In: Christodoulou, G., Harks, T. (eds.) WINE 2018. LNCS, vol. 11316, pp. 188–202. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-04612-5_13

    Chapter  Google Scholar 

  19. Grofman, B., Owen, G., Feld, S.L.: Thirteen theorems in search of the truth. Theory Decis. 15(3), 261–278 (1983)

    Article  MathSciNet  Google Scholar 

  20. Hagberg, A., Swart, P., S Chult, D.: Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab, US (2008)

    Google Scholar 

  21. Hainisch, R., Paulin, A.: Civicracy: establishing a competent and responsible council of representatives based on liquid democracy. In: Proceedings of the 2016 Conference for E-Democracy and Open Government, CeDEM 2016, Krems, Austria, 18–20 May, 2016, pp. 10–16 (2016)

    Google Scholar 

  22. Hardt, S., Lopes, L.C.: Google votes: a liquid democracy experiment on a corporate social network. Technical report (2015)

    Google Scholar 

  23. Hoeffding, W.: Probability inequalities for sums of bounded random variables. In: Fisher, N.I., Sen, P.K. (eds.) The Collected Works of Wassily Hoeffding. Springer Series in Statistics (Perspectives in Statistics), pp. 409–426. Springer, New York (1994). https://doi.org/10.1007/978-1-4612-0865-5_26

  24. Kahng, A., Mackenzie, S., Procaccia, A.D.: Liquid democracy: an algorithmic perspective. J. Artif. Intell. Res. 70, 1223–1252 (2021)

    Article  MathSciNet  Google Scholar 

  25. Kavitha, T., Király, T., Matuschke, J., Schlotter, I., Schmidt-Kraepelin, U.: Popular branchings and their dual certificates. In: Bienstock, D., Zambelli, G. (eds.) IPCO 2020. LNCS, vol. 12125, pp. 223–237. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45771-6_18

    Chapter  Google Scholar 

  26. Kling, C.C., Kunegis, J., Hartmann, H., Strohmaier, M., Staab, S.: Voting behaviour and power in online democracy: a study of liquidfeedback in germany’s pirate party. In: Proceedings of the 9th International Conference on Web and Social Media, ICWSM 2015, Oxford, UK, 26–29 May 2015, pp. 208–217 (2015)

    Google Scholar 

  27. Kotsialou, G., Riley, L.: Incentivising participation in liquid democracy with breadth-first delegation. In: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020, Auckland, New Zealand, 9–13 May, 2020, pp. 638–644 (2020)

    Google Scholar 

  28. Magdon-Ismail, M., Xia, L.: A mathematical model for optimal decisions in a representative democracy. In: Proceedings of the 32nd Annual Conference on Neural Information Processing Systems, NeurIPS 2018, Montréal, Canada, 3–8 December, 2018, pp. 4707–4716 (2018)

    Google Scholar 

  29. Meir, R., Amir, O., Cohensius, G., Ben-Porat, O., Xia, L.: Truth discovery via proxy voting. arXiv preprint arXiv:1905.00629 (2019)

  30. Nitzan, S., Paroush, J.: Optimal decision rules in uncertain dichotomous choice situations. Int. Econ. Rev., 289–297 (1982)

    Google Scholar 

  31. Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998)

    Google Scholar 

  32. Zhang, Y., Grossi, D.: Power in liquid democracy. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, 2–9 February 2021, pp. 5822–5830 (2021)

    Google Scholar 

  33. Zhang, Y., Grossi, D.: Tracking truth by weighting proxies in liquid democracy. arXiv preprint arXiv:2103.09081 (2021)

Download references

Acknowledgements

This work is partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Markets”.

Author information

Authors and Affiliations

  1. Gran Sasso Science Institute, L’Aquila, Italy

    Ruben Becker, Gianlorenzo D’Angelo & Esmaeil Delfaraz

  2. Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, 75016, Paris, France

    Hugo Gilbert

Authors
  1. Ruben Becker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gianlorenzo D’Angelo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Esmaeil Delfaraz
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hugo Gilbert
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Esmaeil Delfaraz .

Editor information

Editors and Affiliations

  1. National Technical University of Athens, Athens, Greece

    Dimitris Fotakis

  2. Consejo Superior de Investigaciones Cientificas, Madrid, Madrid, Spain

    David Ríos Insua

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Becker, R., D’Angelo, G., Delfaraz, E., Gilbert, H. (2021). Unveiling the Truth in Liquid Democracy with Misinformed Voters. In: Fotakis, D., Ríos Insua, D. (eds) Algorithmic Decision Theory. ADT 2021. Lecture Notes in Computer Science(), vol 13023. Springer, Cham. https://doi.org/10.1007/978-3-030-87756-9_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-87756-9_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-87755-2

  • Online ISBN: 978-3-030-87756-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation