2023/01/06 by Rachael Colley, Colley, Rachael, Théo Delemazure +3
Physics and Astronomy · Social Sciences · #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Electoral Systems and Political Participation #FOS: Computer and information sciences #Multiagent Systems (cs.MA) #Opinion Dynamics and Social Influence #Social Media and Politics
paper · pdf · doi:10.48550/arxiv.2301.02462
openalex publication_date 2023/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We introduce new power indices to measure the a priori voting power of voters in liquid democracy elections where an underlying network restricts delegations. We argue that our power indices are natural extensions of the standard Penrose-Banzhaf index in simple voting games. We show that computing the criticality of a voter is #P-hard even when voting weights are polynomially-bounded in the size of the instance. However, for specific settings, such as when the underlying network is a bipartite or complete graph, recursive formulas can compute these indices for weighted voting games in pseudo-polynomial time. We highlight their theoretical properties and provide numerical results to illustrate how restricting the possible delegations can alter voters' voting power.