| paper | Preserving Consistency in Multi-Issue Liquid Democracy |
| authors | Rachael Colley, Umberto Grandi |
| venue | IJCAI 2022 |
| filed under | voting · combinatorial |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 2
statement extracted from the paper’s text layer
Given a finite set of complete voter types \(\Theta\), rational masses \(\mu_\theta\), acyclic type-level delegations, direct votes \(\widehat b_\theta\), canonical votes \(g_\theta\), and a consistency family \(\Gamma\subseteq\{0,1\}^m\) with polynomial-time partial-completion testing, decide whether there are variables \(q_{\theta,x}\ge 0\) for \(x\in\Gamma\) satisfying \(\sum_{x\supseteq\widehat b_\theta}q_{\theta,x}=\mu_\theta\) for every \(\theta\), with total changed mass \(\sum_{\theta,x}q_{\theta,x}|\{j:\theta\text{ delegates on }j,\ x_j\ne g_{\theta j}\}|\) at most a rational threshold \(K\).
A high-multiplicity liquid-democracy society is represented by type masses \(\mu\). Each type has complete direct votes and delegation behavior, inducing \(g_\theta\); decision variables distribute its mass among feasible consistent final ballots \(x\in\Gamma\), minimizing the mass-weighted number of changed delegated votes.
After delegations are compiled into canonical votes, the continuous formulation has no interaction or shared proxy state and becomes a weighted batch of independent consistency-repair problems.
fatal: False
The mirror covers Proposition 2 and its independent-set hardness. It leaves Proposition 1, the PDC and PVC algorithmic results in Propositions 3–5, the approximation results in Propositions 6–7, the priority comparison results in Propositions 8–9, and the budget result in Proposition 10.
The strongest case is built around the paper’s Proposition 2, which proves here that MINIMALVOTECHANGE is NP-complete. The reduction is from INDEPENDENT SET and is therefore a genuine hardness result proved in the paper, rather than merely a cited classification.
I would call the mirror Continuous Minimal Vote Change (\(\mathrm{CMVC}_\infty\)). There are \(m\) binary issues and a finite set \(\Theta\) of voter types. A type \(\theta\) specifies its direct votes, the issues on which it delegates, and the type or proxy-role receiving each delegation. For every issue, the type-level delegation graph is acyclic. The population is a rational mass vector \(\mu\), with \(\mu_\theta\) the fraction of society of type \(\theta\). Following delegations gives each type a canonical vote vector \(g_\theta\in\{0,1\}^m\), exactly as \(X_B\) is computed in the paper.
The constraint \(\Gamma\subseteq\{0,1\}^m\) is part of the instance. It may encode, for example, budget feasibility, transitivity, or the independent-set constraint used in Proposition 2. As in the paper, partial completion to a \(\Gamma\)-consistent vote must be polynomial-time checkable. Direct votes cannot be changed.
The decision variable is a collection \(q_{\theta,x}\ge0\), where \(q_{\theta,x}\) is the mass of type \(\theta\) assigned the final vote \(x\in\Gamma\). It must satisfy
\[ \sum_{\substack{x\in\Gamma\\x\supseteq \widehat b_\theta}}q_{\theta,x}=\mu_\theta \]
for every type \(\theta\). The objective is the normalized number of changed canonical votes:
\[ \min_q \sum_{\theta\in\Theta} \sum_{x\in\Gamma} q_{\theta,x} \left| \{j:\theta\text{ delegates on }j,\ x_j\neq g_{\theta j}\} \right|. \]
The continuous decision problem asks whether this minimum is at most a rational threshold \(K\). Each infinitesimal agent still receives an integral, \(\Gamma\)-consistent ballot; only the amount of population receiving each ballot is divisible. Thus this is continuization of the population, not of the outcome space.
The regime is a large liquid-democracy platform with many recurring cohorts: for example, members of many local chapters or departments who share the same issue positions and delegate each issue to the same small set of trusted proxy roles. There may be millions of agents but only \(\tau\) distinct ballot-and-delegation types, with \(n\gg\tau\). A type is complete in the paper’s sense: it includes every direct vote and every delegation choice relevant to consistency. Repeated agents are genuinely interchangeable, rather than merely being assigned the same preference while retaining idiosyncratic delegation behaviour.
This is recognisably the authors’ problem. It preserves binary multi-issue ballots, transitive delegations, acyclicity, the canonical profile, immutable direct votes, the consistency constraint, and the exact objective of changing as few delegated votes as possible. A finite profile with \(n_\theta\) agents of type \(\theta\) embeds as \(\mu_\theta=n_\theta/n\). Conversely, any rational mass solution can be expanded into a sufficiently large finite population. The continuous formulation is therefore a high-multiplicity version, not a new manipulation problem attached to the paper.
The hardness transfers. Given the paper’s INDEPENDENT SET instance \(G=(V,E)\), create one issue \(I_v\) for each \(v\in V\), a type \(\theta_A\) that delegates every issue to the corresponding direct-voting type \(\theta_v\), and types \(\theta_v\) that approve only \(I_v\). Let \(\Gamma\) require the approved issues to form an independent set. Give \(\theta_A\) mass \(1/2\), and distribute the remaining mass among the \(\theta_v\). The canonical vote of \(\theta_A\) is all ones. Changing it to a feasible vote costs
\[ \frac12\bigl(|V|-|S|\bigr) \]
when \(S\) is the selected independent set. Consequently, the continuous optimum is at most \((|V|-t)/2\) exactly when \(G\) has an independent set of size at least \(t\). The mass relaxation does not remove the combinatorics: the hardness lives in the issue agenda and the geometry of \(\Gamma\), not in the number of named voters. I would therefore expect \(\mathrm{CMVC}_\infty\) to be NP-hard, and likely NP-complete under the paper’s representation assumptions. This is a Class B mirror.
The main further questions are whether particular constraint families make the continuous problem tractable; whether the distance-to-\(\Gamma\) problem admits configuration-LP or separation algorithms; how exact continuous solutions round to finite high-multiplicity electorates; and what happens when delegations target named individuals rather than interchangeable proxy types. One could also formulate continuous versions of PDC and PVC, weighted by population mass, but those would be secondary questions rather than the anchor here.
The weakest point is that Proposition 2’s own reduction has roughly one type per graph vertex, so it does not demonstrate hardness arising from high population multiplicity: in that construction \(\tau\) grows with the number of agents. Replicating every type \(R\) times creates an honest regime with \(n\gg\tau\), but replication itself does not generate the hardness. That limits the claim to a faithful, meaningful Class B mirror rather than evidence that continuization makes this particular problem easier. The mirror nevertheless survives that objection: the paper’s central optimization problem remains intact, its finite instances embed exactly, and the continuous population model identifies precisely why its discrete hardness persists.
The strongest case against the proposed mirror is structural, not complexity-theoretic. Proposition 2 is a genuine computational result, and its reduction transfers correctly. The problem is that the proposed continuous version does not actually couple the population.
For a type \(\theta\), let \(\widehat b_\theta\) be its direct votes, \(g_\theta\) its canonical vote, and
\[ F_\theta=\{x\in\Gamma:\widehat b_\theta\subseteq x\}. \]
The proposed programme solves
\[ \min_q \sum_{\theta,x}\mu_\theta q_{\theta,x} \left|\{j:x_j\neq g_{\theta j}\}\right| \]
subject only to
\[ \sum_{x\in F_\theta}q_{\theta,x}=\mu_\theta \]
for each \(\theta\). Hence it factorises exactly:
\[ \min_q=\sum_\theta \mu_\theta \min_{x\in F_\theta} \left|\{j:x_j\neq g_{\theta j}\}\right|. \]
There is no transfer between types, no shared capacity, no aggregate consistency condition, and no social interaction left after the canonical votes have been computed. The mass vector merely supplies weights for independent individual repair problems. Because the objective is linear, splitting a type across several final ballots offers no benefit: an optimum can assign all of that type’s mass to one minimising ballot.
This makes the apparent continuum ornamental. In the paper’s own reduction, all the real combinatorics sit in the single agent \(A\)’s distance from \(\Gamma_{\mathrm{IND}}\); the remaining voters merely witness the canonical votes. Giving \(A\) mass \(1/2\), or \(0.9\), or \(1/n\), does not create a population-level problem. It just rescales the same one-agent constraint-repair instance. That is not an objection that the answer remains hard; it is an objection that the proposed object has ceased to be a liquid-democracy problem about a society. It is a weighted batch of independent ballot-repair problems.
The named-delegate difficulty does not rescue it. If delegation targets remain named individuals, a continuum over types loses the identity of the proxy—especially when one measure-zero proxy influences a positive mass of followers. If targets are instead replaced by interchangeable proxy roles, the model becomes well-defined, but the role has been compiled into \(g_\theta\), after which delegation has no operative effect. Enforcing a genuinely shared proxy state, proxy capacity, or the requirement that followers inherit the proxy’s changed vote would restore interaction, but that changes MVC into a different rule, closer to delegation deletion or a new coupled optimisation problem.
The negative case is therefore that no faithful continuization of Proposition 2 is both genuinely population-level and still the paper’s problem: preserving MVC yields a separable weighted CSP, while preserving liquid-democracy identity and shared delegation semantics requires changing the feasible set or objective.
This case is not airtight. A platform with institutional proxy roles and a policy goal of minimising the fraction of citizens whose delegated votes are overridden is a plausible high-multiplicity setting, and the resulting weighted repair problem is formally legitimate. Thus I would not honestly claim that Proposition 2 has no continuous mirror whatsoever. The strongest defensible negative claim is narrower: it has no worthwhile *population-coupled* mirror without adding modelling features absent from the theorem being mirrored.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.