Pith. sign in

REVIEW 3 major objections 5 minor 34 references

The Cost Perspective of Liquid Democracy: Feasibility and Control

T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For approval-based liquid democracy, efficient delegation planning is exactly the single-approval case, and the paper proves it.

desk verdict Useful complexity map for a new cost-aware liquid democracy model; the proof of Theorem 3.8 has a repairable gap and the control definitions need clarification. read the letter →

arxiv 2502.02380 v1 pith:5Q2CEW5K submitted 2025-02-04 cs.GT cs.AI

Shiri Alouf-Heffetz , {L}ukasz Janeczko , Grzegorz Lisowski , Georgios Papasotiropoulos This is my paper · ORCID
classification cs.GTcs.AI MSC 91B1268Q17
keywords liquiddemocracydelegationgraphcomputationalcomplexityNP-completenesselectioncontrolvotingpowerboundedpathcostminimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies an approval-based model of liquid democracy in which each voter has a cost for voting and a cost for delegating, names acceptable representatives, and must be represented through a chain of approvals within a budget. It establishes a complexity frontier for choosing casting voters: the basic feasibility problem, DELEGATE REACHABILITY, is polynomial-time solvable, and every studied refinement is polynomial when each voter approves at most one candidate ($\Delta \le 1$) but NP-complete or NP-hard once voters may approve two or more ($\Delta > 1$). The refined problems include bounding the length of delegation paths, bounding the voting power of any caster, bounding the total path length, and strategic control by adding or deleting voters to make a favored voter the unique maximum-power caster. If the dichotomy is right, the single-approval case is the exact frontier of what can be computed efficiently for these delegation-planning tasks.

What carries the argument

The load-bearing object is the delegation graph and its maximum out-degree $\Delta$. On the polynomial side, the key structural fact is that a graph with $\Delta \le 1$ is a disjoint union of components each containing at most one directed cycle, so each component is a forest of upwards-directed trees feeding into either a root or a cycle; this admits bottom-up dynamic programming over in-neighbors for path-length and voting-power caps, while DELEGATE REACHABILITY itself is solved greedily from the strongly connected component condensation by choosing one cheapest casting voter from each sink component. On the hardness side, the reductions construct gadgets from voters with voting cost $1$ and delegating cost $0$, which force exactly one casting voter per pair or per sink and make the budget bind; 3-SAT encodes into bounded-max-length, vertex cover into bounded-power and adding-voters, and clique into deleting-voters.

What would settle it

An exhaustive solver over all delegation functions for all cLD instances with at most seven voters should reproduce the paper's dynamic-programming cost for $\Delta \le 1$ instances, and on the clause gadget from Theorem 3.6 built from an unsatisfiable 3-CNF formula it should certify that no maximum-length-2 solution exists; any mismatch would refute the dichotomy.

Watch

Extended reading notes

Core claim

The paper's central claim is a dichotomy in the maximum out-degree $\Delta$ of the delegation graph. A cLD election is a directed graph whose vertices are voters, with an edge meaning the voter approves that person as a representative, plus voting costs and delegating costs. The paper proves that DELEGATE REACHABILITY—does there exist a set of casting voters and one outgoing delegation per non-caster satisfying the budget and giving every non-caster a directed path to a caster—is always polynomial, via a greedy algorithm on the strongly connected component condensation. For the refined objectives, BOUNDED MAX LENGTH, BOUNDED POWER, and BOUNDED SUM LENGTH, the paper gives dynamic-programming polynomial algorithms for $\Delta \le 1$ and NP-completeness proofs for $\Delta > 1$, using reductions from 3-SAT and vertex cover. For CONTROL BY ADDING VOTERS and CONTROL BY DELETING VOTERS, where a controller must make a designated voter $x$ the sole super-voter under every cost-minimizing delegation function, the paper shows NP-hardness in general and polynomial solvability when $\Delta \le 1$.

Load-bearing premise

The load-bearing premise for the control results is that the controller must make the preferred voter the unique maximum-power caster under every cost-minimizing delegation function satisfying reachability, including every tie choice among equal-cost delegations; if a real system fixes tie-breaking, the control problem becomes a different one to which these results need not transfer.

Editorial extensions

If this is right

  • For any liquid-democracy instance in which each voter approves at most one representative, a platform can compute a cost-minimal set of casting voters in polynomial time, and can also enforce a maximum delegation-path length or a voting-power cap while staying within budget.
  • Once voters may approve two or more representatives, each of these optimization problems becomes NP-complete for fixed bounds ($\ell \ge 2$ for BOUNDED MAX LENGTH, $\ell \ge 4$ for BOUNDED POWER and BOUNDED SUM LENGTH), so no polynomial algorithm is expected unless P = NP.
  • Strategic control—adding or deleting voters to make a favored voter the unique maximum-power caster under every cost-minimizing delegation—is NP-hard in general but polynomial for $\Delta \le 1$; the same holds for the edge-adding and edge-deleting variants.
  • Allowing a non-constant number $\alpha$ of abstainers makes even the basic DELEGATE REACHABILITY problem NP-complete, while a fixed number of abstainers leaves it polynomial.
  • The hardness results remain true on very restricted delegation graphs, including layered directed graphs and directed bipartite graphs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not say this, but the universal 'every cost-minimizing delegation function' condition in the control results is a strong requirement; a concrete system with fixed tie-breaking among equal-cost delegations could face an easier or different control problem, so the NP-hardness findings should be read as worst-case over all tie resolutions.
  • If the dichotomy transfers, nearby problems not explicitly named—destructive control, ensuring a delegating (non-casting) voter accumulates influence, or controlling by both adding and deleting voters—are also likely to be polynomial at $\Delta \le 1$ and hard at $\Delta > 1$, since the paper notes the proofs extend to them.
  • The cost parameters suggest an empirical check of the liquid-democracy savings claim: on synthetic instances, compare the budget needed for direct voting against the budget from the $\Delta \le 1$ algorithm, and measure how much extra budget the path-length and power constraints consume.
  • The parameterized hardness observations (for example, W[1]-hardness by the deletion budget) point toward approximation and parameterized algorithms as the next practical route for control safeguards in real systems.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. This paper studies a model of liquid democracy in which each voter has an approval list of possible representatives and two costs: a voting cost (if the voter casts a ballot) and a delegating cost (if the voter delegates). A solution is a set C of casting voters together with one outgoing delegation edge for every non-casting voter, such that every voter reaches C via a directed path and the total cost is within a budget β. The paper analyzes the complexity of finding such delegation functions under additional constraints on maximum path length, maximum voting power, and sum of path lengths, and then introduces control problems in which an external agent adds or deletes voters (or edges) to make a designated voter the unique 'super-voter' under every cost-minimizing delegation function. The main claimed results are: DELEGATE REACHABILITY is polynomial-time solvable; BOUNDED MAX LENGTH and BOUNDED POWER are polynomial for Δ≤1 and NP-complete for Δ>1; BOUNDED SUM LENGTH is claimed to be NP-complete for fixed ℓ≥4 when Δ>1; and the voter/edge control problems are NP-hard in general but polynomial for Δ≤1.

Significance. If the results are correct, the paper gives a clean complexity map for cost-aware liquid democracy, identifying the one-approval-per-voter regime (Δ≤1) as the tractability frontier for the studied refined feasibility and control problems. The paper also makes a useful conceptual contribution by defining control in terms of voting power rather than election outcomes and by requiring the controller's goal to hold under all cost-minimizing delegation functions, which is a strong robustness condition. The technical approach is standard but suitable: tractability is shown via explicit greedy or DP algorithms, and hardness via reductions from 3-SAT, Vertex Cover, and Clique, with the main proofs collected in an appendix. These are concrete, falsifiable statements and are a strength of the paper. However, the claimed dichotomy rests on Proposition 3.9, which as stated is very likely incorrect, and the proof of Theorem 3.8 has a gap that must be repaired; the control results also need a cleaner formal definition of 'cost-minimizing' when β is part of the input.

major comments (3)
  1. [Section 3, Theorem 3.8 and its Appendix proof] The reverse direction of the Vertex Cover reduction assumes, without proof, that the at most k budgeted casting voters are all vertex voters. In the constructed instance, edge voters also have voting cost 1, so a mixed set of k voters from V∪E can be cast. If an uncovered edge voter e simply casts its own ballot, the proof's claim that e 'will be represented by a voter from D' fails, and the dummy's voting power need not exceed ℓ=4. The proof therefore does not establish NP-hardness of BOUNDED POWER as written. A repair is available by proving a mixed vertex/edge cover lemma: any feasible solution yields sets R⊆V and S⊆E with |R|+|S|≤k such that every edge is in S or incident to R, and any such mixed cover yields a vertex cover of size at most k. This argument is absent and should be supplied. Because Proposition 3.9 is said to follow 'immediately' from Theorem 3.8, this gap propagates to that result as well.
  2. [Section 3, Proposition 3.9] The claim that BOUNDED SUM LENGTH is NP-complete for every fixed ℓ≥4 is unsupported and very likely false. For a fixed constant ℓ, every non-casting voter contributes at least 1 to the sum of path lengths, so any feasible solution has at most ℓ non-casting voters. One can enumerate all O(n^ℓ) candidate sets of non-casting voters and, for each, brute-force over the possible outgoing delegation edges from these voters (n^{O(ℓ)} possibilities) to check reachability, cost, and the sum bound. Hence the problem is in P for every fixed ℓ. The construction in Theorem 3.8 does not transfer either, because its total sum of path lengths grows with the instance size, not with the constant ℓ. The authors should either correct the statement (e.g., to NP-completeness when ℓ is part of the input, if a valid reduction can be given) or remove the hardness claim and adjust the paper's conclusions accordingly.
  3. [Section 4, Definitions of CONTROL BY ADDING/DELETING VOTERS] The term 'cost-minimizing delegation function' is defined in Section 2 only for the case where β is not part of the input, but the control problems CAV and CDV take β as part of the input. As stated, if the given β is smaller than the minimum feasible cost then the set of cost-minimizing delegation functions satisfying reachability is empty, making the controller's goal vacuously true; if β is larger, the budget does not constrain the delegation function at all. The paper should clarify the intended semantics: for example, that the controller must ensure the resulting election has at least one feasible delegation function within budget β, and that the universal quantification is over all delegation functions that minimize total cost among those feasible functions. This ambiguity affects the interpretation of Theorems 4.2–4.7 and should be resolved in the formal problem definitions.
minor comments (5)
  1. [Appendix, Proof of Theorem 3.5] In the recurrence for dp[v,i,k], the expression 'dp[vi+1, p(i+1), k−1]' should read 'dp[vi+1, p(vi+1), k−1]', since p is the in-degree function.
  2. [Appendix, Proof of Theorem 4.3] In the reverse direction, the sentence 'Pick any arbitrary set of k voters from V to add in the election' should say 'to delete from the election', since the proof concerns deleting voters.
  3. [Appendix, Proof of Theorem 4.2] The statement that x and y 'have less voting that delegating cost' is inaccurate because their voting and delegating costs are both 0; the correct justification is that they have no outgoing edges, so in any feasible reachable solution they must cast their ballots.
  4. [Appendix, Proof of Theorem 3.8] The cost assignment for the two additional voters attached to each dummy voter is ambiguous: the sentence 'We set the rest voting costs to 1 and all delegating costs to 0' could be read to exclude or include those two voters. Please state their voting and delegating costs explicitly.
  5. [Section 4, Definition of super-voter] The phrase 'sole super-voter' should be defined precisely as the unique casting voter with maximum voting power; the current informal definition leaves open the treatment of ties. The proofs already use this meaning, but the definition should say so.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all derivations are external reductions or constructive algorithms, with self-citations only contextual.

full rationale

The paper's central claims are supported by reductions from external NP-complete problems (Vertex Cover, 3-SAT, Clique) and by constructive polynomial-time algorithms (SCC-based greedy for DELEGATE REACHABILITY, dynamic programming for Δ≤1 cases, greedy layer-based procedures for control). No fitted parameter is renamed as a prediction, no normalization is defined in terms of the target quantity, and no load-bearing uniqueness theorem is imported from the authors' own prior work. The few self-citations (e.g., Alouf-Heffetz et al. 2024, Markakis and Papasotiropoulos 2021) are contextual, describing related liquid-democracy models or control literature, and the proofs do not depend on those citations for correctness. The skeptical concern about Theorem 3.8 is a possible gap in the reduction's completeness argument (whether mixed vertex/edge casting sets are ruled out), which is a correctness issue, not a circularity issue: the reduction still targets an external NP-complete benchmark, and there is no step where the conclusion is equivalent to the input by definition. Accordingly, the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard complexity-theoretic benchmarks, SCC decomposition, and three domain assumptions (additive costs, transitive trust, universal quantification over cost-minimizing delegation functions). No free parameters are fitted and no new entities are postulated.

assumptions (6)
  • standard math NP-completeness of 3-SAT, Vertex Cover (including 3-regular), and Clique as source problems.
    Invoked by the reductions in Theorems 3.6, 3.8, 4.2, and 4.3.
  • standard math Strongly connected component decomposition yields a DAG whose sinks must each contain a casting voter.
    Used in the greedy algorithm for Theorem 3.1 and its appendix proof.
  • domain assumption A voter is satisfied iff there is a directed path through approved delegates to a casting voter; trust is transitive.
    Core representation notion defined in Section 2 and used in every problem statement.
  • domain assumption Voting and delegating costs are additive, known, and can be zero; no ordering between them is assumed.
    Model definition in Section 2; costs are inputs to the algorithms and reductions.
  • domain assumption The delegation mechanism is any cost-minimizing function satisfying reachability, and control must succeed under every such function.
    Definition of super-voter and CAV/CDV in Section 4; this universal quantification drives the control results.
  • standard math For Δ=1, each weakly connected component contains at most one directed cycle and otherwise is an upwards-directed tree.
    Structural observation preceding Theorems 3.5 and 3.7, enabling the dynamic programs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Cost Perspective of Liquid Democracy: Feasibility and Control." pith.science (2026). https://pith.science/paper/5Q2CEW5K

@misc{pith2026250202380,
  author       = {Pith},
  title        = {Pith review of: The Cost Perspective of Liquid Democracy: Feasibility and Control},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5Q2CEW5K}},
  note         = {Machine review of arXiv:2502.02380}
}
read the original abstract

We examine an approval-based model of Liquid Democracy with a budget constraint on voting and delegating costs, aiming to centrally select casting voters ensuring complete representation of the electorate. From a computational complexity perspective, we focus on minimizing overall costs, maintaining short delegation paths, and preventing excessive concentration of voting power. Furthermore, we explore computational aspects of strategic control, specifically, whether external agents can change election components to influence the voting power of certain voters.

Figures

Figures reproduced from arXiv: 2502.02380 by the authors.

Figure 1
Figure 1. An example of a delegation graph on 6 voters, namely {a, b, c, d, e, f}. Numbers in vertices indicate voting costs, while those on an edge (u, v) show the delegating cost of voter u. In practice, and setting aside the costs for a moment, an electorate in a Liquid Democracy scenario under the discussed model can be partitioned into two groups: Voters who prefer casting a ballot and those who do not. Essentially, a de… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 28 canonical work pages

  1. [1]

    N. Alon, F. Fischer, A. Procaccia, and M. Tennenholtz. Sum of us: Strategyproof selection from the selectors. In Proceedings of the Conference on Theoretical Aspects of Rationality and Knowledge, pages 101--110, 2011

    2011

  2. [2]

    Alouf-Heffetz, T

    S. Alouf-Heffetz, T. Inamdar, P. Jain, N. Talmon, and Y. M. Hiren. Controlling delegations in liquid democracy. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, page 2624–2632, 2024

    work page 2024

  3. [3]

    Armstrong and K

    B. Armstrong and K. Larson. On the limited applicability of liquid democracy. In Games, Agents, and Incentives Workshop, 2021

    work page 2021

  4. [4]

    Armstrong, S

    B. Armstrong, S. Alouf - Heffetz, and N. Talmon. Optimizing viscous democracy. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 2643--2650, 2024

    work page 2024

  5. [5]

    K. A. Awan, I. U. Din, A. Almogren, M. Guizani, and S. Khan. Stab T rust—a stable and centralized trust-based clustering mechanism for IoT enabled vehicular ad-hoc networks. IEEE Access, 8: 0 21159--21177, 2020

    work page 2020

  6. [6]

    Behrens, A

    J. Behrens, A. Kistner, A. Nitsche, and B. Swierczek. The temporal dimension in the analysis of liquid democracy delegation graphs. Interaktive Demokratie, 2021

    work page 2021

  7. [7]

    Who won? Winner Determination and Robustness in Liquid Democracy

    M. Bentert, N. Boehmer, M. Rymar, and H. Tannenberg. Who won? W inner determination and robustness in liquid democracy. arXiv preprint arXiv:2205.05482, 2022

    work page Pith review arXiv 2022

  8. [8]

    Birmpas, P

    G. Birmpas, P. Lazos, E. Markakis, and P. Penna. Reward schemes and committee sizes in proof of stake governance. In Proceedings of the International Conference on Financial Cryptography and Data Security, 2025

    work page 2025

Show all 34 references
  1. [9]

    Bloembergen, D

    D. Bloembergen, D. Grossi, and M. Lackner. On rational delegations in liquid democracy. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1796--1803, 2019

    2019

  2. [10]

    Blum and C

    C. Blum and C. I. Zuber. Liquid democracy: Potentials, problems, and perspectives. Journal of Political Philosophy, 24 0 (2): 0 162--182, 2016

    2016

  3. [11]

    Boldi, F

    P. Boldi, F. Bonchi, C. Castillo, and S. Vigna. Voting in social networks. In Proceedings of the ACM Conference on Information and Knowledge Management, pages 777--786, 2009

    2009

  4. [12]

    Brill, T

    M. Brill, T. Delemazure, A.-M. George, M. Lackner, and U. Schmidt-Kraepelin. Liquid democracy with ranked delegations. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4884--4891, 2022

    2022

  5. [13]

    Campbell, A

    J. Campbell, A. Casella, L. de Lara, V. R. Mooers, and D. Ravindran. Liquid democracy. two experiments on delegation in voting. Technical report, National Bureau of Economic Research, 2022

    2022

  6. [14]

    Colley, T

    R. Colley, T. Delemazure, and H. Gilbert. Measuring a priori voting power in liquid democracy. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 2607--2615, 2023

    2023

  7. [15]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009

    2009

  8. [16]

    Dasgupta, C

    S. Dasgupta, C. H. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill, Inc., 2006

    2006

  9. [17]

    Escoffier, H

    B. Escoffier, H. Gilbert, and A. Pass-Lanneau. The convergence of iterative delegations in liquid democracy in a social network. In Proceedings of the International Symposium on Algorithmic Game Theory, pages 284--297, 2019

    2019

  10. [18]

    Escoffier, H

    B. Escoffier, H. Gilbert, and A. Pass-Lanneau. Iterative delegations in liquid democracy with restricted preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1926--1933, 2020

    1926

  11. [19]

    Faliszewski and J

    P. Faliszewski and J. Rothe. Control and bribery in voting. In Handbook of Computational Social Choice, pages 146--168. Cambridge University Press, 2016

    2016

  12. [20]

    Faliszewski, E

    P. Faliszewski, E. Hemaspaandra, and L. A. Hemaspaandra. Multimode control attacks on elections. Journal of Artificial Intelligence Research, 40: 0 305--351, 2011

    2011

  13. [21]

    Gersbach, A

    H. Gersbach, A. Mamageishvili, and M. Schneider. Staking pools on blockchains. arXiv preprint arXiv:2203.05838, 2022

    2022 arXiv

  14. [22]

    G \"o lz, A

    P. G \"o lz, A. Kahng, S. Mackenzie, and A. D. Procaccia. The fluid mechanics of liquid democracy. ACM Transactions on Economics and Computation, 9 0 (4): 0 1--39, 2021

    2021

  15. [23]

    Green-Armytage

    J. Green-Armytage. Direct voting and proxy voting. Constitutional Political Economy, 26: 0 190--220, 2015

    2015

  16. [24]

    Grossi, U

    D. Grossi, U. Hahn, M. M \"a s, A. Nitsche, J. Behrens, N. Boehmer, M. Brill, U. Endriss, U. Grandi, et al. Enabling the digital democratic revival: A research program for digital democracy. arXiv preprint arXiv:2401.16863, 2024

    2024 arXiv

  17. [25]

    Hemaspaandra, L

    E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe. Anyone but him: The complexity of precluding an alternative. Artificial Intelligence, 171 0 (5-6): 0 255--285, 2007

    2007

  18. [26]

    Kahng, Y

    A. Kahng, Y. Kotturi, C. Kulkarni, D. Kurokawa, and A. Procaccia. Ranking wily people who rank each other. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1087--1094, 2018

    2018

  19. [27]

    Kahng, S

    A. Kahng, S. Mackenzie, and A. Procaccia. Liquid democracy: An algorithmic perspective. Journal of Artificial Intelligence Research, 70: 0 1223--1252, 2021

    2021

  20. [28]

    Kling, J

    C. Kling, J. Kunegis, H. Hartmann, M. Strohmaier, and S. Staab. Voting behaviour and power in online democracy: A study of L iquid F eedback in G ermany's P irate P arty. In Proceedings of the International AAAI Conference on Web and Social Media, pages 208--217, 2015

    2015

  21. [29]

    Markakis and G

    E. Markakis and G. Papasotiropoulos. An approval-based model for single-step liquid democracy. In Proceedings of the International Symposium on Algorithmic Game Theory, pages 360--375, 2021

    2021

  22. [30]

    J. C. Miller III. A program for direct and proxy voting in the legislative process. Public Choice, 7 0 (1): 0 107--113, 1969

    1969

  23. [31]

    Mishra, G

    M. Mishra, G. S. Gupta, and X. Gui. Trust-based cluster head selection using the k-means algorithm for wireless sensor networks. In Proceedings of the International Conference on Smart Systems and Inventive Technology, pages 819--825, 2019

    2019

  24. [32]

    A. Paulin. An overview of ten years of liquid democracy research. In Proceedings of the International Conference on Digital Government Research, pages 116--121, 2020

    2020

  25. [33]

    G. Tullock. Proportional representation. Toward a Mathematics of Politics, pages 144--157, 1967

    1967

  26. [34]

    Zhang and D

    Y. Zhang and D. Grossi. Power in liquid democracy. In Proceedings of the AAAI conference on Artificial Intelligence, pages 5822--5830, 2021

    2021

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.