Research map / Learning theory and algorithms / Submodular and game algorithms
Unravelling Expressive Delegations: Complexity and Normative Analysis
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 ranked Boolean-function delegations, giving complexity dichotomies for MinSum/MinMax unravelling, near-optimal algorithms for classic delegation, and a new cast-monotonicity axiom.
Problem
Unravelling cyclic ranked delegation ballots in liquid democracy where each delegation option is a monotone Boolean function of other agents' votes, selecting outcomes via MinSum or MinMax rules.
Approach
Gives complete complexity dichotomies for monotone Boolean delegation classes under MinSum and MinMax, efficient algorithms for classic liquid democracy (using Fulkerson's arborescence primal-dual method), biased tie-breaking rules for status-quo votes, and a cast-monotonicity axiom satisfied by MinSum and LexiMin but not MinMax.
Key results
- MinSum with any non-trivial monotone function class beyond Liquid is NP-hard and hard to approximate within n^(1-epsilon), even for ballots of size 2.
- MinMax is polynomial-time for Or and And alone, but NP-hard for OrAnd_2 with ballots of size 3.
- MinSum and LexiMin satisfy cast monotonicity while MinMax does not; efficient algorithms give O(n log n + m) for MinSum and O(n + m) for MinMax in the classic model.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow any nontrivial monotonic delegation function instead of only direct delegations and direct votes | MinSum · Enhanced liquid democracy | computational complexity | Hurt |
| Allow functions beyond arbitrary-arity ORs alone or ANDs alone | MinMax · Enhanced liquid democracy | computational complexity | Hurt |
| Use the proposed MinSum certificate algorithm instead of the previous algorithm | MinSum certificates in classic liquid democracy · Classic liquid democracy | runtime: O(nm) -> O(n \log n + m) | Helped |
| Use the proposed MinMax certificate algorithm instead of the previous algorithm | MinMax certificates in classic liquid democracy · Classic liquid democracy | runtime: O(n^2\ell^2) -> O(n + m) | Helped |
| Use MinSum rather than MinMax | Unravelling procedures in classic liquid democracy · Cast monotonicity | cast monotonicity | Helped |
| Refine MinMax lexicographically by minimizing the sorted certificate ranks | MinMax · Classic liquid democracy | cast monotonicity | Helped |
| Allow binary OR or AND delegations | MinSum in the enhanced model · Cast monotonicity | cast monotonicity | Hurt |
Surprising findings
- MinSum fails cast monotonicity once binary OR or AND delegations are allowed, despite satisfying it in the classic model.
- Hardness of MinMax arises already with ballots of size three, whereas for MinSum size two suffices.
Limitations
- Results restricted to binary issues and monotone delegation functions.
- Cardinal preferences not modelled; only ordinal rankings.
- Hardness results rely on P != NP and do not address practical instances.
Experimental setup
Metrics: computational complexity (poly-time vs NP-hard) approximation hardness running time
Baselines: MinSum (Colley et al.) MinMax (Colley et al.)
Builds on: Colley et al. smart voting Fulkerson primal-dual arborescence algorithm liquid democracy with ranked delegations
Closest papers by meaning
- Liquid Democracy with Ranked Delegations (AAAI 2022 · similarity 0.94)
- Liquid Democracy: An Algorithmic Perspective (AAAI 2018 · similarity 0.93)
- The Cost Perspective of Liquid Democracy: Feasibility and Control (AAAI 2025 · similarity 0.89)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.87)
- Participation Incentives in Approval-Based Committee Elections (AAAI 2024 · similarity 0.86)
- Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract) (AAAI 2025 · similarity 0.86)
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.