Controlling Delegations in Liquid Democracy

The strongest positive case is a targeted one: the paper’s single-delegation results admit a faithful high-multiplicity mirror when many citizens are exchangeable members of a small number of proxy cohorts. The mirror does not cover arbitrary delegation networks, but it covers a named and technically central regime of the paper.

My lead anchor is Theorem 2, proved in this paper. It states that CCRA is NP-hard for single delegation even when delegation paths have length at most one, every arc costs \(1\), every approval set has size at most \(3\), and only one voter approves \(c^\star\). The proof is by reduction from Vertex Cover in cubic graphs; the NP-hardness of that source problem is cited from [16], but Theorem 2 itself is proved here.

A natural high-multiplicity setting is a large liquid-democracy referendum in which citizens delegate directly to issue experts. A voter type records whether the voter is active or passive, the approval set of the active proxy to which a passive voter currently delegates, and the applicable redirection-cost profile. Millions of citizens may share one of a finite number of such types: for example, many citizens delegate to interchangeable climate, transport, or housing experts with the same approval ballots. The delegation graph is genuinely the paper’s graph, but in this scenario it is an exchangeable depth-one proxy structure. The number of citizens is much larger than the number of proxy and approval types.

Call the resulting problem Depth-One CCRA\(_\infty\). An instance consists of candidates \(C\), a preferred candidate \(c^\star\), a finite set \(\mathcal A\) of active approval types \(A\subseteq C\) with \(|A|\le 3\), active mass \(a_A\), passive mass \(p_A\) currently delegating to type \(A\), and a normalized budget \(K\). The masses are rational and satisfy \(\sum_{A\in\mathcal A}(a_A+p_A)=1\). In the special case mirroring Theorem 2, only one approval type contains \(c^\star\), and every redirection costs one unit of mass.

The controller chooses variables \(x_{A,B}\ge 0\), where \(x_{A,B}\) is the mass currently delegating to type \(A\) that is redirected to type \(B\). The constraints are \( \sum_B x_{A,B}\le p_A \) and \( \sum_{A,B}x_{A,B}\le K \). After redirection, the mass voting with approval set \(A\) is \(q_A=a_A+p_A-\sum_Bx_{A,B}+\sum_Dx_{D,A}\). Candidate \(c\) therefore receives score \(s_c(x)=\sum_A q_A\mathbf 1[c\in A]\). The question is whether there is a feasible \(x\) for which \(c^\star\) is the unique winner, namely whether the maximum margin \( \lambda \) satisfying \(s_{c^\star}(x)-s_c(x)\ge\lambda\) for every \(c\ne c^\star\) is positive.

This is a linear program with \(O(|\mathcal A|^2)\) redirection variables and \(O(m)\) winner constraints. Thus I expect Depth-One CCRA\(_\infty\) to be Class A, tractable by continuous optimization. The discrete Vertex Cover gadget illustrates why: once many identical voters can be redirected fractionally, choosing a vertex becomes assigning a quantity of mass to that vertex gadget. The edge-candidate constraints become a fractional covering LP rather than an integral vertex-selection problem. This is exactly the kind of population-multiplicity hardness that continuization can remove.

The correspondence is not merely a weighted approval election. The action variable is delegation mass, and the objective is the redirection cost. For rational masses, clearing denominators produces a finite election with repeated citizens and repeated proxy types; scores, budgets, and unique-winner comparisons scale exactly. Conversely, a repeated finite depth-one delegation instance maps back to these masses. Redirecting to a passive voter causes no difficulty in this regime: it is outcome-equivalent to redirecting directly to that voter’s active proxy at the same unit cost, so the type-level formulation does not remove a strategically relevant operation. Since delegation paths have length one, the union, approval, and GreedyMRC unraveling functions coincide, just as they do in the relevant part of the paper’s proof.

A second, independently useful anchor is Theorem 3, also proved here. It states that CCRA is polynomial-time solvable when there is single delegation and every active voter approves exactly one candidate. Its proof relies on Lemma 1, proved in the paper, which computes by dynamic programming the minimum cost of obtaining each possible number of \(c^\star\)-votes from a delegation tree.

The corresponding continuous problem is Repeated-Tree CCRA\(_\infty\). Here the population consists of rational mass of repeated delegation-tree templates. A template \(\sigma\) is an explicitly given rooted tree whose root is an active voter with singleton ballot \(\{r_\sigma\}\), whose other vertices are passive, and whose arcs have redirection costs. Let \(q_\sigma\) be its number of vertices and let \(\nu_\sigma\) be its mass per unit population, with \(\sum_\sigma q_\sigma\nu_\sigma=1\). This describes, for example, a large platform containing many repeated local chapters or organizational cells with the same delegation hierarchy.

For each template \(\sigma\) and each feasible \(j\), let \(\kappa_\sigma(j)\) be the minimum cost of redirecting arcs in one copy of \(\sigma\) so that exactly \(j\) voters in that copy ultimately vote for \(c^\star\). The same tree dynamic program as in Lemma 1 computes these values. The continuous controller chooses \(y_{\sigma,j}\ge0\), the mass of copies of template \(\sigma\) using a redirection pattern achieving \(j\) target votes, with \(\sum_jy_{\sigma,j}=\nu_\sigma\).

Each such configuration contributes \(j\) votes to \(c^\star\), \(q_\sigma-j\) votes to \(r_\sigma\) when \(r_\sigma\ne c^\star\), and zero votes to other candidates. The controller minimizes \(\sum_{\sigma,j}\kappa_\sigma(j)y_{\sigma,j}\), subject to the resulting target score being strictly larger than every other candidate’s score. The budget decision version again becomes an LP by maximizing the winner margin under a given budget.

This second mirror is also expected to be Class A. It retains the indivisibility and topology of each delegation tree; only the multiplicity of identical trees becomes divisible. Clearing rational denominators gives repeated finite tree components exactly. The continuous LP is therefore not replacing delegation by a generic fractional vote: it is mixing whole, discrete redirection configurations across many identical components.

The scope should remain narrow. These mirrors cover Theorem 2’s depth-one single-delegation regime and Theorem 3’s single-delegation, single-approval regime. They do not claim to continuize Theorem 1’s genuinely multi-delegation hardness, the general W[2]-hardness statements, or the paper’s unrestricted graph setting. Natural follow-up questions are whether type-dependent redirection costs preserve the LP formulation, whether multi-delegation can be represented by finite delegation-profile types with an efficient pricing problem, and how much finite-election rounding error is needed when the continuous winner margin is small.

The weakest point is clear: arbitrary delegation graphs are identity- and topology-sensitive, and voter-type marginals alone cannot encode their paths or in-degrees. Repeated-tree CCRA\(_\infty\) addresses this by preserving whole component types, while Depth-One CCRA\(_\infty\) deliberately chooses the paper’s explicit length-one regime where topology disappears without changing the paper’s central control action. A referee might regard the second model as a structured extension rather than a pure distribution over independent voter types. But the lead mirror remains a convincing continuous analogue of a named theorem: it preserves the approval ballots, proxy delegation, redirection action, budget, and unique-winner objective, while exposing a genuine Class-A linear optimization problem behind the paper’s discrete NP-hardness.