| paper | Full Proportional Justified Representation |
| authors | — |
| venue | AAMAS 2025 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.2
Given candidates \(C\), committee size \(k\), committee \(W\subseteq C\) with \(|W|=k\), distinct approval types \(A_1,\ldots,A_\tau\subseteq C\), and rational masses \(\mu_i\ge0\) summing to \(1\), decide whether for every integer \(\ell\ge1\), witness set \(Q\subseteq C\), and type subset \(I\subseteq\{1,\ldots,\tau\}\) satisfying \(\sum_{i\in I}\mu_i\ge|Q|/k\) and \(|A_i\cap Q|\ge\ell\) for all \(i\in I\), we have \(|W\cap\bigcup_{i\in I}A_i|\ge\ell\).
A high-multiplicity approval election with distinct approval types \(A_i\), rational masses \(\mu_i\), and an indivisible committee \(W\) of size \(k\); verification quantifies over witness sets \(Q\) and supported type subsets \(I\), asking whether every qualifying coalition receives collective approval of at least \(\ell\) committee members.
The mirror covers Theorem 4.2, the \(\mathrm{coNP}\)-completeness of FPJR verification; it leaves Theorem 3.11, Proposition 2.3, the corollaries, examples, and other axiomatic results unmirrored.
The strongest honest case is a direct high-multiplicity mirror of the paper’s verification result. It is a good Class B case: the continuous problem remains hard because the combinatorics live in the candidate and witness sets, not in the number of individually named voters.
The paper’s only qualifying named computational anchor is Theorem 4.2, proved in this paper:
“The following problem is coNP-complete: Given an arbitrary ballot profile \(A\) and a winning set \(W\), does \(W\) satisfy FPJR?”
I would use this as the lead and not pad the case with Theorem 3.11 or the rule-property corollaries: those are important axiomatic results, but they are not named complexity classifications.
Call the mirror Continuous-FPJR Verification. An instance consists of a candidate set \(C\), a committee size \(k\), a proposed committee \(W\subseteq C\) with \(|W|=k\), and a finite list of distinct approval types \(A_1,\ldots,A_\tau\), where each \(A_i\subseteq C\). Type \(i\) has rational mass \(\mu_i\ge 0\), with \(\sum_i\mu_i=1\). The question is whether \(W\) satisfies the following continuous FPJR condition.
For every integer \(\ell\ge 1\), every witness set \(Q\subseteq C\), and every set of types \(I\subseteq\{1,\ldots,\tau\}\) such that \(\sum_{i\in I}\mu_i\ge |Q|/k\) and \(|A_i\cap Q|\ge \ell\) for every \(i\in I\), we require \(\left|W\cap\bigcup_{i\in I}A_i\right|\ge \ell\).
Equivalently, one may describe a coalition by mass variables \(0\le \lambda_i\le\mu_i\). It is weakly \(\ell\)-cohesive with witness \(Q\) when \(\sum_i\lambda_i\ge |Q|/k\) and \(\lambda_i>0\) implies \(|A_i\cap Q|\ge\ell\). Its representation is measured by \(\left|W\cap\bigcup_{\lambda_i>0}A_i\right|\). For verification, it is enough to take all mass of every selected type, so the finite-support formulation above is exact.
This is recognizably the authors’ problem. The type is precisely an approval ballot, which is the complete information used by FPJR. Mass replaces \(|S|/n\); the witness condition and collective-utility condition are unchanged. The committee remains an ordinary size-\(k\) subset of candidates, so this does not fractionalize the outcome or quietly replace approval voting by probabilistic committee selection. Only the population is continuized.
The natural regime is a large approval-based election, participatory-budgeting consultation, or representative committee selection process in which millions of voters produce a much smaller number of recurring approval patterns. Standardized issue bundles, party or organizational recommendations, and common policy packages can make many voters have exactly the same approval ballot. Thus \(n\) may be very large while \(\tau\ll n\), with the published or computationally relevant input being the rational ballot-type distribution \(\mu\).
The hardness transfer is especially clean. Given a finite election, aggregate voters with identical approval sets and set \(\mu_i\) equal to the fraction of voters of type \(i\). A discrete FPJR violation maps to a continuous one by taking the types appearing in the violating coalition. Conversely, a continuous violation maps back by taking all finite voters of each selected type. The approval union is unchanged, while the mass threshold is exactly the original population threshold. Therefore the discrete and continuous verification questions are equivalent after aggregation.
The coNP membership also survives: a violating certificate consists of \(\ell\), a witness set \(Q\), and a type subset \(I\), and all three conditions can be checked exactly using rational arithmetic. Hence Continuous-FPJR Verification should itself be coNP-complete under the natural support-list representation.
This hardness is not undermined by the fact that the reduction in Theorem 4.2 contains some singleton voter classes. Clone every original voter type \(q\) times. The number of agents becomes \(qn\), the number of types stays \(\tau\), and the normalized distribution is unchanged. Thus the same continuous instance represents electorates with arbitrarily large multiplicity per type. The reduction’s real combinatorics concern selecting candidate witnesses and approval-type coalitions corresponding to balanced bicliques. This is precisely the programme’s Class B pattern: hardness transfers because it is driven by the agenda, not by voter individuation.
The main weakness is that this mirror does not promise a tractable continuous relaxation or a new continuum-specific phenomenon. A referee could fairly call it a weighted, compressed restatement of the finite verification problem. I would concede that. Its positive value is instead that it is a faithful high-multiplicity object whose input size depends on distinct approval types rather than named voters, while preserving the paper’s exact FPJR predicate and its coNP-completeness. That is already a legitimate continuous-computational result under the programme’s stated scope.
It also generates natural follow-up questions: whether verification is fixed-parameter tractable in \(\tau\), \(k\), or restricted approval structure; whether a continuous greedy-Monroe construction based on assigning exactly \(1/k\) mass to each selected candidate satisfies FPJR; and whether analogous continuous verification problems for FJR, core stability, or participatory budgeting exhibit the same transferred hardness.
The strongest negative argument is that FPJR has almost no genuinely continuous population structure to exploit. For a society with approval types \(A_1,\ldots,A_\tau\) and masses \(\mu_i\), a coalition using masses \(\lambda_i\) is characterized only by its positive-support set \(I=\{i:\lambda_i>0\}\). If it violates FPJR, replacing every \(\lambda_i\) by the full mass \(\mu_i\) preserves the approval union and all type-level cohesiveness conditions, while only increasing coalition mass. Thus fractional participation within a type is irrelevant.
Consequently, the proposed mirror is exactly the weighted finite predicate
\[ \sum_{i\in I}\mu_i\ge \frac{|Q|}{k} \quad\text{and}\quad \left|W\cap\bigcup_{i\in I}A_i\right|<\ell. \]
For rational masses, a common denominator turns the instance into a finite election with cloned voters. Conversely, aggregating identical ballots produces the continuous instance. A more elaborate measurable-coalition formulation therefore collapses to the same object. Allowing fractional committees, probabilistic approvals, or geometric voter types would create different problems—outcome-space or preference-space continuization—not mirrors of this paper’s FPJR result.
That is a legitimate criticism of novelty: unlike R-Swap Bribery, there is no mass-transfer optimization, separation problem, or nontrivial continuum geometry here. The population distribution is merely a weighted encoding of a finite approval set system. The paper’s other results do not repair this: Theorem 3.11 and the rule-property corollaries are axiomatic guarantees, not additional computational anchors, and the natural continuous versions of their constructions would simply assign mass in units of \(1/k\).
But this does not defeat the proponent’s anchor under ChoCo’s stated rules. Theorem 4.2 is an explicit computational result, and its continuous version is well-defined. Approval elections with many repeated ballots are an entirely credible high-multiplicity regime. The coNP-hardness reduction survives aggregation, and cloning every voter type gives arbitrarily large multiplicity without changing the support distribution. The fact that the resulting problem is Class B rather than Class A is expressly not an objection: the programme counts transferred hardness as a worthwhile outcome.
So the honest negative case is weak. I would describe the mirror as low in conceptual novelty and unlikely to produce the programme’s characteristic continuous-optimization insights, but I cannot responsibly claim that no worthwhile mirror exists. The direct continuous FPJR-verification anchor survives.
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.