| paper | Approval-Based Committee Voting in Practice: A Case Study of (over-)Representation in the Polkadot Blockchain |
| authors | N. Boehmer, Markus Brill, Alfonso Cevallos, Jonas Gehrlein, L. Fernández, Ulrike Schmidt-Kraepelin |
| venue | AAAI 2024 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard in both the unrestricted domain and the domain with \(|S|\le16\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given \(C\), a fixed committee \(W\subseteq C\) with \(|W|=k\), \(1\le\ell\le k\), and rational masses \(\mu_S\ge0\) over approval types \(S\subseteq C\) with \(\sum_S\mu_S=1\) (with \(|S|\le16\) in the Polkadot variant), compute an integral \(X\subseteq W\) with \(|X|=\ell\) minimizing \(a_\mu(X)=\sum_{S:S\cap X\neq\varnothing}\mu_S\).
Approval types are sets \(S\subseteq C\) carrying stake mass \(\mu_S\); the decision variable is an integral coalition \(X\subseteq W\) of size \(\ell\), and the objective is its supported mass \(a_\mu(X)\).
The paper already permits arbitrary voter weights, making the proposed \(\mu\)-input an exact aggregation for this objective, and it gives no data on the number of recurring approval types.
fatal: False
It covers Proposition 1's NP-hard fixed-committee minimum-support coalition problem and its Clique reduction; it leaves the empirical comparisons, replacement-cost results, seq-PAV and MES analyses, and design-choice experiments untouched.
My lead, and the only anchor I would use, is Proposition 1.
The continuous mirror is a security problem over a high-multiplicity population of Polkadot nominators. Let \(C\) be the validator candidates and let \(W\subseteq C\) be the elected committee, with \(|W|=k\). A voter type is an approval set \(S\subseteq C\), together with any other voter attribute that the problem uses; for this problem, \(S\) is complete. The society is a rational distribution \(\mu=(\mu_S)\), where \(\mu_S\) is the fraction of total voting stake held by nominators of type \(S\), and \(\sum_S\mu_S=1\). Approval ballots may naturally be restricted to \(|S|\leq16\), as in Polkadot.
For \(X\subseteq C\), define its approval mass by
\[ a_\mu(X)=\sum_{S:S\cap X\neq\varnothing}\mu_S. \]
I would call the mirror Continuous Minimum-Support Coalition, or \(\textsf{CMSC}_\infty\):
Given \(C\), a committee \(W\), an integer \(1\leq\ell\leq k\), and rational type masses \(\mu\), find an integral subset \(X\subseteq W\) with \(|X|=\ell\) minimizing \(a_\mu(X)\).
Equivalently, its decision version asks whether there is such an \(X\) with \(a_\mu(X)\leq q\). A solution is the candidate coalition \(X\), together with its minimum approval mass. The candidates and the attacked coalition remain discrete; only the population is continuous.
This is a direct mirror of the paper’s security question: how little stake can jointly support a group of \(\ell\) elected validators? It is not a fractional committee or a divisible-outcome problem. The continuous object is precisely the distribution of nominators’ approval types.
Proposition 1, proved in this paper rather than cited, states that given a weighted ABC election \((C,V,A,w,k)\), a committee \(W\), and \(\ell\in[|W|]\), it is NP-hard to compute a size-\(\ell\) subset \(W'\subseteq W\) minimizing
\[ w(W')=\sum_{v:A_v\cap W'\neq\varnothing}w(v). \]
The proof reduces Clique on an \(r\)-regular graph. There is one candidate for each graph vertex and one voter approving the two endpoints of each edge. For a \(t\)-vertex set \(X\), the number of edge-voters approving at least one candidate in \(X\) is
\[ rt-e(X), \]
where \(e(X)\) is the number of edges induced by \(X\). Thus the threshold \(rt-\binom{t}{2}\) is attained exactly when \(X\) is a \(t\)-clique.
The same reduction gives the continuous problem immediately. Give each edge type mass \(1/|E|\). Then
\[ a_\mu(X)=\frac{rt-e(X)}{|E|}, \]
so deciding whether \(a_\mu(X)\leq (rt-\binom{t}{2})/|E|\) is NP-hard. The hardness therefore transfers to the continuous mirror: this is a Class B problem, not continuum-specific hardness. The combinatorics live in the candidate graph and the choice of an integral coalition, not in the number of named voters.
The high-multiplicity interpretation is exact. From a finite weighted election, set
\[ \mu_S=\sum_{v:A_v=S}w(v). \]
Conversely, rational masses can be realized by sufficiently many voters with the corresponding approval sets. Thus the mirror is not changing the security metric; it is exposing the type-compressed population on which that metric operates.
A plausible regime is a validator ecosystem with tens of thousands of nominators but substantially fewer recurring approval policies: staking pools, custodians, exchanges, companies, and cohorts of delegators following the same validator recommendations. The paper itself notes that high-weight voters often represent organizations and tend to approve their own candidate groups. In such a regime, \(n\) may be tens of thousands while the number of approval types \(\tau\) is perhaps hundreds or a few thousand. Stake is naturally mass, and one-person granularity is not the meaningful security unit.
The authors should recognize this as their problem because the paper already defines approval weight exactly as a union of voters’ weights and motivates it through the stake lost when committee members misbehave. The mirror preserves the underlying NP-hard optimization rather than simplifying it into a tractable surrogate.
It also generates natural follow-up questions, especially the committee-design problem
\[ \max_{\substack{W\subseteq C\\|W|=k}} \min_{\substack{X\subseteq W\\|X|=\ell}}a_\mu(X), \]
as well as parameterized algorithms in \(\tau\), \(\ell\), or the maximum approval-set size, and robustness of the minimum-support value under changes in the population distribution.
The weakest point is that the paper already uses weighted voters, and this particular objective depends only on aggregated approval mass. In a dataset where almost every approval ballot is unique, the mirror may look like a reparameterization rather than a transformative continuization. The paper does not report the number of distinct approval types, so the high-multiplicity regime is plausible rather than empirically established. Nevertheless, the organizational and stake-based setting supplies a credible scenario, and Proposition 1 gives a clean, named computational anchor whose continuous counterpart is precise and whose hardness meaningfully survives the passage to a continuous population.
The proponent’s anchor is the right place to look, but it fails because \(\textsf{CMSC}_\infty\) is already the paper’s formal problem.
For every weighted election, define
\[ \mu_S=\sum_{v:A_v=S}w(v). \]
Then, for every candidate subset \(X\),
\[ w(X)=\sum_{S:S\cap X\neq\varnothing}\mu_S=a_\mu(X). \]
Conversely, every rational distribution \(\mu\) can be represented by a weighted election containing one voter of approval type \(S\) with weight \(\mu_S\). Thus the proposed “continuous” instance, feasible solution, and objective are exactly the weighted election already defined in the paper. The list of named voters is merely an atomic encoding of the distribution. This is not a discrete-to-continuous identity that the paper proves; the paper’s input model already admits the purported continuum.
The proposed high-multiplicity story—many nominators following a small number of staking policies—is plausible, and this is the negative case’s weakest point. It would justify aggregating repeated ballots and might motivate algorithms parameterized by the number of approval types. But that would be high-multiplicity optimization for an already weighted ABC problem, not a missing continuous-population mirror. Proposition 1 already applies after aggregation, without any new modelling assumption.
Adding organization labels, identities, or other attributes cannot repair the mirror: if they do not affect \(a_\mu(X)\), they are irrelevant; if they do affect it, the result is no longer a mirror of Proposition 1. Likewise, optimizing the committee itself,
\[ \max_{|W|=k}\min_{\substack{X\subseteq W\\|X|=\ell}}a_\mu(X), \]
would be a sensible new weighted committee-design problem, but it changes the task from evaluating a fixed committee to designing one. It is not the continuous counterpart of the paper’s named result.
So the paper does contain a legitimate high-multiplicity regime, but the proponent has not identified a worthwhile continuization. Its sole anchor is already formulated over voter weights, and passing from weighted voters to a distribution over approval types adds notation and perhaps a useful compression parameter—not a new computational object.
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.