Introduction
Liquid Democracy (LD) offers a flexible middle ground between direct and representative democracy by allowing voters to delegate their voting power transitively. In this system, if voter A delegates to B, and B delegates to C, then C acts as the "guru" for both A and B. However, the stability of such systems is a significant concern: if voters have conflicting preferences over who should represent them, the delegation process may fail to reach a stable equilibrium or may cycle indefinitely.
Previous research has demonstrated that in general settings, a stable state—a Nash equilibrium where no voter wishes to change their proxy—might not exist. Furthermore, determining the existence of such a state is often NP-hard. This paper investigates whether restricting voter preferences to natural structures, such as political spectrums or geographic proximity, can guarantee stability and enable efficient computation.
Modeling Delegations as Games
The authors model the delegation process as a delegation game. Voter preferences are represented using a delegation-acceptability digraph, where a directed edge from voter $i$ to $j$ indicates that $i$ is willing to accept $j$ as their guru.
In this framework, finding a stable set of gurus is mathematically equivalent to finding a kernel (a subset of nodes that are both independent and absorbing) within the graph. The paper explores how specific constraints on these graphs affect the existence and complexity of finding such kernels.
Restricted Preference Structures
The study focuses on three primary preference models common in social choice theory:
- Single-Peaked (SP): Voters are positioned along a one-dimensional axis (e.g., a left-to-right political spectrum). Voters prefer gurus closer to their own position, and the resulting digraph becomes an "interval catch digraph."
- Symmetrical: A reciprocal model where if voter $i$ accepts $j$ as a guru, then $j$ must also accept $i$.
- Distance-Based (DB): A generalization of the symmetrical model where voters are embedded in a metric space and accept any guru within a personal radius $\rho_i$.
Convergence and Complexity Results
The paper distinguishes between two types of voter behavior: Improved Response Dynamics (IRD), where voters make any move that improves their outcome, and Best Response Dynamics (BRD), where they choose the optimal available proxy.
A key finding is that while single-peaked preferences guarantee a stable equilibrium that can be found in $O(n^2)$ time, other structures present more complex trade-offs. For instance, while symmetrical and distance-based models always possess an equilibrium, finding an optimal one (e.g., minimizing total dissatisfaction) remains NP-hard.
Notably, BRD is guaranteed to converge in symmetrical and distance-based models, whereas IRD can still lead to infinite loops. This suggests that the specific rules of how voters update their delegations are as critical as the preference structures themselves.
Conclusion and Future Work
By restricting preferences to natural structures like the political spectrum, liquid democracy becomes significantly more stable and computationally tractable. However, these guarantees often rely on the assumption of a "complete" social network where any voter can delegate to any other. The authors demonstrate that if the underlying social network is restricted (e.g., a cycle), stability can vanish even with well-behaved preferences.
Future research will focus on identifying broader classes of social network topologies that maintain stability and exploring the "Price of Anarchy"—the loss of social welfare when voters act selfishly rather than following a centrally optimized delegation scheme.
Summary updated