Answer: \(\mathrm{P}\) (polynomial-time solvable)
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIn the 3VA model, PosCom⟨2⟩is NP-complete under Chamberlin–Courant.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), a target \(W\subseteq C\) with \(|W|=2\), and finitely many 3VA information types \(\theta=(\mathrm{Top}_\theta,\mathrm{Middle}_\theta,\mathrm{Bottom}_\theta)\) with rational masses \(\mu_\theta\) summing to \(1\), does there exist \(q_{\theta,A}\ge 0\) for valid completions \(A\) such that \(\sum_A q_{\theta,A}=\mu_\theta\) and the induced society \(\nu_A=\sum_\theta q_{\theta,A}\) makes \(W\) a Chamberlin–Courant winning committee, meaning \(\sum_A\nu_A\mathbf{1}[A\cap W\ne\varnothing]\ge\sum_A\nu_A\mathbf{1}[A\cap W'\ne\varnothing]\) for every \(W'\subseteq C\) with \(|W'|=2\)?
For a 3VA type \(\theta=(\mathrm{Top}_\theta,\mathrm{Middle}_\theta,\mathrm{Bottom}_\theta)\), a valid completion is any approval set \(A=\mathrm{Top}_\theta\cup X\) with \(X\subseteq\mathrm{Middle}_\theta\). The rational masses \(\mu_\theta\) sum to \(1\).
Target. Is the continuous possible-committee problem for Chamberlin–Courant with committee size \(2\) solvable in polynomial time, or is it NP-hard?
Given \(C\), \(W\subseteq C\) with \(|W|=2\), and the types above, decide whether there are \(q_{\theta,A}\ge0\) with \(\sum_A q_{\theta,A}=\mu_\theta\) such that \(\nu_A=\sum_\theta q_{\theta,A}\) satisfies \(\sum_A\nu_A\mathbf{1}[A\cap W\ne\varnothing]\ge\sum_A\nu_A\mathbf{1}[A\cap W'\ne\varnothing]\) for every \(W'\subseteq C\) with \(|W'|=2\).
For finite voter profiles in the 3VA model, deciding whether a specified size-\(2\) committee is a possible Chamberlin–Courant winner is NP-complete. No result for the mass-distribution version above is stated here.
The continuous possible-committee problem for Chamberlin–Courant with committee size \(2\) is polynomial-time solvable.
The decisive difference from the finite-voter problem is that each type mass may be divided fractionally among several completions. After a dominance reduction, only at most three completions per type are needed, so feasibility is expressible by a polynomial-size rational linear program.
For a committee \(U\subseteq C\), define the coverage indicator
\[ h_U(A)=\mathbf 1[A\cap U\neq\varnothing]. \]
Given completion masses \(q_{\theta,A}\), the Chamberlin–Courant score of \(U\) is
\[ \operatorname{sc}(U)=\sum_{\theta}\sum_A q_{\theta,A}h_U(A). \]
Thus \(W\) is a co-winner exactly when, for every \(U\in\binom{C}{2}\),
\[ \sum_{\theta}\sum_A q_{\theta,A}\bigl(h_W(A)-h_U(A)\bigr)\geq 0. \]
Write \(W=\{a,b\}\).
Lemma. If some completion-mass assignment makes \(W\) a co-winner, then another such assignment exists in which each type \(\theta\) uses only the following completions:
If \(\mathrm{Top}_\theta\cap W\neq\varnothing\), only \(\mathrm{Top}_\theta\) is needed.
Fix a type \(\theta\) and one of its valid completions
\[ A=\mathrm{Top}_\theta\cup X, \qquad X\subseteq\mathrm{Middle}_\theta. \]
Define a reduced completion \(\rho_\theta(A)\) as follows.
\(\rho_\theta(A)=\mathrm{Top}_\theta\cup\{w\}\).
Because \(w\in X\subseteq\mathrm{Middle}_\theta\), the reduced set is a valid completion. Moreover,
\[ \rho_\theta(A)\subseteq A. \]
The reduction preserves whether \(W\) is covered:
\[ h_W\bigl(\rho_\theta(A)\bigr)=h_W(A). \]
Indeed, if \(W\) was already hit by \(\mathrm{Top}_\theta\), it remains hit. Otherwise, \(W\) is hit precisely when \(X\cap W\neq\varnothing\), in which case one such approved member is retained.
For every committee \(U\), monotonicity under set inclusion gives
\[ h_U\bigl(\rho_\theta(A)\bigr)\leq h_U(A). \]
Consequently,
\[ h_W\bigl(\rho_\theta(A)\bigr)-h_U\bigl(\rho_\theta(A)\bigr) \geq h_W(A)-h_U(A). \]
Now push the mass of every completion \(A\) onto \(\rho_\theta(A)\). Formally, for every reduced completion \(R\), let
\[ q'_{\theta,R} = \sum_{A:\rho_\theta(A)=R}q_{\theta,A}. \]
This preserves the total mass of every type. For every committee \(U\),
\[ \sum_{\theta,R}q'_{\theta,R} \bigl(h_W(R)-h_U(R)\bigr) \geq \sum_{\theta,A}q_{\theta,A} \bigl(h_W(A)-h_U(A)\bigr). \]
Hence all co-winner inequalities remain satisfied. The new assignment uses at most the three stated completions per type. This proves the lemma.
For each type \(\theta\), define
\[ \mathcal R_\theta= \begin{cases} \{\mathrm{Top}_\theta\}, & \mathrm{Top}_\theta\cap W\neq\varnothing,\\ \{\mathrm{Top}_\theta\} \cup \{\mathrm{Top}_\theta\cup\{w\}:w\in W\cap\mathrm{Middle}_\theta\}, & \mathrm{Top}_\theta\cap W=\varnothing. \end{cases} \]
By the pruning lemma, the original instance is feasible if and only if the following linear program is feasible. Introduce a variable \(x_{\theta,R}\) for every \(R\in\mathcal R_\theta\), and impose
\[ x_{\theta,R}\geq 0, \]
\[ \sum_{R\in\mathcal R_\theta}x_{\theta,R}=\mu_\theta \qquad\text{for every type }\theta, \]
and
\[ \sum_\theta\sum_{R\in\mathcal R_\theta} x_{\theta,R}\bigl(h_W(R)-h_U(R)\bigr)\geq 0 \qquad \text{for every }U\in\binom{C}{2}. \]
The forward equivalence follows from the pruning lemma. The reverse equivalence is immediate because every member of \(\mathcal R_\theta\) is a valid completion of type \(\theta\).
If there are \(t\) types and \(m=|C|\) candidates, this program has at most \(3t\) variables, \(t\) mass equalities, and \(\binom m2\) winner inequalities. Every inequality coefficient belongs to \(\{-1,0,1\}\), while the right-hand sides are the input rational masses. The program can therefore be constructed and tested for feasibility in time polynomial in \(t\), \(m\), and the binary encoding length of the masses.
In the finite-voter problem, each voter must select one completion integrally. After the pruning lemma, that voter must still make a discrete choice among as many as three reduced completions. Those coupled integral choices can encode an NP-hard problem.
In the continuous formulation, a type mass \(\mu_\theta\) may be split arbitrarily among those completions. The corresponding variables are continuous, so the remaining problem is ordinary linear-program feasibility. Thus the finite NP-completeness result does not imply hardness of the mass-distribution version.
The continuous possible-committee problem for Chamberlin–Courant and committee size \(2\) belongs to \(\mathrm{P}\). In particular, it is not NP-hard unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes that the continuous possible-committee problem is polynomial-time solvable. The pruning lemma is valid, preserves the target committee’s score, weakly decreases every competing committee’s score, and reduces each type to at most three relevant completions. The resulting feasibility problem is a polynomial-size rational linear program.
The definition
\[
h_U(A)=\mathbf 1[A\cap U\neq\varnothing]
\]
correctly expresses Chamberlin–Courant coverage. The co-winner condition is correctly rewritten as
\[
\sum_{\theta,A}q_{\theta,A}\bigl(h_W(A)-h_U(A)\bigr)\geq 0
\]
for every size-\(2\) committee \(U\).
Each reduced completion is either \(\mathrm{Top}_\theta\) or \(\mathrm{Top}_\theta\cup\{w\}\) with \(w\in\mathrm{Middle}_\theta\). Hence each is a valid completion under the stated model.
The case distinction defining \(\rho_\theta(A)\) correctly preserves whether \(A\) intersects \(W\):
\[
h_W(\rho_\theta(A))=h_W(A).
\]
All cases are covered, including when both members of \(W\) occur in \(X\).
Since \(\rho_\theta(A)\subseteq A\), the claimed monotonicity
\[
h_U(\rho_\theta(A))\leq h_U(A)
\]
holds for every committee \(U\). Together with preservation of \(W\)-coverage, this yields the pointwise margin inequality
\[
h_W(\rho_\theta(A))-h_U(\rho_\theta(A))
\geq h_W(A)-h_U(A).
\]
Pushing all mass from \(A\) to \(\rho_\theta(A)\) preserves nonnegativity and the total mass of each type. Summing the pointwise inequalities shows that every co-winner inequality remains satisfied simultaneously.
If \(\mathrm{Top}_\theta\cap W\neq\varnothing\), only \(\mathrm{Top}_\theta\) is needed. Otherwise the support consists of \(\mathrm{Top}_\theta\) and at most one completion for each of the two members of \(W\), giving at most three completions per type.
The pruning lemma proves the forward implication. Conversely, every LP variable corresponds to a valid completion, so every feasible LP solution gives a feasible completion-mass assignment. Thus the equivalence is established in both directions.
With \(t\) explicitly represented types and \(m\) candidates, the LP has at most \(3t\) variables and \(t+\binom m2\) substantive constraints, aside from nonnegativity. Its coefficients are rational with polynomial encoding length. Standard rational linear-program feasibility therefore gives a polynomial-time algorithm.
The conclusion that the problem belongs to \(\mathrm P\) follows. The qualification that it is not NP-hard unless \(\mathrm P=\mathrm{NP}\) is also correct under ordinary polynomial-time many-one reductions.
No unjustified step, missing hypothesis, or substantive edge case was 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.