TL;DR
This paper introduces "pairwise liquid democracy," a more flexible model where voters can delegate specific pairwise comparisons of alternatives, not just their entire vote. They explore the challenges of potential intransitive preferences arising from this flexibility and propose novel voting rules and consistency checks designed for this new paradigm.
What Problem Does This Paper Address?
Traditional liquid democracy allows voters to either vote directly or delegate their entire vote to another person. This paper tackles the limitations of this model by proposing a more granular approach: "pairwise liquid democracy." In this system, voters can specify their preferences for some pairs of alternatives while delegating the comparison of other pairs to different trusted individuals. This significantly increases flexibility, especially for voters who are not fully informed about all comparisons but have specific expertise or trust in others for certain aspects. However, this increased flexibility introduces a new challenge: the possibility of individual voters developing intransitive preferences (e.g., preferring A over B, B over C, and C over A), which violates a fundamental assumption in social choice theory. The paper aims to address how to detect and manage these intransitivities and develop appropriate voting mechanisms for this richer model.
Methods
The authors introduce a formal framework for "pairwise liquid democracy" using pairwise delegation graphs. They define concepts like "weak consistency" (no immediate preference cycles) and "consistency" (the possibility of extending the partial preferences to a complete and transitive order). They analyze the computational complexity of checking for consistency, proving it to be NP-complete. To handle potential intransitivities, they explore several strategies: restricting allowed delegations, modifying existing delegation graphs by removing arcs, and consolidating intransitive preferences into weak rankings. A key contribution is the development of "liquid voting rules" based on "distance rationalization." This framework generalizes standard voting rules by operating directly on delegation graphs and using a distance metric to find the "closest" graph that leads to a consensus profile. They specifically propose "LiquidKemeny" as an example, adapting Kemeny's rule to this new setting.
Datasets
Not discussed in the paper. The paper focuses on theoretical modeling and algorithmic analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Granular Delegation is Powerful but Risky: Allowing voters to delegate specific pairwise comparisons offers unprecedented flexibility but introduces the significant challenge of potential intransitive preferences.
- Consistency is Computationally Hard: Determining if a pairwise delegation graph can lead to a consistent set of preferences is an NP-complete problem, suggesting that practical systems might need to rely on approximations or heuristics.
- Liquid Voting Rules are a Natural Extension: The concept of "distance rationalization" provides a principled way to extend existing voting rules to the pairwise liquid democracy setting by considering the structure of delegation graphs.
- LiquidKemeny: A Practical Adaptation: The proposed LiquidKemeny rule offers a way to adapt a well-regarded voting rule (Kemeny's) to the new paradigm, focusing on the cost of changing internal pairwise preferences rather than the full preference profiles.
Key Results
- NP-Completeness of Consistency Checking: Deciding whether a given pairwise delegation graph is consistent is proven to be NP-complete.
- NP-Completeness of Consistency Modification: The problem of making a graph consistent by removing a limited number of delegation arcs is also NP-complete.
- Framework for Liquid Voting Rules: The paper establishes a general framework for creating "liquid voting rules" by generalizing distance rationalization to delegation graphs.
- LiquidKemeny Defined: A specific liquid voting rule, LiquidKemeny, is introduced, which adapts Kemeny's rule by measuring distance based on swaps of internal pairwise preferences.
Limitations and Future Work
The authors acknowledge that their proposed distance function for LiquidKemeny might not fully capture the intuition that preferences of voters with many delegations should be more influential. They suggest future work could involve developing more sophisticated cost functions for distance metrics that account for delegation path lengths or other structural properties of the graph. They also point to exploring other generalizations of liquid democracy, such as "statement voting," and "liquidizing" other classes of voting rules. The paper also notes that their approach might violate the "one man-one vote" principle, as the outcome can depend on the structure of the delegation graph itself.
Summary updated