Preserving Consistency in Multi-Issue Liquid Democracy

Rachael Colley, Umberto GrandiIJCAI 2022 · DOI

TL;DR

This paper tackles the challenge of maintaining consistent voting outcomes in multi-issue liquid democracy systems, where voters can delegate their votes. The authors propose novel algorithms that leverage voter priorities to achieve consistency efficiently, outperforming existing methods in certain scenarios.

What Problem Does This Paper Address?

Liquid democracy, a voting system where individuals can either vote directly or delegate their vote to a trusted individual, offers a flexible approach to collective decision-making. However, when applied to multiple interconnected issues (e.g., approving projects within a budget, or ensuring transitive preferences), this delegation can lead to inconsistent outcomes. For instance, a voter might delegate their vote on several issues, and the aggregated outcome might violate a predefined constraint (like a budget limit) or lead to logically contradictory preferences. Existing approaches to resolve these inconsistencies often involve computationally expensive optimization methods or make arbitrary changes to ballots. This paper aims to bridge this gap by proposing efficient algorithms that preserve consistency while respecting voter preferences and delegations.

Methods

The paper introduces two main algorithmic approaches:

  • Priority Delegation Changing (PDC): This algorithm iteratively modifies delegations into direct votes if they lead to inconsistencies. It prioritizes changes based on the voter's stated preferences over issues. If adding a delegate's vote is inconsistent, it either reverts to the opposite vote or, if the voter has no direct vote, it assigns the opposite of the delegate's vote.
  • Priority Vote Changing (PVC): This approach first determines the "canonical profile" of votes by resolving all delegations. Then, it iteratively adjusts these votes based on voter priorities. If adding a vote from the canonical profile is consistent, it's adopted; otherwise, the opposite vote is chosen.

Both algorithms are designed to run in polynomial time and guarantee consistent outcomes. The authors also analyze the complexity of two "minimization" rules (MDC and MVC) from prior work, showing they are NP-complete, which motivates the development of their priority-based, tractable algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic design, using illustrative examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Priorities are Key: The core insight is that voter priorities over issues can be effectively used to resolve inconsistencies in liquid democracy, offering a more principled approach than simply minimizing changes.
  • Tractability vs. Minimization: While minimizing the number of changes to ballots or votes is a natural goal, the paper demonstrates that these minimization rules are computationally intractable (NP-complete). This highlights the practical advantage of priority-based algorithms, which are polynomial-time solvable.
  • PDC vs. PVC Trade-offs: The paper shows that while both PDC and PVC are efficient and produce consistent results, they have different strengths. PVC, in particular, is shown to respect voter priorities more effectively than its minimization counterpart (MVC).
  • Budget Constraints Matter: The paper specifically examines knapsack constraints (budget limits) and finds that the MVC rule (minimal vote changes) can outperform other rules in terms of maximizing accepted projects, suggesting that the "best" rule might depend on the specific constraint type.

Key Results

  • The decision problems associated with minimizing delegation changes (MDC) and vote changes (MVC) are proven to be NP-complete.
  • The proposed algorithms, PDC and PVC, are shown to terminate and always output a consistent profile of votes in polynomial time.
  • PDC and PVC run in O(nm(n + l)) time, where n is the number of voters, m is the number of issues, and l is the time to check for Γ-consistent completion.
  • The paper demonstrates that PDC and PVC are not necessarily good polynomial approximations of MDC and MVC, as they prioritize respecting priorities over minimizing changes.
  • For knapsack constraints, MVC is shown to accept at least as many projects as MDC, PVC, and PDC.

Limitations and Future Work

  • Approximation Bounds: The paper shows that PDC and PVC do not offer good approximation bounds for MDC and MVC, indicating that their focus on priorities leads to different outcomes than pure minimization.
  • PDC's Priority Usage: Proposition 9 suggests that PDC might not be using voter priorities in the most optimal way, leaving room for improvement. The authors conjecture that a better PDC might not be achievable in polynomial time, but this remains an open question.
  • Constraint Specificity: The paper highlights that the choice of a consistent delegation rule can be constraint-dependent, suggesting that future work should focus on specifying general settings for specific classes of constraints.
  • Empirical Evaluation: While the paper provides theoretical guarantees, an empirical evaluation of the proposed algorithms on real-world or simulated data would be valuable to further validate their performance and compare them against existing methods in practice.

Summary updated

BibTeX
@inproceedings{colley2022preserving,
  author = {Rachael Colley and Umberto Grandi},
  title = {{Preserving Consistency in Multi-Issue Liquid Democracy}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/29},
}
Figure