An approval-based model for single-step liquid democracy. (English) Zbl 1492.91263
Caragiannis, Ioannis (ed.) et al., Algorithmic game theory. 14th international symposium, SAGT 2021, Aarhus, Denmark, September 21–24, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12885, 360-375 (2021).
Summary: 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.
For the entire collection see [Zbl 1487.91002].
For the entire collection see [Zbl 1487.91002].
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.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 2, 308-340 (1991) · Zbl 0734.68073 · doi:10.1016/0196-6774(91)90006-K |
| [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., 25, 6, 1305-1317 (1996) · Zbl 0864.68074 · doi:10.1137/S0097539793251219 |
| [7] | Boldi, P.; Bonchi, F.; Castillo, C.; Vigna, S., Viscous democracy for social networks, Commun. ACM, 54, 6, 129-137 (2011) · doi:10.1145/1953122.1953154 |
| [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) · Zbl 1484.91159 |
| [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) · Zbl 0722.03008 |
| [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) · Zbl 1431.91138 |
| [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) · Zbl 1202.68278 |
| [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) · Zbl 1443.91127 |
| [16] | Green-Armytage, J., Direct voting and proxy voting, Const. Polit. Econ., 26, 2, 190-220 (2015) · doi:10.1007/s10602-014-9176-9 |
| [17] | Grohe, M., Logic, graphs, and algorithms, Log. Automata, 2, 357-422 (2008) · Zbl 1244.03053 |
| [18] | Kahng, A.; Mackenzie, S.; Procaccia, A., Liquid democracy: an algorithmic perspective, J. Artif. Intell. Res., 70, 1223-1252 (2021) · Zbl 1520.91144 · doi:10.1613/jair.1.12261 |
| [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) · Zbl 1489.90156 |
| [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) · Zbl 1427.68125 |
| [21] | Kreutzer, S.; Grohe, M.; Niedermeier, R., Algorithmic meta-theorems, Parameterized and Exact Computation, 10-12 (2008), Heidelberg: Springer, Heidelberg · Zbl 1142.68458 · doi:10.1007/978-3-540-79723-4_3 |
| [22] | Masařík, T.; Toufar, T., Parameterized complexity of fair deletion problems, Discret. Appl. Math., 278, 51-61 (2020) · Zbl 1437.05227 · doi:10.1016/j.dam.2019.06.001 |
| [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, 25, 2, 237-254 (1997) · Zbl 0887.68040 · doi:10.1006/jagm.1997.0887 |
| [26] | Szeider, S., Monadic second order logic on graphs with local cardinality constraints, ACM Trans. Comput. Log., 12, 2, 1-21 (2011) · Zbl 1351.68121 · doi:10.1145/1877714.1877718 |
| [27] | Zhang, Y., Grossi, D.: Tracking truth by weighting proxies in liquid democracy. arXiv preprint arXiv:2103.09081 (2021) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
