| paper | d4-conf-ecai-2012-0131 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable for every fixed \(w\), in \(m,\tau,\kappa,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), a support \(T\) of \(\tau\) complete rankings with positive binary-rational masses \(\lambda_t\) summing to \(1\), committee size \(\kappa\), a nondecreasing misrepresentation function \(g\), and a compatible ordered candidate partition \((C_1,\ldots,C_q)\) of width \(w=\max_i |C_i|-1\), compute a committee \(S\subseteq C\) of size \(\kappa\) minimizing \(\sum_{t\in T}\lambda_t\min_{c\in S} g(r_t(c))\). For fixed \(w\), can this be done in time polynomial in \(m\), \(\tau\), and the input bit length \(L\)?
Mass-weighted Chamberlin–Courant proportional representation: ranking types carry rational population masses, while the committee remains a set of \(\kappa\) candidates and the objective is the mass-weighted sum of each type’s best-representative misrepresentation.
The mirror covers Theorem 1’s bounded-width proportional representation algorithm and Theorem 2’s width computation for narcissistic support. It leaves general-width proportional representation and minimum-width computation for non-narcissistic profiles unresolved.
The strongest honest case is an algorithmic one. The paper has no numbered hardness theorem: its introduction cites Procaccia et al. [11] for NP-hardness of general proportional representation, but that is background rather than a numbered result proved here. My anchors are therefore Theorem 1 and, more tentatively, Theorem 2, both proved in this paper.
Take a large ranked-ballot electorate in which many people share the same complete ranking. A type \(t\) is one such ranking; its mass \(\lambda_t>0\) is the fraction of the electorate with that ranking, with \(\sum_{t\in T}\lambda_t=1\). The input lists the \(\tau\) supported rankings and their rational masses. A plausible regime is millions of voters but only hundreds or thousands of recurring ranking types, perhaps organized around party or candidate clusters. The committee remains a set of \(\kappa\) actual candidates; only the electorate is represented by a distribution.
My lead question is Mass-CC at bounded clustered width. Its instance is \(C\), the ranking types \(T\) and masses \(\lambda_t\), a committee size \(\kappa\), a nondecreasing misrepresentation function \(g\), and an ordered candidate partition \(\mathcal C=(C_1,\ldots,C_q)\) compatible with clustered single-peakedness for every supported ranking. The width is \(w=\max_i |C_i|-1\), assumed bounded by a fixed constant. The question is to return a committee \(S\subseteq C\), \(|S|=\kappa\), minimizing
\[
F_\lambda(S)=\sum_{t\in T}\lambda_t\min_{c\in S}g(r_t(c)).
\]
This preserves Chamberlin–Courant’s exact objective and decision: the mass of each ranking type receives the misrepresentation of its best representative in \(S\).
Theorem 1 says that proportional representation over preferences of bounded single-peaked width is polynomial-time solvable. It is proved here. In the paper’s dynamic program, sums over voters can be replaced by mass-weighted sums over distinct ranking types. Its stated \(O(nq^2t2^{2t}\kappa)\) work therefore replaces the voter-count factor \(n\) with support size \(\tau\); the width-zero case is trivial. With fixed width, the mirror is polynomial in \(m,\tau\), and the binary input length \(L\). The paper’s recurrence also gives an FPT dependence on width. I expect Class A: tractable by the same structural dynamic program and exact rational arithmetic. This is a direct weighted extension of the result, not a claim that the paper already proves a theorem about mass inputs.
A second, useful anchor is Theorem 2, which says that finding the single-peaked width is polynomial when the preference profile is narcissistic. It too is proved here. Its continuous question is: given \(C,T,\lambda\), with every candidate top-ranked by some positive-mass type—that is, \(\sum_{t:\operatorname{top}(t)=c}\lambda_t>0\) for every \(c\)—find the minimum width of an ordered partition compatible with all supported rankings, and return such a partition. The paper’s forbidden-minor and contraction procedure depends on the profile’s rankings and top choices, so duplicate rankings can be collapsed; the continuous version is polynomial in \(m\) and \(\tau\). I expect Class A here as well. This result can supply the partition required by the lead problem in narcissistic societies. It is a weaker anchor for population continuization because the masses’ magnitudes do not affect the answer once support is fixed.
The mirror is plausible to the authors: it retains their candidates, committee size, ranking-based misrepresentation, clustered single-peaked condition, and exact winner. It replaces the sum over individually listed voters with the expectation over ranking types. For a finite election with \(n_t\) voters of type \(t\), setting \(\lambda_t=n_t/n\) gives \(F_\lambda(S)=s(S)/n\), so the winners are unchanged. Conversely, any rational mass profile can be scaled to an equivalent finite replicated profile. This is precisely a compact high-multiplicity representation; the paper itself still writes one column per voter. The continuous formulation does not make the committee fractional.
The scope is the paper’s bounded-width PR algorithm and its narcissistic width-finding result. It does not cover general-width PR or give a new hardness theorem. The general Mass-CC question is a natural follow-up: the paper’s cited discrete NP-hardness embeds through the rational normalization above, so I expect that unrestricted problem to be hardness-transferring (Class B). Another follow-up is whether minimum width can be found in polynomial time for non-narcissistic support, which the paper explicitly leaves open.
The soft spot is that the lead theorem is already polynomial for the corresponding finite, bounded-width problem. The continuous version’s main gain is expressing and solving it in time tied to the number of distinct types rather than the total electorate; it does not show discrete hardness dissolving. Theorem 2 also requires every candidate to have positive-mass top support. So this is a credible mirror of the authors’ problem, but its strongest contribution is a precise compressed-population formulation and algorithm, not a dramatic change in complexity.
The strongest case against is that these mirrors may add little beyond compressing the paper’s existing finite profile. In the proportional representation objective, each voter contributes independently according to their ranking. Replacing the voter list with ranking types and masses leaves the committee choices and their ordering unchanged. Theorem 1’s dynamic program already sums voter contributions; grouping identical rankings turns those sums into mass-weighted sums. That is a natural high-multiplicity implementation, but it introduces no new optimization structure or continuous technique. For any rational mass vector, scaling by a common denominator recovers an equivalent finite election with the same winners.
That objection weakens against the better version of the mirror. The scaled election may be exponentially larger than the binary rational input, so the continuous formulation asks a real computational question: can the exact answer be found in time polynomial in the support size and bit length? The recurrence appears to answer yes by aggregation, and the paper’s theorem does not state that bound. Under ChoCo’s high-multiplicity brief, this is a legitimate result, even if the proof may be a modest adaptation.
Theorem 2 is a less compelling anchor. Its continuous version asks for minimum width when every candidate is top-ranked by some positive-mass type. But the masses themselves play no role: the answer depends only on which rankings occur. The same instance is obtained by giving each supported ranking equal mass. Arbitrarily small positive mass can change the result just as a single extra voter can in a finite profile, so this is best understood as a support-recognition problem rather than a result about aggregate population behaviour. Still, it is a named computational result about the distribution’s support, and the programme permits that kind of high-multiplicity question.
The negative case therefore rests on incremental value: Theorem 1 looks like a direct aggregation of an existing dynamic program, and Theorem 2 is insensitive to mass magnitudes. Neither point rules out a worthwhile mirror. The ranked-ballot type space is natural, individual identities do not matter to the objective, and the bounded-width algorithm can operate on a compact population description. I cannot honestly defeat the stronger version of the Theorem 1 mirror; claiming that no scenario makes it worthwhile would overstate the case.
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.