{"id":"16f36e08-7e3a-43e7-a19e-e683d77a42ce","arxiv_id":"2502.02380","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For approval-based liquid democracy with voting and delegation costs, finding a budget-feasible representative set is polynomial, while bounded path length, bounded voting power, and voter-control variants become NP-hard once voters may approve two or more delegates.","lead":"This paper studies how to pick a small set of voters to cast ballots in liquid democracy when voting and delegating both cost money, and asks which such selection problems can be solved efficiently. It shows the basic cost-minimizing selection is easy, but adding limits on delegation length or voting power, or letting an attacker add or remove voters, makes most variants computationally hard.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.8's Vertex Cover reduction never excludes edge voters from the budget-limited casting set; without a mixed-cover argument, the claimed NP-hardness of BOUNDED POWER (and Prop. 3.9) is incomplete.","rationale":"The reader's verdict is CONDITIONAL, and the reader's rationale explicitly mentions the omitted mixed vertex/edge cover argument in Theorem 3.8, but the reader's stated weakest assumption concerns universal quantification over cost-minimizing delegation functions in the control problems. My stress-test pass identifies the Theorem 3.8 gap as the more directly load-bearing technical issue for the paper's central dichotomy. The dichotomy claim that BOUNDED POWER is NP-hard for Δ>1 depends entirely on this reduction, and Proposition 3.9 inherits the gap. The issue is concrete: the proof considers only vertex voters as the budgeted casting voters, whereas the model permits any voter to cast at cost 1, including edge voters. The missing mixed-cover equivalence is a standard and likely repairable argument, but it is not present in the submitted text. I am not claiming the theorem is false; I am claiming that, as written, the proof does not establish it. This supports a CONDITIONAL recommendation: accept only after the authors supply the missing argument or modify the construction to force all cost-1 casters to be vertex voters. This is consistent with the reader's conditional verdict and sharpens the reason for it.","tokens_in":21558,"tokens_out":15572,"duration_ms":166525,"concrete_test":"Take a small 3-regular graph with minimum vertex cover size τ, set k=τ−1, and brute-force all subsets of V∪E of size k; cast those voters plus all dummy voters, then check whether every dummy can be kept at voting power ≤4 by choosing delegations for the remaining edge and vertex voters. If any such mixed selection is feasible, the reduction is invalid. Separately verify the missing mixed-cover lemma: for any R⊆V and S⊆E with every edge either in S or incident to R, there exists a vertex cover of size at most |R|+|S|; this is the analytic check that would repair the proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing soft spot is the negative direction of Theorem 3.8. The reduction from Vertex Cover to BOUNDED POWER sets β=k with voting cost 1 and delegating cost 0 for vertex and edge voters, while dummy voters have voting cost 0 and therefore can always be cast for free. The proof argues that if no k-vertex cover exists, some edge voter must be represented through a dummy, pushing some dummy above the power bound ℓ=4. But this only rules out solutions whose cost-1 casters are all vertex voters. Nothing in the argument forbids a budget-feasible solution from casting k voters drawn from V∪E: an uncovered edge voter could simply cast its own ballot rather than delegate through a vertex to a dummy. If such a mixed selection keeps every dummy's voting power at most ℓ, the constructed instance would be feasible even though no k-vertex cover exists. The analogous \"without loss of generality, casting voters are vertex voters\" step is explicitly supplied in the proof of Theorem 3.2, but it is absent here. What is needed is a mixed vertex/edge cover lemma: any feasible solution corresponds to a set R⊆V and S⊆E with |R|+|S|≤k such that every edge not in S is incident to R, and any such mixed cover of size k yields a vertex cover of size at most k. Neither statement appears in the proof. Since Proposition 3.9 says BOUNDED SUM LENGTH is NP-hard 'immediately' from Theorem 3.8, this gap propagates to that result as well.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21827,"tokens_out":21646,"duration_ms":220710,"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":[{"comment":"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.","section":"Section 3, Theorem 3.8 and its Appendix proof"},{"comment":"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.","section":"Section 3, Proposition 3.9"},{"comment":"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.","section":"Section 4, Definitions of CONTROL BY ADDING/DELETING VOTERS"}],"minor_comments":[{"comment":"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.","section":"Appendix, Proof of Theorem 3.5"},{"comment":"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.","section":"Appendix, Proof of Theorem 4.3"},{"comment":"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.","section":"Appendix, Proof of Theorem 4.2"},{"comment":"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.","section":"Appendix, Proof of Theorem 3.8"},{"comment":"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.","section":"Section 4, Definition of super-voter"}],"recommendation":"major_revision","confidential_remarks":"The most serious issue is Proposition 3.9: a fixed-ℓ NP-completeness claim for a problem whose feasible solutions have at most ℓ delegating voters appears inconsistent with the standard enumeration argument, and the paper does not provide a valid reduction that would overcome this. This is not a mere proof gap but a potential false theorem, and it must be corrected before the paper can be accepted. The Theorem 3.8 gap is also real and should be fixed with a mixed-cover argument. I do not think rejection is warranted if the authors are willing to revise these points, since the remaining results and the overall model are valuable and appear sound under the intended interpretations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: a useful and largely correct complexity map for a new cost-aware liquid democracy model. The main thing to check is the proof of Theorem 3.8, which has a real gap, but it is repairable with a mixed vertex/edge cover argument.\n\nThe new modeling contribution is solid: each voter has a voting cost and a delegating cost, there is a budget, and the central authority must choose casting voters so that every voter is represented, optionally under path-length or voting-power constraints. The paper then maps the frontier: polynomial when each voter approves at most one other voter (Δ≤1) and NP-hard as soon as Δ=2. That is a clean and useful dichotomy. The SCC-based greedy for DELEGATE REACHABILITY is neat, the DP sketches for Δ≤1 are believable, and the hardness reductions use standard external problems with details in the appendix. The paper is also honest about what is a sketch and what is a full proof; the self-citations are contextual.\n\nThe biggest issue: Theorem 3.8. The reverse direction of the Vertex Cover reduction assumes the budget-limited casting set contains only vertex voters. But edge voters also have voting cost 1, so a feasible solution could cast a mix of vertex and edge voters within budget k. The stress-test note is right: the proof needs a mixed vertex/edge cover lemma. If S⊆V and T⊆E are the casting voters with |S|+|T|≤k, then an edge with neither endpoint in S and not in T forces some dummy's voting power above ℓ; conversely, any such mixed cover yields a vertex cover of size at most k by taking S plus one endpoint of each edge in T. That argument is missing, so the proof as written is incomplete. The theorem is very likely true with this repair, and Proposition 3.9 inherits the gap.\n\nSecond, the control problems (CAV/CDV) include β as input, but 'cost-minimizing delegation function' is not connected to β in the question. Do we require feasibility within β after the modification, or is cost-minimization unconstrained? The Section 4 proofs reason purely from v 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.","feed_headline":"Liquid democracy's easy cases end at one approved delegate","feed_subtitle":"With two or more approvals, bounded-path, power-cap, and control problems turn NP-complete.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the approval-based single-step liquid democracy model whose feasibility questions the paper extends with explicit voting and delegating costs.","marker":"Markakis and Papasotiropoulos [2021]"},{"why":"Defines the classical election-control framework and the adding/deleting voters control actions that Section 4 adapts to voting-power manipulation.","marker":"Faliszewski and Rothe [2016]"},{"why":"Motivates bounding voting power by analyzing how concentrated power threatens liquid democracy.","marker":"Gölz et al. [2021]"},{"why":"Provides the algorithmic-perspective analysis of voting-power concentration and delegation paths that the refined feasibility problems formalize.","marker":"Kahng et al. [2021]"},{"why":"Supplies the strongly connected component decomposition used by the greedy algorithm that proves DELEGATE REACHABILITY polynomial.","marker":"Dasgupta et al. (2006)"},{"why":"Prior work on controlling delegations in liquid democracy that the strategic-control section extends.","marker":"Alouf-Heffetz et al. [2024]"},{"why":"Term source for 'super-voter', which the paper redefines as the unique maximum-power casting voter in control problems.","marker":"Kling et al. [2015]"}],"fun_headline_variants":["Liquid democracy: easy with one approval, NP-complete with two","Out-degree 1 keeps liquid democracy tractable; >1 is NP-hard","One approved delegate: tractable control, two: intractable","Liquid democracy's complexity cliff: from one to two approvals","Dichotomy in liquid democracy: Δ=1 easy, Δ>1 hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Liquid democracy: easy with one approval, NP-complete with two","Out-degree 1 keeps liquid democracy tractable; >1 is NP-hard","One approved delegate: tractable control, two: intractable","Liquid democracy's complexity cliff: from one to two approvals","Dichotomy in liquid democracy: Δ=1 easy, Δ>1 hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000292,"raw_usage":{"total_tokens":1649,"prompt_tokens":838,"completion_tokens":811,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":716}},"tokens_in":454,"tokens_out":811,"duration_ms":8021,"temperature":1.0,"reasoning_tokens":716,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T12:22:28.440357+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}