| paper | Achieving fully proportional representation: Approximability results |
| authors | P. Skowron, Piotr Faliszewski, A. Slinko |
| venue | AI 2015 |
| 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-hard to approximate within any fixed factor \(r>1\); no polynomial-time \(r\)-approximation exists unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(A\), committee limit \(K\), a normal increasing positional scoring function \(\alpha^m\), complete ranking types \(\mathcal{T}\), and rational masses \(\mu_\pi\ge 0\) with \(\sum_{\pi\in\mathcal{T}}\mu_\pi=1\), choose \(S\subseteq A\) with \(|S|\le K\) and \(x_{\pi,a}\ge 0\) satisfying \(\sum_{a\in S}x_{\pi,a}=\mu_\pi\), minimizing \(D_\mu(S,x)=\sum_{\pi\in\mathcal{T}}\sum_{a\in S}x_{\pi,a}\alpha^m(\operatorname{pos}_\pi(a))\); determine whether a polynomial-time \(r\)-approximation exists for each fixed \(r>1\).
A high-multiplicity Chamberlin–Courant electorate in which ranking types \(\pi\) carry masses \(\mu_\pi\); select at most \(K\) candidates and assign each type's mass to selected candidates, minimizing average dissatisfaction. With unlimited CC capacity, this is equivalently \(\min_{|S|\le K}\sum_\pi\mu_\pi\min_{a\in S}\alpha^m(\operatorname{pos}_\pi(a))\).
Because Chamberlin–Courant has unlimited capacities, the mass-assignment variables collapse to each type's best selected candidate, so the mirror adds little optimization structure beyond weighted committee selection.
fatal: False
The mirror covers Theorem 3's dissatisfaction hardness and Theorem 15's Borda-satisfaction PTAS; it leaves the Monroe variants, egalitarian objectives, general resource allocation, and empirical results untreated.
My lead mirror is a continuous-population version of the Chamberlin–Courant dissatisfaction problem, with the paper’s Theorem 3 as the anchor.
The regime is a recommendation or representative-selection platform with a very large population but recurring preference types. A type is a complete ranking \(\pi\) of the \(m\) candidates. If \(\mu_\pi\) is the fraction of users with ranking \(\pi\), then \(N\) may be millions while the number of distinct rankings \(\tau\) is only hundreds or thousands. This is plausible for demographic, departmental, geographic, or application-defined user segments. Each individual still receives one integral recommendation; only the mass of users assigned to each recommendation is represented continuously.
Define Continuous-\(\alpha\)-DU-CC as follows. An instance consists of candidates \(A\), committee bound \(K\), a normal increasing positional scoring function \(\alpha^m\), a finite set of ranking types \(\mathcal T\), and rational masses \(\mu_\pi\) satisfying \(\sum_{\pi\in\mathcal T}\mu_\pi=1\). We choose \(S\subseteq A\) with \(|S|\le K\), together with mass assignments \(x_{\pi,a}\ge0\) satisfying
\[ \sum_{a\in S}x_{\pi,a}=\mu_\pi \]
for every type \(\pi\). The objective is to minimize
\[ D_\infty(S,x)= \sum_{\pi\in\mathcal T}\sum_{a\in S} x_{\pi,a}\,\alpha^m(\operatorname{pos}_\pi(a)). \]
Thus the question is: which at most \(K\) candidates should be selected, and how should the population mass be assigned to them, so as to minimize average dissatisfaction?
For a fixed \(S\), splitting a type’s mass cannot improve the objective: all of it can be assigned to its least-dissatisfying selected candidate. Hence the problem is equivalently
\[ \min_{|S|\le K} \sum_{\pi\in\mathcal T}\mu_\pi \min_{a\in S}\alpha^m(\operatorname{pos}_\pi(a)). \]
This is exactly the high-multiplicity form of the paper’s underlying problem, not a different optimization problem. A finite election becomes \(\mu_\pi=n_\pi/n\), and dividing the paper’s total dissatisfaction by \(n\) gives precisely this expression.
Theorem 3, proved in this paper, states:
For every normal increasing positional scoring function \(\alpha\) and every constant \(r>1\), there is no polynomial-time \(r\)-approximation algorithm for \(\alpha\)-DU-CC unless \(\mathrm{P}=\mathrm{NP}\).
Here \(\alpha\)-DU-CC is the Chamberlin–Courant case of the paper’s dissatisfaction-based utilitarian assignment problem: at most \(K\) alternatives may be used, alternatives have unlimited CC capacity, and the sum of voters’ dissatisfaction is minimized.
The theorem’s hardness should transfer to the continuous mirror. In its Vertex-Cover reduction, each ground-set element becomes a distinct ranking type \(\pi_i\), with mass \(\mu_{\pi_i}=1/n\). If a cover of size \(K\) exists, selecting the corresponding candidates lets every type use an incident candidate, giving the low dissatisfaction promised by the reduction. Conversely, if the selected candidates do not cover some element type, every selected candidate is placed in the reduction’s deliberately bad part of that type’s ranking, producing a cost gap larger than the approximation threshold. Fractional assignment cannot evade this: for that type, if no suitable candidate is selected, its entire mass must be assigned to unsuitable candidates after one replaces any split assignment by the type’s cheapest selected candidate.
The genuinely high-multiplicity version is obtained simply by taking \(q\) copies of every type. Then the population has \(N=qn\) agents but still only \(\tau=n\) types, with the same mass vector. The hardness is therefore not driven by the number of individually named voters. It lives in the candidate-selection and incidence structure—the \(K\)-set-cover combinatorics—which is exactly the programme’s Class B pattern. I would expect this continuous problem to remain inapproximable up to every constant factor, rather than become tractable.
As a secondary anchor, Theorem 15, also proved in the paper, states:
There is a polynomial-time approximation scheme for \(\alpha^m_{\bordadec}\)-SU-CC, where \(\alpha^m_{\bordadec}(i)=m-i\).
This is the satisfaction-based utilitarian Chamberlin–Courant problem with Borda satisfaction: choose at most \(K\) candidates and an assignment maximizing total satisfaction. Its continuous mirror is Continuous-Borda-SU-CC:
\[ \max_{|S|\le K} \sum_{\pi\in\mathcal T}\mu_\pi \max_{a\in S}\bigl(m-\operatorname{pos}_\pi(a)\bigr). \]
The same PTAS should extend directly by replacing voter counts with type masses. In the paper’s greedy algorithm, the number of voters ranking a candidate in their top \(x\) positions becomes the total mass of such types. The covering argument and its bound are unchanged. For fixed \(K\), exact enumeration of candidate sets is polynomial in the input size, while for large \(K\) the paper’s greedy guarantee approaches \(1\). Thus this mirror is expected to be tractable in the PTAS sense.
These two anchors show why the mirror is worthwhile even though the lead result remains hard: continuization does not merely produce a fractional restatement. It gives a compact distributional input, permits arbitrary rational population proportions, and separates the complexity caused by population multiplicity from the complexity caused by selecting alternatives. For this paper, the latter survives in dissatisfaction minimization, while Borda satisfaction admits a PTAS.
The weakest point is that Theorem 3 does not establish hardness when \(\tau\) is fixed once and for all; the number of types grows with the Vertex-Cover instance. If “continuum” were required to mean a fixed finite type space with only the masses varying, this particular hardness transfer would not suffice. I would not claim that stronger result. The honest claim is narrower: there are highly convincing regimes with \(N\gg\tau\) in which the paper’s Chamberlin–Courant problem has a natural continuous-population formulation, and its core hardness is caused by candidate selection rather than by individual voter multiplicity.
The strongest negative case is that both proposed mirrors are weighted finite elections, not genuinely continuous computational models. That is a criticism of their payoff, not of their formal validity.
For Theorem 3, the proponent’s \(D_\infty\) notation is misleading: the displayed objective is utilitarian, hence \(D_1\). But the corrected mirror is still well-defined. Its weakness is that, under Chamberlin–Courant’s unlimited capacities, the mass variables are vacuous. For any selected committee \(S\), each type’s entire mass can be assigned to its best member of \(S\), giving
\[ \min_{|S|\le K} \sum_{\pi}\mu_\pi \min_{a\in S}\alpha^m(\operatorname{pos}_\pi(a)). \]
There is no genuine fractional allocation, transportation, or column-generation problem here. The continuous population contributes only coefficients to an otherwise discrete committee-selection problem.
Indeed, after clearing denominators, every rational mass vector becomes an ordinary finite weighted election, and duplicating every type \(q\) times changes nothing except the redundant population scale. The Vertex-Cover reduction therefore shows hardness of weighted Chamberlin–Courant selection, not hardness created by continuization. Its \(q\)-copy version does give \(N\gg\tau\), but \(q\) is computationally irrelevant; the reduction’s combinatorics live entirely in the growing collection of ranking types and candidate incidences.
If one insists on a fixed type space, the contrast is even sharper. For fixed \(\tau\), one can enumerate, for every type, the candidate that serves it best. There are at most \(m^\tau\) such tuples, so both the dissatisfaction and satisfaction versions are exactly solvable in polynomial time for fixed \(\tau\). Thus the mirror is either a compressed weighted finite problem whose hardness comes from type diversity, or a fixed-type problem with elementary exact enumeration. Neither gives strong evidence for a population-continuum phenomenon.
Theorem 15 has the same defect. Its PTAS does extend to rational masses: counts of voters ranking a candidate in the top \(x\) positions become masses of types doing so, and the covering argument goes through. But this merely gives a PTAS for weighted Chamberlin–Courant. The theorem already applies to arbitrary finite profiles, so the continuous formulation adds no new optimization structure, no new separation problem, and no population-driven tractability result. The fractional assignment again collapses to assigning each type wholly to its best selected candidate.
A more elaborate type space does not rescue these particular anchors. If demographic or application-specific segments are added, they must be folded into the type because the programme defines a type as a complete description relevant to the objective. One then has the same weighted problem with more types. If instead one imposes a parametric density over rankings, the resulting integration and input model are new assumptions not supplied by the paper and no longer directly mirror its theorems.
This is the best negative argument: these mirrors do not make the society itself the computational object in the programme’s stronger sense; they merely replace repeated voters by weights while leaving the decisive combinatorial choice integral. But it is not enough to defeat the proposal under the programme’s rules. High-multiplicity weighted formulations are explicitly allowed, Class B hardness is explicitly valuable, and the Theorem 3 reduction really can be lifted to a population with many copies of each type. Theorem 15 also survives cleanly. A Monroe version with per-capita capacities would be a substantially more convincing continuous mirror, which further weakens any universal rejection.
So the honest conclusion is that the negative case is weak. It can argue that the proposed CC mirrors are less novel and less “continuous” than advertised, but it cannot establish that no worthwhile continuous mirror exists. Both anchors remain viable.
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.