| paper | Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Perspectives |
| authors | Piotr Faliszewski, P. Skowron, A. Slinko, Nimrod Talmon |
| venue | AAAI 2016 |
| 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: \(\mathrm{NP}\text{-complete}\) for every fixed scoring family satisfying the hypotheses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), a rational distribution \(\mu\) over complete ranking types \(t\), and a rational threshold \(\theta\), decide whether there exists \(S\subseteq C\) with \(|S|=k\) such that \(\sum_t\mu_t g_k(|S\cap A_t|)\ge\theta\), under the hypotheses of Theorem 11.
Types are complete rankings, with mass \(\mu_t\); \(A_t\) is the type's top-\(k\) set. The decision variable is an integral committee \(S\), and the objective is the normalized aggregate score \(\sum_t\mu_t g_k(|S\cap A_t|)\).
The mirror covers Theorems 11 and 13, including broad convex top-\(k\)-counting hardness and NearlyBloc inapproximability. It leaves the axiomatic characterizations and the algorithmic results in Propositions 8, 9, 15 and Theorems 12, 14 and 16 untreated.
The strongest positive case is a population mirror of the paper’s computational winner-determination problem for top-\(k\)-counting rules. It preserves the paper’s committee, candidates, scoring function, and optimization question; only the electorate is replaced by a distribution.
A type is a complete ranking \(t\) of the candidates. For a fixed committee size \(k\), let \(A_t\subseteq C\) be the \(k\) candidates ranked by \(t\) in the top \(k\) positions. A society is a rational distribution \(\mu=(\mu_t)\) over these types. Since top-\(k\)-counting rules ignore the order within \(A_t\) and below it, types with the same \(A_t\) may be aggregated without loss.
The natural regime is a large parliamentary, organizational, or institutional electorate: millions of voters, but many recurring ballot types generated by party slates, issue coalitions, demographic constituencies, or standardized preference templates. Thus the population size \(N\) is very large while the number \(\rho\) of supported types is much smaller, perhaps \(\rho=\operatorname{poly}(m)\). This is a sensible high-multiplicity regime, not an assumption about every election.
For a top-\(k\)-counting function \(g_k\), define the continuous score of a committee \(S\), \(|S|=k\), by
\[ F_\mu(S)=\sum_t \mu_t\,g_k(|S\cap A_t|). \]
The decision variable remains the integral committee \(S\); only the population is continuous. This is therefore not an outcome-space relaxation.
The exact discrete-to-continuous dictionary is immediate but substantive. If an election has \(n_t\) voters of type \(t\), then with \(N=\sum_t n_t\) and \(\mu_t=n_t/N\),
\[ F_\mu(S)=\frac{1}{N}\operatorname{score}_E(S). \]
Thus a discrete threshold \(T\) becomes the rational continuous threshold \(T/N\). Conversely, any rational distribution can be cleared of denominators and realized by a finite election. The continuous problem is consequently the high-multiplicity version of the paper’s problem, not a different voting rule.
My lead anchor is Theorem 11, proved in this paper and supported by the reduction in Appendix A. It states that for a top-\(k\)-counting rule with integer-valued committee scoring functions, if the counting functions \(g_k\) are independent of \(m\), polynomial-time computable, have polynomially bounded \(g_k(k)\), and, for all sufficiently large \(k\), are convex with
\[ k-\operatorname{sing}(g_k)\ge \frac{k}{c} \]
for some constant \(c\), then deciding whether there exists a size-\(k\) committee with score at least a given threshold is NP-hard. Here \(\operatorname{sing}(g_k)\) is the first point at which the successive differences of \(g_k\) change. The paper proves this by reducing from Clique on regular graphs.
The corresponding continuous problem is:
Continuous Convex Top-\(k\)-Counting Winner. Given candidates \(C\), committee size \(k\), a rational distribution \(\mu\) over rankings, and a rational threshold \(\theta\), decide whether there exists \(S\subseteq C\), \(|S|=k\), such that
\[ \sum_t\mu_t\,g_k(|S\cap A_t|)\ge \theta. \]
A solution is such a committee \(S\), or a correct yes/no answer.
This is a faithful mirror: the rule is unchanged, the committee is still integral, and the objective is the same aggregate score, merely normalized per voter. Theorem 11’s reduction maps directly by replacing its election by its empirical distribution and replacing \(T\) by \(T/N\). Hence the unrestricted continuous problem inherits NP-hardness. I would classify this version as Class B: the reduction’s combinatorics live in the candidate graph and the committee, not in the magnitude of the population. Repeating every supported type arbitrarily many times leaves \(\mu\) unchanged, so large multiplicities do not remove the underlying difficulty.
The paper’s second useful anchor is Theorem 13, also proved here, in Appendix B. It concerns the rule NearlyBloc, whose counting function is
\[ g(x)=\max(x-1,0). \]
The theorem states that there is no polynomial-time constant-factor approximation algorithm for computing the score of a winning committee under NearlyBloc unless the Densest at most \(K\) Subgraph problem, DamkS, also has such an algorithm. DamkS asks for a subgraph with at most \(K\) vertices maximizing
\[ \frac{|E(H)|}{|V(H)|}. \]
The continuous counterpart is:
Continuous NearlyBloc Approximation. Given \(C\), \(k\), and a rational distribution \(\mu\) over top-\(k\) types, compute a size-\(k\) committee \(S\) maximizing
\[ F_\mu(S)=\sum_t\mu_t\max(|S\cap A_t|-1,0), \]
or output a committee whose score is at least \(\alpha\) times the optimum for some fixed constant \(\alpha>0\). Equivalently, one may ask for the optimum value itself.
This is again not merely an analogy. In the paper’s DamkS reduction, an edge \(e=\{u,v\}\) produces a voter whose top-\(k\) set contains \(u\), \(v\), and filler candidates. A committee representing vertices of an induced subgraph receives one unit from precisely the relevant edge types, up to the filler-handling argument in the proof. Replacing equal voter counts by equal masses only multiplies every score by the same normalization factor, so approximation ratios are unchanged. I would therefore also expect Class B behaviour here, with a conditional inapproximability barrier inherited from DamkS.
These mirrors cover the paper’s computational winner-determination results for broad convex top-\(k\)-counting rules and for NearlyBloc. They do not claim to continuize the fixed-majority axioms, the characterization of Bloc, or the OWA terminology; those are axiomatic or structural results rather than the computational population problem.
The weakest point is that the paper’s reductions use edge-specific and sometimes dummy-specific ballot patterns. They therefore do not by themselves prove hardness when the number of distinct voter types is bounded by a constant, or even very small independently of the candidate structure. A skeptical referee could say that the continuous formulation is, on these instances, a weighted-election encoding rather than a dramatic collapse of population complexity. I think that criticism limits the strength of the hardness-transfer claim, but not the mirror itself. The high-multiplicity problem is well-defined, authors of the paper would recognize it as their winner-determination problem with repeated ballot types, and the central follow-up question is meaningful: which restrictions on \(\rho\), \(m\), or the representation of \(\mu\) make these discrete hardness results dissolve, and which remain hard because the combinatorics belong to the committee rather than to the population?
The strongest case against is that both anchors are population-inert weighted-election reformulations. For a rational distribution \(\mu\), clearing denominators produces a finite election with exactly the same committee scores up to a common factor. The continuous model introduces no fractional committee, mass transfer, or continuous decision variable: \(S\) remains an integral size-\(k\) committee, and \(\mu\) merely supplies coefficients.
That objection is especially sharp for Theorem 11. Its reduction uses edge-specific and filler-specific voter types, so the combinatorics lie entirely in candidate selection. Replicating every type \(M\) times merely inflates the electorate while leaving \(\mu\) unchanged. Thus the proposed mirror does not show that population continuization changes the source problem; it shows that the same NP-hard weighted election remains NP-hard. If ChoCo required population multiplicity to be the source of the difficulty, this would be a poor anchor.
The same criticism applies to Theorem 13. The DamkS construction has essentially one voter type per edge, and normalization preserves approximation ratios exactly. Its continuous version therefore gives no continuum-specific approximation phenomenon and no hardness result for a genuinely small type space. It is conditional hardness transfer for an integral committee problem.
But this is not enough for the requested universal negative. The programme explicitly allows Class B mirrors, and high-multiplicity is not required to make hardness disappear. More importantly, the natural stronger question—what happens when the support size \(\rho\) is small relative to \(m\), or is a parameter—is not answered by either reduction. For fixed \(\rho\), candidates can be grouped by their membership signature across the \(\rho\) top-\(k\) sets, yielding a finite-dimensional dynamic programme or integer optimization problem. That is a legitimate computational question about the high-multiplicity regime, even if unrestricted instances retain the original hardness.
Nor can one rescue the negative case by saying that fractional committees would be artificial: that is true, but unnecessary. The integral-committee, mass-population model already is a faithful population continuization. Conversely, adding campaigning, robustness, or mass perturbations would create worthwhile new problems, though they would be extensions rather than results already proved in the paper.
So the honest negative case can justify calling these mirrors low-novelty Class B transfers, not continuum-specific breakthroughs. It cannot establish that no worthwhile mirror exists. Theorem 11 alone survives the attack, and Theorem 13 independently reinforces it; under the programme’s stated standards, I would not sign a universal negative verdict.
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.