| paper | The Fluid Mechanics of Liquid Democracy |
| authors | Paul Gölz, Anson Kahng, Simon Mackenzie, Ariel D. Procaccia |
| venue | WINE 2018 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time exactly solvable; consequently a polynomial-time \(\tfrac12\log_2 k\)-approximation exists. A conservative exact running time is \(O(\tau(m+\tau)^2L^3)\) bit operations. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite type set \(T=D\dot\cup V\), rational distribution \(\mu\), and at most two permitted target types \(R(t)\) for each \(t\in D\), choose a measurable acyclic resolution in which every infinitesimal delegator selects one concrete delegate from a permitted target type, retain maximum reachable mass, and minimize \(z=\max_{v\in V:\mu_v>0} w_v/\mu_v\), where \(w_v\) is the total mass ultimately voting through voter type \(v\).
A role-based high-multiplicity liquid-democracy model with complete types \(T=D\dot\cup V\), atomless mass \(\mu\), trusted delegate pools \(R\), and one concrete delegate per individual. Aggregate flows \(f_{tu}\) route mass between types, voter-pool load is \(w_v\), and the objective is \(\min\max_v w_v/\mu_v\) subject to acyclic support and maximum active mass.
Theorem 5's reduction uses named downstream identities and vertex-disjoint paths; replacing them by interchangeable target pools and averaging \(w_v/\mu_v\) may remove the correlation that makes the hardness result true.
fatal: False
The mirror covers the computational optimization and hardness results centered on Theorem 5 and the confluence-flow formulation, while leaving Theorems 7–9, the empirical simulations, and most probabilistic analysis unmirrored.
The strongest honest case is a high-multiplicity, pool-based version of their delegation problem. I would make this a one-anchor case, led by Theorem 5.
The paper’s lead anchor is Theorem 5, proved in the paper itself. It states that it is NP-hard to approximate MinMaxWeight within a factor of \( \frac{1}{2}\log_2 |V| \), even when every node has outdegree at most \(2\). MinMaxWeight takes a directed potential-delegation graph, with voter sinks \(V\); one chooses an acyclic delegation subgraph, using as many nodes as possible, with exactly one outgoing delegation for every used non-voter, and then minimizes the maximum recursively accumulated weight of a voter. The proof is an approximation-preserving reduction from their Lemma 6, which adapts the confluence-flow hardness of Chen et al.; the theorem itself is not merely cited.
My continuous problem would be called Fluid-MinMaxWeight. An instance consists of a finite set of complete agent types \(T\), partitioned into delegator types \(D\) and direct-voter types \(V\); a directed relation \(R\subseteq D\times T\) of permissible delegation-pool choices; and a rational population distribution \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_{t\in T}\mu_t=1\). Each type includes everything the problem uses: whether its agents vote directly, which delegate pools they trust, and any other relevant restriction. We can impose \(|R(t)|\le 2\) to mirror the theorem’s bounded-outdegree regime.
The society contains an atomless mass \(\mu_t\) of agents of type \(t\). Every infinitesimal delegator chooses exactly one concrete representative from one permitted target type; no individual splits her vote. Agents of the same type may, however, choose different permitted delegates. Thus a type can be partitioned into measurable subpopulations making different choices.
After transitive delegation, let \(f_{tu}\) be the total voting mass travelling from type \(t\) to type \(u\). For every active delegator type \(t\), flow conservation is
\( \sum_{u:(t,u)\in R} f_{tu}=\mu_t+\sum_{s:(s,t)\in R}f_{st}. \)
For a voter type \(v\), its total received mass is
\( w_v=\mu_v+\sum_{s:(s,v)\in R}f_{sv}. \)
Because \(\mu_v\) direct voters share this load, the analogue of the paper’s maximum individual voter weight is the maximum load density \(w_v/\mu_v\). The continuous question is therefore: among resolutions using the maximum possible active population mass, minimize
\( z=\max_{v\in V} \frac{w_v}{\mu_v}. \)
A solution is a measurable one-delegate resolution, or equivalently its aggregate rational flow \(f\) together with the value \(z\). Types with no path to a voter are discarded in the first, maximum-utilization phase, exactly as the paper discards inactive nodes.
This is a credible high-multiplicity regime for a large party, union, professional association, or online cooperative with \(10^5\)–\(10^7\) members but perhaps \(50\)–\(500\) recurring participation and trust types. For example, many members may share the same role, expertise, voting status, and two trusted delegate pools. The relevant comparison is \(n\gg\tau\), with \(\tau=|T|\) fixed or moderate while every type contains many agents. Members with genuinely idiosyncratic delegation options would be separate types; the model is not pretending that arbitrary named relationships disappear.
The authors should recognize this as their problem because the object being optimized is unchanged: potential delegation, one representative per delegator, transitive accumulation, voter congestion, and minimization of the heaviest voter. What changes is the population regime. The normalization by \(\mu_v\) is forced by continuity: \(w_v\) is total mass assigned to a voter pool, while \(w_v/\mu_v\) is the average weight carried by one direct voter. This is a population modification, not continuity in the outcome space.
I expect Fluid-MinMaxWeight to be Class A. Its formulation is a finite linear program with variables \(f_{tu}\), \(w_v\), and \(z\), solvable exactly in time polynomial in \(|T|\), \(|R|\), and the encoding length of \(\mu\). The discrete hardness in Theorem 5 comes from the all-or-nothing choice at each named node. In the atomless regime, a fraction of a repeated type can choose one option and the remainder another, while every individual still chooses exactly one delegate. Thus the integral congestion obstruction can disappear without giving any individual a split vote.
This also gives the required high-multiplicity bridge. A rational distribution \(\mu_t=n_t/n\) is the normalized version of a finite society with \(n_t\) agents of type \(t\). Conversely, a rational LP solution can be implemented by sufficiently many repeated agents, or rounded with additive error vanishing as multiplicity grows. The question is therefore not merely “can splittable flow solve their MILP?” It asks whether their individually con fluent delegation problem becomes a fluid flow problem when the population consists of many interchangeable agents.
The further questions are substantial: whether every feasible type-level flow has a measurable realization by one-delegate forests; whether named atomic representatives restore Theorem 5’s hardness; whether capacities or type-specific accountability constraints create continuum-specific hardness; and whether the paper’s Theorems 7 and 9 admit a mean-field analogue for concentration under random delegation. I would not use those probabilistic theorems as additional anchors: they are useful follow-on questions, but Theorem 5 is the paper’s clear computational anchor.
The weakest point is that this mirror can look too close to the paper’s explicitly discussed splittable-flow variant. If the authors regard accountability as requiring delegation to a named individual and reject delegation to a type pool, then the aggregate LP may be judged a different problem. The defence is that no individual is splitting: the split occurs across a continuum of otherwise identical agents. But if that distinction is not accepted, this mirror fails. Subject to accepting that standard high-multiplicity interpretation, however, it is a precise and natural continuous analogue, and Theorem 5 supplies a meaningful hardness boundary that the continuum may genuinely dissolve.
The proponent raised only Theorem 5, so the case against has to attack that anchor. The strongest objection is that its hardness is about an individualized trust graph, not about a population with repeated agent types. The reduction uses vertex-disjoint paths: whether two delegations can share a vertex depends on the identity and downstream position of that vertex. Those positions are part of what an agent is for purposes of this problem.
If types retain the paper’s actual semantics, an agent whose options are \(b_i,c_i\) is not interchangeable with one whose options are \(b_j,c_j\), because those targets have different incoming paths and loads. Encoding the relevant target identities and downstream graph therefore makes the types essentially graph positions. Duplicating such positions does not produce the proponent’s finite type model unless the duplicates are allowed to delegate to one another interchangeably.
That is exactly where the proposed rescue changes the problem. Once every member of type \(A\) may choose any representative in target type \(B\), the aggregate variable \(f_{AB}\) allows the mass of one type to use several outgoing edges. No individual splits her vote, but the type-level object has lost the correlation between a concrete agent’s incoming delegation mass and her own outgoing choice. The vertex-disjoint-path obstruction behind Theorem 5 has been replaced by splittable, pool-based flow. The normalization \(w_v/\mu_v\) makes the change sharper: it assumes that incoming mass can be perfectly balanced across all members of voter type \(v\), whereas the paper minimizes the load of an actual named voter.
There is a faithful-looking alternative, but it does not solve the problem. Preserve named trust relations by giving each repeated copy an identity coordinate and allowing only the corresponding concrete targets. Then the coordinate is information used by the problem, so the population is no longer represented by a fixed finite distribution over types. One has a continuum-indexed network or graphon-style confluence problem, not the paper’s high-multiplicity type model. If the coordinate is discarded, one gets the pool variant above; if it is retained, multiplicity has not erased the identities that drive the theorem.
There is also a technical gap in the proposed LP: its conservation equations permit circulation around type cycles, while a delegation resolution must be a well-founded one-delegate structure. This can probably be repaired by cycle elimination or an ordering constraint, so it is not the main objection. The main issue is that the LP is not equivalent to the paper’s confluence constraint unless one accepts the pool/splittable reinterpretation.
This is a real negative case under the paper’s own named-delegation and accountability semantics. It is not an objection that the continuous answer might be easier; the objection is that the only finite-type construction changes the object whose hardness Theorem 5 proves. But the universal claim is not airtight. A large organization in which agents genuinely trust role-based delegate pools is a plausible high-multiplicity regime, and the authors might reasonably recognize the resulting fluid problem as their own splittable variant. If they do, the proponent has a legitimate mirror. So the strongest honest conclusion is that the negative case can reject the proposed mirror as faithful to the theorem, but cannot establish that no worthwhile continuous mirror exists in any scenario.
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.