Approval-Based Committee Voting in Practice: A Case Study of (over-)Representation in the Polkadot Blockchain (d4-conf-aaai-2024-1567)

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\).

Let \(C\) be a candidate set with \(|C|=m\), and let \(W\subseteq C\) be a supplied committee with \(|W|=k\), where \(1\le\ell\le k\le m\) are input integers.
A society is given by its support: a list of \(\tau\) distinct approval types \(S\subseteq C\) with positive binary rational masses \(\mu_S\), summing to \(1\). Unlisted types have zero mass; \(\tau\) is the support size, not the number of possible approval sets. Let \(L\) be the total input bit length.
Empty approval sets are allowed. For an integral subset \(X\subseteq W\), define \(a_\mu(X)=\sum_{S:S\cap X\neq\varnothing}\mu_S\). The optimization problem returns any size-\(\ell\) subset minimizing this quantity.
Consider both unrestricted approval types and the restriction \(|S|\le16\) for every supported type.

Is this exact optimization problem solvable in polynomial time in \(m,\tau,L,k,\ell\), or is it NP-hard, for each of these two domains?

For finite weighted approval elections, finding a size-\(\ell\) subset of a supplied committee with minimum joint approval weight is NP-hard; the hardness construction uses approval sets of size two.

Classification

The exact optimization problem is \(\mathrm{NP}\)-hard in both domains, including the restriction \(|S|\le16\). Consequently, a polynomial-time algorithm in the stated input parameters would imply \(\mathrm{P}=\mathrm{NP}\).

We use the finite weighted-election hardness result supplied in the question and prove that its hardness transfers to the normalized support representation.

Reduction to normalized support

Consider a finite weighted approval-election instance with voters indexed by \(i\in\{1,\ldots,n\}\), approval sets \(A_i\subseteq C\), and positive binary rational weights \(w_i\). Retain its candidate set \(C\), supplied committee \(W\), and required subset size \(\ell\).

Let \(T=\sum_{i=1}^n w_i\). For every distinct approval set \(S\) occurring in the instance, define

\(\displaystyle \mu_S=\frac{\sum_{i:A_i=S}w_i}{T}.\)

These masses are positive, and

\(\displaystyle \sum_S\mu_S=\frac{\sum_{i=1}^n w_i}{T}=1.\)

Thus they define a valid instance of the requested problem. Each approval type is listed exactly once, and the support size satisfies \(\tau\le n\).

For every feasible integral subset \(X\subseteq W\) with \(|X|=\ell\), grouping voters by their approval sets gives

\(\displaystyle a_\mu(X)=\sum_{S:S\cap X\ne\varnothing}\mu_S =\frac{1}{T}\sum_{i:A_i\cap X\ne\varnothing}w_i.\)

The factor \(1/T\) is positive and independent of \(X\). Therefore, the ordering of objective values, including all ties, is preserved. In particular, every minimizer returned for the normalized instance is a minimizer for the original finite election.

Polynomial encoding size

It remains to verify that normalization does not produce an excessively large rational encoding.

Write \(w_i=p_i/q_i\), where \(p_i,q_i\) are positive integers represented in binary. Let \(B\) be the total bit length of these integers, and define

\(\displaystyle Q=\prod_{i=1}^n q_i,\qquad z_i=p_i(Q/q_i),\qquad Z=\sum_{i=1}^n z_i.\)

All these quantities are integers, and the constructed masses can be represented as

\(\displaystyle \mu_S=\frac{\sum_{i:A_i=S}z_i}{Z}.\)

The binary length of \(Q\) is at most \(B+1\). Each \(z_i\) has binary length at most \(2B+2\), and \(Z\) has binary length at most \(2B+\lceil\log_2 n\rceil+3\). Every mass numerator is at most \(Z\). Hence each mass has encoding length \(O(B+\log n)\), and all \(\tau\le n\) masses together have polynomial encoding length.

Integer multiplication, exact division, addition, and grouping identical approval sets can all be performed in polynomial time. Reducing fractions to lowest terms, if required by the encoding, also takes polynomial time. The candidate and committee data are unchanged. Thus the complete transformation is polynomial in the original input length.

An optimizer polynomial in \(m,\tau,L,k,\ell\) would consequently yield a polynomial-time optimizer for the supplied \(\mathrm{NP}\)-hard finite-election problem.

Applying the approval-size restriction

The supplied hardness construction uses approval sets of size two. Aggregation and normalization change only weights; they introduce no new approval sets. Therefore, every supported type in the transformed hard instances still satisfies \(|S|=2\), and hence \(|S|\le16\).

This proves hardness for the restricted domain. Since these instances also belong to the unrestricted domain, it proves hardness there as well.

The easy boundary cases do not alter this classification: when \(\ell=1\), one can compare the individual approval masses of the members of \(W\); when \(\ell=k\), the only feasible subset is \(W\). The hardness concerns the general problem with \(k\) and \(\ell\) supplied as input.

⟨structured verdict parsed — rendered above⟩

The classification is correct in substance: the reduction establishes NP-hardness in both domains. There is one minor omission concerning elections with no voters.

• Use of the supplied hardness premise. The prover uses the finite weighted-election hardness statement supplied in USER_TASK, including its restriction to approval sets of size two. This is an authorized premise; an independent hardness construction is unnecessary. Its use assumes the usual explicit finite-election encoding with binary rational weights, which the prover states.

• Validity of the constructed support. Provided \(n\ge1\), positivity of the weights gives \(T>0\). Aggregating identical approval sets produces distinct supported types with positive rational masses summing to \(1\), and \(\tau\le n\). Empty approval sets, if present, cause no difficulty: their masses enter the normalization but contribute to neither objective.

Minor issue: The write-up does not explicitly require \(n\ge1\). If the source problem permits an election with no voters, then \(T=0\) and the displayed normalization is undefined. The minimum clarification is to restrict the source hardness family to nonempty elections, explaining that empty elections are trivial and do not affect hardness.

• Preservation of the optimization objective. The grouping identity is exact:

\[ a_\mu(X)=\frac{1}{T}\sum_{i:A_i\cap X\ne\varnothing}w_i. \]
The feasible subsets are unchanged. Multiplication by the positive constant \(1/T\) preserves every comparison and tie, so any returned optimizer solves the original instance. This establishes the required reduction for an algorithm returning any minimizer.

• Encoding-size calculation. The stated bounds are valid, though loose. The product \(Q\) has binary length at most \(B+1\); each \(z_i=p_i(Q/q_i)\) is an integer of polynomial binary length; summing \(n\) such integers adds at most a logarithmic term. Every constructed numerator is at most \(Z\). Consequently, the total rational encoding length is polynomial in the source input length. The integer operations, grouping, and optional fraction reduction are all polynomial-time operations on these bounded-length inputs.

• Complexity consequence. The transformation preserves candidate and committee data and produces polynomially many bits. Under the stated explicit encoding, the transformed parameters are polynomially bounded in the source input length. Thus an optimizer polynomial in the requested parameters would solve the supplied NP-hard problem in polynomial time.

• Restricted domain. Aggregation and normalization do not change approval sets. Starting from the supplied size-two hardness family therefore produces instances satisfying \(|S|\le16\). This establishes restricted-domain hardness and, by inclusion, unrestricted-domain hardness.

• Boundary cases. The claims for \(\ell=1\) and \(\ell=k\) are correct. They do not conflict with hardness when \(k\) and \(\ell\) vary as inputs.

No false central step or substantive missing lemma was found. The only requested repair is an explicit treatment of the nonempty-source assumption.

⟨structured verdict parsed — rendered above⟩