| paper | Proportional Justified Representation |
| authors | Luis Sánchez-Fernández, Edith Elkind, M. Lackner, N. F. García, Jesús Arias Fisteus, P. Basanta-Val et al. |
| venue | AAAI 2017 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates (mathcal{C}), committee size (k), a finite approval-type set (mathcal{T}subseteq 2^{mathcal{C}}), and rational masses (mu_Age0) summing to (1), decide whether some (Wsubseteq\mathcal{C}) with (|W|=k) admits nonnegative masses (x_{A,w}) such that (x_{A,w}=0) for (wnotin A), (sum_{win W}x_{A,w}=mu_A) for every (A), and (sum_{Ainmathcal{T}}x_{A,w}=1/k) for every (win W); if so, output (W) and such an assignment.
An atomless society of total mass (1) is partitioned by approval type (A) with mass (mu_A); the integral decision is the committee (W), while (x_{A,w}) records measurable pieces of type mass assigned one approved representative (w), with each winner receiving (1/k).
The paper's FPR formulation is exactly the same type-mass flow after aggregation, so the continuous problem may add no new mathematical constraints or algorithmic content.
fatal: False
The mirror covers Theorem 1's (mathrm{PR})-existence hardness and the surrounding (mathrm{PR}/mathrm{FPR}) feasibility relationship; it leaves the axiomatic incompatibility, (mathrm{PJR}/mathrm{EJR}) guarantees, average-satisfaction results, and rule-characterization theorems unmirrored.
The strongest honest positive case is a genuine Class B mirror of the paper’s PR-existence problem. It does not claim that continuity makes representation easy; it claims that the population can be made continuous while the committee-selection problem remains recognisably the authors’ problem.
My lead anchor is Theorem 1, proved in this paper. It states:
Given an approval profile \(\mathcal A\) and a committee size \(k\) dividing the number of voters \(n\), deciding whether there exists a size-\(k\) committee providing Perfect Representation is NP-complete.
Here PR means that the voters can be partitioned into \(k\) groups of exactly \(n/k\) voters, with one distinct committee member assigned to each group, such that every voter in a group approves its assigned member. The paper proves membership in NP through a \(b\)-matching formulation and obtains NP-hardness by adapting the X3C-based hardness construction for Monroe score. Thus the theorem is proved here, although its reduction adapts an earlier result.
I would mirror it with the following problem, which I would call Atomless Perfect-Representation Existence, or \(\mathrm{PR}_\infty\)-Existence.
An instance consists of a candidate set \(C\), a committee size \(k\), and an explicitly listed finite set of approval types \(\mathcal T\subseteq 2^C\). Type \(A\in\mathcal T\) consists of agents who approve exactly the candidates in \(A\). The society is an atomless population of total mass \(1\), with rational mass \(\mu_A\ge 0\) of type \(A\), where \(\sum_{A\in\mathcal T}\mu_A=1\).
The question is whether there exists a committee \(W\subseteq C\) with \(|W|=k\) and a measurable assignment of population mass to committee members such that:
Equivalently, the solution is a committee \(W\) and nonnegative flows \(x_{A,w}\) satisfying \(x_{A,w}=0\) whenever \(w\notin A\), \(\sum_{w\in W}x_{A,w}=\mu_A\) for every type \(A\), and \(\sum_{A\in\mathcal T}x_{A,w}=1/k\) for every \(w\in W\). The objective is feasibility: output such a committee and assignment, or certify that none exists.
The \(x_{A,w}\) variables do not fractionalise the committee or the social outcome. The committee is still an integral \(k\)-set, and every infinitesimal agent receives one integral representative. They only describe how an atomless mass of otherwise identical agents is partitioned among approved representatives. That is exactly the co-modification forced by continuizing the population.
The natural regime is a large electorate, user base, or constituency with recurring approval profiles: for example, millions of residents choosing a fixed number of public projects, voters selecting a parliamentary slate, or users whose approval patterns over recommendations cluster into a few hundred or thousand profiles. The number of agents can be enormous while the number of distinct approval types \(\tau=|\mathcal T|\) is much smaller. Agents with the same approval set are genuinely indistinguishable for the paper’s problem, so this is a proper high-multiplicity interpretation rather than an arbitrary loss of identity.
The bridge to Theorem 1 is exact. Given a finite profile with \(n_A\) voters of type \(A\), set \(\mu_A=n_A/n\). If \(k\mid n\), multiplying the continuous constraints by \(n\) produces a bipartite flow instance with integer type supplies \(n_A\) and integer committee capacities \(n/k\). By flow integrality, a feasible continuous assignment exists exactly when there is an integral assignment of individual voters, hence exactly when the original profile has a PR committee.
Therefore \(\mathrm{PR}_\infty\)-Existence is NP-hard, and in fact NP-complete under explicit rational encoding: guess \(W\), then test the induced flow problem in polynomial time. The expected classification is thus hardness transfers, not continuum-specific hardness. The assignment problem becomes a polynomial flow problem once \(W\) is fixed, but the combinatorics of choosing the candidates remain. This is precisely the paper’s X3C-style hardness, now exposed as hardness in the alternative structure rather than in named voter identities.
The paper is not already using this model. Its population is always a finite set \(N\) of named voters; its FPR variables fractionally represent those finite voters. The proposed mirror instead takes the distribution \(\mu\) as the primitive object and removes individual identities altogether. The paper’s FPR and flow discussion is excellent evidence that the authors would recognise the construction, but it is not a novelty collision with a continuous-population model.
This mirror deliberately covers Theorem 1 and the PR/FPR feasibility theme around it. It does not claim to continuize every axiomatic result in the paper, nor does it turn PJR or EJR into computational problems without further modelling choices.
The weakest point is that Theorem 1 by itself does not establish hardness when \(\tau\) is bounded or exceptionally small. Its reduction may use many distinct approval types. Replicating every type many times gives a genuinely huge high-multiplicity electorate with the same \(\mu\), but it does not prove hardness as a function of fixed \(\tau\). That is a real limitation, not a reason to reject the mirror: it becomes a further research question—whether \(\mathrm{PR}_\infty\)-Existence is tractable for bounded \(\tau\), fixed \(k\), restricted approval families, or whether candidate-side hardness persists under much stronger multiplicity compression.
The proponent’s construction is mathematically coherent, but its strongest anchor does not yield a new continuous problem. In an atomless population, the proposed mirror of Theorem 1 is exactly the paper’s FPR problem.
The reason is structural. In an atomless society, any type mass can be divided measurably. Thus, if type \(A\) has mass \(\mu_A\), an assignment to committee \(W\) is completely described by masses \(x_{A,w}\) satisfying
\[ \sum_{w\in W}x_{A,w}=\mu_A \quad\text{and}\quad \sum_A x_{A,w}=\frac1k. \]
Saying that every infinitesimal voter receives one integral representative does not restore the indivisibility present in Theorem 1: a type-\(A\) population can simply be partitioned into measurable pieces assigned to different approved candidates. Atomlessness makes precisely this splitting possible.
This is not merely analogous to FPR. It is exactly its type-compressed form. For rational \(\mu_A\), choose \(n\) such that \(n\mu_A\) is integral and create \(n\mu_A\) finite voters of type \(A\). Given \(x\), assign every such voter the fractional representation \(v_{i,w}=x_{A,w}/\mu_A\); conversely, aggregate the paper’s \(v_{i,w}\) variables over voters of the same type. The resulting constraints are identical. The paper’s individual-voter flow network therefore contracts directly to the proposed type-mass flow network.
Consequently, the paper has already formulated and computationally studied this object. Definition 4 introduces FPR, and Proposition 7 proves that deciding whether some committee provides FPR is NP-complete. The proposed \(\mathrm{PR}_\infty\)-Existence problem is therefore not a continuous mirror of Theorem 1 so much as a relabelling and compression of the paper’s own FPR problem. Theorem 1 concerns integral \(b\)-matching for finite voters; its atomless counterpart loses exactly that integrality and becomes FPR.
The obvious attempts to improve the mirror do not escape this collision. If one forbids splitting a type’s mass, one has imposed indivisibility at the type level, which is not implied by a continuous population and is not the paper’s PR requirement. If one retains indivisible unit voters, the society is finite again. If one adds identity-dependent constraints to preserve the distinction, one abandons the approval-type problem being mirrored.
There is no honest objection that recurring approval profiles are implausible: they are quite plausible, and the paper’s approvals are otherwise well suited to high multiplicity. The negative case rests instead on the fact that the only natural atomless formulation is already present in the paper as FPR, including its flow formulation and complexity result. A study of binary encoding or parameterization by the number of approval types could still be worthwhile, but that would be a compressed-complexity follow-up to FPR, not a new continuization of this paper.
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.