| paper | Approval-Based Committee Voting in Practice: |
| authors | — |
| venue | AAAI 2024 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1 (informal)
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), approval cap \(q\), replacement target \(\ell\), rational masses \(\mu\) over approval types \(S \subseteq C\), and fixed tie-breaking, let \(W\) be the AV committee. Add fresh candidates \(D\) of size \(\ell\) and nonnegative masses \(y_B\) over approval types \(B \subseteq C \cup D\) with \(|B| \le q\). Minimize the total added mass \(x = \sum_B y_B\) subject to the resulting tie-broken AV committee replacing exactly \(\ell\) members of \(W\) by \(D\).
A high-multiplicity weighted ABC election: approval sets, together with any rule-relevant eligibility or stake parameters, are voter types with rational mass \(\mu\); attacker variables are masses \(y_B\) of new approval types; the objective is minimum added stake causing exogenous committee replacement.
For AV, the type distribution collapses to aggregate candidate approval scores, and Theorem 1 is conditional on data precomputed during rule execution; this makes the mirror more like weighted-score postprocessing than a deep continuization result.
fatal: False
Covers the AV clause of Theorem 1; it leaves the SAV, seq-Phragmén, and Phragmms clauses, other empirical measures, and axiomatic analyses untreated.
The strongest honest case is a narrow one: the paper’s exogenous-attack problem has a faithful population mirror, especially for Approval Voting. I would make this my lead, rather than trying to continuize every proportionality measure in the paper.
The anchor is Theorem 1 (informal):
“For AV, SAV, seq-Phragmén, and Phragmms, the minimum exogenous cost of replacing \(\ell\) candidates can be computed in \(O(1)\) time, assuming we use data from executions of the rules.”
This is presented as the authors’ own result, not as a theorem cited from elsewhere; the supplied conference version states it informally and defers the details to the full version.
The relevant high-multiplicity scenario is a large proof-of-stake network in which many nominators, delegation units, or custodial staking accounts follow a small number of standard validator-selection policies. A type is an approval set \(S\subseteq C\), with \(|S|\le16\) for the actual Polkadot rule; if stake denomination or eligibility affects the rule, those parameters are included in the type as well. The mass \(\mu(S)\) is the fraction of total participating stake held by that type. Thus the population may contain \(10^5\) or more stake-bearing agents, while only \(10^2\)–\(10^3\) approval-policy types occur, alongside roughly \(m=10^3\) named candidates and \(k\approx300\) committee seats. The paper’s observed scale—18,202–48,025 voters and 920–1,080 candidates per election—makes the many-agent regime entirely credible, although the smaller number of repeated types is an additional modelling assumption rather than an empirical fact established by this paper.
The crucial point is that this is already the paper’s weighted ABC model with voter identities aggregated. For Approval Voting, the only relevant quantity is
\[ a(c)=\sum_{S\ni c}\mu(S), \]
the total stake approving candidate \(c\). The committee remains an integral \(k\)-element subset of named candidates. Nothing is being made continuous in the outcome space, and time is not being continuized; only the voter population is replaced by a distribution over approval types.
I would name the continuous problem:
Continuous Exogenous Replacement for Approval Voting, \(\mathrm{CER\text{-}AV}_\infty\).
An instance consists of:
Let \(W\) be the \(k\) candidates with largest approval weights \(a(c)\). The attacker introduces exactly \(\ell\) fresh candidates \(D=\{d_1,\ldots,d_\ell\}\). For every approval set \(B\subseteq C\cup D\) with \(|B|\le q\), the attacker may add a nonnegative mass \(y_B\) of new voters of type \(B\). The total added stake is
\[ x=\sum_B y_B. \]
After the attack, every old candidate \(c\in C\) has approval weight
\[ a_y(c)=a(c)+\sum_{B\ni c}y_B, \]
and every fresh candidate \(d\in D\) has approval weight
\[ a_y(d)=\sum_{B\ni d}y_B. \]
Equivalently, one may normalize all weights by \(1+x\); this does not change the AV ranking. Let \(W_y\) be the resulting tie-broken AV committee. The task is to minimize \(x\) subject to
\[ W_y=(W\setminus R)\cup D \]
for some \(R\subseteq W\) with \(|R|=\ell\). In decision form: given a rational budget \(b\), does there exist such an attack with \(x\le b\)? The exact Polkadot version sets \(q=16\); the paper’s unbounded-approval comparison is obtained by taking \(q=m+\ell\).
This is the paper’s question almost verbatim: how much additional malicious stake must be introduced, together with new candidates and new approval votes, to replace \(\ell\) members of the elected committee? The continuous variable is not a softened committee or a fractional candidate. It is precisely the amount of attacking population mass. The paper’s reported security statements—such as the stake needed to replace one-third of the committee—have exactly this interpretation.
I expect \(\mathrm{CER\text{-}AV}_\infty\) to be Class A. Once the AV execution data are available, the attack only changes candidate approval scores by linear increments. The relevant information is a collection of approval-weight thresholds, so the optimization reduces to a finite threshold calculation or a small linear program rather than a search over named voters. This is the continuous counterpart of Theorem 1’s \(O(1)\)-time postprocessing claim. The initial aggregation from \(\mu\) costs polynomial time in the explicit type representation; the constant-time claim, as in the paper, concerns queries made after the rule-execution statistics have been computed.
The mirror should be recognizable to the authors because it preserves all of the substantive ingredients: weighted approval ballots, an integral committee of size \(k\), newly added candidates, newly added voter stake, and the objective of replacing elected validators. It merely identifies voters with the same rule-relevant approval behaviour and treats their total stake as mass. In fact, the paper’s use of weighted voters makes this aggregation especially natural: a type’s mass is simply the combined stake of all nominators with that approval pattern.
This mirror covers only the AV clause of Theorem 1. I would not use the paper’s sentence that “computing these values is NP-hard” as a second anchor, because in the supplied text it appears only in a footnote and is not a numbered theorem or proposition. Nor would I claim that the paper provides a computational result for all of its empirical proportionality measures.
The natural follow-up questions are whether the same population relaxation yields tractable continuous replacement problems for seq-Phragmén and Phragmms; whether an attacker may instead transfer or persuade existing mass rather than add new mass; and whether one can choose \(k\), the approval cap, or the voting rule to maximize the minimum continuous attack mass.
The weakest point is that this is a modest Class A mirror. For AV, the continuous version may look like a clean weighted reformulation rather than a deep new optimization problem, and Theorem 1 itself is only informal in the supplied version. More seriously, Polkadot’s actual approval lists and stake holdings may be highly idiosyncratic, so the assumption \(\tau\ll n\) needs a constructed staking-cohort interpretation rather than being read directly off the dataset. Finally, this argument does not yet establish that the central proportional rules admit equally elegant continuous algorithms. Even with those concessions, it gives a precise, faithful population problem anchored in the paper’s named computational result, and it is strong enough to justify a positive mirror for this part of the work.
The strongest negative case is that the proposed AV mirror is much thinner than it first appears. Theorem 1 is only stated informally here and is conditional on data produced while running the rule; it is not a complexity theorem for an input distribution over voter types. Moreover, the proposed \(\mathrm{CER\text{-}AV}_\infty\) is not quite the paper’s problem: it introduces a new mass-attack model with arbitrary approval patterns and fresh candidates.
Under that model, however, the population distribution disappears almost completely. For AV, the old society matters only through the vector of candidate approval weights \(a(c)\). If an attacker may add arbitrary stake and approve up to \(q\) fresh candidates per unit of mass, the optimum is obtained by identifying the weakest retained candidate and raising each fresh candidate to the relevant threshold, subject only to the approval cap. The approval-type support, multiplicities, and individual identities play no role. This is a weighted-score calculation, not a high-multiplicity optimization problem whose tractability depends on continuization. The \(O(1)\) result is therefore better viewed as postprocessing an already aggregated AV election than as evidence for the programme’s computational agenda.
That objection does not survive the best repair, though. One can fix a finite set of approval-policy types, give them rational masses, and allow the attacker to transfer or campaign against existing mass with type-dependent costs. Approval sets can be represented by rankings with an approval cutoff, and all relevant costs, budgets, and eligibility parameters can be included in the type definition. The resulting minimum-cost committee-replacement problem is a genuine continuous-population version of the paper’s security question. A plausible high-multiplicity setting is a staking ecosystem containing many custodial accounts or delegators following a small number of standard validator-selection policies. The fact that the observed permissionless electorate may contain many idiosyncratic ballots does not rule out that regime.
Nor do the other standard objections work. The objective is total stake, not the identity of the voters; stake remains meaningful mass in the limit; and no existing continuous computational treatment is cited. High-multiplicity election work would support, rather than defeat, this modelling move.
So the honest negative verdict is limited: this is probably a modest, possibly low-depth Class A mirror, and the proponent overstates how much of the paper’s theorem is genuinely about population continuization. But I cannot defeat the anchor universally. With the natural mass-transfer/campaigning formulation, it is a recognizable and defensible continuous computational question. A thoughtful reader should therefore regard the case against as weak rather than conclude that no worthwhile mirror exists.
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.