Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Autonomous Agents and Multi-Agent Systems
Published in: Autonomous Agents and Multi-Agent Systems 1/2022

01-04-2022

Unravelling multi-agent ranked delegations

Authors: Rachael Colley, Umberto Grandi, Arianna Novaro

Published in: Autonomous Agents and Multi-Agent Systems | Issue 1/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We introduce a voting model with multi-agent ranked delegations. This model generalises liquid democracy in two aspects: first, an agent’s delegation can use the votes of multiple other agents to determine their own—for instance, an agent’s vote may correspond to the majority outcome of the votes of a trusted group of agents; second, agents can submit a ranking over multiple delegations, so that a backup delegation can be used when their preferred delegations are involved in cycles. The main focus of this paper is the study of unravelling procedures that transform the delegation ballots received from the agents into a profile of direct votes, from which a winning alternative can then be determined by using a standard voting rule. We propose and study six such unravelling procedures, two based on optimisation and four using a greedy approach. We study both algorithmic and axiomatic properties, as well as related computational complexity problems of our unravelling procedures for different restrictions on the types of ballots that the agents can submit.
previous article Fair allocation of conflicting items
next article An explainable assistant for multiuser privacy

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
Note that in order to use Boolean functions to express a delegation, the domain of the alternatives for the issue must be a Boolean algebra. We restrict this to a two-element Boolean algebra, namely \(\{0,1\}\).
 
2
This notion, when restricted to ballots with single-agent delegations, corresponds to the definition of confluent sequence rules by Brill et al. [12].
 
3
In the following, we will simply write Unravel(\(\#\)), for \(\# \in \{\mathbf{U}, \mathbf{DU}, \mathbf{RU}, \mathbf{DRU} \}\), to indicate the Unravel algorithm using Update procedure \(\#\).
 
4
Unless otherwise specified, in case the condition in an if statement fails, our programs will skip to the next step. Recall also that \(Y_{\restriction S}\) denotes the restriction of vector Y to the elements in set S.
 
5
Observe that a formula of propositional logic is a Boolean function.
 
6
Note that in previous work [19], the language \(\textsc {Bool}\) was initially defined simply as the language of contingent propositional formulas in DNF, for which however the necessary winners cannot be computed in polynomial time. We are grateful to an anonymous reviewer for pointing this out.
 
7
We previously showed [19] that checking if a ballot of contingent DNF formulas is valid is an NP-complete problem. Restricting formulas to contingent complete DNFs makes this problem tractable.
 
8
The formulation by Karp [35] is on directed graphs G which allow for reflexive edges. However, our sub-problem is also NP-complete, since a reduction can be given where the constructed graph \(G'\) adds a dummy node \(a'\) for each node a that had a reflexive edge in G, as well as the edges \((a,a')\) and \((a',a)\).
 
9
Also independently suggested by Chu [16] and Bock [7].
 
10
For undirected graphs, the corresponding problem is that of finding a minimum spanning tree.
 
11
Recall that since both \(\mathcal {D}\) and the possible sets of delegates are finite, and since all functions given in an agent’s valid ballot must differ, the possible number of functions must also be finite.
 
12
Note that Definition 10 slightly differs from the one given in previous work [19], and thus Theorem 5 does not hold for \(\mathbf {RU}\) or \(\mathbf {DRU}\): a counterexample can be constructed exploiting the fact that an agent may prefer the outcome of one random iteration of the procedure to another.
 
Literature
1.
Abramowitz, B., & Mattei, N. (2019).Flexible Representative Democracy: An Introduction with Binary Issues. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI).
2.
Alger, D. (2006). Voting by proxy. In Public Choice 126.1-2, pp. 1–26.
3.
Behrens, J., & Swierczek, B. (2015) Preferential Delegation and the Problem of Negative Voting Weight. In The Liquid Democracy Journal 3.
4.
Behrens, J. et al. (2014). Principles of Liquid Feedback. Interacktive Demokratie.
5.
Bloembergen, D., Grossi, D., & Lackner, M. (2019). On Rational Delegations in Liquid Democracy. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI).
6.
Blum, C., & Zuber, C. I. (2016). Liquid democracy: Potentials, problems, and perspectives. Journal of Political Philosophy, 24(2), 162–182.CrossRef
7.
Bock, F.C. (1971). An algorithm to construct a minimum directed spanning tree in a directed network. In Developments in operations research, pp. 29–44.
8.
Boldi, P., et al. (2011). Viscous democracy for social networks. Communications of the ACM, 54(6), 129–137.CrossRef
9.
Bredereck, R., & Elkind, E. (2017). Manipulating Opinion Diffusion in Social Networks. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI).
10.
Brill, M. (2018).Interactive democracy. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS).
11.
Brill, M., & Talmon, N. (2018). Pairwise Liquid Democracy. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI).
12.
13.
Brill, M. et al. (2016). Pairwise Diffusion of Preference Rankings in Social Networks. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI).
14.
Caragiannis, I., & Micha, E. (2019).A contribution to the critique of liquid democracy. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI).
15.
Christoff, Z., & Grossi, D. (2017). Binary Voting with Delegable Proxy: An Analysis of Liquid Democracy. In Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK).
16.
Chu, Y.-J. (1965). On the shortest arborescence of a directed graph. Scientia Sinica, 14, 1396–1400.MathSciNetMATH
17.
Cohensius, G., & Meir, R. (2017). Proxy Voting for Revealing Ground Truth. In Proceedings of the 4th Workshop on Exploring Beyond the Worst Case in Computational Social Choice (EXPLORE).
18.
Cohensius, G., et al. (2017) Proxy Voting for Better Outcomes. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS).
19.
Colley, R., Grandi, U., & Novaro, A. (2020). Smart Voting. In Proceeding of the the 29th International Joint Conference on Artificial Intelligence (IJCAI).
20.
Cormen, T. H., et al. (2009). Introduction to algorithms. Cambridge: MIT Press.MATH
21.
Crama, Y., & Hammer, P. L. (2011). Boolean functions: Theory, algorithms, and applications. Cambridge: Cambridge University Press.CrossRef
22.
23.
Dhillon, A., et al. (2019) Introduction to Voting and the Blockchain: some open questions for economists. Tech. rep. Competitive Advantage in the Global Economy (CAGE).
24.
Dodgson, C. L. (1884). The Principles of Parliamentary Representation. High Wycombe: Harrison and Sons.
25.
Edmonds, J. (1967). Optimum branchings. Journal of Research of the National Bureau of Standards B, 71(4), 233–240.MathSciNetCrossRef
26.
Escoffier, B., Gilbert, H., & Pass-Lanneau, A. (2020). Iterative delegations in liquid democracy with restricted preferences. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI).
27.
Escoffier, B., Gilbert, H., & Pass-Lanneau, A. (2019). The Convergence of Iterative Delegations in Liquid Democracy in a Social Network. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT).
28.
Ford, B.A. (2002). Delegative democracy. Tech. rep.
29.
Gölz, P., et al. (2018). The fluid mechanics of liquid democracy. In International Conference on Web and Internet Economics (ICWIE).
30.
Grandi, U. (2017). Social choice and social networks. In Trends in Computational Social Choice, pp. 169–184.
31.
Granovetter, M. (1978). Threshold models of collective behavior. American Journal of Sociology, 83(6), 1420–1443.CrossRef
32.
Green-Armytage, J. (2015). Direct voting and proxy voting. Constitutional Political Economy, 26(2), 190–220.CrossRef
33.
Hardt, S., & Lopes, L.C.R. (2015). Google Votes: A Liquid Democracy Experiment on a Corporate Social Network. Tech. rep. Technical Disclosure Commons, Google.
34.
Kahng, A., Mackenzie, S., & Procaccia, A.D. (2018). Liquid democracy: An algorithmic perspective. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI).
35.
Karp, R.M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations. Springer, pp. 85–103.
36.
Kling, C., et al. (2015). Voting behaviour and power in online democracy: A study of LiquidFeedback in Germany’s Pirate Party. In Proceedings of the International AAAI Conference on Web and Social Media.
37.
Konczak, K., & Lang, J. (2005). Voting procedures with incomplete preferences. In Proceedings of the IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling (MPREF).
38.
Kotsialou, G., & Riley, L. (2020). Incentivising Participation in Liquid Democracy with Breadth-First Delegation. In Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
39.
Kozen, D. C. (2012). The design and analysis of algorithms. Berlin: Springer.
40.
41.
Litvinenko, A. (2012). Social media and perspectives of liquid democracy on the example of political communication of Pirate Party in Germany. In Proceedings of the 12th European Conference on e-Government in Barcelona.
42.
Mancini, P. (2015). Why it is time to redesign our political system. In European View 14.1, pp. 69–75.
43.
44.
Miller, J.C. (1969). A program for direct and proxy voting in the legislative process. In Public choice 7. , pp. 107–113.
45.
Moulin, H. (1988). Axioms of Cooperative Decision Making. Cambridge: Cambridge University Press.CrossRef
46.
Mueller, D.C., Tollison, R.D., & Willett, T.D. (1972). Representative democracy via random selection. In Public Choice 12.1, pp. 57–68.
47.
Shapiro, E. (2018). Point: foundations of e-democracy. Communications of the ACM, 61(8), 31–34.CrossRef
48.
Swierczek, B. (2014). Five years of Liquid Democracy in Germany. The Liquid Democracy Journal, 1(1), 8–19.
49.
50.
Tullock, G. (1967). Toward a mathematics of politics. Ann Arbor: University of Michigan Press.
51.
Zhang, B., & Zhou, H.-S. (2019). Statement voting. In International Conference on Financial Cryptography and Data Security.
52.
Zhang, Y., & Grossi, D. (2021). Power in Liquid Democracy. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI).
Metadata
Title
Unravelling multi-agent ranked delegations
Authors
Rachael Colley
Umberto Grandi
Arianna Novaro
Publication date
01-04-2022
Publisher
Springer US
Published in
Autonomous Agents and Multi-Agent Systems / Issue 1/2022
Print ISSN: 1387-2532
Electronic ISSN: 1573-7454
DOI
https://doi.org/10.1007/s10458-021-09538-2

Other articles of this Issue 1/2022

Autonomous Agents and Multi-Agent Systems 1/2022 Go to the issue

OriginalPaper

Formal verification of group and propagated trust in multi-agent systems

OriginalPaper

Exploiting environmental signals to enable policy correlation in large-scale decentralized systems

OriginalPaper

Candidate selections with proportional fairness constraints

OriginalPaper

Fair allocation of indivisible goods and chores

OriginalPaper

Online revenue maximization for server pricing

OriginalPaper

Input addition and deletion in reinforcement: towards protean learning

Premium Partner

    Image Credits