| paper | Multiwinner Rules on Paths From k-Borda to Chamberlin-Courant |
| authors | Piotr Faliszewski, P. Skowron, A. Slinko, Nimrod Talmon |
| venue | IJCAI 2017 |
| 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}\)-hard for every fixed rational \(p>1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), fixed rational \(p>1\), a rational distribution \(\mu\) over complete rankings \(\pi\) of \(C\), and threshold \(\theta\), decide whether there is a committee \(S\subseteq C\) with \(\lvert S\rvert=k\) and \(F_{\mu,p}(S)=\sum_{\pi}\mu_\pi\left(\sum_{j=1}^{k}b_j(\pi,S)^p\right)^{1/p}\ge\theta\), where \(b_j(\pi,S)\) are the sorted Borda scores of committee members.
A society consists of ranking types \(\pi\) with masses \(\mu_\pi\). The decision variable is a discrete committee \(S\) of size \(k\), and the objective is the population-average \(\ell_p\)-Borda score \(F_{\mu,p}(S)\); the computational task is threshold decision or maximization.
The mirror covers Theorem 2 and the corresponding \(\ell_p\)-Borda winner problem over distributions of ranking types. It does not by itself cover the paper's convergence, approximation, \(t\)-Borda, \(p\)-HarmonicBorda, experimental, or earth-mover-distance results.
My strongest positive case is a high-multiplicity version of the paper’s \(\ell_p\)-Borda winner problem. It is a genuine mirror, although I expect it to belong to Class B: the discrete hardness should survive continuization.
The regime is a large population choosing a \(k\)-item slate from a fixed catalogue: movies for a streaming service, products for a platform, or candidates shortlisted for a position. There may be millions of agents but only \(\tau\) distinct preference rankings, with \(N\gg\tau\). A type is a complete ranking \(\pi\) of the \(m\) candidates. Its mass \(\mu_\pi\) is the fraction of the population with that ranking, so \(\mu\) is a rational distribution over the \(m!\) possible rankings. Agents of one type are indistinguishable for this problem.
For a committee \(S\) of size \(k\), let \(b_1(\pi,S)\ge\cdots\ge b_k(\pi,S)\) be the Borda scores of its members according to \(\pi\), sorted from largest to smallest. For fixed rational \(p>1\), define the population score
\[ F_{\mu,p}(S)=\sum_{\pi}\mu_\pi \left(\sum_{j=1}^{k} b_j(\pi,S)^p\right)^{1/p}. \]
The decision problem is:
Continuous-\(\ell_p\)-Borda Threshold. Given \(C\), \(k\), a rational distribution \(\mu\) over rankings, a fixed rational \(p>1\), and a threshold \(\theta\), decide whether there is a committee \(S\subseteq C\) with \(|S|=k\) and \(F_{\mu,p}(S)\ge\theta\). A solution is such a committee; the optimization version asks for a maximizing committee.
This is exactly the per-capita version of the paper’s underlying problem. The committee remains discrete, and \(p\) remains the paper’s rule parameter; only the electorate is replaced by its distribution.
The anchor is Theorem 2, proved in this paper: “For each rational \(p>1\), deciding whether there is a winning committee with at least a given score is NP-hard.” Here “winning” means maximizing the \(\ell_p\)-Borda societal score, and the theorem applies to every rational \(p>1\), not merely to the limiting CC rule. The paper proves this result itself. Its reduction follows the hardness intuition for Chamberlin–Courant but requires polynomially bounded padding so that the \(\ell_p\)-Borda scores behave sufficiently like CC scores.
The authors should recognise the continuous problem as their problem because the paper’s score is already an aggregate over voters. Given an ordinary election \(E\) with \(n\) voters, define \(\mu_\pi=n_\pi/n\), where \(n_\pi\) is the number of voters with ranking \(\pi\). Then for every committee \(S\),
\[ F_{\mu,p}(S)=\frac{1}{n}\operatorname{score}_{\ell_p\text{-Borda}}(S,E). \]
Thus a discrete threshold \(q\) becomes the continuous threshold \(q/n\), with exactly the same winning committees. This is not continuizing the rule’s outcome space or its parameter: it is replacing the empirical voter list by its type distribution. If desired, every voter can be replicated \(R\) times, giving \(Rn\) agents while leaving \(\mu\) unchanged, so the same instance has an arbitrarily high-multiplicity realization.
I therefore expect hardness to transfer, rather than dissolve. The reduction’s combinatorics live in choosing a committee of candidates and exploiting interactions among representatives, not in the identities of individual voters. Continuous masses compress repeated voters but do not remove those candidate-selection interactions. This is precisely the programme’s Class B situation.
The mirror also generates useful follow-up questions: is the problem fixed-parameter tractable in the number \(\tau\) of ranking types; does it become tractable on single-peaked or Euclidean supports; can the optimum be approximated efficiently from a distribution; and how does the winning committee change as \(p\) varies or as \(\mu\) is perturbed? Those questions connect naturally to the paper’s convergence and approximation results without pretending that those results themselves continuize the population.
My weakest point is that, for winner determination alone, this mirror may look like nothing more than a weighted-election reformulation. It offers no immediate LP or convex-optimization gain, and the hardness reduction may use many distinct types before the voters are replicated. So this is not the paper’s strongest route to a tractable continuous mirror. It is nevertheless a legitimate and well-motivated high-multiplicity problem, and Theorem 2 gives a clean, named result whose complexity should carry over exactly.
The strongest case against is that the proposed mirror is only a weighted-election reformulation. The paper’s score already has the form
\[ \operatorname{score}(S,E)=\sum_{v\in V} f(\operatorname{pos}_v(S)). \]
Replacing \(V\) by its empirical distribution \(\mu\) merely rewrites this as
\[ F_{\mu,p}(S)=\sum_{\pi}\mu_\pi f_p(\pi,S). \]
Nothing in the paper treats population mass as a decision variable, a resource, a constraint, or an object subject to intervention. The committee remains an indivisible \(k\)-subset, and \(\mu\) only supplies coefficients to the same finite optimization problem. Thus the proposed “continuous” problem has no limiting phenomenon: every rational \(\mu\) can be converted back into a finite election by clearing denominators, while every finite election produces such a \(\mu\). It is a compressed encoding of the original instance, not a new population-level computational model.
The better version does not help much. One could allow all ranking types, arbitrary rational masses, and very large multiplicities, or formulate the same question for the paper’s \(t\)-Borda and \(p\)-HarmonicBorda families from Proposition 1. But these remain anonymous weighted elections. The mass has no independent operational meaning, and the continuous formulation contributes neither an LP over mass transfers nor a fractional feasibility structure. If one instead introduces fractional committees, probabilistic representation, or population interventions, one has changed the outcome space or the problem rather than continuized the paper’s population.
Theorem 2 is nevertheless a real obstacle to the negative case. It is a named computational result, and its hardness transfers cleanly: for an election with \(n_\pi\) voters of type \(\pi\), taking \(\mu_\pi=n_\pi/n\) preserves every committee score up to the factor \(n\). Replicating every voter type arbitrarily many times gives a genuine high-multiplicity realization without changing the continuous instance. The hardness is therefore not dependent on named voter identities.
Consequently, the negative argument can establish only low novelty and low expected payoff, not inadmissibility. Theorem 2 supplies a legitimate Class B mirror, exactly of the kind the programme says should count even when hardness survives. The honest verdict is that a universal “no worthwhile mirror” case cannot be sustained: this paper has at least one valid, if rather unexciting, continuous-population anchor.
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.