| paper | Pairwise Liquid Democracy |
| authors | Markus Brill, Nimrod Talmon |
| venue | IJCAI 2018 |
| filed under | voting · rationalization |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given alternatives \(A\), finite role types \(T\), rational masses \(\mu_t\) summing to \(1\), and a type-level delegation map \(\delta(t,\{a,b\})\), delete external rules \(D\) at cost \(\sum_{(t,\{a,b\})\in D}\mu_t\), and decide whether the remaining role graph admits complete transitive rankings \(R_t\) respecting every internal comparison and every surviving equality \(R_t|_{\{a,b\}}=R_{\delta(t,\{a,b\})}|_{\{a,b\}}\), within budget \(B\).
A finite role graph whose vertices are voter types, each carrying internal pairwise preferences and type-to-type delegation rules; \(\mu_t\) is the mass of each role, and deleting a shared rule edits all members of that role at cost \(\mu_t\). Feasibility is a family of complete transitive rankings, with objective equal to the minimum mass of edited role rules.
The exact semantics of copies delegating to a role rather than to a named voter is not formalised, so the mirror's faithfulness depends on accepting shared role policies as part of the liquid-democracy instance.
fatal: False
It covers Theorem 2's consistency decision and both variants of Theorem 3's consistency modification; it leaves LiquidKemeny, liquid distance rationalisation, and the proposed liquid voting rules without a named computational theorem to mirror.
The strongest positive case is a mirror of the paper’s consistency-modification problem, with Theorem 3 as the lead anchor and Theorem 2 as a second, independent anchor. Both are computational results proved in this paper, not merely cited.
The natural regime is a large organisation or online liquid-democracy platform with recurring role types. A type \(t\) records, for every pair \(ab\) of alternatives, either an internal comparison \(a\succ b\), or a delegation of \(ab\) to another role type \(\delta_t(ab)\). It therefore includes the complete information relevant to this paper: preferences, delegated pairs, and delegate identities at the role level. A society is a rational distribution \(\mu\) over finitely many such types. Thus \(\mu_t\) is the fraction of members in role \(t\), with \(N=M\tau\) agents when each of the \(\tau\) types has \(M\gg 1\) interchangeable members.
This is plausible for, say, a party or association with many members occupying repeated expertise or organisational roles. A member may decide some comparisons personally but delegate others to the “environmental-policy role” or “local-budget role”. Since the consistency question only uses the delegate’s pairwise decision and outgoing delegation pattern, individual identity can be replaced by the relevant role type.
My lead problem is Mass-Weighted Type-Level Consistency Modification\(_\infty\). An instance consists of alternatives \(A\), a finite type set \(\mathcal T\), rational masses \(\mu_t\), the type-level delegation graph, and a rational budget \(B\). The decision variable is a set \(D\) of external delegation rules to remove. Removing \((t,ab)\) means changing the shared delegation policy of the entire mass \(\mu_t\) of type \(t\); its cost is \(\mu_t\). The objective is
\[ \min_{D}\ \sum_{(t,ab)\in D}\mu_t \]
subject to the remaining type-level delegation graph being consistent, namely admitting a complete and transitive extension respecting all remaining delegations. The decision version asks whether the optimum is at most \(B\). Replacing “consistent” by “weakly consistent” gives the parallel weak version.
This is a genuine population mirror rather than an outcome-space relaxation: the only continuous object is the population, while delegation rules and rankings remain discrete. The type-level edit is also natural when the intervention is a policy change applied to an entire role, rather than independently editing millions of identical individuals.
The anchor is Theorem 3, proved in this paper: “The consistency modification problem is NP-complete, both for weak consistency and for consistency.” The paper’s problem is: given a pairwise delegation graph \(G\) and an integer \(b\), can at most \(b\) arcs be removed to make \(G\) weakly consistent, or to make \(G\) consistent? The proof reduces Feedback Arc Set on Tournaments. For each tournament edge \(e=(x,y)\), the construction creates a voter \(v_e\) who internally prefers \(x\) to \(y\), and a voter \(v^\ast\) who delegates the pair \(xy\) to \(v_e\). The resulting preferences of \(v^\ast\) encode the tournament. Removing delegation arcs to make the graph consistent is therefore equivalent to removing tournament edges to make the tournament acyclic.
The hardness transfers directly. Given a finite graph with \(n\) voters, create one type per voter, set \(\mu_t=1/n\), and use budget \(B=b/n\). Then deleting a set of type-level rules of mass at most \(B\) is equivalent to deleting at most \(b\) original arcs. The same construction can be populated by arbitrarily many copies of every type, so the hardness is not caused by the raw number of named voters. It is driven by the alternatives and the delegation structure. I therefore expect this mirror to be Class B: NP-hardness survives continuization.
The second problem is Continuum Pairwise-Delegation Consistency\(_\infty\). Its input is \(A\), \(\mathcal T\), \(\mu\), and the type-level delegation graph. Its decision variables are complete transitive rankings \(R_t\), one for every positive-mass type. They must agree with every internal comparison and satisfy
\[ R_t|ab=R_{\delta_t(ab)}|ab \]
for every delegated pair. The question is whether such a family of rankings exists. A solution is the family \((R_t)_{t\in\mathcal T}\); the objective is feasibility.
The anchor is Theorem 2, also proved here: “Deciding whether a given pairwise delegation graph is consistent is NP-complete.” Consistency means precisely that there exists a complete and transitive \(G\)-respecting extension of \(R(G)\). The paper proves NP-hardness by reducing from 3SAT. Variable voters decide pairs \(t_i f_i\), clause voters delegate those pairs to the relevant variable voters, and carefully chosen internal comparisons make a clause voter intransitive exactly when the corresponding clause is falsified. Thus a consistent extension exists exactly when the 3CNF formula is satisfiable.
The same reduction becomes a continuous-population instance by assigning positive rational mass to every variable and clause type. Hence this mirror is also expected to be Class B. The mass vector is deliberately irrelevant to this particular feasibility property: duplicating identical agents should not change whether their common delegation policy admits a coherent ranking. That is not a defect of the mirror; it is the correct high-multiplicity behaviour of a qualitative consistency question.
The scope is intentionally narrow. These mirrors cover the paper’s two named computational results: consistency detection and consistency modification. I would not claim a computational mirror for LiquidKemeny, liquid distance rationalization, or the proposed liquid voting rules, because the paper gives definitions and examples for them but no named complexity or algorithmic theorem.
The weakest point is the treatment of delegation targets and edits at the role level. The original paper speaks about arcs between named voters, whereas the mirror assumes that members of a role can delegate to an interchangeable representative of another role, and that an edit changes the role’s shared policy. If the authors insist that individual target identity is essential, this mirror becomes less faithful. A finer variant would allow a fraction of a type’s mass to delete an arc independently; that is an interesting further problem, but its complexity could differ substantially, perhaps becoming tractable through fractionalisation or becoming hard for continuum-specific reasons. The type-level policy version is nevertheless a credible continuous analogue of the problems actually proved in the paper, and its hardness survives for exactly the reason the programme predicts: the reduction’s combinatorics live in the alternatives and delegation constraints, not in population multiplicity.
The positive case has one serious vulnerability: it silently replaces a voter-to-voter delegation graph by a role-to-role graph. That is not an innocuous population aggregation. In the paper, delegation is a relation between particular vertices, and consistency depends on following labelled paths through that graph.
There are only three ways to continuize this relation.
First, one can quotient voters into finitely many behavioural types. Then delegation becomes a map \(\delta:T\times P\to T\cup\{\bot\}\). Theorem 2’s consistency question is now determined entirely by \((A,T,\delta)\); the mass vector \(\mu\) can be deleted without changing the answer. This is not because the continuous answer is uninteresting, but because there is no population-level object left in the question: it is a finite labelled role graph with a redundant measure attached.
Second, one can preserve delegation to named individuals. Then the delegate target, and recursively the target’s outgoing delegations, are part of the agent’s relevant description. In a generic graph, different vertices therefore have different types. Cloning the graph produces more copies of the same network position, but does not produce a society whose behaviour is determined by a distribution over voter types. An atomless version is worse: a deterministic delegate is a measure-zero point, so an almost-everywhere consistency notion either ignores precisely the exceptional cycles that drive Theorem 2 or must retain pointwise identities, defeating the continuum.
Third, one can let a mass of agents delegate to a type or distribute delegation across types. But the paper has no semantics for this. A delegate supplies one pairwise comparison, not an average comparison. Choosing majority, expectation, or universal agreement introduces a new aggregation model rather than continuizing pairwise liquid democracy.
This defeats the proposed Theorem 2 mirror. The family \((R_t)_{t\in T}\) is a coherent problem on a role graph, but its feasibility is support-invariant: changing a positive type’s mass from \(10^{-6}\) to \(0.9\) changes nothing. Calling the roles “types” does not make the consistency property population-continuous. If one instead asks for the mass of inconsistent voters, or permits almost-everywhere consistency, one has changed the decision problem that Theorem 2 proves NP-complete.
Theorem 3 is a stronger anchor, because a mass-weighted intervention is at least conceivable. But the proposed objective is not the high-multiplicity version of deleting arcs from the paper’s graph. It is a new intervention in which an entire role’s delegation policy is rewritten at once. That may be sensible for an organisation governed by shared role policies, but it is not implied by pairwise liquid democracy, where a delegation arc belongs to an individual voter.
The literal high-multiplicity version has an awkward dichotomy. If individual arcs may be removed independently, removing an arc from one member splits that member off into a new type; consistency of the remaining copies is unchanged until an entire problematic role-policy mass is removed. If edits must preserve type homogeneity, then the decision is a discrete weighted graph-edit problem on role types, with \(\mu\) merely supplying edge weights. Fractional edits have no meaning unless one again introduces a new rule for how a partially edited delegation population yields a single preference relation.
Thus both anchors face the same structural obstruction: the paper’s computational content lies in identity-sensitive network topology, not in the aggregate distribution of voters. A finite role quotient discards that topology; retaining it prevents genuine high multiplicity; aggregating it changes the model.
I would not claim that this is an airtight universal negative. A genuinely role-governed organisation could make the weighted Theorem 3 variant a defensible new problem. But that is the one surviving scenario, and its value comes from adding collective role policies, not from continuizing the society in the sense of the programme. The proponent has therefore established a plausible weighted role-network problem, but not yet a compelling continuous-population mirror of this paper.
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.