| paper | The Complexity of Fully Proportional Representation for Single-Crossing Electorates |
| authors | P. Skowron, Lan Yu, Piotr Faliszewski, Edith Elkind |
| venue | SAGT 2013 |
| 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 · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
Given candidates \(C\), parliament size \(k\), and a rational distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\) over complete ranking types \(t_1,\ldots,t_\tau\), ordered so that for every candidate pair \(a,b\), the types preferring \(a\) to \(b\) form a prefix, choose \(S\subseteq C\) with \(|S|=k\) and masses \(x_{i,c}\ge 0\) satisfying \(x_{i,c}=0\) for \(c\notin S\), \(\sum_{c\in S}x_{i,c}=\mu_i\), and \(\sum_i x_{i,c}=1/k\) for each \(c\in S\), minimizing \(\sum_i\sum_{c\in S}x_{i,c}\alpha_B(\operatorname{pos}_{t_i}(c))\); output an optimal parliament and allocation.
A high-multiplicity single-crossing society consists of complete ranking types with masses \(\mu_i\). The decision variables are the selected winners \(S\) and divisible assignment masses \(x_{i,c}\), each selected candidate receiving mass \(1/k\); the objective is total Borda dissatisfaction.
The mirrors cover Theorem 11’s utilitarian Borda Monroe hardness and Theorem 6’s Chamberlin–Courant algorithm, with Lemma 5 as structural support; they leave Proposition 9, Corollary 10, Theorem 15, and the counterexamples unmirrored.
The strongest positive case is that this paper studies exactly the kind of population-level assignment problem that has a natural high-multiplicity form. I would use two anchors, with Theorem 11 as the lead.
The common mirror is as follows. Let the candidates be \(C\), let \(k\) be the parliament size, and let the society consist of ordered voter types \(t_1,\ldots,t_\tau\). Each type is a complete ranking of \(C\), and type \(t_i\) has mass \(\mu_i\), where \(\mu_i\ge 0\) and \(\sum_i\mu_i=1\). The ordering is single-crossing: for every pair \(a,b\), the types preferring \(a\) to \(b\) form a prefix of the order. Equivalently, type \(t_i\) occupies an interval of length \(\mu_i\) on a unit ideological axis.
The regime is a large electorate of citizens grouped into a relatively small number of ideological, geographic, or constituency cohorts. All members of a cohort have the same ranking, so \(N\gg\tau\). This is particularly natural for Monroe’s rule: a selected representative must represent exactly \(1/k\) of the population in the continuum, the limiting version of Monroe’s requirement that every selected candidate represent approximately \(N/k\) voters.
My lead mirror is the following.
SC-Borda-Monroe\(_\infty\). An instance consists of \(C\), \(k\), an ordered single-crossing type support \((t_i,\mu_i)_{i=1}^{\tau}\), and Borda dissatisfaction \(\alpha_B(r)=r-1\). The question is to choose exactly \(k\) winners \(S\subseteq C\), together with an allocation \(x_{i,c}\ge 0\), such that
\(x_{i,c}=0\) for \(c\notin S\),
\(\sum_{c\in S}x_{i,c}=\mu_i\) for every type \(t_i\), and
\(\sum_i x_{i,c}=\frac{1}{k}\) for every \(c\in S\).
The objective is to minimize
\(\sum_i\sum_{c\in S}x_{i,c}\alpha_B(\operatorname{pos}_{t_i}(c))\).
The output is an optimal parliament and allocation, or equivalently the set of Monroe winners.
This is a direct continuous version of the underlying problem in Theorem 11, which states that finding winners under the \(\alpha_B\)-\(\ell_1\)-Monroe rule is NP-hard even when the election is single-crossing. The theorem is proved in this paper, although its reduction starts from the previously known hardness of unrestricted Monroe winner determination.
The correspondence is exact at the modelling level. A finite election with \(n_i\) voters of type \(t_i\) becomes \(\mu_i=n_i/N\), and a rational mass distribution can be expanded into a finite high-multiplicity election by taking a common denominator. The continuous objective is the finite total dissatisfaction divided by \(N\). Conversely, \(x_{i,c}\) records the mass of a type assigned to a candidate. The only genuine co-modification is replacing the finite \(\lfloor N/k\rfloor/\lceil N/k\rceil\) quota by the continuum quota \(1/k\), which is exactly the proportional limit.
I would initially expect hardness to survive for this mirror, hence Class B: the hard combinatorics in Theorem 11 concern selecting candidates and arranging their representation, not merely naming individual voters. The paper’s reduction also uses extensive repeated voter blocks, so a weighted version of its gadgetry is plausible.
The necessary qualification is that Theorem 11 alone does not prove hardness when \(\tau\) is fixed or very small relative to the population. Divisibility of mass may weaken a discrete reduction, and the theorem’s hard source can contain many distinct rankings. Thus the genuinely high-multiplicity question is a worthwhile strengthening:
Does SC-Borda-Monroe\(_\infty\) remain NP-hard when the number of distinct single-crossing types is bounded, or does the hardness dissolve into a polynomial-time weighted optimization problem?
That is a legitimate continuous-computational question, not a restatement of the paper’s finite model.
My second mirror uses the paper’s positive result.
SC-CC\(_\infty\). The instance is the same ordered single-crossing society, together with \(k\), a polynomial-time computable dissatisfaction function \(\alpha\), and a choice of \(\ell\in\{\ell_1,\ell_\infty\}\). The task is to choose at most \(k\) candidates and assign all population mass to them, minimizing
\(\sum_{i,c}x_{i,c}\alpha(\operatorname{pos}_{t_i}(c))\) for \(\ell_1\), or
\(\max\{\alpha(\operatorname{pos}_{t_i}(c)):x_{i,c}>0\}\) for \(\ell_\infty\).
This mirrors Theorem 6, proved in the paper: for every polynomial-time computable family of dissatisfaction functions and either \(\ell_1\) or \(\ell_\infty\), optimal \(k\)-Chamberlin–Courant assignments can be found in polynomial time on single-crossing elections.
I expect SC-CC\(_\infty\) to be Class A. The supporting Lemma 5, also proved here, says that an optimal assignment exists in which each selected candidate represents a contiguous block of the single-crossing voter order, with the blocks ordered consistently with the first voter’s ranking. In the continuum, the same argument gives contiguous mass intervals. Since rankings are constant within each type, the finite dynamic program can be replaced by a weighted dynamic program over the \(\tau\) type blocks and their rational masses. Its running time should depend polynomially on \(m\), \(k\), \(\tau\), and the bit-length of the masses, rather than on the population denominator \(N\). That is important: expanding a binary-encoded mass into \(N\) individual voters could be exponentially expensive, so this is not merely a cosmetic rewriting of Theorem 6.
The natural follow-up questions are whether the weighted algorithm can be made strongly polynomial, whether its contiguous-block structure gives approximation or rounding guarantees for finite electorates, and how the result changes under bounded single-crossing width.
These mirrors cover only Theorems 11 and 6. I would not claim that every result in the paper continuizes equally well. In particular, the paper’s counterexamples concerning noncontiguous Monroe assignments may become either more powerful or less relevant once type mass can be split.
My weakest point is the lead hardness claim: discrete NP-hardness does not automatically survive passage to divisible population mass. The paper proves the right finite hardness anchor, but a fractional-robust reduction or a hardness theorem for genuinely small-support high-multiplicity instances would still be needed. The positive case nevertheless stands because both proposed questions preserve the paper’s candidates, preferences, representation constraints, and objectives; they continuize the population, not the outcome rule.
I cannot honestly make a strong universal negative case here. This paper is unusually well suited to continuization, and both anchors survive the available objections.
For Theorem 11, the proposed mirror is not an artificial reinterpretation. A society with ordered ranking types \(t_1,\ldots,t_\tau\) and masses \(\mu_i\) is exactly a high-multiplicity single-crossing electorate. Monroe’s quota has a canonical limit: each selected candidate represents mass \(1/k\). For rational masses, the correspondence is exact: choosing a common denominator expands the society into a finite election, while any finite election becomes \(\mu_i=n_i/N\). The continuous objective is precisely the finite Borda dissatisfaction divided by \(N\).
Nothing essential depends on voter identity. The rule only uses rankings, candidate membership, assignment mass, and equal representation quotas. A plausible regime is a large electorate divided into ideological or geographic cohorts with identical rankings, where \(N\gg\tau\). Thus neither “no multiplicity” nor “identity-dependent objective” applies.
The proponent does overstate what Theorem 11 establishes. Its reduction does not show that the continuous problem remains hard with bounded \(\tau\), and divisibility may destroy the reduction. But that is a question about the answer, not about whether the mirror is worthwhile. If the hardness disappears, that is precisely a valuable Class A result; if it survives under compressed type descriptions, that is a Class B result. The paper’s reduction failing to settle the issue is a reason to study the mirror, not a reason to reject it.
Theorem 6 is an even harder anchor to defeat. Lemma 5 already identifies the relevant population structure: an optimal assignment partitions the ordered electorate into contiguous blocks. In a continuous society those become contiguous mass intervals. The finite dynamic program can then be reformulated over cumulative type masses, with a type split when a block boundary falls inside an atom. For \(\ell_1\), interval costs are weighted sums; for \(\ell_\infty\), the natural formulation is threshold feasibility. The resulting question can depend polynomially on \(m\), \(k\), \(\tau\), and the encoding length of the masses, rather than on an explicitly expanded population size \(N\).
Calling this “only a weighted version” is not a valid objection in this programme. That compression is the point of high multiplicity. A finite algorithm running in \(n\) is not automatically an algorithm for binary-encoded masses whose denominator may be exponentially larger than the input. Nor has the paper itself supplied a continuous-population complexity theorem: its dynamic program is stated for an explicit voter list, not for a mass-encoded society.
The only credible negative case is therefore modest: the continuous Monroe hardness claim is unproved, and the continuous CC algorithm requires a careful encoding and endpoint analysis. But those are open computational details. They do not reveal a modelling obstruction. The natural population, type space, objective, and proportionality constraints all survive. Consequently, the universal claim that no worthwhile continuous mirror exists cannot be defended for this paper; at least the two proposed mirrors are legitimate ChoCo problems, even if one or both ultimately turn out to be easy.
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.