| paper | Computation and Bribery of Voting Power in Delegative Simple Games |
| authors | — |
| venue | AAMAS 2022 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 7
statement extracted from the paper’s text layer
Given finite complete role types \(T\), rational masses \(\mu_t\) summing to \(1\), a role-symmetric support relation \(A\subseteq T\times T\), a baseline action \(d_0:T\to T\cup\{\mathrm{vote}\}\), target role \(r\in T\), normalized budget \(B\), and target mass \(\theta\), choose a finite mass-valued acyclic delegation forest whose subcohort masses sum to \(\mu_t\), whose arcs obey \(A\), and whose changed-delegation mass \(\sum_v a_v\mathbf{1}[p(v)\ne d_0(\ell(v))]\) is at most \(B\); decide whether at least \(\theta\) mass has a delegation root of type \(r\), and maximize that rooted mass in the optimization version.
Mass-WMaxP\(_\infty\): a role-symmetric typed blow-up of the liquid-democracy support network with types \(T\), masses \(\mu\), admissible delegation relation \(A\), baseline actions, and a normalized modification budget; the objective is represented mass rooted at target role \(r\).
The typed relation \(A\) and finite subcohort forest do not by themselves specify a fixed blow-up preserving individual incidence and acyclicity; that typed-network semantics must be formalized.
fatal: False
The mirror covers WMaxP and OWMaxP from Theorem 7, with Theorem 8’s rooted-tree-orienteering equivalence as supporting structure; it leaves the power-index bribery problems and the other approximation and parameterized results uncovered.
The strongest mirror is the paper’s WMaxP, anchored on Theorem 7, proved in this paper. The theorem says that WMaxP is NP-complete and that its optimization version OWMaxP cannot be approximated within any factor better than \(1-1/e\), unless \(P=NP\), even when every voter has weight one. I would use this as the lead and would not anchor on the Banzhaf or Shapley-Shubik results: their continuum limits require a non-canonical notion of pivotality for a nonatomic population.
The natural mirror is Mass-WMaxP\(_\infty\). An instance contains a finite set of complete voter types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), an allowed support relation \(A\subseteq T\times T\), an initial acyclic delegation policy \(d_0\), a target type \(r\), a normalized budget \(B\), and a target mass \(\theta\). Every voter has unit weight, as in Theorem 7.
A feasible post-bribery policy is a finite mass-valued delegation forest. Each subcohort \(v\) has a type label \(\ell(v)\in T\), a rational mass \(a_v\), and either votes directly or delegates to another subcohort \(p(v)\). The total mass carrying type \(t\) must be \(\mu_t\); delegation must follow \(A\); and the resulting delegation graph must be acyclic. A type may be split into subcohorts, representing different fractions of that type receiving different delegation recommendations.
The bribe cost is the mass whose delegation differs from the baseline:
\[ \operatorname{cost}(F) = \sum_{v} a_v\, \mathbf{1}\!\left[\ell(p(v))\neq d_0(\ell(v))\right]. \]
Let \(\rho(v)\) be the root reached by following delegation from \(v\). The mass represented by the target type is
\[ \operatorname{rep}_r(F) = \sum_{v:\,\ell(\rho(v))=r} a_v. \]
The decision problem asks whether there exists a forest \(F\) with \(\operatorname{cost}(F)\le B\) and \(\operatorname{rep}_r(F)\ge\theta\). The optimization version maximizes \(\operatorname{rep}_r(F)\).
This is a genuine continuization of WMaxP. It retains the directed social network, transitive delegation, acyclicity, the budget on changed delegations, and the accumulated weight of the target. Only individual counts become mass, and the cardinality budget becomes a mass budget. For a discrete instance with \(N\) voters, the dictionary is
\[ \mu_t=\frac{n_t}{N},\qquad B=\frac{k}{N},\qquad \theta=\frac{\tau}{N}. \]
Conversely, any rational mass instance can be expanded into a finite population by multiplying all masses by a common denominator. Thus this is more than an analogy: it has a direct high-multiplicity dictionary.
A convincing regime is a large liquid-democracy electorate in a federation of repeated chapters or organizations. A type records the complete support role of a member: the class of acceptable delegates, the initial delegation choice, the member’s price, and any relevant organizational parameters. Millions of members may share a few dozen or few hundred such roles. A campaign or faction can influence a fraction of each role, paying per affected member, and wants a particular representative role to accumulate as much represented mass as possible. This is a sensible high-multiplicity setting; it is not merely assigning fractional outcomes to a discrete election.
The original authors should recognize this mirror. Their WMaxP objective is already accumulated voting weight under delegation changes, rather than a uniquely individualistic power index. Theorem 8 strengthens the connection: the paper itself proves an equivalence between OWMaxP and a rooted directed tree-orienteering problem. A mass-valued rooted delegation forest is therefore the continuous version of the combinatorial object the authors identify as central.
For the unrestricted type-graph problem, I would expect Class B more than Class A. Theorem 7’s difficulty appears to come from selecting and arranging support-network branches, not from large numerical weights or from the sheer number of voters. That combinatorics can remain when population mass is divisible. In the genuine high-multiplicity regime with moderate \(\tau\), however, fractionality may produce a configuration LP or flow formulation, especially on tree, laminar, or bounded-width support graphs. The key downstream question is whether the pricing problem for rooted mass forests is polynomial. If it is, the discrete hardness dissolves; if it remains hard after fractionality, that would be a continuum-specific boundary.
The weakest point is the treatment of identity. In the paper, one named voter can be a uniquely powerful guru. In a nonatomic population, a named individual has zero mass, so the meaningful target must be a representative type or role. Also, if an arbitrarily small subcohort can become a hub for a large mass, the limit can develop singular behaviour. That objection is real. The mirror therefore has to commit to role-symmetric mass delegation, with explicit subcohorts and preserved acyclicity, rather than silently turning a type into one super-agent. With that qualification, the model remains faithful to the paper’s central question and gives a precise, worthwhile continuous problem anchored in its strongest hardness result.
The only serious anchor is WMaxP/Theorem 7, and the strongest case against it is that WMaxP is not fundamentally a population problem. Its vertices are positions in a support network, its edges point to named individuals, and its objective is the basin of one named target \(i^\star\). Theorem 7’s hardness is encoded in precisely those identity-specific incidences.
The proposed mass model therefore loses essential input information. In the paper, changing a delegation from \(u\) to \(v\) is costly even if \(u\) and \(v\) have identical weights and roles. In the proposed formula, changing between same-labelled subcohorts is free whenever \(\ell(p(v))=\ell(d_0(\ell(v)))\). To repair this, the destination’s identity or network position must be part of the type. But then agents with different neighbourhoods or baseline delegates are different complete types, and the type space grows with the support network rather than representing high multiplicity. The distribution \(\mu\) becomes decorative: it records how much mass occupies already-individuated network positions.
The subcohort formulation does not solve this. A type distribution does not determine which copies support which other copies. That missing incidence structure is reintroduced as an arbitrary finite forest chosen in the solution. Its number of subcohorts is unbounded, and acyclicity is a property of that hidden identity-level forest, not of the type relation. Thus the proposed problem is not yet a finite continuous society problem; it is an underspecified optimization over variable-size identity graphs. Bounding the number of subcohorts would add an arbitrary discrete parameter, while allowing arbitrary splitting changes the object being optimized.
The target creates a second mismatch. WMaxP asks for the accumulated weight of one voter \(i^\star\). Replacing \(i^\star\) by a target type \(r\) permits mass to be represented by any of many interchangeable gurus, which is a different objective. Marking one target individual instead produces a hybrid continuum-plus-atom model: the population is continuous, but the object whose power is measured remains exceptional and identity-specific. Its basin may have positive mass, so this is not a mere measure-zero objection; it is a warning that the principal quantity has not itself been continuized.
Theorem 8 reinforces rather than repairs this concern. OWMaxP is equivalent to rooted directed tree-orienteering, whose essential data are vertex-specific edge incidences and edge-change costs. A graphon or measure-valued network could preserve that information, but it would be a new continuous network-design theory, not the high-multiplicity relaxation \(\mu\) of WMaxP. Conversely, quotienting repeated chapters or organizational roles into a finite type graph produces a legitimate mass-routing problem, but it replaces named-root delegation by role-level aggregation and no longer mirrors the paper’s computational object.
This is a substantial objection to the proponent’s particular mirror: it is not faithful or well-defined without either discarding the network structure or reintroducing it at identity resolution. But the universal negative case is honestly weak. A marked representative with many repeated follower types, or a role-level delegation model for repeated chapters, is a plausible new problem and could be worthwhile even though it is not a clean mirror of WMaxP as stated. Theorem 7 therefore cannot be defeated categorically; at most, the proposed continuization should be rejected until its identity, destination, and acyclicity semantics are specified.
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.