Answer: \(\mathrm{coNP}\)-hard.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any sequential and non-sequential Thiele rule except AV, even in the first step of the query policy, it is coNP-hard to decide whether a given candidate is safe. For non-sequential Thiele rules it may happen that no can- didate is safe. Moreover, we show that it is computationally intractable to decide whether there exists a safe candidate or not in a given instance.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates C, committee size k, a fixed non-AV Thiele rule w, a rational distribution μ over approval-set types, and candidate c, decide whether for every availability set X⊆C there is a winning committee W⊆X of size min(k,|X|) containing c whenever c∈X.
Definitions. An instance consists of a candidate set \(C\), committee size \(k\), and a non-increasing nonnegative Thiele vector \(w\) with \(w_1=\cdots=w_q=1\) and \(w_{q+1}<1\). A society is given by a rational approval-type distribution \(\mu=(\mu_S)_{S\subseteq C}\), with \(\mu_S\ge0\) and \(\sum_S\mu_S=1\). For \(X\subseteq C\), let \(\mathcal W_{w,\mu}(k,X)\) be the size-\(\min(k,|X|)\) subsets \(W\subseteq X\) maximizing \(\sum_{S\subseteq C}\mu_S\sum_{j=1}^{|S\cap W|}w_j\). The question is whether some \(Q\subseteq C\) with \(|Q|=q+1\) satisfies: for every \(X\subseteq C\), some \(W\in\mathcal W_{w,\mu}(k,X)\) contains \(Q\cap X\).
Target. Is this mass-distribution safe-set problem NP-hard or in \(\mathrm P\)?
Nearest known results. For finite approval profiles, deciding whether \(q+1\) safe candidates exist for the corresponding \(w\)-Thiele rule is coNP-hard. No result for the exact rational mass-distribution formulation above was verified.
The formulation does not have a representation-independent complexity classification.
Thus, under the literal full-vector interpretation, the answer is \(\mathrm P\). The finite-profile hardness result does not by itself prove hardness for that dense encoding because writing all zero coordinates may require exponential output.
I assume throughout that \(w\) is fixed or is explicitly represented by rationals in binary. Without an effective exact representation of \(w\), Turing complexity is not defined.
Let \(m=|C|\), and define
\(g(t)=\sum_{j=1}^{t}w_j\)
and
\(F(W)=\sum_{S\subseteq C}\mu_S g(|S\cap W|)\).
For \(X\subseteq C\), put \(r_X=\min(k,|X|)\) and define
\(\mathcal F(X)=\{W\subseteq X:|W|=r_X\}\),
\(\mathcal F_Q(X)=\{W\in\mathcal F(X):Q\cap X\subseteq W\}\).
When \(\mathcal F_Q(X)\) is empty, define its maximum score to be \(-\infty\).
For fixed \(Q\) and \(X\), some \(W\in\mathcal W_{w,\mu}(k,X)\) contains \(Q\cap X\) if and only if
\(\max_{W\in\mathcal F_Q(X)}F(W)=\max_{W\in\mathcal F(X)}F(W)\).
If such an optimal \(W\) exists, then \(W\in\mathcal F_Q(X)\), so the restricted maximum is at least the unrestricted optimum. The reverse inequality follows from \(\mathcal F_Q(X)\subseteq\mathcal F(X)\).
Conversely, suppose the two maxima are equal. Since \(\mathcal F(X)\) is nonempty, equality implies that \(\mathcal F_Q(X)\) is nonempty. A maximizer in \(\mathcal F_Q(X)\) therefore has the unrestricted optimal score and contains \(Q\cap X\). This proves the equivalence.
Assume the input explicitly contains all \(2^m\) coordinates of \(\mu\). Let \(T=2^m\), and let \(L\) be the total binary input length. Since every coordinate requires at least one input symbol, \(T\leq L\).
The following exhaustive algorithm decides the problem.
There are at most \(T\) choices for each of \(Q\), \(X\), and \(W\). Precomputing all scores uses at most \(T^2m\) approval-type contributions, and the subsequent exhaustive test uses at most \(T^3\) score comparisons. Since \(T\leq L\) and \(m\leq\log_2 L\), the number of arithmetic operations is polynomial in \(L\).
Write \(\mu_S=a_S/b_S\) and \(w_j=c_j/d_j\) in binary. All scores can be multiplied by the common positive denominator
\(D=\left(\prod_{S\subseteq C}b_S\right)\left(\prod_jd_j\right)\).
The binary length of \(D\) is at most the sum of the binary lengths of the input denominators, hence is \(O(L)\). Every scaled score \(D F(W)\) is therefore an integer with polynomially many bits and can be computed and compared exactly in polynomial time.
Consequently, with the full \(2^m\)-coordinate representation,
\(\textsc{Mass-Distribution Safe-Set}\in\mathrm P\).
This proof does not require the special plateau condition on \(w\); that condition only determines the requested cardinality \(q+1\).
Now suppose that the input lists only pairs \((S,\mu_S)\) for which \(\mu_S>0\), with all omitted masses understood to be zero.
Consider a finite approval profile with voters \(1,\ldots,n\), where voter \(i\) approves \(A_i\subseteq C\). For every \(S\subseteq C\), let
\(n_S=|\{i:A_i=S\}|\)
and construct the rational distribution
\(\mu_S=n_S/n\).
Only the at most \(n\) sets with \(n_S>0\) need to be output, so this construction has polynomial size under sparse-support encoding.
For every committee \(W\),
\[ F(W) =\sum_{S\subseteq C}\frac{n_S}{n}g(|S\cap W|) =\frac{1}{n}\sum_{i=1}^{n}g(|A_i\cap W|). \]
Thus the mass-distribution score is exactly \(1/n\) times the finite-profile score. Multiplication by the positive constant \(1/n\) preserves all score comparisons and all ties. Hence, for every \(X\subseteq C\),
\(\mathcal W_{w,\mu}(k,X)=\mathcal W_{w,V}(k,X)\),
where the right-hand side denotes the winner set for the finite profile \(V\).
It follows that a set \(Q\) is safe in the finite profile if and only if it is safe in the constructed mass distribution. Therefore, assuming the supplied finite-profile theorem, the sparse-support mass-distribution problem is \(\mathrm{coNP}\)-hard under polynomial-time many-one reductions.
This establishes \(\mathrm{coNP}\)-hardness, not automatically \(\mathrm{NP}\)-hardness under many-one reductions. In particular, sparse-support membership in \(\mathrm P\) would imply \(\mathrm P=\mathrm{coNP}\).
The normalized profile usually has at most \(n\) positive coordinates, but the dense representation requires all \(2^m\) coordinates, including zeros. When \(m\) is not logarithmically bounded in the finite-profile input length, producing that vector takes exponential time and space.
Therefore the normalization argument is a valid polynomial reduction for sparse support, but not for the literal full-coordinate input. This is exactly consistent with the polynomial exhaustive algorithm above.
The precise answer is:
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes a representation-sensitive classification:
The argument does not establish \(\mathrm{NP}\)-hardness for the sparse version, but the prover explicitly and correctly says so. The only material imprecision concerns the representation and computational accessibility of \(w\).
The stated equivalence is correct.
If an unrestricted optimum belongs to \(\mathcal F_Q(X)\), the restricted and unrestricted maxima coincide. Conversely, equality with a finite unrestricted maximum rules out the conventionally assigned value \(-\infty\), so \(\mathcal F_Q(X)\) is nonempty and contains an unrestricted maximizer.
This also handles the edge case \(|Q\cap X|>\min(k,|X|)\): then \(\mathcal F_Q(X)=\varnothing\), and the desired safety condition fails.
Letting \(T=2^m\), the enumeration bounds are valid:
Thus the combinatorial portion takes at most polynomially many operations in \(T\). Under the expressly stated dense encoding, every one of the \(T\) coordinates occupies input space, so \(T\leq L\). Consequently, the \(T^3\)-type enumeration is polynomial in \(L\). Omitted factors polynomial in \(m\), such as subset tests and cardinality computations, do not affect this conclusion because \(m\leq\log_2 L\).
The score precomputation bound is also valid: there are \(T\) committees and \(T\) approval types, with at most an additional polynomial factor in \(m\).
For rationally encoded \(\mu_S\) and rationally encoded \(w_j\), the common-denominator argument is sound. The product \(D\) contains every denominator needed to clear all terms in every score. Its binary length is bounded by the sum of the input denominator lengths, hence by \(O(L)\). Products, sums, and comparisons therefore involve integers with polynomially bounded bit lengths.
The write-up does not explicitly account for the numerator lengths and the extra \(\log T\) bits introduced when summing \(T\) terms, but both are already polynomially bounded by the input length. This is routine and does not constitute a gap.
The normalization is exact:
\[ F(W)=\frac1n\sum_{i=1}^n g(|A_i\cap W|). \]
Because \(1/n>0\), multiplying all finite-profile scores by this constant preserves strict comparisons and ties. Hence the full set of winning committees agrees for every restricted candidate set \(X\), not merely the identity of one selected winner. The safe-set property is therefore preserved exactly.
The support contains at most \(n\) approval types, and the rational masses \(n_S/n\) have polynomial encoding length. Thus the reduction is polynomial under sparse-support encoding.
Given the finite-profile hardness statement supplied in the task, the conclusion of \(\mathrm{coNP}\)-hardness is justified. The prover correctly avoids claiming that this alone yields \(\mathrm{NP}\)-hardness.
The observation is correct. A sparse normalized profile may have polynomially many positive types while the required dense vector has \(2^m\) coordinates. Unless \(m\) is logarithmically bounded in the source input length, explicitly outputting all zero coordinates is not a polynomial-time reduction.
The statement “\(w\) is fixed or is explicitly represented by rationals in binary” is too broad. Merely being fixed does not guarantee that the values of \(w\), or the necessary score comparisons involving them, are computable in polynomial time. The subsequent exact-arithmetic proof specifically assumes rational values \(w_j=c_j/d_j\).
Minimum clarification: restrict the polynomial-time conclusion to \(w\) given explicitly as binary rationals, or to a fixed \(w\) whose required entries and exact comparisons are polynomial-time accessible with polynomially bounded representations. This does not undermine the proved rational-input case, and the prover already recognizes that the original task fails to specify an effective representation of \(w\).
⟨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.