| paper | Computational Aspects of Multi-Winner Approval Voting |
| authors | H. Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, T. Walsh |
| venue | AAAI 2014 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-complete, and hence NP-hard, even when every positive-mass approval type contains exactly two candidates. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), rational finite-support masses \(\mu_A\) over approval types \(A\subseteq C\), and threshold \(q\), decide whether there exists an integral committee \(W\subseteq C\) with \(\lvert W\rvert=k\) and \(\sum_A\mu_A H_{\lvert W\cap A\rvert}\ge q\), where \(H_r=\sum_{j=1}^{r}1/j\); equivalently, compute a maximizing \(W\).
Types are approval ballots \(A\subseteq C\) with masses \(\mu_A\); the decision variable is an integral \(k\)-candidate committee \(W\), and the objective is expected harmonic satisfaction \(\sum_A\mu_A H_{\lvert W\cap A\rvert}\).
The proposed HM-PAV input does not formally require \(\tau\ll n\) or bounded support, so the reduction itself may expose no computational benefit from multiplicity; this limits the mirror's novelty but does not kill its well-posedness.
fatal: False
The mirror covers PAV winner determination and its \(\mathrm{W[1]}\)-hardness parameterized by \(k\), and can cover RAV manipulation after lifting the manipulator to positive strategic mass; it leaves the paper's SAV results, most other manipulation variants, and strategyproofness result untouched.
The strongest case is a yes, led by a literal high-multiplicity version of PAV winner determination.
My lead anchor is Theorem 1, proved in this paper: “WD for PAV is NP-complete, even if each agent approves of two candidates.” Their WD problem takes candidates \(C\), approval ballots \(A_1,\ldots,A_n\), and committee size \(k\), and asks for the size-\(k\) committee maximizing
\[ \mathrm{PAV}(W)=\sum_{i=1}^{n}H_{\lvert W\cap A_i\rvert}, \qquad H_r=\sum_{j=1}^{r}\frac1j. \]
The proof reduces from Independent Set. A graph vertex becomes a candidate, edge agents approve the two endpoint candidates, and dummy candidates and vertex agents calibrate every vertex candidate to the same maximum marginal score. A committee reaches the threshold precisely when its corresponding vertices form an independent set. The paper also records the parameterized strengthening as Corollary 1, proved from the same reduction: WD for PAV is W[1]-hard parameterized by \(k\), even when every agent approves exactly two candidates.
The continuous problem I would hand to a prover is:
\[ \textbf{HM-PAV-WD:} \]
An instance consists of a candidate set \(C\), committee size \(k\), and a finite-support rational distribution \(\mu\) over approval types \(A\subseteq C\). Thus \(\mu_A\) is the fraction of society approving exactly \(A\), with \(\sum_A\mu_A=1\). The task is to find a size-\(k\) committee maximizing
\[ \mathrm{PAV}_{\mu}(W) = \sum_{A\subseteq C}\mu_A H_{\lvert W\cap A\rvert}. \]
Equivalently, the decision version asks whether some size-\(k\) committee has score at least a rational threshold \(q\). A solution is the winning committee \(W\), which remains an integral set of \(k\) candidates.
This is not outcome-space continuization: the committee is not fractional. Only the society is continuous. A type is exactly an approval ballot \(A\), since that is the complete information used by PAV. The mass \(\mu_A\) represents a large constituency of indistinguishable voters.
The high-multiplicity interpretation is very natural in committee selection, hiring, recommendation, or representative elections. For example, millions of users or constituents may fall into a few dozen or few hundred approval patterns induced by department, constituency, professional role, or user cohort. In the computational reduction, \(\tau\) may grow with the graph, but genuine high multiplicity is still available: replicate every type \(R\) times. Then the number of agents is \(R n\), while the number of distinct types remains \(\tau\), and the distribution \(\mu\) is unchanged.
The discrete-to-continuous identity is exact. If \(n_A\) voters have approval type \(A\), then
\[ \mu_A=\frac{n_A}{n} \quad\text{and}\quad \mathrm{PAV}_{\mu}(W)=\frac{1}{n}\mathrm{PAV}(W). \]
Thus the winning committees are identical. Replicating the entire electorate preserves the same continuous instance while making every type highly populated. Consequently, the expected classification is Class B: hardness transfers. The W[1]-hardness parameterized by \(k\) transfers as well. Continuization does not make this problem easy, but it produces a meaningful computational object: weighted PAV over a compressed population description, with its own questions about approximation, fixed \(\tau\), and algorithms parameterized by \(k\) or the number of types.
The paper’s authors should recognize this immediately as their problem. Their formula is already a sum over agents; replacing that sum by expectation over approval types changes the population representation, not the voting rule, committee semantics, or optimization objective.
A second, independent anchor is Theorem 11, also proved in this paper: “For RAV, WM is NP-hard.” Their Winner Manipulation problem takes an approval profile, candidates \(C\), committee size \(k\), a number \(j\) of additional voters, and a preferred candidate \(p\), and asks whether the additional voters can submit approval ballots making \(p\) belong to the RAV winning committee. The theorem’s reduction is from 3SAT. It introduces candidates for positive and negative literals, candidates representing satisfied and unsatisfied clauses, two auxiliary candidates \(a,b\), carefully weighted approval agents, and sets \(k=\lvert\Phi\rvert+\lvert\Psi\rvert+1\). In the one-manipulator construction, the manipulator’s ballot encodes a truth assignment, and candidate \(a\) enters the committee exactly when that assignment satisfies every clause.
The corresponding continuous problem is:
\[ \textbf{HM-RAV-WM:} \]
An instance consists of a candidate set \(C\), committee size \(k\), a rational base mass distribution \(\mu\) over approval types, a rational strategic mass \(\alpha>0\), a preferred candidate \(p\), and a fixed lexicographic tie-breaking order. The strategic mass consists of a homogeneous bloc whose members share the same objective of electing \(p\). The bloc chooses one approval ballot \(B\subseteq C\).
For a current selected set \(S\), the RAV score of an unelected candidate \(c\) is
\[ q_{\mu,\alpha,B}(c\mid S) = \sum_A \mu_A \frac{\mathbf{1}[c\in A]}{1+\lvert S\cap A\rvert} + \alpha \frac{\mathbf{1}[c\in B]}{1+\lvert S\cap B\rvert}. \]
RAV selects the highest-scoring candidate for \(k\) successive rounds, using the prescribed tie-breaking order. The question is whether there exists a ballot \(B\) such that \(p\) is selected.
This is again a genuine population mirror: the committee and sequential RAV rule remain discrete, while the electorate and the strategic bloc are represented by masses. The hardness transfer is exact. Given a discrete profile with base counts \(n_A\) and one manipulator, set
\[ \mu_A=\frac{n_A}{N+1}, \qquad \alpha=\frac1{N+1}. \]
Every RAV score in the continuous instance is the corresponding discrete score divided by \(N+1\), so every round and tie-breaking decision is unchanged. To obtain arbitrarily high multiplicity, replicate every base type and the manipulator \(R\) times; the strategic bloc then consists of \(R\) identical voters. Hence this mirror is also expected to be Class B: hardness transfers.
The weak point is this second anchor. The paper phrases its key reduction around a single manipulator, whereas a nonatomic individual would have zero influence. I am therefore explicitly lifting that individual into a positive-mass homogeneous bloc. A referee could regard that as a coalition version rather than the exact single-agent problem. The PAV anchor does not have this vulnerability: it requires no strategic reinterpretation, and the population distribution is a direct high-multiplicity form of the paper’s own approval profile.
So I would make the case for the continuous mirror emphatically on Theorem 1 / HM-PAV-WD, with Theorem 11 / HM-RAV-WM as a useful second example. The claim is not that continuity automatically dissolves their hardness. It is that their central computational questions survive as well-defined, natural problems when the electorate itself becomes a distribution over approval types.
The strongest negative case is that both proposed mirrors are only weighted-profile formulations. For PAV, the paper’s Theorem 1 uses approval ballots as the entire voter type, and
\[ \mathrm{PAV}_{\mu}(W)=\sum_A \mu_A H_{|W\cap A|} \]
is exactly the finite PAV score divided by the population size whenever \(\mu_A=n_A/n\). The reduction itself does not exploit population multiplicity: its edge, vertex, and dummy agents can all have distinct approval types. Replicating them creates arbitrarily many voters but no new computational structure. Thus, unless the proposed work imposes a genuinely compressed regime such as bounded support or \(\tau\ll n\), it is a change of encoding rather than a new population phenomenon.
That is the best objection to HM-PAV-WD, but it does not defeat it under this programme’s rules. A distribution over a small number of approval types is a natural committee-election regime, and the resulting bounded-support problem is not the same as the unrestricted finite presentation. It raises exactly the kinds of questions the programme wants: dependence on \(\tau\), approximation with binary masses, and whether candidate-selection hardness survives compression. The fact that the unrestricted problem is an exact normalized restatement is not disqualifying; Class B mirrors are explicitly valuable.
The RAV anchor has a sharper literal defect. A single manipulator has vanishing mass in a nonatomic society, so the paper’s one-agent reduction disappears unless the manipulator is assigned positive mass. But assigning mass \(\alpha>0\) changes the problem into coalition manipulation. Restricting that coalition to one common ballot is also an additional assumption: the paper’s \(j\) manipulators may submit different ballots.
Even this objection does not survive the better formulation. One can let the strategic coalition choose a distribution \(\nu\) over approval ballots, with total mass \(\alpha\), and run RAV on
\[ \mu+\nu. \]
This is a natural high-multiplicity version of the paper’s coalition-manipulation problem. It preserves the integral committee, sequential rounds, and tie-breaking, while making the strategic population genuinely continuous. The single-agent case is indeed degenerate, but the coalition case is not.
So the honest negative case is weak. Neither anchor is invalidated by identity dependence, loss of meaning, or an existing continuous treatment. The most one can argue is that the proponent should present PAV as a weighted/high-multiplicity computational mirror—not as a fundamentally new voting rule—and should formulate RAV around a positive-mass strategic coalition rather than a nonatomic individual. Those are qualifications, not a case that no worthwhile continuous mirror exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.