Research map / Learning theory and algorithms / Submodular and game algorithms
The Cost Perspective of Liquid Democracy: Feasibility and Control
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies liquid democracy with voting and delegating costs under a budget, analyzing complexity of feasibility, path-length and voting-power refinements, and strategic control by adding/deleting voters.
Problem
Selecting casting voters in liquid democracy under a cost budget while ensuring every voter is represented via trust paths, with bounds on delegation path length and voting power, plus strategic control of a designated voter's power.
Approach
Introduces a cost-based liquid democracy model (voting and delegating costs with a budget) and studies its computational complexity, including a control framing where an external agent manipulates the electorate to make a preferred voter the sole super-voter.
Key results
- Delegate Reachability is solvable in polynomial time via SCC decomposition and greedy selection of sink representatives.
- Bounded Max Length and Bounded Power are polynomial for max out-degree at most 1 (dynamic programming) and NP-complete for out-degree above 1 (Bounded Max Length for fixed length at least 2; Bounded Power for fixed bound at least 4).
- Control by adding voters and control by deleting voters are NP-hard in general but polynomial when max out-degree is at most 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow α abstainers | Delegate Reachability · Delegate Reachability with α abstainers | computational complexity | Hurt |
| Restrict the maximum out-degree to Δ≤1 | Bounded Max Length · Bounded Max Length | computational complexity | Helped |
| Allow maximum out-degree Δ>1 | Bounded Max Length · Bounded Max Length | computational complexity | Hurt |
| Restrict the maximum out-degree to Δ≤1 | Bounded Power · Bounded Power | computational complexity | Helped |
| Allow maximum out-degree Δ>1 | Bounded Power · Bounded Power | computational complexity | Hurt |
| Restrict the maximum out-degree to Δ≤1 | Bounded Sum Length · Bounded Sum Length | computational complexity | Helped |
| Allow maximum out-degree Δ>1 | Bounded Sum Length · Bounded Sum Length | computational complexity | Hurt |
| Restrict the maximum out-degree to Δ≤1 | Control by Adding/Deleting Voters · Control by Adding/Deleting Voters | computational complexity | Helped |
| Allow adding or deleting delegation edges | Control by Adding/Deleting Edges · Strategic control | computational complexity | Hurt |
| Restrict the maximum out-degree to Δ≤1 | Control by Adding/Deleting Edges · Strategic control | computational complexity | Helped |
Surprising findings
- Allowing a fixed number of abstainers as small as the constant case stays polynomial, but with abstainers as part of the input Delegate Reachability becomes NP-complete.
Limitations
- Hardness results hold for out-degree 2 and above, so most problems are intractable in general.
- Model abstracts away from actual ballots and voter preferences over outcomes.
- No empirical evaluation; simulations are suggested as future work.
Experimental setup
Builds on: liquid democracy election control
Closest papers by meaning
- On Rational Delegations in Liquid Democracy (AAAI 2019 · similarity 0.91)
- Unravelling Expressive Delegations: Complexity and Normative Analysis (AAAI 2024 · similarity 0.89)
- Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract) (AAAI 2025 · similarity 0.85)
- Towards a More Burkean Approach to Computational Social Choice (AAAI 2024 · similarity 0.83)
- Voter Priming Campaigns: Strategies, Equilibria, and Algorithms (AAAI 2025 · similarity 0.83)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.