Following Zhang and Grossi (AAAI 2021), we study in more depth a variant of weighted voting games in which agents' weights are induced by a transitive support structure. This class of simple games is notably well suited to study the relative importance of agents in the liquid democracy framework. We first propose a pseudo-polynomial time algorithm to compute the Banzhaf and Shapley-Shubik indices for this class of game. Then, we study a bribery problem, in which one tries to maximize/minimize the voting power/weight of a given agent by changing the support structure under a budget constraint. We show that these problems are computationally hard and provide several parameterized complexity results. © 2022 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved
Computation and Bribery of Voting Power in Delegative Simple Games
D'Angelo, G.;DELFARAZPAHLEVANLOO, E.;Gilbert, H.
2022-01-01
Abstract
Following Zhang and Grossi (AAAI 2021), we study in more depth a variant of weighted voting games in which agents' weights are induced by a transitive support structure. This class of simple games is notably well suited to study the relative importance of agents in the liquid democracy framework. We first propose a pseudo-polynomial time algorithm to compute the Banzhaf and Shapley-Shubik indices for this class of game. Then, we study a bribery problem, in which one tries to maximize/minimize the voting power/weight of a given agent by changing the support structure under a budget constraint. We show that these problems are computationally hard and provide several parameterized complexity results. © 2022 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reservedFile | Dimensione | Formato | |
---|---|---|---|
2022_AAMAS22_336_DAngelo.pdf
accesso aperto
Tipologia:
Versione Editoriale (PDF)
Licenza:
Creative commons
Dimensione
1.09 MB
Formato
Adobe PDF
|
1.09 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.