Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Autonomous Agents and Multi-Agent Systems
Erschienen in: Autonomous Agents and Multi-Agent Systems 1/2022

01.04.2022

Unravelling multi-agent ranked delegations

verfasst von: Rachael Colley, Umberto Grandi, Arianna Novaro

Erschienen in: Autonomous Agents and Multi-Agent Systems | Ausgabe 1/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel Fair allocation of conflicting items
Nächster Artikel An explainable assistant for multiuser privacy

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
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.
 
Literatur
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).
Metadaten
Titel
Unravelling multi-agent ranked delegations
verfasst von
Rachael Colley
Umberto Grandi
Arianna Novaro
Publikationsdatum
01.04.2022
Verlag
Springer US
Erschienen in
Autonomous Agents and Multi-Agent Systems / Ausgabe 1/2022
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
DOI
https://doi.org/10.1007/s10458-021-09538-2

Weitere Artikel der Ausgabe 1/2022

Autonomous Agents and Multi-Agent Systems 1/2022 Zur Ausgabe

OriginalPaper

Combining quantitative and qualitative reasoning in concurrent multi-player games

OriginalPaper

Exploring the influence of a user-specific explainable virtual advisor on health behaviour change intentions

OriginalPaper

Input addition and deletion in reinforcement: towards protean learning

OriginalPaper

Representing and reasoning about auctions

OriginalPaper

Verification of multi-layered assignment problems

OriginalPaper

Designing empathic virtual agents: manipulating animation, voice, rendering, and empathy to create persuasive agents

Premium Partner

    Bildnachweise