Article

An Approval-Based Model for Single-Step Liquid Democracy

Authors:

Evangelos Markakis,

Georgios PapasotiropoulosAuthors Info & Claims

Algorithmic Game Theory: 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21–24, 2021, Proceedings

Pages 360 - 375

https://doi.org/10.1007/978-3-030-85947-3_24

Published: 21 September 2021 Publication History

Abstract

We study a Liquid Democracy framework where voters can express preferences in an approval form, regarding being represented by a subset of voters, casting a ballot themselves, or abstaining from the election. We examine, from a computational perspective, the problems of minimizing (resp. maximizing) the number of dissatisfied (resp. satisfied) voters. We first show that these problems are intractable even when each voter approves only a small subset of other voters. On the positive side, we establish constant factor approximation algorithms for that case, and exact algorithms under bounded treewidth of a convenient graph-theoretic representation, even when certain secondary objectives are also present. The results related to the treewidth are based on the powerful methodology of expressing graph properties via Monadic Second Order logic. We believe that this approach can turn out to be fruitful for other graph related questions that appear in Computational Social Choice.

References

[1]

Abramowitz, B., Mattei, N.: Flexible representative democracy: an introduction with binary issues. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, (IJCAI-19), pp. 3–10 (2019)

[2]

Anshelevich, E., Fitzsimmons, Z., Vaish, R., Xia, L.: Representative proxy voting. arXiv preprint arXiv:2012.06747 (2020)

[3]

Arnborg S, Lagergren J, and Seese D Easy problems for tree-decomposable graphs J. Algorithms 1991 12 2 308-340

[4]

Bloembergen, D., Grossi, D., Lackner, M.: On rational delegations in liquid democracy. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, (AAAI-19), pp. 1796–1803 (2019)

[5]

Blum, C., Zuber, C.I.: Liquid democracy: potentials, problems, and perspectives. J. Polit. Philos. 24(2), 162–182 (2016)

[6]

Bodlaender HL A linear-time algorithm for finding tree-decompositions of small treewidth SIAM J. Comput. 1996 25 6 1305-1317

[7]

Boldi P, Bonchi F, Castillo C, and Vigna S Viscous democracy for social networks Commun. ACM 2011 54 6 129-137

[8]

Caragiannis, I., Micha, E.: A contribution to the critique of liquid democracy. In: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, (IJCAI-19), pp. 116–122 (2019)

[9]

Christoff, Z., Grossi, D.: Binary voting with delegable proxy: an analysis of liquid democracy. In: Proceedings of the Sixteenth Conference on Theoretical Aspects of Rationality and Knowledge, (TARK-17), pp. 134–150 (2017)

[10]

Colley, R., Grandi, U., Novaro, A.: Smart voting. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, (IJCAI-20), pp. 1734–1740 (2021)

[11]

Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)

[12]

Escoffier, B., Gilbert, H., Pass-Lanneau, A.: The convergence of iterative delegations in liquid democracy in a social network. In: Proceedings of the Twelfth International Symposium on Algorithmic Game Theory, (SAGT-19), pp. 284–297 (2019)

[13]

Escoffier, B., Gilbert, H., Pass-Lanneau, A.: Iterative delegations in liquid democracy with restricted preferences. In: Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, (AAAI-20), pp. 1926–1933 (2020)

[14]

Golovach, P.A., Villanger, Y.: Parameterized complexity for domination problems on degenerate graphs. In: Proceedings of the Thirty-Fourth International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 195–205 (2008)

[15]

Gölz, P., Kahng, A., Mackenzie, S., Procaccia, A.D.: The fluid mechanics of liquid democracy. In: Proceedings of the Fourteenth International Conference on Web and Internet Economics, (WINE-18), pp. 188–202 (2018)

[16]

Green-Armytage J Direct voting and proxy voting Const. Polit. Econ. 2015 26 2 190-220

[17]

Grohe M Logic, graphs, and algorithms Log. Automata 2008 2 357-422

[18]

Kahng A, Mackenzie S, and Procaccia A Liquid democracy: an algorithmic perspective J. Artif. Intell. Res. 2021 70 1223-1252

[19]

Kavitha, T., Király, T., Matuschke, J., Schlotter, I., Schmidt-Kraepelin, U.: Popular branchings and their dual certificates. In: Proceedings of the Twenty-First International Conference on Integer Programming and Combinatorial Optimization, pp. 223–237 (2020)

[20]

Knop, D., Koutecký, M., Masarík, T., Toufar, T.: Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. Log. Methods Comput. Sci. 15(4), 1–32 (2019)

[21]

Kreutzer S Grohe M and Niedermeier R Algorithmic meta-theorems Parameterized and Exact Computation 2008 Heidelberg Springer 10-12

[22]

Masařík T and Toufar T Parameterized complexity of fair deletion problems Discret. Appl. Math. 2020 278 51-61

[23]

Paulin, A.: An overview of ten years of liquid democracy research. In: The Proceedings of the Twenty-First Annual International Conference on Digital Government Research, pp. 116–121 (2020)

[24]

Seymour, P.: The origin of the notion of treewidth. Theoretical Computer Science Stack Exchange (2014). https://cstheory.stackexchange.com/q/27317. Accessed 16 May 2021

[25]

Slavık P A tight analysis of the greedy algorithm for set cover J. Algorithms 1997 25 2 237-254

[26]

Szeider S Monadic second order logic on graphs with local cardinality constraints ACM Trans. Comput. Log. 2011 12 2 1-21

[27]

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

Cited By

Markakis EPapasotiropoulos G(2024)As Time Goes By: Adding a Temporal Dimension to Resolve Delegations in Liquid DemocracyAlgorithmic Decision Theory10.1007/978-3-031-73903-3_4(48-63)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-73903-3_4
Colley RDelemazure TGilbert HElkind E(2023)Measuring a priori voting power in liquid democracyProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/290(2607-2615)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/290

Index Terms

An Approval-Based Model for Single-Step Liquid Democracy

Index terms have been assigned to the content through auto-classification.

Recommendations

In Defense of Liquid Democracy
EC '23: Proceedings of the 24th ACM Conference on Economics and Computation

Liquid democracy is a voting paradigm that is conceptually situated between direct democracy, in which voters have direct influence over decisions, and representative democracy, where voters choose delegates who represent them for a period of time. ...
An Experiment in Approval Voting

The first major experimental comparison of approval voting with regular plurality voting occurred in the 1985 annual election of The Institute of Management Sciences TIMS. In approval voting a person votes for approves of as many candidates as desired, ...
On Parameterized Complexity of Liquid Democracy
Algorithms and Discrete Applied Mathematics
Abstract
In liquid democracy, each voter either votes herself or delegates her vote to some other voter. This gives rise to what is called a delegation graph. To decide the voters who eventually votes along with the subset of voters whose votes they give, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Algorithmic Game Theory: 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21–24, 2021, Proceedings

Sep 2021

423 pages

ISBN:978-3-030-85946-6

DOI:10.1007/978-3-030-85947-3

Editors:
Ioannis Caragiannis
Aarhus University, Aarhus, Denmark
,
Kristoffer Arnsfelt Hansen
Aarhus University, Aarhus, Denmark

© Springer Nature Switzerland AG 2021.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 September 2021

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Markakis EPapasotiropoulos G(2024)As Time Goes By: Adding a Temporal Dimension to Resolve Delegations in Liquid DemocracyAlgorithmic Decision Theory10.1007/978-3-031-73903-3_4(48-63)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-73903-3_4
Colley RDelemazure TGilbert HElkind E(2023)Measuring a priori voting power in liquid democracyProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/290(2607-2615)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/290

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents