Measuring a Priori Voting Power in Liquid Democracy

Rachael Colley, Théo Delemazure, Hugo GilbertIJCAI 2023 · DOI

TL;DR

This paper introduces new "I-voting power" indices to measure a voter's influence in liquid democracy (LD) systems, where voters can delegate their votes. They show that computing this power is generally #P-hard but can be done efficiently in pseudo-polynomial time for specific network structures like bipartite or complete graphs, offering a way to understand how delegation impacts voter influence.

What Problem Does This Paper Address?

Traditional voting power measures, like the Penrose-Banzhaf index, focus on simple voting games where voters directly decide on a proposal. However, modern democratic systems increasingly incorporate delegation, where voters can entrust their vote to others. Liquid Democracy (LD) and Proxy Voting (PV) are prominent examples of such systems, allowing for flexible and transitive delegation. The challenge is that existing voting power measures don't adequately capture the nuances of these delegation structures. This paper aims to fill this gap by developing and analyzing voting power measures that account for the underlying social network that governs delegation possibilities in LD and PV settings.

Methods

The core contribution is the introduction of the "LD Penrose-Banzhaf measure," an extension of the standard Penrose-Banzhaf index to account for delegation. This measure quantifies a voter's probability of influencing an election outcome, considering that voters can either vote directly or delegate their vote along a social network represented by a directed graph (digraph).

Key methodological aspects include:

  • Modeling Delegation: The paper models the social network as a digraph $G=(V, E)$, where an edge $(i, j)$ signifies that voter $i$ can delegate to voter $j$.
  • G-Delegation Partitions: A G-delegation partition defines how each voter chooses to vote or delegate, constrained by the network.
  • Induced Direct-Vote Partitions: These partitions are derived from G-delegation partitions by resolving delegations, potentially leading to abstentions if cycles occur.
  • I-Voting Power: The measure focuses on "influence" (I-power) rather than "pay-off" (P-power), meaning it's concerned with a voter's ability to change the outcome based on their stance, not just their presence in a winning coalition.
  • Individual Uniformity Assumption: This assumption posits that voters choose their delegation or voting options uniformly at random, reflecting a lack of prior information about voter preferences or the proposal.
  • Hardness and Tractability: The paper proves that computing the LD Penrose-Banzhaf measure is generally #P-hard for arbitrary graphs. However, they derive pseudo-polynomial time algorithms for two important special cases:
  • Proxy Voting (PV): When the graph is bipartite, with delegations flowing from one set of voters to another (e.g., citizens to elected representatives).
  • Liquid Democracy (LD) with Complete Digraph: When any voter can delegate to any other voter.
  • Recursive Formulas: For the complete digraph case, they develop recursive formulas to efficiently compute probabilities related to delegation structures.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and computational aspects, using synthetic examples for illustration rather than real-world datasets.

Key Insights and Ideas

  • Delegation Fundamentally Alters Voting Power: The most significant insight is that the ability to delegate, even with simple network structures, can drastically change a voter's influence compared to a direct voting scenario.
  • In-Degree Matters: In delegation networks, a voter's in-degree (the number of voters who can delegate to them) is a strong predictor of their voting power. More potential delegates mean more potential influence.
  • Network Structure is Crucial: The paper highlights that the specific structure of the delegation network (e.g., bipartite vs. complete) significantly impacts the tractability of computing voting power and the distribution of power among voters.
  • #P-Hardness is the Norm, Tractability is the Exception: While computing voting power in LD is generally computationally hard, specific, structured scenarios (like PV and complete graphs) allow for efficient (pseudo-polynomial) computation. This suggests that practical applications might rely on these specific structures or approximation methods.
  • Flattening Effect of Delegation: In some scenarios, as delegation becomes more prevalent (higher $p_d$), the differences in voting power between voters with different weights tend to decrease, leading to a more egalitarian distribution of influence.

Key Results

  • #P-Hardness Result: Computing the LD Penrose-Banzhaf measure is #P-hard even for weighted voting games with linearly bounded weights, under Turing reductions.
  • Pseudo-Polynomial Algorithms:
    • For Proxy Voting (bipartite graphs), the measure can be computed in pseudo-polynomial time.
  • For Liquid Democracy with a complete graph, the measure can also be computed in pseudo-polynomial time.
  • Experimental Observations:
    • In PV, increasing the probability of delegation ($p_d$) increases the criticality of delegatees while decreasing that of delegators, showing a transfer of power.
  • In LD with complete graphs, voters with higher weights generally have more power, but this difference is flattened as $p_d$ increases. Voters with smaller weights tend to see their criticality increase with $p_d$.

Limitations and Future Work

  • Limitations:
    • The current model primarily considers binary voting outcomes (for/against) and does not explicitly handle abstention in the core LD measure, though it's mentioned as a possibility in delegation cycles.
  • The analysis relies on the "individual uniformity assumption," which might not always reflect real-world voter behavior or strategic delegation.
  • The #P-hardness for general graphs implies that exact computation for arbitrary social networks is infeasible, necessitating approximation techniques.
  • Future Work:
    • Extend the model to incorporate more voting options, such as abstention, more explicitly.
  • Investigate how specific network properties (e.g., adding/removing neighbors) affect voting power.
  • Explore extensions of Coleman indices to differentiate between supporting and vetoing power in delegation settings.
  • Apply the developed models and measures to analyze real-world election data to validate findings and gain practical insights.

Summary updated

BibTeX
@inproceedings{colley2023measuring,
  author = {Rachael Colley and Théo Delemazure and Hugo Gilbert},
  title = {{Measuring a Priori Voting Power in Liquid Democracy}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/290},
}
Figure