Answer: \(\mathrm{NP}\)-complete.
Corollary 2 — class: hardness
Given a finite candidate set \(C\), committee size \(k\), and rational finite-support distribution \(\mu=(\mu_A)_{A\subseteq C}\) over approval types \(A\subseteq C\), decide whether there exists \(W\subseteq C\) with \(|W|=k\) such that, for every \(\ell\in[k]\) and every subpopulation \(x\) satisfying \(0\le x_A\le\mu_A\), \(\sum_A x_A\ge\ell/k\), and \(x_A>0\Rightarrow R\subseteq A\) for some \(R\subseteq C\) with \(|R|\ge\ell\), we have \(\sum_A x_A|A\cap W|/\sum_A x_A\ge1\).
Given a finite candidate set \(C\), committee size \(k\), and rational masses \((\mu_A)_{A\subseteq C}\) with \(\sum_A\mu_A=1\), a subpopulation is a vector \(x\) with \(0\le x_A\le\mu_A\). It is \(\ell\)-cohesive if \(\sum_Ax_A\ge\ell/k\) and there is an \(R\subseteq C\) with \(|R|\ge\ell\) such that \(x_A>0\) implies \(R\subseteq A\).
A size-\(k\) committee \(W\subseteq C\) has continuous unit proportionality degree if every \(\ell\)-cohesive subpopulation, for every \(\ell\in[k]\), has average satisfaction \(\frac{\sum_Ax_A|A\cap W|}{\sum_Ax_A}\ge1\).
Target. Is deciding whether such a committee \(W\) exists NP-hard, or solvable in polynomial time?
For finite electorates, deciding whether a size-\(k\) committee has unit proportionality degree is NP-complete; equivalently, the constant-unit variant is NP-complete.
No result for the stated mass-distribution formulation is assumed here.
The answer depends on how the mass vector is encoded.
Thus, under the literal full-vector reading of the statement, the answer is polynomial-time solvable. Under the usual sparse-support representation of a distribution, it is NP-hard, indeed \(\mathrm{NP}\)-complete.
Let \(W\) be any size-\(k\) committee.
The committee \(W\) has continuous unit proportionality degree if and only if every \(1\)-cohesive subpopulation has average satisfaction at least \(1\).
One direction is immediate because the definition includes \(\ell=1\).
Conversely, suppose \(x\) is \(\ell\)-cohesive for some \(\ell\geq 1\). Then
\[ \sum_A x_A\geq \frac{\ell}{k}\geq\frac1k. \]
Moreover, there is a nonempty set \(R\) such that every type used by \(x\) contains \(R\). Choosing any \(c\in R\), the same \(x\) is \(1\)-cohesive with common candidate \(c\). Therefore the guarantee for all \(1\)-cohesive subpopulations implies the guarantee for every \(\ell\). \(\square\)
Put \(q=1/k\). For \(c\in C\), consider the approval types containing \(c\). For each such type define its satisfaction
\[ s_A=\lvert A\cap W\rvert. \]
A violating subpopulation supported on these types can be assumed to have mass exactly \(q\). Indeed, if \(x\) has mass \(t\geq q\) and average satisfaction below \(1\), then
\[ x'_A=\frac{q}{t}x_A \]
has mass \(q\), satisfies \(0\leq x'_A\leq\mu_A\), has the same support, and has the same average satisfaction.
For \(j\in\{0,\ldots,k\}\), define
\[ M_{c,j}=\sum_{\substack{A\ni c\\ \lvert A\cap W\rvert=j}}\mu_A. \]
If \(\sum_jM_{c,j}<q\), no \(1\)-cohesive subpopulation with common candidate \(c\) exists. Otherwise let \(r\) be the smallest index such that
\[ \sum_{j=0}^{r}M_{c,j}\geq q. \]
The minimum total satisfaction of a mass-\(q\) subpopulation supported on types containing \(c\) is
\[ P_c= \sum_{j=0}^{r-1}jM_{c,j} + r\left(q-\sum_{j=0}^{r-1}M_{c,j}\right). \]
This is the fractional-knapsack optimum: all available mass with lower satisfaction is taken before any mass with higher satisfaction. An exchange of mass from a higher-satisfaction type to an unused lower-satisfaction type can only decrease the objective.
Consequently,
\[ W\text{ has unit proportionality degree} \quad\Longleftrightarrow\quad P_c\geq q \]
for every \(c\) whose total supporting mass is at least \(q\). This gives a polynomial-time exact verifier for a fixed \(W\).
Let \(m=\lvert C\rvert\), and suppose all \(2^m\) rational entries \(\mu_A\) are explicitly written. Set \(N=2^m\). The input length \(L\) satisfies \(L\geq N\).
There are at most
\[ \binom{m}{k}\leq 2^m=N \]
possible committees. For each committee, the verifier above can compute all quantities \(M_{c,j}\) by scanning the \(N\) entries. A direct implementation uses at most \(O(m^2N)\) rational arithmetic operations per committee, hence at most \(O(m^2N^2)\) operations overall.
Because \(N\leq L\) and \(m\leq\log_2L\), this is polynomial in the explicit full-vector input length. Exact rational sums and comparisons also have polynomial bit complexity.
Therefore the literal dense-vector formulation is in \(\mathrm{P}\).
Now suppose the input lists only the types \(A\) with \(\mu_A>0\).
Membership in \(\mathrm{NP}\) follows by guessing \(W\) and applying the verifier from Section 2 to the listed types.
For hardness, reduce from the standard NP-complete Restricted Exact Cover by \(3\)-Sets problem, abbreviated \(\mathrm{RX3C}\). This is also the regular exact-cover source used in the finite unit-proportionality construction; see [Janeczko and Faliszewski](https://arxiv.org/abs/2207.03518).
An \(\mathrm{RX3C}\) instance consists of
\[ U=\{u_1,\ldots,u_{3h}\} \]
and a family
\[ \mathcal S=\{S_1,\ldots,S_{3h}\} \]
such that every \(S_j\) has size \(3\), every \(u\in U\) belongs to exactly three members of \(\mathcal S\), and the question is whether \(h\) sets form an exact cover of \(U\).
Create one candidate \(c_j\) for each \(S_j\), and set the committee size to \(k=h\).
For every element \(u\in U\), define its approval type
\[ A_u=\{c_j:u\in S_j\}. \]
Because every element occurs in exactly three sets, every \(A_u\) has size \(3\). Assign mass
\[ \mu_A=\frac{\lvert\{u\in U:A_u=A\}\rvert}{3h}. \]
There are at most \(3h\) nonzero types, so this is a polynomial-size sparse instance.
Each candidate \(c_j\) has supporting mass
\[ \sum_{A\ni c_j}\mu_A =\frac{\lvert S_j\rvert}{3h} =\frac1h =\frac1k. \]
If \(\ell\geq2\), an \(\ell\)-cohesive subpopulation would need mass at least \(\ell/h>1/h\). Yet, choosing any \(c_j\) from its common set shows that its total available supporting mass is at most \(1/h\). Hence no such subpopulation exists.
Now consider \(\ell=1\). If \(x\) is cohesive with common set \(R\), choose \(c_j\in R\). All its mass lies among the supporters of \(c_j\), whose total mass is exactly \(1/h\). Since \(x\) must itself have mass at least \(1/h\), it must use all this supporting mass. Thus every relevant cohesive subpopulation is precisely the full supporter population of some candidate \(c_j\).
For a committee \(W\), define
\[ d_W(u)=\lvert\{j:c_j\in W,\ u\in S_j\}\rvert. \]
The average satisfaction of the supporters of \(c_j\) is
\[ \frac13\sum_{u\in S_j}d_W(u). \]
Therefore \(W\) has unit proportionality degree exactly when
\[ \sum_{u\in S_j}d_W(u)\geq3 \]
for every \(j\in\{1,\ldots,3h\}\).
Suppose \(\mathcal T\subseteq\mathcal S\) is an exact cover with \(\lvert\mathcal T\rvert=h\). Select the corresponding candidates. Every \(u\in U\) then belongs to exactly one selected set, so \(d_W(u)=1\). Hence every displayed inequality holds with equality.
Conversely, suppose a size-\(h\) committee \(W\) satisfies all the inequalities. Summing them gives
\[ \sum_{j=1}^{3h}\sum_{u\in S_j}d_W(u) = \sum_{u\in U}3d_W(u), \]
because every element occurs in exactly three sets. Moreover,
\[ \sum_{u\in U}d_W(u) = \sum_{c_j\in W}\lvert S_j\rvert = 3h. \]
Thus the sum of the left-hand sides is exactly \(9h\). There are \(3h\) inequalities, each with lower bound \(3\), so every one must hold with equality.
Consider a selected set \(S_j\). Every \(u\in S_j\) has \(d_W(u)\geq1\), while
\[ \sum_{u\in S_j}d_W(u)=3. \]
Since \(S_j\) contains three elements, each of them has \(d_W(u)=1\). Consequently, no two selected sets intersect. The \(h\) selected sets therefore cover \(3h\) distinct elements, which is all of \(U\). They form an exact cover.
This proves \(\mathrm{NP}\)-hardness, and hence \(\mathrm{NP}\)-completeness, for sparse-support input.
The finite-electorate hardness does survive the continuous relaxation on sparse instances, but not merely by normalization: the reduction works because every candidate has supporting mass exactly \(1/k\), leaving no fractional boundary type.
For the formulation literally giving all masses \((\mu_A)_{A\subseteq C}\), exhaustive enumeration is polynomial in that exponentially long vector. Thus the requested unqualified classification requires an encoding convention.
⟨structured verdict parsed — rendered above⟩
The prover correctly resolves the stated target once the input encoding is distinguished. The dense full-vector formulation is polynomial-time solvable in its explicit input length, while the sparse-support formulation is NP-complete. No substantive gaps or false steps were found.
Lemma 1 is correct.
If \(x\) is \(\ell\)-cohesive, then its mass is at least \(\ell/k\), hence at least \(1/k\). Its common set \(R\) has at least one candidate. Choosing \(c\in R\) makes the same \(x\) a valid \(1\)-cohesive subpopulation. Thus checking all \(1\)-cohesive subpopulations suffices.
All quantifiers and support conditions are preserved.
The scaling argument is valid. For a violating subpopulation of mass \(t\geq q=1/k\), multiplication by \(q/t\) preserves:
The fractional-knapsack calculation is also correct. Since satisfaction values are the integers \(0,\ldots,k\), minimizing total satisfaction at fixed mass \(q\) is achieved by taking all available lower-satisfaction mass before higher-satisfaction mass. The formula for \(P_c\) correctly handles the partially used boundary level \(r\), including \(r=0\).
Every \(1\)-cohesive subpopulation has at least one common candidate \(c\), so checking the minimum for every such \(c\) is both necessary and sufficient. This yields a polynomial-time exact verifier.
Letting \(N=2^m\), the estimate \(\binom{m}{k}\leq N\) is correct. Exhaustively testing every committee therefore requires only polynomially many operations relative to the explicitly written vector length.
The inference \(N\leq L\) and consequently \(m\leq\log_2 L\) is valid when every one of the \(2^m\) entries is explicitly represented. Exact addition and comparison of binary-encoded rationals have polynomial bit complexity because intermediate numerator and denominator lengths grow at most polynomially in the total input length.
Thus the dense formulation is indeed in \( \mathrm{P} \).
A committee is a polynomial-size certificate. The fixed-committee verifier scans only the listed support types and uses exact rational arithmetic of polynomial bit complexity. Membership in NP follows.
The RX3C instance has \(3h\) elements and \(3h\) triples, with each element occurring in exactly three triples.
The construction is polynomial-size. The masses are nonnegative rationals, and their sum is \(1\), since the multiplicities of the types \(A_u\) partition the \(3h\) elements and each contributes mass \(1/(3h)\).
For every candidate \(c_j\), its supporting mass is exactly \(3/(3h)=1/h=1/k\). This remains true when several elements induce the same approval type, because their multiplicities are aggregated in \(\mu_A\).
No \(\ell\)-cohesive subpopulation exists for \(\ell\geq2\): choosing any candidate from its common set bounds its available mass by \(1/h\), whereas cohesiveness requires at least \(\ell/h>1/h\).
For \(\ell=1\), a cohesive subpopulation supported by candidate \(c_j\) must have mass at least \(1/h\), while the entire supporting mass of \(c_j\) is exactly \(1/h\). Hence every capacity on those supporting types must be saturated. Therefore it is precisely the full supporter population of \(c_j\).
This remains correct when the common set contains multiple candidates.
For the supporter population of \(c_j\), each element \(u\in S_j\) contributes equal mass \(1/(3h)\), and its satisfaction is \(d_W(u)\). Dividing total satisfaction by supporting mass \(1/h\) gives
\(\frac13\sum_{u\in S_j}d_W(u)\).
Thus the condition \(\sum_{u\in S_j}d_W(u)\geq3\) is exactly equivalent to unit average satisfaction for that cohesive population.
The forward direction is correct: an exact cover makes every \(d_W(u)=1\), so every inequality holds with equality.
For the reverse direction:
\(\sum_j\sum_{u\in S_j}d_W(u)=3\sum_ud_W(u)\).
\(\sum_ud_W(u)=3h\).
The selected triples form an exact cover. The reduction proves NP-hardness.
The cited arXiv record correctly identifies the referenced Janeczko–Faliszewski paper, although the proof presented here is self-contained apart from the standard NP-completeness of RX3C. [ArXiv record](https://arxiv.org/abs/2207.03518)
The argument is internally consistent and establishes the claimed encoding-dependent classification. No repair is required.
⟨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.