On Parameterized Complexity of Liquid Democracy

• URL: http://arxiv.org/abs/2011.14192v1
• Date: Sat, 28 Nov 2020 18:48:22 GMT
• Title: On Parameterized Complexity of Liquid Democracy
• Authors: Palash Dey, Arnab Maiti and Amatya Sharma
• Abstract summary: 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.
• Score: 5.897728689802829
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In liquid democracy, each voter either votes herself or delegates her vote to some other voter. This gives rise to what is called a delegation graph. 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. This gives rise to the Resolve Delegation problem where we need to find an acyclic sub-graph of the delegation graph such that the number of voters whose votes they give is bounded above by some integer {\lambda}. Putting a cap on the number of voters whose votes a voter gives enable the system designer restrict the power of any individual voter. The Resolve Delegation problem is already known to be NP-hard. In this paper we study the parameterized complexity of this problem. We show that Resolve Delegation is para-NP-hard with respect to parameters {\lambda}, number of sink nodes and the maximum degree of the delegation graph. We also show that Resolve Delegation is W[1]-hard even with respect to the treewidth of the delegation graph. We complement our negative results by exhibiting FPT algorithms with respect to some other parameters. We finally show that a related problem, which we call Resolve Fractional Delegation, is polynomial time solvable.

Related papers

• Determining Winners in Elections with Absent Votes [26.675597212113658]
  We study the determining winner with the absent votes problem when the votes are top-truncated. We show that the WAV problem is NP-complete for the single transferable vote. We propose a special case of positional scoring rule such that the problem can be computed in time.
  arXiv  Detail & Related papers  (2023-10-11T02:52:16Z)
• 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)
• Predicting the Silent Majority on Graphs: Knowledge Transferable Graph Neural Network [45.790140824712616]
  Graphs consisting of vocal nodes ("the vocal minority") and silent nodes ("the silent majority"), namely VS-Graph, are ubiquitous in the real world. We propose Knowledge Transferable Graph Neural Network (KT-GNN), which models distribution shifts during message passing and representation learning.
  arXiv  Detail & Related papers  (2023-02-02T04:46:21Z)
• Accelerating Voting by Quantum Computation [35.03314687289671]
  We propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. Our algorithm outputs the correct winner with high probability in $Thetaleft(fracntextMOVright)$ time.
  arXiv  Detail & Related papers  (2023-01-08T07:29:38Z)
• Measuring a Priori Voting Power -- Taking Delegations Seriously [8.12790806321461]
  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.
  arXiv  Detail & Related papers  (2023-01-06T11:16:57Z)
• 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)
• 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)
• Graph-Based Tri-Attention Network for Answer Ranking in CQA [56.42018099917321]
  We propose a novel graph-based tri-attention network, namely GTAN, to generate answer ranking scores. Experiments on three real-world CQA datasets demonstrate GTAN significantly outperforms state-of-the-art answer ranking methods.
  arXiv  Detail & Related papers  (2021-03-05T10:40:38Z)
• Topology-Aware Graph Pooling Networks [51.9008939769679]
  Pooling operations are effective on computer vision and natural language processing tasks. One challenge of performing pooling operations on graph data is the lack of locality that is not well-defined on graphs. We propose the topology-aware pooling (TAP) layer that explicitly considers graph topology.
  arXiv  Detail & Related papers  (2020-10-19T20:14:30Z)
• Representative Graph Neural Network [113.67254049938629]
  We present a Representative Graph layer to dynamically sample a few representative features. Instead of propagating the messages from all positions, our RepGraph layer computes the response of one node merely with a few representative nodes.
  arXiv  Detail & Related papers  (2020-08-12T09:46:52Z)

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.