| paper | Liquid Democracy with Ranked Delegations |
| authors | Markus Brill, Théo Delemazure, Anne-Marie George, Martin Lackner, Ulrike Schmidt-Kraepelin |
| venue | AAAI 2022 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper fails the objective computational gate: no numbered theorem, proposition, or corollary asserts a complexity, algorithmic, approximation, or parameterized result. Proposition 18 is axiomatic, while the BordaBranching algorithmic observation is unnumbered and standard. A repeated-template weighted branching is coherent, but it cannot make this paper green.
fails bit a — no named computational result to mirror
The proposed mirror covers only BordaBranching and weighted branching; it leaves the sequence-rule axioms, impossibility and characterization results, copy-robustness, and empirical comparisons outside scope.
The honest first point is that this paper has no qualifying computational anchor. None of its numbered Theorems, Propositions, or Corollaries asserts NP-hardness, membership in \(P\), parameterized hardness, or a comparable complexity result. Its numbered results are axiomatic or structural: for example, Proposition 8 proves that Diffusion is confluent, Corollary 13 proves guru-participation for several rules, and Proposition 17 proves an incompatibility between confluence and copy-robustness. Those axiomatic results are also outside ChoCo’s computational scope.
The strongest positive case therefore has to be a salvage case built around the paper’s BordaBranching object. The paper states, unnumbered, that BordaBranching can be computed using a minimum-cost arborescence algorithm; that is a genuine algorithmic statement, but it is not a numbered result of this paper and relies on standard optimization machinery cited to Korte and Vygen. Proposition 18, stated here and proved in the authors’ full version, is the closest named result: there exists a tie-breaking rule under which BordaBranching is copy-robust. I would use it as supporting evidence for the mirror, not falsely present it as a complexity anchor.
A plausible regime is a large organization consisting of many repeated local delegation templates: for example, thousands of union chapters or party branches, each with the same finite set of roles, the same ranked backup delegates, and the same possibility of cycles or abstention. An agent type is a role together with its complete ranked list of delegate roles and its casting/delegating status. The copy index is not part of the type. Thus \(N\) copies of a template give \(N|T|\) agents but only \(|T|=\tau\) types, with \(\tau\) fixed while \(N\) is large. The mass \(\mu_t\) is the fraction of all agents occupying role type \(t\).
The precise lead problem would be:
\[ \textbf{Mass-BordaBranching}_{\infty}. \]
An instance consists of a finite directed type graph \(H=(T,E)\), a partition \(T=C\mathbin{\dot\cup}D\mathbin{\dot\cup}I\), a rank function \(r:E\to\mathbb N_{\ge 1}\), and rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\). Every \(t\in D\) must have a path to a type in \(C\), while types in \(I\) do not. A feasible solution is an acyclic \(C\)-branching \(B\subseteq E\): every \(t\in D\) has exactly one outgoing edge in \(B\), and following those edges reaches a casting type.
The objective is
\[ R_\mu(B)=\sum_{(t,u)\in B}\mu_t\,r(t,u). \]
The required output is a minimum-cost branching \(B\), together with the induced root map \(\rho_B(t)\in C\) and aggregate voting masses
\[ W_c(B,\mu) = \mu_c+ \sum_{\substack{t\in D\\ \rho_B(t)=c}}\mu_t. \]
This is recognisably the authors’ problem: the graph, ranked delegation edges, acyclicity, casting endpoints, and branching objective are unchanged. The only change is that the paper’s count of agents using an edge becomes the high-multiplicity quantity \(\mu_t\). A discrete population with \(N\mu_t\) agents of type \(t\) recovers the same objective after multiplying by \(N\).
I expect this problem to be Class A. Give each edge \((t,u)\) cost \(\mu_t r(t,u)\), reverse the edges, add a super-root connected to the casting types, and solve a minimum-cost arborescence problem. The running time is polynomial in \(|T|\), \(|E|\), and the encoding length of \(\mu\). This is not a dramatic example of discrete hardness disappearing—the discrete BordaBranching problem is already tractable—but it is a clean computational mirror in which mass is the honest quantity and the high-multiplicity regime is meaningful.
A more ambitious follow-up would continuize the paper’s unpopularity margin. For branchings \(B,B'\), define
\[ \Delta_\mu(B,B') = \sum_{t\in D}\mu_t \left( \mathbf 1[r_B(t)<r_{B'}(t)] - \mathbf 1[r_{B'}(t)<r_B(t)] \right), \]
and
\[ U_\mu(B)=\max_{B'}\Delta_\mu(B',B). \]
The problem is to find a branching minimizing \(U_\mu(B)\), or decide whether some branching has \(U_\mu(B)\le q\). This is the exact mass analogue of the paper’s unpopularity-margin analysis. The paper attributes the corresponding LP computation to Kavitha et al. (2021), so the fixed-\(B\) evaluation problem plausibly remains Class A with rational weights; the global minimization problem is less clear. Any hardness would most likely come from the branching structure and therefore transfer from the finite problem, rather than being continuum-specific.
The mirror covers only the BordaBranching and weighted-branching parts of the paper. It does not cover the sequence-rule axioms, Proposition 17’s impossibility result, the characterization Theorems 20 and 21, or the experiments on arbitrary Facebook- and Twitter-like graphs. Those results are not computational population problems.
The weakest point is substantial: the proposed regime replaces the paper’s arbitrary individual network by repeated finite templates. If delegation options are genuinely person-specific, then the complete type includes the network neighborhood and \(\tau\) grows with \(N\); the continuum loses its force. Moreover, because the paper contains no named hardness or algorithmic-complexity theorem, this cannot support ChoCo’s central question of whether discrete hardness dissolves. The best honest positive verdict is therefore: a sensible, author-recognisable Class A mirror exists for BordaBranching in a repeated-role high-multiplicity regime, but this paper supplies no qualifying computational anchor and hence only a weak case for the programme as a whole.
The negative case is unusually strong at ChoCo’s entry gate: this paper has no qualifying computational anchor. Its numbered results—Proposition 18 included—are axiomatic or structural. Proposition 18 says that a suitable tie-breaking rule makes BordaBranching copy-robust; it does not give a complexity, approximation, or algorithmic theorem. The only algorithmic claim is an unnumbered observation that BordaBranching is a standard minimum-cost arborescence problem, with the relevant unpopularity computation attributed to other work. Adding masses to those objects does not turn them into results of this paper.
The proposed Mass-BordaBranching model is also not the genuine high-multiplicity lift of the paper’s branching problem. In the paper, vertices are individuals and the feasibility of a branching depends on individual-level paths, cycles, and identities of delegate targets. If there are \(N\mu_t\) copies of type \(t\), a branching may assign different copies to different outgoing edges. Its natural aggregate description therefore needs variables \(x_{t,u}\) satisfying \(\sum_u x_{t,u}=\mu_t\), together with constraints encoding acyclicity and reachability. The proposed objective
\[
\sum_{(t,u)\in B}\mu_t r(t,u)
\]
instead forces every unit of type \(t\) onto one common edge and replaces the individual branching by a branching of the quotient type graph. That is a new unanimity model, not the paper’s problem under high multiplicity.
One can repair this by assuming repeated, disconnected organizational templates whose role-types all behave identically. But then the network problem is merely replicated: each copy runs the same finite branching, while \(\mu\) scales its cost and voting weight. If copies are allowed genuinely different relational wiring, then the relevant type must include the agent’s reachable delegation structure and target identities; in the general case the number of types grows with the population. The proposed middle ground—anonymous masses with nontrivial individual-level branching structure—requires a new mass-flow or fractional-branching theory that the paper neither defines nor motivates.
Proposition 18 fares even worse under continuization. Copy-robustness concerns changing one named delegating voter into a casting voter. In a nonatomic population, that voter has mass zero, so the aggregate voting weights and every mass-based rule remain unchanged: the axiom becomes vacuous. Giving a whole type positive mass and making it casting is not copying one voter; it is a block intervention that changes the instance macroscopically. An \(\varepsilon\)-mass sensitivity axiom could be interesting, but it would be a newly invented robustness problem, not a continuous mirror of Proposition 18.
The proposed mass unpopularity margin has the same problem. With deterministic type-level branchings, it is just a weighted reformulation of the finite comparison. With fractional assignments, \(r_B(t)\) is no longer defined: a type’s mass may use several outgoing edges, so one must choose expected rank, worst rank, a distribution over branchings, or some other new preference extension. The paper contains no theorem about minimizing its unpopularity margin over branchings; the fixed-branching LP comes from Kavitha et al. Thus this proposal is an independent optimization problem built around a metric used in the experiments, not a computational result to be continuized.
The honest concession is that a role-based mass branching model can be made mathematically coherent, and repeated chapters or departments may provide a defensible high-multiplicity story. But that would be a new paper about anonymous weighted branchings, not a computational mirror of this one. The source paper contributes axiomatic classifications and empirical comparisons of identity-dependent delegation networks, while ChoCo needs a named computational question whose population axis is genuinely exposed. On that standard, no worthwhile continuous mirror is supplied here.
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.