| paper | Unravelling Expressive Delegations: Complexity and Normative Analysis |
| authors | — |
| venue | AAAI 2024 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 11
statement extracted from the paper’s text layer
Given finitely many role types with rational masses, binary roots 0 and 1, and ranked delegation options between role nodes or canonical delegate offices, choose one option per role so the selected role graph is an arborescence, minimize the mass-weighted rank sum, and subject to optimality maximize the mass whose resolved vote is 1.
A finite weighted role-level delegation graph: masses weight each role's delegation rank and resolved vote, while selected edges determine acyclic delegation paths to binary roots; the objective is lexicographic minimum-cost arborescence followed by maximum mass voting 1.
The mirror is valid only under an explicit structured wiring or canonical-office restriction, since masses and role ballots alone do not preserve arbitrary individual identity-sensitive cycles.
fatal: False
The mirror covers high-multiplicity classic MINSUM and MINMAX unravelling with target-favouring tie-breaking; it leaves the general identity-wired model, expressive Boolean-function dichotomy, and normative axioms largely untouched.
The strongest honest positive case is a high-multiplicity, role-based version of the paper’s classic liquid-democracy model. I would lead with Theorem 11, and use Theorem 9 as a second, closely related anchor. Theorem 7 gives a broader but weaker third mirror.
Take a platform with millions of voters but only a few dozen or few hundred recurring delegation roles: “members of local union branch A,” “employees in department B,” “supporters of councillor C,” and so on. A type contains the complete ranked ballot of its members, including their ordered delegation targets and direct fallback vote. Its mass is the fraction \(\mu_t\) of the population with that ballot. Delegate targets may be other massed roles or small canonical delegate offices. Thus \(N\) may be \(10^6\) while \(\tau\) is, say, \(50\)–\(500\).
The continuous object is not a fractional outcome: the issue still has the binary alternatives \(0\) and \(1\). What becomes continuous is the population weight. A type-level certificate chooses one entry from every ranked ballot, and is valid when the selected delegation edges form an arborescence reaching \(0\) or \(1\), exactly as in the paper. If \(v_A(t)\) is the resulting vote of type \(t\), then the population share voting for \(1\) is
\[ V_1(A)=\sum_t \mu_t\,\mathbf 1[v_A(t)=1]. \]
For a finite realization with \(N\mu_t\) copies of each type, this is exactly the normalized number of voters voting \(1\). Likewise, the paper’s rank sum becomes the mass-weighted rank sum
\[ C_{\mathrm{sum}}(A)=\sum_t \mu_t\,\mathrm{rank}_A(t), \]
and MINMAX becomes the largest rank used by any positive-mass type. If a platform permits different cohorts of the same type to use different tied certificates, one can distribute their mass over certificates; this is the natural high-multiplicity refinement, although a deterministic certificate suffices for the linear objectives below.
My lead anchor is Theorem 11, proved in this paper. It states that, in the classic model, one can compute in polynomial time a minimum-cost arborescence in which every agent who votes \(1\) in some minimum-cost arborescence votes \(1\). The theorem uses Fulkerson’s tight-edge characterization; Fulkerson’s algorithm is cited, but the stated result and its application are proved here.
The corresponding continuous problem is:
Mass-MINSUM-1. Given a finite role set \(T\), rational masses \(\mu_t\), ranked delegation ballots, roots \(0,1\), and a target alternative \(1\), output a valid certificate \(A\) minimizing \(C_{\mathrm{sum}}(A)\), and subject to that, maximizing \(V_1(A)\). Equivalently, decide whether there is a minimum-mass-cost certificate with \(V_1(A)\ge q\), for a given rational threshold \(q\).
This is recognisably the same question: choose the cheapest consistent unravelling, then use the authority’s permitted tie-breaking power to favor the status quo or another target. The expected classification is Class A. The weighted problem should reduce to minimum-cost arborescence with rational edge cost \(\mu_t i\), followed by reachability in the tight-edge graph. The expected running time is polynomial in \(\tau\), the number of role-level delegation edges, and the encoding length of the masses.
This mirror also generates useful follow-up questions: characterize the full interval of achievable \(V_1\) values among optimal certificates; study winner robustness under adversarial rather than favorable tie-breaking; and determine whether arbitrary rational mass vectors preserve the paper’s strongest near-linear bounds or only polynomial solvability.
The second anchor is Theorem 9, also proved in this paper. It gives the analogous result for MINMAX: from the set \(N_1\) of agents voting \(1\) in some minimum-bottleneck arborescence, the authors construct in \(O(n+m)\) time a minimum-bottleneck arborescence in which all agents in \(N_1\) vote \(1\).
The continuous problem is:
Mass-MINMAX-1. Given the same type-level instance, minimize
\[ C_{\max}(A)=\max\{\mathrm{rank}_A(t):\mu_t>0\}, \]
and among all minimizers maximize \(V_1(A)\). Output the certificate and its resulting population share for alternative \(1\).
Here the mass interpretation is particularly natural: MINMAX asks for the smallest worst delegation rank affecting any non-negligible cohort, while the secondary objective asks how much of society can be made to support the favored alternative without worsening that guarantee. The expected classification is again Class A. The paper’s threshold-graph and reachability argument should work directly on role types; masses affect the secondary objective but not the bottleneck threshold.
The paper’s Theorem 8 supports both mirrors: it gives the paper’s near-linear algorithms for MINSUM and MINMAX certificates in the classic model. I would not count it as a separate anchor because Theorems 9 and 11 already capture the more interesting population-level control question.
A broader, less secure mirror comes from Theorem 7, proved here. It gives the complete dichotomy for monotone Boolean delegation functions: MINSUM is polynomial only for classic LIQUID and otherwise NP-hard and hard to approximate; MINMAX is polynomial for OR-only or AND-only functions and otherwise NP-hard and hard to approximate within a constant factor.
The corresponding problem is:
Mass-SMART-DICHOTOMY. The input is a rational distribution \(\mu\) over finitely many role types. Each type has a ranked list of monotone Boolean functions over the role-level vote variables, ending in a constant \(0\) or \(1\). A certificate chooses one function per type and is valid exactly when its equations can be evaluated in a sequential order, using the paper’s definition of consistency. The MINSUM objective is \(\sum_t\mu_t c_t\); the MINMAX objective is \(\max_{t:\mu_t>0}c_t\). Output an optimal valid certificate, or decide whether its objective is at most a given rational threshold.
This could describe a large organization whose members belong to a small number of recurring blocs, with ballots such as “support the proposal if either branch A or branch B supports it” or “if both committee roles support it.” The expected classification is Class B for the hard cases: setting all masses equal reproduces the paper’s finite instance up to normalization, so the reductions transfer. The tractable LIQUID, OR-only, and AND-only cases should remain polynomial. The hardness here is driven by the number and interaction of role types, not by population multiplicity.
The weakest point is that real liquid democracy often has person-specific friendship networks. If every voter delegates to a different named friend, then almost nobody shares a complete type, and the continuum loses exactly the dependency structure that makes the original problem interesting. The positive case therefore relies on a defensible but narrower regime: institutional or platform liquid democracy with canonical delegates, recurring ballot schemas, and large interchangeable cohorts. That is not every liquid-democracy instance, but it is a genuine high-multiplicity regime, and the resulting questions preserve ranked delegation, transitivity, cycle avoidance, MINSUM/MINMAX, and winner-oriented tie-breaking. In that regime, the paper admits a clear continuous population mirror; the classic mirrors are expected to be tractable, while the smart-voting mirror preserves the paper’s hardness boundary.
The strongest case against the proposed mirrors is that they silently replace a delegation network on named individuals by a network on roles. That is not a harmless high-multiplicity relaxation: it removes the object on which every computational theorem in the paper depends.
Theorem 11 is the clearest example. Its input is a directed graph whose vertices are individual agents. Whether a certificate is consistent, which agents are reachable from 1, and which edges are tight all depend on the exact identity of each delegation target. A distribution over ballot types does not contain this information.
For example, suppose there are \(k\) agents of type \(A\) and \(k\) of type \(B\), with every \(A\)-agent’s first choice described as “delegate to \(B\)” and every \(B\)-agent’s as “delegate to \(A\).” One underlying network may pair them as \(A_i\leftrightarrow B_i\), producing \(k\) cycles. Another may have all \(A\)-agents delegate to one \(B\)-hub and all \(B\)-agents to one \(A\)-hub, producing only one cycle. With direct voting as a rank-one fallback, the minimum rank-sum is proportional to \(k\) in the first network and constant in the second. The two societies have the same role masses and the same role-level ballots, but different MINSUM problems.
If target identity is included in the type—as it must be, since it affects consistency—then the types distinguish the agents and their number grows with \(k\). If target identity is replaced by a role label, the problem has become delegation to roles, not the paper’s liquid democracy. Adding canonical delegates does not solve this: it produces a hybrid model with a finite collection of exceptional, identity-bearing hubs and a continuum of leaves. The difficult arborescence remains on the finite individual core; the mass merely supplies coefficients for its attached leaves.
Allowing a type’s mass to split among several certificates also fails to restore the mirror. One then needs a distribution of mass over individual delegation graphs, or a measurable parent relation and an acyclicity condition. That extra network or coupling is precisely the missing information; it is not determined by \(\mu\). A mass-transfer formulation is not enough, because delegation is not ordinary flow: accumulated influence moves along individual paths, while cycles and branching are identity-sensitive.
Theorem 9 has the same defect. Its set \(N_1\) is defined by reachability in the individual tight-edge graph. Replacing it by the set of types that can reach 1 loses the distinction between one hub and a positive-mass cohort, and between different wirings within the same roles. Taking the maximum rank only over positive-mass types is also not faithful: a measure-zero hub may determine the votes of a positive fraction of the population. Giving that hub positive mass turns it into an ordinary population type and changes the delegation semantics; giving it zero mass makes the proposed society insufficient to determine the outcome. The favorable mass tie-breaker \(V_1\) weights descendants after the graph is known, but does not supply the missing graph.
Theorem 7 is even less transferable. Its Boolean functions are functions of variables indexed by individual agents. A type-level expression such as “OR of type \(B\)” has no unique meaning: it could mean the OR of all \(B\)-members, the vote of a representative, whether a positive-measure subset supports 1, or a majority or threshold of that type. These alternatives have different limiting consistency notions. The paper’s sequential evaluation rule also relies on resolving finitely many individual variables; an OR over a continuum of members is not resolved merely because one role variable has been assigned.
Keeping every individual argument preserves the paper but makes the number of types grow with the population. Collapsing arguments to roles yields a new typed Boolean-network or population-fixed-point model, potentially interesting but not a high-multiplicity mirror of the stated dichotomy. In particular, the reductions in Theorem 7 use individually addressed agents and gadgets; a role quotient does not preserve their instances without retaining essentially the original identity structure.
Thus the proponent has not actually defined Mass-MINSUM-1, Mass-MINMAX-1, or Mass-SMART-DICHOTOMY from a distribution over voter types. They have defined role-level variants whose central semantics—what it means to delegate to a role, how influence aggregates within it, and how cycles are detected—must be supplied afresh. The paper’s results do not determine those choices.
The negative case is not airtight. A carefully specified model with canonical delegate offices, finite identity-bearing hubs, and massed interchangeable followers could be a worthwhile hybrid. But that is substantially narrower than the claimed continuous society, and it does not continuize the paper’s graph-wide delegation problem. The universal “no scenario” claim therefore remains stronger than the evidence supports; the honest conclusion is that the proposed mirrors, as written, are invalid, while a repaired role-delegation model would require a new paper-level formalization rather than a routine continuous mirror.
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.