Approval-Based Committee Voting under Incomplete Information

The strongest positive case is a direct high-multiplicity mirror of Theorem 2, proved in this paper: in the 3VA model, \(\mathrm{PosCom}\langle 2\rangle\) is NP-complete under Chamberlin–Courant. The reduction is from one-in-three positive 3SAT, so this is exactly the kind of discrete hardness for which continuization is worth testing.

I would call the mirror Continuous Possible Two-Committee under 3VA–CC, or \(\mathrm{PosCom}^{3VA}_{\infty}(\mathrm{CC},2)\). Its instance consists of a finite candidate set \(C\), a target committee \(W\subseteq C\) with \(|W|=2\), and finitely many 3VA types \(\theta\). A type is a triple
\[ \theta=(\mathrm{Top}_\theta,\mathrm{Middle}_\theta,\mathrm{Bottom}_\theta), \]
together with a rational mass \(\mu_\theta\ge 0\), where \(\sum_\theta\mu_\theta=1\). Thus all voters of a type have exactly the same known approvals, known disapprovals, and unknown candidates.

A completion of type \(\theta\) is any approval set \(A\) satisfying
\[ \mathrm{Top}_\theta\subseteq A\subseteq \mathrm{Top}_\theta\cup \mathrm{Middle}_\theta. \]
The action is to split each type’s mass among its valid completions. Formally, choose \(q_{\theta,A}\ge 0\) such that
\[ \sum_{A\text{ completes }\theta}q_{\theta,A}=\mu_\theta. \]
The resulting complete society has mass
\[ \nu_A=\sum_\theta q_{\theta,A} \]
of voters with approval set \(A\). The question is whether there exists such a mass assignment for which \(W\) is a Chamberlin–Courant winning committee:
\[ \sum_A \nu_A\mathbf 1[A\cap W\neq\varnothing] \;\ge\; \sum_A \nu_A\mathbf 1[A\cap W'\neq\varnothing] \]
for every \(W'\subseteq C\) with \(|W'|=2\).

This is recognisably the authors’ problem. Candidates and committees remain discrete; the Chamberlin–Courant score is unchanged; the 3VA completion semantics are unchanged; and “possible committee” remains existential completion followed by winner comparison. The only change is that a large population is represented by rational masses, so different members of the same type may occupy different valid completions. That is the natural atomless version of independent completion choices, not a change to the voting rule or to the information model.

The regime is plausible in the paper’s own applications. Consider a large pool of users, annotators, hiring evaluators, or search-result assessors. Many people may share the same coarse expertise profile and therefore the same sets of candidates they definitely approve, definitely reject, or have not evaluated. The committee may be a fixed-size shortlist, such as two search results or two hires. The relevant regime is \(N\gg\tau\): millions of voters, but only \(\tau\) distinct partial-approval types. The reduction behind Theorem 2 can itself be replicated: give every type appearing in the reduction many identical clones. Clearing denominators recovers the corresponding finite high-multiplicity instance.

I expect this continuous problem to be Class A, even though the paper’s discrete problem is NP-complete. For fixed committee size \(2\), write one LP variable for every possible completion column \(A\). The constraints are the mass-conservation equations above and one linear winner inequality for each competing committee. There may be exponentially many completion columns, but the pricing problem is simple for 3VA under Chamberlin–Courant. In a dual pricing query, adding an unknown candidate outside \(W\) can only help competing committees and cannot improve \(W\)’s score, so it is never useful. The only relevant choices are which of the at most two target candidates in \(\mathrm{Middle}_\theta\) to approve. Thus each type has only \(2^{|W\cap\mathrm{Middle}_\theta|}\le 4\) relevant priced completions. Since there are only \(\binom{m}{2}\) competing committees, standard separation-based LP machinery should give a polynomial-time algorithm in the number of types, candidates, and mass encoding length.

The reduction in Theorem 2 illustrates why the hardness may dissolve. In the discrete proof, each element \(x\) makes a binary choice between approving \(w_1\) and approving \(w_2\). In the mass model, a type corresponding to \(x\) can send a fraction \(q_x\) of its mass to the first completion and \(1-q_x\) to the second. The one-in-three constraints then become linear conditions such as
\[ \sum_{x\in S_i}q_x=1, \]
rather than integral choices. The exact-cover obstruction is replaced by fractional feasibility, precisely the kind of population-multiplicity effect ChoCo is meant to expose.

This is not a claim that Theorem 2 becomes easy under every interpretation. If one required all mass of a type to make one common completion, the fractional relaxation would disappear and the model would remain close to the discrete problem. Nor does the LP argument automatically cover variable committee size, PAV, or the general poset model. Those are separate questions, and potentially different complexity classes.

My weakest point is that the paper itself does not identify a high-multiplicity application, and the reduction has many incidence-specific voter types—potentially one per Boolean variable. The regime \(N\gg\tau\) is therefore supplied by the mirror rather than demonstrated by the theorem. The case survives because the model passes the rational-clone test exactly: a rational mass can be cleared to many identical voters, and the only new operation is splitting a repeated type across its already permitted completions. The natural follow-up questions are whether the same Class A result holds for larger fixed \(k\), whether linear and poset incompleteness retain tractable pricing, and how accurately a continuous solution can be rounded back to a finite election with an exact winning guarantee.