Answer: \(\mathrm{NP}\)-hard exactly; for every fixed \(\varepsilon\in(0,1/2)\), obtaining welfare at least \(\mathrm{OPT}/k^{1/2-\varepsilon}\) is also \(\mathrm{NP}\)-hard.
Theorem 4.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any ε ∈(0, 1/2), the following problem is NP-hard:2 Given an instance I = (C, A, k), find a com- mittee W ∈JR(I) such that sw(W) ≥swJR(I)/k1/2−ε. This problem remains NP-hard even if k = n/2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), committee size \(k\), nonempty approval types \(A_1,\ldots,A_\tau\subseteq C\), and rational masses \(\mu_t\ge0\) summing to \(1\), choose \(W\subseteq C\) with \(|W|=k\) maximizing \(\mathrm{sw}_\mu(W)=\sum_{t=1}^{\tau}\mu_t|A_t\cap W|\), subject to \(\sum_{t:\,c\in A_t,\;A_t\cap W=\varnothing}\mu_t<1/k\) for every \(c\in C\); also study the fixed-\(\varepsilon\) approximation version with \(\varepsilon\in(0,1/2)\).
Given a finite candidate set \(C\), \(k\le |C|\), nonempty approval types \(A_1,\ldots,A_\tau\subseteq C\), and rational masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), a size-\(k\) committee \(W\) has welfare \(\mathrm{sw}_\mu(W)=\sum_{t=1}^{\tau}\mu_t|A_t\cap W|\). It provides mass-JR if, for every \(c\in C\), \(\sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t<1/k\).
Target. Is maximizing \(\mathrm{sw}_\mu(W)\) over mass-JR committees solvable in polynomial time, or is it NP-hard? For every fixed \(\varepsilon\in(0,1/2)\), is finding a mass-JR committee with welfare at least \(1/k^{1/2-\varepsilon}\) times optimum in polynomial time, or is this approximation problem NP-hard?
Nearest known results. For finite lists of voters, maximizing utilitarian social welfare subject to JR is NP-hard to approximate within a factor \(k^{1/2-\varepsilon}\) for every fixed \(\varepsilon\in(0,1/2)\), even when the number of voters is \(2k\).
Both problems are \( \mathrm{NP} \)-hard. More precisely, for every fixed \( \varepsilon\in(0,1/2) \), a polynomial-time algorithm that always returns a mass-JR committee \(W\) satisfying
\( \mathrm{sw}_{\mu}(W)\geq \mathrm{OPT}_{\mu}/k^{1/2-\varepsilon} \)
would imply \( \mathrm{P}=\mathrm{NP} \). The hardness already holds when there are at most \(2k\) positive-mass types and every mass is an integer multiple of \(1/(2k)\).
Consider a finite approval election
\(I=(C,(B_i)_{i\in[n]},k)\),
where every ballot \(B_i\) is nonempty. For a size-\(k\) committee \(W\) and candidate \(c\), define
\(U_c(W)=\{i\in[n]:c\in B_i,\ B_i\cap W=\varnothing\}\).
Thus, \(U_c(W)\) is the set of unrepresented voters approving \(c\).
The committee \(W\) provides finite-voter JR if and only if
\(\lvert U_c(W)\rvert<n/k\)
for every \(c\in C\).
Suppose first that \(\lvert U_c(W)\rvert\geq n/k\) for some \(c\). The voters in \(U_c(W)\) form a group of size at least \(n/k\), all approve \(c\), and every one of them is unrepresented. Hence \(W\) violates JR.
Conversely, suppose \(W\) violates JR. Then there is a group \(X\subseteq[n]\) with \(\lvert X\rvert\geq n/k\), a candidate \(c\in\bigcap_{i\in X}B_i\), and \(B_i\cap W=\varnothing\) for every \(i\in X\). Therefore \(X\subseteq U_c(W)\), so \(\lvert U_c(W)\rvert\geq n/k\). This proves the equivalence. \( \square \)
Partition the voters according to identical approval ballots. Let the distinct ballots be \(A_1,\ldots,A_\tau\), and let
\(q_t=\lvert\{i:B_i=A_t\}\rvert\).
Define the mass instance by
\(\mu_t=q_t/n\).
These masses are positive rational numbers, satisfy \(\sum_t\mu_t=1\), and all approval types are nonempty. Moreover, \(\tau\leq n\), and the construction is polynomial-time.
For every committee \(W\) and candidate \(c\),
\[ \sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t = \frac{1}{n} \left\lvert \{i:c\in B_i,\ B_i\cap W=\varnothing\} \right\rvert = \frac{\lvert U_c(W)\rvert}{n}. \]
Consequently,
\[ \sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t<\frac1k \quad\Longleftrightarrow\quad \lvert U_c(W)\rvert<\frac nk. \]
By the lemma, \(W\) is mass-JR in the constructed instance if and only if \(W\) is JR in the original finite election.
The strict inequality causes no discrepancy. In the hard instances with \(n=2k\), the condition becomes \(\lvert U_c(W)\rvert<2\), exactly excluding the finite-JR violations consisting of at least two unrepresented voters with a common approved candidate.
Let the unnormalized finite-voter welfare be
\(\mathrm{SW}_I(W)=\sum_{i=1}^{n}\lvert B_i\cap W\rvert\).
Then
\[ \mathrm{sw}_{\mu}(W) = \sum_{t=1}^{\tau}\frac{q_t}{n}\lvert A_t\cap W\rvert = \frac1n\sum_{i=1}^{n}\lvert B_i\cap W\rvert = \frac{\mathrm{SW}_I(W)}n. \]
Since the feasible committee families are identical,
\(\mathrm{OPT}_{\mu}=\mathrm{OPT}_{I}/n\).
Therefore every committee has exactly the same approximation ratio in the two instances:
\[ \frac{\mathrm{sw}_{\mu}(W)}{\mathrm{OPT}_{\mu}} = \frac{\mathrm{SW}_I(W)}{\mathrm{OPT}_{I}}. \]
The finite-voter theorem states that, for every fixed \(\varepsilon\in(0,1/2)\), finding a JR committee with welfare at least \(\mathrm{OPT}_{I}/k^{1/2-\varepsilon}\) is \( \mathrm{NP} \)-hard even when \(n=2k\). Its model explicitly requires all approval ballots to be nonempty, so every resulting type is admissible here. See Theorem 4.1 of [Elkind et al., *The Price of Justified Representation*](https://arxiv.org/abs/2112.05994).
Suppose there were a polynomial-time algorithm for the mass problem with guarantee
\(\mathrm{sw}_{\mu}(W)\geq\mathrm{OPT}_{\mu}/k^{1/2-\varepsilon}\).
Apply the aggregation reduction to a hard finite instance with \(n=2k\). The returned committee is finite-voter JR, and multiplying its guarantee by \(n\) gives
\(\mathrm{SW}_I(W)\geq\mathrm{OPT}_{I}/k^{1/2-\varepsilon}\),
contradicting the finite-voter hardness theorem unless \(\mathrm{P}=\mathrm{NP}\).
Thus the approximation problem is \( \mathrm{NP} \)-hard. Exact maximization is also \( \mathrm{NP} \)-hard, because an exact polynomial-time algorithm would in particular satisfy this approximation guarantee.
⟨structured verdict parsed — rendered above⟩
The prover correctly resolves both targets. The reduction from finite-voter JR to mass-JR preserves the feasible committees, welfare up to a common positive scaling factor, and therefore all approximation ratios. The cited hardness theorem has the stated hypotheses: nonempty ballots, approximation factor \(k^{1/2-\varepsilon}\), and hardness even when \(n=2k\). See [Theorem 4.1 and its setting](https://arxiv.org/html/2112.05994v2#S4.SS1).
A finite-JR violation is precisely a cohesive group \(X\) with \(\lvert X\rvert\ge n/k\) whose members are all unrepresented. Choosing a common approved candidate \(c\) gives \(X\subseteq U_c(W)\). Conversely, if \(\lvert U_c(W)\rvert\ge n/k\), then \(U_c(W)\) itself is a cohesive, unrepresented group. This remains valid when \(n/k\) is nonintegral because \(\lvert U_c(W)\rvert\) is integral.
Grouping identical ballots and assigning mass \(\mu_t=q_t/n\) produces legal nonempty types with positive rational masses summing to \(1\). The construction has at most \(n\) types and polynomial encoding length.
For each candidate \(c\),
\[ \sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t = \frac{\lvert U_c(W)\rvert}{n}. \]
Hence the mass-JR inequality is equivalent to \(\lvert U_c(W)\rvert<n/k\), exactly the finite-JR characterization. The strict inequality is handled correctly. When \(n=2k\), it becomes \(\lvert U_c(W)\rvert<2\).
The equality \(\mathrm{sw}_\mu(W)=\mathrm{SW}_I(W)/n\) follows directly from multiplicities. Because the feasible committee families coincide, the optima differ by the same factor \(1/n\), so approximation ratios are identical.
The cited theorem states that, for every fixed \(\varepsilon\in(0,1/2)\), finding a JR committee with welfare at least the JR optimum divided by \(k^{1/2-\varepsilon}\) is NP-hard, even for \(n=2k\). Its underlying model requires nonempty approval ballots. These are precisely the hypotheses used by the aggregation reduction.
With \(n=2k\), every resulting mass is \(q_t/(2k)\), hence an integer multiple of \(1/(2k)\), and there are at most \(2k\) positive-mass types.
An exact polynomial-time optimizer would return an optimal mass-JR committee and therefore satisfy the forbidden approximation guarantee for any fixed admissible \(\varepsilon\). Thus exact maximization is NP-hard as claimed.
No unjustified mathematical steps, missing hypotheses, or relevant edge-case failures were found.
⟨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.