Answer: \(\mathrm{NP}\)-complete when \(k\) is part of the input, already for \(d=1\) and \(k\ge 3\).
Lemma 5.10 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateJustified committee with highest AV problem is NP- complete for 𝑘≥2 ∧𝑑≥2 and 𝑘≥3 ∧𝑑= 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\) with attribute values \(c[j]\in D_j\), committee size \(k\), dimensions \(j\in[1,d]\), and \(\tau\) complete voter types \(t=(A_t^1,\ldots,A_t^d)\) with positive rational masses \(\mu_t\) summing to \(1\), define \(U_W=\{t:\forall c\in W,\forall j,\ c[j]\notin A_t^j\}\). For each candidate-realizable value \(a\in D_j^C=\{c[j]:c\in C\}\), require \(\sum_{t\in U_W:\,a\in A_t^j}\mu_t<1/k\). Given a rational threshold \(q\), decide whether there is a committee \(W\subseteq C\), \(|W|=k\), satisfying these SJR constraints and \(\mathrm{AV}_\mu(W)=\frac{1}{d}\sum_t\mu_t\sum_{c\in W}\sum_{j=1}^d\mathbf{1}[c[j]\in A_t^j]\ge q\).
Let \(C\) be an explicitly listed set of \(m\) distinct candidates, each with \(d\ge 1\) attribute values \(c[j]\). Let \(1\le k\le m\) be an input integer. Candidates may share attribute vectors. For each dimension use the finite domain \(D_j=\{c[j]:c\in C\}\).
A society is given by its support: an explicit list of \(\tau\) distinct complete types \(t=(A_t^1,\ldots,A_t^d)\), with explicitly listed approval sets \(A_t^j\subseteq D_j\) (possibly empty) and positive binary rational masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total binary input length, including a rational threshold \(q\in\mathbb Q\).
For a committee \(W\subseteq C\) with \(|W|=k\), define \(U_W=\{t:\forall c\in W\;\forall j\in\{1,\ldots,d\},\ c[j]\notin A_t^j\}\). It satisfies simple justified representation (SJR) precisely when \(\sum_{t\in U_W:\,a\in A_t^j}\mu_t<1/k\) for every dimension \(j\) and every \(a\in D_j\).
Define \(\mathrm{AV}_\mu(W)=\frac1d\sum_t\mu_t\sum_{c\in W}\sum_{j=1}^d\mathbf1\{c[j]\in A_t^j\}\); approvals count separately for every selected candidate and dimension, even when attribute values coincide. The decision problem asks whether such an SJR committee exists with \(\mathrm{AV}_\mu(W)\ge q\).
Is this decision problem solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,d,k,L\).
For explicitly listed individual voters, the SJR committee decision problem with an AV threshold is NP-complete when \(k\) is part of the input, including the restriction \(d=1,\ k\ge3\); hardness is also asserted for the regime \(d\ge2,\ k\ge2\). [Kagita et al.](https://cgi.cse.unsw.edu.au/~haziz/commt-attribute.pdf)
No prior result for exactly the rational-mass formulation above was identified in the literature search.
The problem is \(\mathrm{NP}\)-complete when \(k\) is part of the input, already for \(d=1\) and \(k\ge 3\).
This follows by a polynomial reduction from the individual-voter problem stated in the question. The requirement that support types be distinct is handled by merging identical voters and retaining their multiplicities as rational masses.
Every fixed \(k\) admits a polynomial-time algorithm. In particular, hardness for a regime allowing \(k\ge 2\) does not mean hardness for the fixed value \(k=2\).
Write each mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive integers. Define
\(B=\prod_{t=1}^{\tau}b_t,\qquad w_t=a_t(B/b_t).\)
Then \(w_t\) are positive integers, \(\mu_t=w_t/B\), and \(\sum_t w_t=B\). Since the denominators are explicitly encoded, the binary length of \(B\) is at most the sum of their binary lengths, hence is \(O(L)\).
Preprocess approval membership into Boolean tables. For each candidate define the integer score
\(s_c=\sum_{t=1}^{\tau}w_t\sum_{j=1}^{d}\mathbf 1\{c[j]\in A_t^j\}.\)
The objective is additive:
\(\mathrm{AV}_{\mu}(W)=\dfrac{\sum_{c\in W}s_c}{dB}.\)
This identity counts every selected candidate separately, including candidates with equal attribute vectors.
A certificate consists of \(k\) distinct candidate identifiers. Given it, compute \(U_W\) by checking the selected candidates against each type’s approvals. For every dimension and domain value, compute
\(z_{j,a}(W)=\sum_{\substack{t\in U_W\\a\in A_t^j}}w_t.\)
The SJR condition is exactly
\(kz_{j,a}(W)<B\qquad\text{for every }j\text{ and }a\in D_j.\)
Thus the strict inequalities are tested exactly. If \(q=u/v\), with \(v>0\), the score condition is exactly
\(v\sum_{c\in W}s_c\ge udB.\)
All integers in these calculations have \(O(L)\) bits: in particular, \(s_c\le dB\) and \(\sum_{c\in W}s_c\le kdB\).
There are at most \(md\) dimension–value pairs. Using elementary integer arithmetic, a conservative bound for preprocessing and verification together is
\(O\bigl((L+\tau md)L^2\bigr)\)
bit operations. Here membership preprocessing can be performed within the same bound, and committee verification uses \(O(\tau kd+\tau md)\) table operations and integer additions. Consequently, the problem belongs to \(\mathrm{NP}\).
We invoke the supplied hardness result: for explicitly listed individual voters, deciding whether a size-\(k\) SJR committee reaches an AV threshold is \(\mathrm{NP}\)-complete for \(d=1\), with variable \(k\ge 3\). This is the restriction stated in [Kagita et al., Lemma 5.10](https://cgi.cse.unsw.edu.au/~haziz/commt-attribute.pdf).
Consider such a source instance with \(n\) individual voters. Let \(Q\) be its threshold for the unnormalized approval count
\(H(W)=\sum_{i=1}^{n}\sum_{c\in W}\mathbf 1\{c[1]\in A_i^1\}.\)
Keep the candidates, their attributes, and \(k\). Partition the voters by identical complete approval types. For each distinct type \(t\), let \(n_t\) be its number of voters, and output the mass
\(\mu_t=n_t/n.\)
Output the threshold \(q=Q/n\).
These are valid support data: types are distinct, every mass is positive, and their sum is one. There are at most \(n\) types. Each numerator and denominator requires \(O(\log n)\) bits, and grouping explicitly listed voters takes polynomial time in the source input length.
We now verify equivalence for every committee \(W\).
SJR preservation. All voters of a type have identical approvals, so either all are unrepresented by \(W\), or none are. For every value \(a\in D_1\),
\(\sum_{\substack{t\in U_W\\a\in A_t^1}}\mu_t =\dfrac{\#\{\text{unrepresented individual voters approving }a\}}{n}.\)
Therefore the target inequality that this mass is strictly below \(1/k\) is equivalent to the source inequality that the corresponding voter count is strictly below \(n/k\). Equality violates both conditions.
Score preservation. Grouping identical voters gives
\(\mathrm{AV}_{\mu}(W) =\sum_t\frac{n_t}{n}\sum_{c\in W}\mathbf 1\{c[1]\in A_t^1\} =\frac{H(W)}{n}.\)
Hence \(\mathrm{AV}_{\mu}(W)\ge q\) holds exactly when \(H(W)\ge Q\).
Candidate identities are retained throughout; candidates sharing an attribute value still contribute separately to both scores. Thus the reduction preserves yes-instances and no-instances, proving \(\mathrm{NP}\)-hardness. Together with membership in \(\mathrm{NP}\), this establishes the classification.
Hardness also holds for every fixed dimension \(D\ge 2\): append \(D-1\) dimensions with a single domain value and empty approvals for every type. The additional SJR sums are zero, representation is unchanged, and the AV score is divided by \(D\). Replacing \(q\) by \(q/D\) preserves the answer.
Enumerate the \(\binom{m}{k}\) committees and verify each one using the preceding procedure. A conservative bit-operation bound is
\(O\bigl((L+\tau md+\binom{m}{k}\tau md)L^2\bigr).\)
Since \(\binom{m}{k}\le m^k\), this is polynomial for every fixed \(k\), even when \(d\) is variable. For \(k=2\), the bound becomes
\(O\bigl((L+\tau m^3d)L^2\bigr).\)
There is also an algorithm exponential only in \(\tau\).
Index the types by \(T=\{1,\ldots,\tau\}\). Define the represented-type set of a candidate by
\(R_c=\{t\in T:\exists j,\ c[j]\in A_t^j\}.\)
For a committee, its represented set is \(R(W)=\bigcup_{c\in W}R_c\), and \(U_W=T\setminus R(W)\). Thus SJR depends only on \(R(W)\), while the score remains additive.
Order the candidates as \(c_1,\ldots,c_m\). Let \(F_i(\ell,R)\) be the largest integer score attainable by selecting exactly \(\ell\) of the first \(i\) candidates whose represented set is exactly \(R\). Mark unattainable states by \(-\infty\). Initialize \(F_0(0,\varnothing)=0\).
For each attainable state \(F_{i-1}(\ell,R)\), perform the two updates
\(F_i(\ell,R)\leftarrow\max\{F_i(\ell,R),F_{i-1}(\ell,R)\},\)
and, when \(\ell<k\),
\(F_i(\ell+1,R\cup R_{c_i}) \leftarrow\max\{F_i(\ell+1,R\cup R_{c_i}),F_{i-1}(\ell,R)+s_{c_i}\}.\)
The recurrence is correct by induction: every selection either omits \(c_i\), or includes it and arises by adding it to a selection among the first \(i-1\) candidates. Keeping only the maximum score for a state is valid because future representation depends only on \(R\), and future scores are added identically.
For each final represented set \(R\), test SJR using \(T\setminus R\). Accept precisely when some valid state satisfies
\(vF_m(k,R)\ge udB.\)
There are \(O(k2^\tau)\) states per candidate layer. Charging \(O(\tau)\) operations for each set union and scanning all SJR conditions for each final set yields the conservative bound
\(O\bigl((L+\tau md+2^\tau\tau(mk+md))L^2\bigr).\)
Thus the problem is fixed-parameter tractable in the support size \(\tau\). This algorithm works directly with the rational masses; it never expands them into individual voters.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The reduction preserves both SJR and the AV threshold, exact verification takes polynomial time, and the additional enumeration and support-based algorithms have valid conservative running-time bounds. I found no major or minor mathematical issues.
Each denominator divides \(B=\prod_t b_t\), so every \(w_t=a_t(B/b_t)\) is a positive integer and \(\mu_t=w_t/B\). The normalization assumption gives \(\sum_t w_t=B\).
The bit length of \(B\) is bounded by the total encoded denominator length. Consequently, \(B\) has \(O(L)\) bits. The bounds \(s_c\le dB\) and \(\sum_{c\in W}s_c\le kdB\) are correct: each candidate receives at most one approval per type and dimension. Since the candidates and their attributes are explicitly listed, the additional factors \(d\) and \(k\le m\) preserve the \(O(L)\) bit-length bound.
Products involving the threshold numerator and denominator also have \(O(L)\) bits. Thus the arithmetic-size claim covers the actual comparisons, not merely the scores.
The identity
\(\mathrm{AV}_\mu(W)=\bigl(\sum_{c\in W}s_c\bigr)/(dB)\)
follows directly from the stated definition. In particular, summation is over candidate identities, so coincident attribute vectors do not collapse contributions.
The certificate consists of exactly \(k\) distinct candidate identifiers. Checking approval membership for every selected candidate, type, and dimension computes precisely the defined set \(U_W\).
Because \(B>0\), the SJR comparison is exactly \(kz_{j,a}(W)<B\). The strict inequality is preserved, including its equality boundary. Because \(v>0\) and \(dB>0\), the threshold comparison is exactly
\(v\sum_{c\in W}s_c\ge udB\).
This remains valid when the rational threshold is zero or negative.
There are at most \(md\) dimension–value pairs. The stated verification work is bounded by the claimed
\(O((L+\tau md)L^2)\)
bit operations, using elementary arithmetic and \(k\le m\). Approval-table preprocessing also fits this conservative bound. Membership in \(\mathrm{NP}\) is established.
The cited [Kagita et al., Lemma 5.10](https://cgi.cse.unsw.edu.au/~haziz/commt-attribute.pdf) states the individual-voter hardness restriction used by the prover. Its decision formulation uses a committee approval-count threshold and the strict residual-voter bound. For \(d=1\), these match the source problem invoked here. Conditions concerning selected attribute values are automatically satisfied because their approving voters are represented.
The prover uses variable \(k\ge3\), not a fixed committee size. This is consistent with both the supplied hardness premise and the later enumeration algorithm.
Grouping identical complete approval types produces distinct support entries with positive masses \(n_t/n\), summing to one. Since voters are explicitly listed, grouping takes polynomial time and the resulting rational encodings have polynomial total length.
Representation is identical for all voters in one type. Consequently, each residual approval mass is exactly the corresponding residual voter count divided by \(n\). Multiplication by positive \(n\) preserves the strict SJR comparison, including equality.
For \(d=1\), the normalized target objective is exactly \(H(W)/n\). Therefore the threshold transformation \(q=Q/n\) preserves the score condition in both directions.
Candidate identities and committee size are retained. The construction is a polynomial many-one reduction and establishes \(\mathrm{NP}\)-hardness. Together with certificate verification, it proves \(\mathrm{NP}\)-completeness.
Appending dimensions with singleton domains and empty approvals is permitted by the task. Their residual approval sums are zero, which is strictly below \(1/k\). They introduce no representation or score contributions.
Changing the dimension count from one to \(D\) divides the objective by \(D\), so replacing the threshold by \(q/D\) preserves the answer. For every fixed \(D\ge2\), the construction is polynomial. This establishes hardness with variable committee size in those dimensions.
Enumerating all \(\binom{m}{k}\) committees is exhaustive. Verification per committee fits the stated bound, so the total
\(O((L+\tau md+\binom{m}{k}\tau md)L^2)\)
is valid.
The inequality \(\binom{m}{k}\le m^k\) establishes polynomial time for every fixed \(k\), including variable \(d\). Substituting \(k=2\) gives the stated conservative bound. The method also covers \(k=1\) and \(k=m\).
The definition of \(R_c\) agrees exactly with representation in the task. Hence \(U_W=T\setminus R(W)\), and SJR depends only on the represented-type set.
The state records both exact committee cardinality and exact represented set. The initialization and include/omit transitions correctly enforce selection of distinct candidates. Retaining only the maximum score is justified by the stated dependence of future representation and additive scores on the state.
Final acceptance checks cardinality \(k\), attainability, SJR, and the exact threshold. The state count, set-union cost, and final SJR scans fit
\(O((L+\tau md+2^\tau\tau(mk+md))L^2)\).
This establishes fixed-parameter tractability in \(\tau\).
No repair or additional clarification is needed.
⟨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.