| paper | The Cost Perspective of Liquid Democracy: Feasibility and Control |
| authors | Shiri Alouf-Heffetz, Łukasz Janeczko, Grzegorz Lisowski, Georgios Papasotiropoulos |
| venue | AAAI 2025 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.8
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\), voting and delegating costs \(v_t\) and \(d_t\), an approved type relation \(A\), a per-capita budget \(b\), and \(L=4\), decide whether a complete type-role blow-up admits a measurable delegation policy that partitions each type mass into casting and noncasting mass, assigns exactly one approved outgoing edge to every noncasting voter, routes every delegation along an edge-respecting path ending at casting mass, gives each type-\(u\) casting mass total represented mass at most \(L\) times its casting mass, and has total normalized cost \(\sum_t[v_t a_t + d_t(\mu_t-a_t)]\) at most \(b\).
A complete type-role blow-up with type masses, approved type edges, casting mass, edge- and path-consistent aggregate delegation flow, per-casting-mass power capacity L=4, and normalized voting/delegation cost.
The stated LP pools representative capacity by type and permits incompatible paths, so it does not by itself establish equivalence to individual delegation functions; role-level symmetry may also weaken the paper's concern with concentration in named voters.
fatal: False
The mirror covers BOUNDED POWER and Theorem 3.8; it leaves DELEGATE REACHABILITY, the bounded-length and bounded-sum-length results, the Delta less than or equal to 1 algorithms, and all strategic-control results untouched.
The strongest honest mirror is a continuous, high-multiplicity version of the paper’s BOUNDED POWER problem. I would anchor it on Theorem 3.8, proved in this paper: for every fixed \(\ell\ge4\), BOUNDED POWER is NP-complete when the delegation graph has maximum out-degree \(\Delta>1\). The nearby positive result, Theorem 3.7, is a useful consistency check: the paper already finds polynomial solvability when \(\Delta\le1\), but it is not a separate anchor here.
Consider a large membership organisation, union, or digital democracy platform with millions of members but only a few hundred recurring role profiles. A role might specify local chapter, issue expertise, participation burden, and the classes of representatives trusted by members in that role. All members of a role have the same voting cost \(v_t\), delegating cost \(d_t\), and approved representative-role set. Thus a type is a complete delegation profile, not merely a preference or a price.
Let \(T\) be the finite set of types, \(\mu_t\) the fraction of the population of type \(t\), and \(A\subseteq T\times T\) the approved type-level delegation relation. An edge \((t,u)\) means that any member of type \(t\) may delegate to a member of type \(u\). This is the block-structured high-multiplicity regime: the individual population is large, while the number of distinct trust-and-cost types is much smaller.
I would call the resulting problem Power-Capped Delegation\(_\infty\). Fix \(L=4\), matching the smallest value in Theorem 3.8. An instance consists of rational type masses \(\mu_t\), the relation \(A\), rational costs \(v_t,d_t\), and a rational per-capita budget \(b\). The decision variable is:
Every unit of \(z_{tu}\) must have an approved directed path from \(t\) to \(u\). If \(R^+(t)\) denotes the types reachable from \(t\) by a positive-length path, the mass constraints are
\[ a_t+\sum_{u\in R^+(t)}z_{tu}=\mu_t. \]
Let
\[ r_u=a_u+\sum_t z_{tu} \]
be the total mass represented by casting voters of type \(u\), including their own casting mass. The continuous power constraint is
\[ r_u\le L a_u \]
for every \(u\). This is the correct normalization of the paper’s individual power bound. In an \(n\)-voter expansion, \(na_u\) identical type-\(u\) voters cast and \(nr_u\) voters are represented by them. The represented mass can be distributed among the \(na_u\) casting voters, so every one has power at most \(L\) exactly when \(nr_u\le L(na_u)\).
The objective is the normalized version of the paper’s cost:
\[ \min \sum_t\bigl(v_ta_t+d_t(\mu_t-a_t)\bigr), \]
and the decision question is whether this value is at most \(b\), while all mass is represented and the power bound holds. Each individual still delegates along one path; the splitting occurs only in the aggregate because many identical individuals may make different choices.
This continuous problem is polynomial-time solvable. Compute the transitive closure of \(A\), introduce the \(a_t\) and \(z_{tu}\) variables, and solve the resulting linear program. There are only polynomially many variables and constraints in \(|T|\) and the input encoding length. Equivalently, one can use pair-indexed flow variables rather than precomputing reachability.
This is precisely the kind of population continuization the programme is meant to study. The trust graph remains present, transitivity remains present, costs remain present, the budget remains present, and concentration of voting power remains the central feasibility requirement. What disappears is the indivisibility of choosing particular voters as representatives. In the reduction behind Theorem 3.8, choosing \(k\) vertex voters becomes choosing casting mass across vertex types, while edge mass may be split between its two endpoint types. The vertex-cover gadget therefore becomes a fractional, LP-solvable covering structure. The graph combinatorics have not been erased; they have become linear constraints.
I would therefore expect this mirror to be Class A: tractable by continuous optimization, despite the discrete problem being NP-complete for \(\Delta>1\). It also gives a natural two-way high-multiplicity dictionary. A finite election with \(n_t\) copies of each type has \(\mu_t=n_t/n\), and a continuous solution can be rounded to a large finite instance, with the usual small discretization effects. Conversely, repeated role-based populations in the organisation above naturally produce the continuous instance.
The authors should recognise this as their problem rather than as a generic fractional relaxation. It preserves exactly the objects they study: selecting casting voters, paying voting or delegating costs, satisfying transitive reachability, and preventing excessive voting power. It also fits scenarios the paper itself names—large sensor networks, vehicle fleets, blockchain communities, and representative organisations—better than a seven-person committee does.
The mirror generates several follow-up questions. What rounding guarantee can be proved for \(n\)-voter expansions? Does adding a fixed path-length bound lead to a layered LP, and does a variable path bound introduce a genuine pricing problem? What happens when delegation costs depend on both the source and target types? Finally, can adding or deleting a positive mass of voters give continuous counterparts of the paper’s control problems, especially the universal quantifier over every cost-minimizing delegation?
The weakest point is that this is a block-symmetric version of the paper’s graph model. If every voter has an idiosyncratic list of trusted individuals, there is no persuasive finite type system, and the mirror would not apply. Moreover, the continuous power condition treats equivalent casting voters as divisible capacity, whereas the paper speaks about the power of named individuals. That is a real modelling choice. But it is exactly the choice justified by a large population of genuinely interchangeable members, and it keeps the paper’s substantive question intact. I would not claim that the whole paper has been continuized; I would claim, more narrowly and defensibly, that Theorem 3.8 has a natural population-level mirror whose discrete hardness is plausibly caused by indivisible population mass and disappears into a polynomial LP.
The strongest objection is that the proposed LP is not actually a continuization of Theorem 3.8’s problem. It silently replaces named representatives and a functional delegation graph with anonymous representative capacity.
In the paper, a solution chooses a set \(C\) of particular voters and exactly one outgoing edge for every non-casting voter. Voting power is attached to each named caster. The proponent’s \(z_{tu}\) variables do something different: they send source mass independently to a target type through the transitive closure of \(A\), while \(r_u\le L a_u\) pools all type-\(u\) representatives into divisible capacity. It does not ensure that all those paths can coexist in one delegation function.
For example, if \(A\) contains \(A\to B\to C\), the proposed LP may send \(A\)-mass to \(C\) while designating all \(B\)-mass as casting. But in the paper, a casting \(B\)-voter has no outgoing delegation edge, so an \(A\)-voter delegating to \(B\) stops at \(B\); the path to \(C\) is unavailable. Repairing this requires variables describing a common delegation policy, including which submass of each type delegates and which edges those individuals use. That is not the stated transitive-closure LP.
More fundamentally, the proposed model faces a dilemma. If types preserve the paper’s interpersonal trust structure, then a type must encode an individual’s exact approved representatives or exact trust neighbourhood. In the hard instances behind Theorem 3.8, those neighbourhoods are largely different: edge voters approve different endpoint pairs, and vertex voters have different dummy connections. The number of types then grows with the number of named voters, and the masses are merely replicated atoms. There is no meaningful population compression.
If, instead, a type approves whole representative roles, then every member of a target role becomes interchangeable. Delegation mass can be balanced freely among them, and the resulting finite elections are complete blow-ups of a role graph rather than high-multiplicity versions of the paper’s arbitrary delegation graphs. That may define a useful new problem—anonymous representative-capacity allocation—but it changes what “trust,” “casting voter,” and “voting power” mean. The paper’s democratic concern is concentration in particular people; the role model replaces that with concentration in divisible role capacity.
A richer graphon-style mirror does not solve the dilemma. If it retains the individual trust relation, its computational input must describe essentially the same identity-bearing graph, so the population continuum supplies little simplification. If it has a finite succinct description, it is again a role abstraction whose semantics differ from the paper’s.
This is the best negative case, but it is not enough for the universal conclusion. The paper has a genuine named computational result, and a large organisation with institutionalised representative roles is a plausible high-multiplicity setting. The proposed LP is technically and semantically too loose as written, but I cannot honestly claim that no worthwhile continuous mirror exists. The strongest defensible verdict is rejection of this particular formulation—not rejection of the BOUNDED POWER anchor altogether.
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.