Answer: There exists an absolute constant \(c>0\) for which attaining a \(c\log\Delta/\Delta\)-approximation is NP-hard, even with uniform positive rational masses and an explicit feasible committee.
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateA fea- sible constrained multiwinner voting problem that satisfies ℓi = 0 for each i ∈[p] is NP-hard to approximate within a factor of Ω(log ∆/∆). The reduction is from maximum ∆-hypergraph matching, which is hard to approximate within a factor of Ω(log ∆/∆) [Hazan et al., 2003] and works even when the scoring func- tion is the SNTV rule.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), candidate groups \(P_1,\ldots,P_p\), upper bounds \(u_i\), and a rational distribution \(\mu\) over complete ranking types, promised that some committee \(S\) with \(|S|=k\) satisfies \(|S\cap P_i|\le u_i\), compute or approximate a feasible committee maximizing \(\operatorname{score}_\mu(S)=\sum_t\mu_t\mathbf{1}[\operatorname{top}(t)\in S]\), with complexity measured in the type representation and mass encoding.
Given a candidate set \(C\) of size \(m\), an integer \(1\le k\le m\), explicitly listed, possibly overlapping groups \(P_1,\ldots,P_p\subseteq C\), and binary-encoded bounds \(u_i\in\mathbb Z_{\ge0}\), define \(\Delta=\max_{c\in C}|\{i:c\in P_i\}|\); consider \(\Delta\ge3\).
A society is given by its support: the list of \(\tau\) distinct complete strict ranking types with positive masses \(\mu_t\) encoded as binary rationals, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings.
A committee is a subset \(S\subseteq C\) with \(|S|=k\); it is feasible when \(|S\cap P_i|\le u_i\) for every \(i\). Feasibility is promised. Candidates may belong to no group.
Its SNTV score is \(\operatorname{score}_\mu(S)=\sum_t\mu_t\mathbf1[\operatorname{top}(t)\in S]\), where \(\operatorname{top}(t)\) is the first-ranked candidate. Let \(\mathrm{OPT}\) be the maximum feasible score. A \(\rho\)-approximation returns a feasible committee of score at least \(\rho\mathrm{OPT}\), with no constraint violations.
State running times in \(m,\tau,L,p,k,\Delta\), where \(L\) is the total input bit length.
Is there an absolute constant \(c>0\) for which attaining a \(c\log\Delta/\Delta\)-approximation is NP-hard, or is this ratio attainable in polynomial time for every fixed \(c>0\), on instances where \(c\log\Delta/\Delta\le1\)?
For finite electorates, feasible upper-bound-constrained SNTV committee selection is NP-hard to approximate at the \(\Omega(\log\Delta/\Delta)\) scale. [Source](https://arxiv.org/html/1710.10057v2).
No separate result for exactly the rational-mass formulation was identified in the sources checked.
There is an absolute constant \(c>0\) for which attaining a \(c\log\Delta/\Delta\)-approximation is NP-hard. This holds even when all positive masses are equal, all upper bounds equal \(1\), and an explicit feasible committee is available.
Thus, unless \(\mathrm{P}=\mathrm{NP}\), the ratio is not polynomial-time attainable for every fixed \(c>0\). Throughout, \(\log\) denotes the natural logarithm; changing its base only changes the constant.
A matching in a hypergraph is a collection of pairwise disjoint hyperedges. Write \(\nu(H)\) for its maximum cardinality.
Hazan, Safra, and Schwartz prove that maximum matching in explicitly represented \(d\)-uniform hypergraphs is NP-hard to approximate within a multiplicative factor at the \(d/\log d\) scale. Consequently, there is an absolute constant \(a>0\) such that attaining a matching of size at least \(\nu(H)/(a d/\log d)\) is NP-hard for an unbounded family of uniformities \(d\). [Hazan–Safra–Schwartz](https://doi.org/10.1007/s00037-006-0205-6).
We construct a reduction preserving approximation guarantees exactly. It makes explicit the normalization and committee-size choices in the cited finite-electorate reduction. [Celis–Huang–Vishnoi, Theorem 11](https://arxiv.org/html/1710.10057v2#Thmtheorem11).
Let \(H=(V,E)\) be a \(d\)-uniform hypergraph, with \(E=\{e_1,\ldots,e_q\}\), \(q\ge1\), and \(d\ge3\).
Create the candidate set
\(\displaystyle C=\{c_1,\ldots,c_q\}\cup\{b_1,\ldots,b_q\}.\)
Here \(c_j\) represents \(e_j\), and the \(b_j\) are filler candidates. Set the required committee size to \(k=q\).
For every vertex \(v\in V\), create the group
\(\displaystyle P_v=\{c_j:v\in e_j\},\qquad u_v=1.\)
No filler belongs to any group. Each \(c_j\) belongs to exactly \(d\) indexed groups, so the constructed instance has \(\Delta=d\). Moreover, \(\{b_1,\ldots,b_q\}\) is an explicit feasible committee.
For each \(j\), create one complete strict ranking \(R_j\): rank \(c_j\) first, followed by every remaining candidate in a fixed order. Give this ranking mass
\(\displaystyle \mu_j=\frac1q.\)
These rankings are distinct because their first-ranked candidates differ. All masses are positive binary rationals and sum to \(1\). Thus the support size is exactly \(\tau=q\).
For every committee \(S\),
\(\displaystyle \operatorname{score}_\mu(S)=\frac{|S\cap\{c_1,\ldots,c_q\}|}{q}.\)
For a feasible committee \(S\), define
\(\displaystyle M(S)=\{e_j:c_j\in S\}.\)
This is a matching. Indeed, if two selected hyperedges shared a vertex \(v\), their corresponding candidates would both belong to \(P_v\), contradicting \(u_v=1\). Consequently,
\(\displaystyle |M(S)|=q\,\operatorname{score}_\mu(S)\le\nu(H).\)
Conversely, let \(M\) be any matching of size \(r\). Select its \(r\) corresponding candidates and any \(q-r\) distinct fillers. This yields a committee of size exactly \(q\). Its group constraints hold because the hyperedges in \(M\) are disjoint and the fillers belong to no groups. Its score is \(r/q\).
Applying both directions to optimal solutions proves
\(\displaystyle \mathrm{OPT}=\frac{\nu(H)}q.\)
Therefore, a feasible \(\rho\)-approximate committee yields a matching satisfying
\(\displaystyle |M(S)|=q\,\operatorname{score}_\mu(S)\ge q\rho\,\mathrm{OPT}=\rho\,\nu(H).\)
There is no additive loss or change in the approximation ratio.
Choose \(c=2/a\), where \(a\) is the hardness constant above. An algorithm with the requested guarantee would produce a matching of size at least
\(\displaystyle c\frac{\log d}{d}\nu(H)=2\frac{\log d}{a d}\nu(H),\)
which is stronger than the guarantee excluded by the hardness theorem.
Furthermore, \(c\log d/d\) tends to \(0\) as \(d\) grows. Hence \(c\log d/d\le1\) for all sufficiently large \(d\). The unbounded hard family therefore remains within the question’s restricted domain after discarding finitely many uniformities. This proves the claimed hardness.
Write \(r=|V|\) and \(L_H\) for the bit length of an explicitly indexed hypergraph input. The constructed parameters are
\(\displaystyle m=2q,\qquad \tau=q,\qquad p=r,\qquad k=q,\qquad \Delta=d.\)
There are \(\tau m\) ranking entries and \(q d\) group-incidence entries. Each mass requires \(O(\log(q+1))\) bits. With ordinary indexed-list encodings, the output length satisfies
\(\displaystyle L=O\!\left((\tau m+m\Delta+p)\log(m+p+2)\right),\)
which is polynomial in \(L_H\). The construction takes \(O(L_H+L)\) bit operations; extracting the matching takes \(O(m\log(m+1))\) bit operations.
Thus an algorithm running in time \(T(m,\tau,L,p,k,\Delta)\) would give a hypergraph-matching algorithm running in
\(\displaystyle T(2q,q,L,r,q,d)+O(L_H+L).\)
In particular, polynomial time in the listed parameters would imply polynomial time in the source input length, contradicting the stated hardness unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output proves the claimed hardness. The reduction is correct, preserves the approximation guarantee exactly, satisfies the feasibility promise, and has polynomial output size. No major or minor mathematical issues were found.
The source problem is maximum matching in an explicitly represented uniform hypergraph, equivalently maximum uniform set packing. The cited Hazan–Safra–Schwartz result establishes NP-hardness of approximation at the multiplicative-factor scale \(d/\log d\). This is confirmed by the [published paper](https://doi.org/10.1007/s00037-006-0205-6) and Theorem 4.2 in [Schwartz’s thesis](https://www.cs.tau.ac.il/~amnon/Students/oded.schwartz.thesis.pdf).
The prover translates this into a retained-score guarantee correctly: for some absolute \(a>0\), attaining at least
\[
\frac{\log d}{ad}\nu(H)
\]
is NP-hard on an unbounded family of uniformities. A numerical value of \(a\) is unnecessary because the task asks only for existence of an absolute constant.
The additional citation to [Celis–Huang–Vishnoi, Theorem 11](https://arxiv.org/html/1710.10057v2#Thmtheorem11) is consistent with the reduction. The prover supplies its own complete correspondence, so correctness does not depend on omitted details of that cited construction.
For \(q\ge1\), the construction gives \(m=2q\) and \(k=q\), hence \(1\le k\le m\).
Each edge candidate belongs to exactly \(d\) indexed vertex groups. Fillers belong to none. Consequently, \(\Delta=d\), including when different vertices induce identical group subsets: the task counts indexed groups.
All upper bounds are the permitted nonnegative integer \(1\). The \(q\) fillers form an explicitly available feasible committee, so the reduction respects the feasibility promise.
Each ranking lists all candidates exactly once and has a different first-ranked candidate. Thus the rankings are complete, strict, and distinct, and the support size is exactly \(\tau=q\).
The masses \(1/q\) are positive, sum to \(1\), and have binary numerator–denominator encodings of length \(O(\log(q+1))\). “Binary-encoded rationals” does not require terminating binary expansions.
The case \(q=1\) also satisfies these claims.
Each edge candidate is first-ranked in exactly one supported type, with mass \(1/q\); no filler is first-ranked. Therefore every committee satisfies
\[
\operatorname{score}_{\mu}(S)
=\frac{|S\cap\{c_1,\ldots,c_q\}|}{q}.
\]
No other ranking positions affect SNTV score.
If two selected edge candidates represented intersecting hyperedges, their common vertex group would contain two selected candidates, violating its upper bound \(1\). Hence the extracted edges form a matching, with
\[
|M(S)|=q\,\operatorname{score}_{\mu}(S)\le\nu(H).
\]
Conversely, a matching of size \(r\le q\) can be supplemented with \(q-r\) distinct fillers. The resulting committee has exactly the required size and satisfies every group constraint.
Both directions therefore justify
\[
\mathrm{OPT}=\frac{\nu(H)}q.
\]
A feasible committee meeting the guarantee \(\operatorname{score}_{\mu}(S)\ge\rho\mathrm{OPT}\) yields
\[
|M(S)|\ge\rho\nu(H).
\]
There is no rounding, additive loss, or feasibility violation in this extraction.
With \(c=2/a\), the requested guarantee is twice the retained fraction excluded by the cited hardness theorem. This avoids any issue about equality at a hardness threshold.
For this fixed positive \(c\), \(c\log d/d\) tends to \(0\). Thus all sufficiently large uniformities in the unbounded hard family satisfy the task’s restriction \(c\log d/d\le1\). The restriction does not remove the hardness.
The conclusion concerns existence of one hard constant; the prover does not incorrectly claim hardness for every positive constant.
The parameter identities
\[
m=2q,\qquad \tau=q,\qquad p=|V|,\qquad k=q,\qquad \Delta=d
\]
are correct.
There are \(\tau m\) ranking entries and \(qd\) group incidences. The stated output-length bound accounts for these entries, the groups, and the rational masses. Under the explicitly indexed input representation stated by the prover, it is polynomial in the source input length.
The construction and extraction bounds are compatible with indexed-list processing. Consequently, the displayed composed running time establishes that a polynomial-time target algorithm would give a polynomial-time source approximation algorithm.
None. The output resolves the rational-mass formulation and the requested complexity alternative.
⟨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.