Answer: \(\mathrm{NP}\text{-complete}\), and therefore \(\mathrm{NP}\text{-hard}\)
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven an instance and a committee W, the PSC value of W can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates C, committee size k, an explicit finite set T of top-truncated ordinal ballot types with rational masses mu, and a committee W of size k, compute the infimum alpha such that every solid coalition of mass at least alpha times ell/k contains at least min(|C'|,ell) members of W for every candidate set C' and ell in [k].
Definitions. An input consists of candidates \(C\), a committee size \(k\), finitely many top-truncated ranking types \(T\), rational masses \(\mu_t\geq 0\) with \(\sum_{t\in T}\mu_t=1\), and rational \(0<\alpha<1\). A type strictly ranks a listed subset of \(C\), places every listed candidate above every unlisted candidate, and is indifferent among unlisted candidates.
For \(S\subseteq C\), let \(M(S)\) be the total mass of types that strictly rank every candidate in \(S\) above every candidate in \(C\setminus S\). A committee \(W\subseteq C\) with \(|W|=k\) is feasible if, for every \(S\subseteq C\) and \(\ell\in[k]\), \(M(S)\geq \alpha\ell/k\) implies \(|W\cap S|\geq\min(|S|,\ell)\).
Target. Is deciding whether a feasible integral committee exists NP-hard or solvable in polynomial time?
Nearest known results. With a finite list of voters in place of rational type masses, deciding satisfiability of \(\alpha\)-PSC for input \(\alpha<1\) is NP-complete. No result for the exact mass-profile formulation was verified.
The rational mass-profile problem is \(\mathrm{NP}\)-complete, and hence \(\mathrm{NP}\)-hard. Therefore, a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The only external ingredient is the finite-voter result stated in the question: for rational \(0<\alpha<1\), deciding whether an \(\alpha\)-PSC committee exists is \(\mathrm{NP}\)-complete for explicitly listed voters with strict rankings. This is Theorem \(2\) of [Bardal, Brill, McCune, and Peters](https://www.ac.tuwien.ac.at/comsoc2025/comsoc2025-papers/89.pdf).
Consider a finite profile \(V=\{1,\ldots,n\}\). For every \(S\subseteq C\), define
\(A_V(S)=\{i\in V : i\text{ strictly ranks every candidate in }S\text{ above every candidate in }C\setminus S\}\).
Thus \(A_V(S)\) is the maximal group of voters solidly supporting \(S\).
The usual finite-voter definition quantifies over every coalition \(X\subseteq A_V(S)\). This is equivalent to considering only \(A_V(S)\):
Consequently, a committee \(W\) satisfies finite-voter \(\alpha\)-PSC exactly when, for every \(S\subseteq C\) and \(\ell\in[k]\),
\(|A_V(S)|/n\geq\alpha\ell/k\)
implies
\(|W\cap S|\geq\min(|S|,\ell)\).
Take an instance of the finite-voter problem. Let \(T\) be the set of distinct rankings occurring among the \(n\) voters. For each \(t\in T\), let \(n_t\) be the number of voters having ranking \(t\), and define
\(\mu_t=n_t/n\).
These masses are nonnegative rationals and satisfy \(\sum_{t\in T}\mu_t=1\). Copy \(C\), \(k\), and \(\alpha\) unchanged.
Every complete strict ranking is an allowed top-truncated type: it is obtained by listing all candidates. Hence the hard finite instances lie inside the target domain.
For every \(S\subseteq C\), the mass in the constructed instance is
\(M(S)=\sum_{t:\,t\text{ supports }S}n_t/n=|A_V(S)|/n\).
Therefore, for every committee \(W\), every \(S\subseteq C\), and every \(\ell\in[k]\), the mass-profile constraint is identical to the corresponding finite-voter constraint. It follows that
\(W\text{ is feasible in the mass profile}\)
if and only if
\(W\text{ satisfies finite-voter }\alpha\text{-PSC}\).
In particular, the two instances have the same answer to the committee-existence question.
The transformation is polynomial-time. Identical rankings can be grouped by sorting or hashing their explicit encodings. There are at most \(n\) resulting types, and each rational \(n_t/n\) has \(O(\log n)\) bits. Thus this is a polynomial many-one reduction, proving \(\mathrm{NP}\)-hardness.
If the finite formulation permits committees of size at most \(k\), this creates no mismatch: any feasible committee of size less than \(k\) can be padded to size exactly \(k\), and adding candidates cannot violate any lower-bound constraint.
It remains to establish membership in \(\mathrm{NP}\), since the definition apparently contains exponentially many sets \(S\).
For a type \(t\), write its listed ranking as
\(c^t_1\succ_t c^t_2\succ_t\cdots\succ_t c^t_{r_t}\),
with all remaining candidates tied below the listed candidates. Define its nonempty prefixes by
\(P_{t,j}=\{c^t_1,\ldots,c^t_j\}\)
for \(1\leq j\leq r_t\).
If \(\varnothing\neq S\subsetneq C\) and type \(t\) strictly ranks every member of \(S\) above every member of \(C\setminus S\), then \(S=P_{t,j}\) for some \(j\).
Indeed:
Hence \(S\) is a prefix.
Let
\(\mathcal F=\{P_{t,j}:t\in T,\ 1\leq j\leq r_t\}\).
Then \(|\mathcal F|\leq\sum_{t\in T}r_t\leq |T||C|\).
Because \(\alpha>0\) and \(\ell\geq1\), every triggered constraint has \(M(S)>0\). Apart from \(S=\varnothing\) and \(S=C\), the prefix lemma implies that every such \(S\) belongs to \(\mathcal F\). The omitted cases are harmless:
A verifier can therefore enumerate \(\mathcal F\), compute \(M(S)\) for each \(S\in\mathcal F\), and check all \(\ell\in[k]\). If \(k>|C|\), it rejects immediately; otherwise \(k\leq|C|\), so this enumeration is polynomial. Exact sums and comparisons of binary-encoded rationals also take polynomial bit complexity.
Thus feasibility of a given committee is decidable in polynomial time. A committee \(W\) is a polynomial-size certificate, so the existence problem belongs to \(\mathrm{NP}\).
The rational mass-profile formulation does not remove the finite problem’s hardness: normalizing and aggregating voter multiplicities preserves every solid-coalition constraint exactly. Together with polynomial verification, this proves that the target problem is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed \(\mathrm{NP}\)-completeness in substance. The reduction preserves every relevant coalition constraint, and the proposed verifier correctly reduces the exponentially quantified family of sets to polynomially many ballot prefixes.
Two minor clarifications are required. Neither needs new mathematics.
The cited paper does state that deciding satisfiability of \(\alpha\)-PSC for \(\alpha<1\) is \(\mathrm{NP}\)-complete. Its underlying preference model is explicitly top-truncated rankings, with ranked candidates strictly ordered and unranked candidates tied below them—not explicitly the complete-ranking restriction suggested by the prover. See [Theorem 2 and the paper’s definitions](https://www.ac.tuwien.ac.at/comsoc2025/comsoc2025-papers/89.pdf).
The sentence
“Every complete strict ranking is an allowed top-truncated type: it is obtained by listing all candidates. Hence the hard finite instances lie inside the target domain.”
does not follow from the cited theorem unless hardness for complete rankings is separately established. The cited hard instances themselves use top-truncated ballots. Since the target also allows exactly such ballots, this is a domain-description issue rather than a substantive obstacle. The write-up must say explicitly that source ballots are preserved as top-truncated types, or cite a hardness theorem restricted to complete rankings.
For fixed \(S\) and \(\ell\), replacing all solid coalitions \(X\subseteq A_V(S)\) by the maximal coalition \(A_V(S)\) is correct:
The consequent depends only on \(S\), \(\ell\), and \(W\), so enlargement introduces no mismatch.
Grouping identical voter types and assigning \(\mu_t=n_t/n\) is correct. For every \(S\),
\[ M(S)=\frac{|A_V(S)|}{n}. \]
Thus the antecedents and consequents of all finite-voter and mass-profile constraints coincide committee by committee.
The encoding-size argument is also correct: there are at most \(n\) types and each multiplicity ratio has polynomial bit length. Padding a committee from size at most \(k\) to exactly \(k\) preserves every lower-bound constraint.
The prefix lemma is correct for every nonempty proper \(S\):
This covers empty listed sets and fully listed ballots as well.
Because \(\alpha>0\), \(k\geq1\), and \(\ell\geq1\), every triggered constraint has \(M(S)>0\). Hence at least one positive-mass type supports \(S\), and the prefix lemma places every nontrivial such \(S\) in \(\mathcal F\). The bound \(|\mathcal F|\leq |T||C|\) is valid.
For \(S=C\), the consequent is \(k\geq\ell\), so the constraint is automatic.
For \(S=\varnothing\), the conclusion is indeed \(0\geq0\), but \(M(\varnothing)=1\) under the stated universal definition, not \(0\). The prover’s wording “the required inequality is \(0\geq0\)” is acceptable only if it refers to the consequent. This should be made explicit.
After rejecting \(k>|C|\), enumerating all \(\ell\in[k]\) and all members of \(\mathcal F\) is polynomial. Testing whether a type supports a given prefix and summing binary-encoded rational masses can also be done in polynomial bit complexity.
Therefore feasibility has polynomial certificates, giving membership in \(\mathrm{NP}\).
The reduction and membership argument are sound. The result is \(\mathrm{NP}\)-complete, subject only to correcting the source-domain description and clarifying the vacuous \(S=\varnothing\) case.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.