Computation and Bribery of Voting Power in Delegative Simple Games
This work addresses theoretical challenges in liquid democracy for researchers in computational social choice, but it is incremental as it builds on prior studies.
The paper tackles the problem of computing voting power indices and manipulating them via bribery in delegative simple games, proposing a pseudo-polynomial algorithm for computation and showing computational hardness for bribery problems.
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.