| paper | Measuring a Priori Voting Power in Liquid Democracy |
| authors | Rachael Colley, Théo Delemazure, Hugo Gilbert |
| venue | IJCAI 2023 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given delegator types \(A\), proxy types \(B\), rational masses \(\mu_a,\nu_b\) summing to \(1\), per-agent weights \(w_t\), quota \(q\in(1/2,1]\), direct-voting probability \(p_v\), delegation probability \(p_d=1-p_v\), and a delegation distribution \(\rho\) over \(B\), each \(a\in A\) chooses \(+\), \(-\), or \(b\in B\), while each \(b\in B\) votes \(+\) or \(-\). For profile \(d\), define \(S^+_\mu(d)=\sum_{a:d(a)=+}w_a\mu_a+\sum_{b:d(b)=+}(w_b\nu_b+\sum_{a:d(a)=b}w_a\mu_a)\), define \(S^-_\mu(d)\) analogously, and let \(W_\mu(d)=1\) iff \(S^+_\mu(d)>q(S^+_\mu(d)+S^-_\mu(d))\). Compute the expected criticality \(\mathbb{E}_d[(W_\mu(d[r\leftarrow+])-W_\mu(d[r\leftarrow-]))/2]\) of a positive-mass target type \(r\), or decide whether it is at least \(\theta\).
A typed-cohort extension of PV Penrose–Banzhaf power: the society is given by masses \((\mu,\nu)\), delegation routes type mass, and one random action represents each repeated role type.
The target cohort's common \(+\)/\(-\) action is perfectly correlated across its copies, whereas independent microscopic choices make a named voter's pivotal probability vanish; \(B_r^\infty\) is therefore not a literal limit of \(M_i^{ld}\).
fatal: False
The mirror covers Theorem 3's PV computation as a typed-cohort exact-power problem and leaves Theorem 2's arbitrary-digraph reduction, Theorem 4 as a separate anchor, and the sampling and experimental claims aside.
The strongest positive case is a typed-cohort mirror of the paper’s voting-power problem, with Theorem 3 as the lead anchor and Theorem 2 as a harder secondary anchor. Both theorems are proved in this paper.
The high-multiplicity setting is a large federation or platform referendum with many interchangeable ordinary members and proxy members. A type records everything relevant: whether an agent is an ordinary delegator or proxy, its voting weight, its allowed proxy classes, and its delegation probability. There may be millions of voters but only \(\tau\) such roles, with rational masses \(\mu_t\). This is especially plausible for the paper’s PV setting: many ordinary members can delegate to a small number of repeated proxy roles.
The necessary continuous replacement for an individual voter is a positive-mass cohort. An atomless individual has zero pivotal effect, so asking whether one unnamed member is critical would be vacuous. The cohort version asks whether an interchangeable role-cohort can change its direct stance and thereby change the outcome. This is a substantive extension, but it preserves the paper’s central object: a priori probability of being critical under random delegation choices.
Call the lead problem \( \mathrm{PV\text{-}Cohort\text{-}Power}_\infty \). Its instance consists of delegator types \(A\), proxy types \(B\), rational masses \(\mu_a\) and \(\nu_b\), per-unit weights \(w_t\), a quota \(q\in(1/2,1]\), a direct-voting probability \(p_v\), and a delegation probability \(p_d=1-p_v\). Every \(a\in A\) may delegate to any proxy type \(b\in B\); a delegation chooses \(b\) with probability proportional to \(\nu_b\). Each proxy type votes directly for or against with probability \(1/2\). A type-level delegation profile \(d\) therefore assigns every delegator type either \(+\), \(-\), or a proxy type, while every proxy type receives \(+\) or \(-\).
For a profile \(d\), the final positive weighted mass is \(S^+_\mu(d)=\sum_{a:d(a)=+}w_a\mu_a+\sum_{b:d(b)=+}w_b\bigl(\nu_b+\sum_{a:d(a)=b}\mu_a\bigr)\), with the analogous definition of \(S^-_\mu(d)\). The outcome is positive exactly when \(S^+_\mu(d)>q(S^+_\mu(d)+S^-_\mu(d))\). For a target proxy type \(r\), let \(d[r\leftarrow +]\) and \(d[r\leftarrow -]\) be the profiles obtained by forcing the whole \(r\)-cohort to vote directly in favour or against while leaving all other delegation choices unchanged. The problem asks for the exact value \(B_r^\infty(\mu)\) given by \(B_r^\infty(\mu)=\mathbb E_d\bigl[(W_\mu(d[r\leftarrow +])-W_\mu(d[r\leftarrow -]))/2\bigr]\), or, in decision form, whether \(B_r^\infty(\mu)\ge\theta\).
This is recognisably the paper’s question: same binary proposal, same weighted voting rule, same direct/delegate actions, same proxy structure, and the same counterfactual definition of criticality. Clearing the denominators of the masses produces repeated role-cohorts, and multiplying every mass by \(N\) leaves the quota comparison unchanged. The paper’s Proposition 2 already aggregates its formula by role counts and weight sums, which is strong evidence that this is not an arbitrary reinterpretation.
The anchor is Theorem 3, which proves that \(M_i^{ld}\) in the bipartite PV setting can be computed in pseudo-polynomial time. I expect the stated continuous problem to have the same boundary: pseudo-polynomial dynamic programs when aggregate weights and mass denominators are small or unary-encoded, but exact binary-input evaluation to remain Class B. The weighted-voting slice \(p_d=0\) already contains standard Banzhaf computation, and the paper connects that slice through Proposition 1 to the known \(\#\mathrm P\)-complete problem. Delegation does not remove the weighted-threshold combinatorics; it adds structured mass-routing variables. Approximation and fixed-\(\tau\) algorithms are natural further questions.
The secondary mirror is \( \mathrm{Typed\text{-}LD\text{-}Power}_\infty \), anchored by Theorem 2. Here the type space \(T\) carries a directed graph \(H\) between delegation roles, rational masses \(\mu_t\), weights \(w_t\), and probabilities \(p_t\). A random profile chooses, independently for every type, either \(+\), \(-\), or an allowed successor type. Delegations are resolved transitively; mass reaching a type-level cycle abstains. The weighted outcome is computed from the positive and negative type masses exactly as above. The requested output is the expected criticality of a target type under the counterfactual \(+\) and \(-\) assignments.
This mirrors Theorem 2, which proves \(\#\mathrm P\)-hardness under Turing reductions for arbitrary digraphs, even when weights are linearly bounded. The reduction’s combinatorics live in simple paths of the delegation graph, not in the number of individual voters. That makes hardness likely to transfer: take one type for each vertex of the hard graph, set \(\mu_t=1/|T|\), and use the paper’s weights. Scaling every type mass by \(K\) gives \(K\) interchangeable members of every role without changing the quota comparison or the type-level power value. Thus this is naturally Class B, with hardness surviving because the difficult object is the role network rather than population multiplicity.
The complete-digraph case from Theorem 4 is a special case of the same typed model with \(H\) complete. Its recursive forest calculation suggests a useful restricted continuous problem, but I would not count it as a third anchor: it adds little beyond the PV and arbitrary-network cases.
The weakest point is unavoidable: the paper measures the criticality of an independently acting named voter, whereas the non-vacuous continuum formulation measures the criticality of a positive-mass cohort. If one insists on independent microscopic choices by every clone, a representative individual’s pivotal probability generally tends to zero, and one needs a separate \(\sqrt N\)-scaled or coalition-based limit. I would present the cohort model explicitly as an extension rather than claim it is the literal atomless limit. Its defence is that proxy cohorts, caucuses, local chapters, and institutional delegate roles genuinely act as repeated blocks, and the paper’s own PV aggregation already treats voters through role-level cardinalities and weights. That is enough for a credible, author-recognisable continuous mirror covering Theorems 2 and 3, without pretending that every individual-level statement survives unchanged.
The strongest negative case is that the proposed mirrors do not preserve the paper’s central object: the probability that one named voter is pivotal under independent delegation choices.
Theorem 3 is a genuine computational anchor, so “the paper has no computational result” is unavailable. But its \(M_i^{ld}\) concerns one individual coordinate of a finite delegation partition. Suppose a voter type is replicated \(N\) times. Under the paper’s individual-uniformity assumption, the members of that type make independent choices. A proxy cohort of mass \(\nu_b\) therefore contains \(N\nu_b\) independent voters; the probability that they all vote positively is \(2^{-N\nu_b}\), not \(1/2\). The proponent’s type-level profile instead assigns one common action to the whole type. That is perfect correlation among clones, not a high-multiplicity relaxation.
The literal high-multiplicity limit is degenerate for individual power. Changing one voter changes the weighted outcome by \(O(1/N)\), while aggregate random fluctuations are typically \(O(N^{-1/2})\). Away from an exact quota boundary, the probability that one individual changes the outcome tends to zero. One can rescue a nonzero quantity by introducing a \(\sqrt N\)-normalisation, a boundary-layer analysis, or a positive-mass bloc intervention, but each is an additional modelling choice. In particular, forcing an entire proxy cohort to vote positively or negatively is coalition power, not the paper’s individual Penrose–Banzhaf power. It may be an interesting new index, but it is not what Theorem 3 establishes.
The proxy setting does offer a plausible high-multiplicity story, so the negative case is not that repeated delegators are impossible. The problem is that the proposed \(B_r^\infty\) has to choose between two incompatible interpretations. If actions remain independent across members, the individual measure vanishes and a cohort intervention becomes a deterministic threshold-crossing question in the limit. If actions are sampled once per type, the model has only finitely many random role-players, regardless of how large the masses are. Scaling the masses then preserves a weighted voting expression but not the paper’s probability distribution. The pseudo-polynomial boundary in Theorem 3 consequently does not transfer as claimed.
Theorem 2 is weaker still as a continuous anchor. Its reduction counts simple paths in a labelled voter graph. Giving each graph vertex one type of mass \(1/|V|\) does not create multiplicity; it merely relabels each individual as a type. Replicating those vertices does not fix the problem. A type-level delegation graph cannot record which particular clone is adjacent to which other clone, while that identity information determines whether a delegation path is simple and whether a cycle produces abstention. With independent clones, a path may revisit the same type through different individuals; with one shared choice per type, all clones are artificially correlated. Either way, the simple-path reduction used for Theorem 2 is no longer a reduction for the proposed continuum.
This is a consequence of the paper’s arbitrary network model, not an objection that its hardness “does not help.” A voter’s complete type must include the network information relevant to their criticality. In a general digraph that information is essentially individual-specific, so a genuine type compression destroys the object being measured. Symmetric cases such as complete or bipartite graphs admit repeated roles, but there the individual-pivotality problem still suffers the vanishing-or-correlation dichotomy above.
The honest limitation is that an absolute claim that no related continuum problem could ever be worthwhile is too strong. A carefully defined block-power index for repeated proxy cohorts, or a normalized fluctuation limit, could be a legitimate new research problem. But it would be a collective or mean-field voting-power theory, not a faithful continuous mirror of the paper’s \(M_i^{ld}\). Thus both anchors in the proponent’s case fail as stated; the remaining positive case depends on conceding a new object rather than continuizing either theorem.
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.