Measuring a Priori Voting Power -- Taking Delegations Seriously

• URL: http://arxiv.org/abs/2301.02462v4
• Date: Mon, 15 May 2023 09:13:25 GMT
• Title: Measuring a Priori Voting Power -- Taking Delegations Seriously
• Authors: Rachael Colley, Th\'eo Delemazure, Hugo Gilbert
• Abstract summary: 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 show that computing the criticality of a voter is #P-hard even when voting weights are asly-bounded in the size of the instance. We highlight their theoretical properties and provide numerical results to illustrate how restricting the possible delegations can alter voters' voting power.
• Score: 8.12790806321461
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Elections in the Post-Quantum Era: Is the Complexity Shield Strong Enough? [0.0]
  We consider quantum computers to be a new threat to the complexity shield described above. We provide an overview of possible attacks on election, discuss the abilities of quantum computing, and chart possible directions for future research in this area.
  arXiv  Detail & Related papers  (2024-03-08T12:52:11Z)
• Learning to Manipulate under Limited Information [44.99833362998488]
  We trained over 70,000 neural networks of 26 sizes to manipulate against 8 different voting methods. We find that some voting methods, such as Borda, are highly manipulable by networks with limited information, while others, such as Instant Runoff, are not.
  arXiv  Detail & Related papers  (2024-01-29T18:49:50Z)
• As Time Goes By: Adding a Temporal Dimension Towards Resolving Delegations in Liquid Democracy [16.219158909792256]
  Our work takes a first step to integrate a time horizon into decision-making problems in Liquid Democracy systems. Our approach, via a computational complexity analysis, exploits concepts and tools from temporal graph theory.
  arXiv  Detail & Related papers  (2023-07-24T15:46:45Z)
• Private Multi-Winner Voting for Machine Learning [48.0093793427039]
  We propose three new DP multi-winner mechanisms: Binary, $tau$, and Powerset voting. Binary voting operates independently per label through composition. $tau$ voting bounds votes optimally in their $ell$ norm for tight data-independent guarantees. Powerset voting operates over the entire binary vector by viewing the possible outcomes as a power set.
  arXiv  Detail & Related papers  (2022-11-23T20:06:46Z)
• Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning [58.23459346724491]
  We use the "map of elections" approach of Szufa et al. (AAMAS 2020) to analyze several well-known vote distributions. We draw the "skeleton map" of distributions, evaluate its robustness, and analyze its properties.
  arXiv  Detail & Related papers  (2022-05-16T17:40:22Z)
• Obvious Manipulability of Voting Rules [105.35249497503527]
  The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability.
  arXiv  Detail & Related papers  (2021-11-03T02:41:48Z)
• Learning to Elect [7.893831644671976]
  Voting systems have a wide range of applications including recommender systems, web search, product design and elections. We show that set-input neural network architectures such as Set Transformers, fully-connected graph networks and DeepSets are both theoretically and empirically well-suited for learning voting rules.
  arXiv  Detail & Related papers  (2021-08-05T17:55:46Z)
• Mundus vult decipi, ergo decipiatur: Visual Communication of Uncertainty in Election Polls [56.8172499765118]
  We discuss potential sources of bias in nowcasting and forecasting. Concepts are presented to attenuate the issue of falsely perceived accuracy. One key idea is the use of Probabilities of Events instead of party shares.
  arXiv  Detail & Related papers  (2021-04-28T07:02:24Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)
• Computation and Bribery of Voting Power in Delegative Simple Games [12.259540948639327]
  We propose a pseudo-polynomial time algorithm to compute the delegative Banzhaf and Shapley-Shubik values in delegative simple games. We then investigate a bribery problem where the goal is to maximize/minimize the voting power/weight of a given voter in a delegation graph by changing at most a fixed number of delegations.
  arXiv  Detail & Related papers  (2021-04-08T11:28:50Z)
• On Parameterized Complexity of Liquid Democracy [5.897728689802829]
  In liquid democracy, each voter either votes herself or delegates her vote to some other voter. To decide the voters who eventually votes along with the subset of voters whose votes they give, we need to resolve the cycles in the delegation graph. Putting a cap on the number of voters whose votes a voter gives enable the system designer restrict the power of any individual voter.
  arXiv  Detail & Related papers  (2020-11-28T18:48:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.