| paper | The Price of Justified Representation |
| authors | Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong |
| venue | AAAI 2022 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.1
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), committee size \(k\), nonempty approval types \(A_1,\ldots,A_\tau\subseteq C\), and rational masses \(\mu_t\ge0\) summing to \(1\), choose \(W\subseteq C\) with \(|W|=k\) maximizing \(\mathrm{sw}_\mu(W)=\sum_{t=1}^{\tau}\mu_t|A_t\cap W|\), subject to \(\sum_{t:\,c\in A_t,\;A_t\cap W=\varnothing}\mu_t<1/k\) for every \(c\in C\); also study the fixed-\(\varepsilon\) approximation version with \(\varepsilon\in(0,1/2)\).
An anonymous high-multiplicity approval election: types are complete approval ballots \(A_t\), masses are \(\mu_t\), the decision variable is an integral committee \(W\), and the objective is weighted utilitarian welfare under per-candidate unrepresented-mass JR constraints.
The exact hardness transfer does not establish hardness or a tractability boundary when the support size \(\tau\) is small, so it does not yet isolate what computational work is caused by population multiplicity.
fatal: False
It directly covers Theorem 4.1's \(k^{1/2-\varepsilon}\)-inapproximability result for welfare-maximizing JR committees; it leaves the price bounds, EJR results, empirical study, and Theorem 4.5's \(1\mathrm{D}\)-VCR exact algorithm outside the mirror.
The strongest honest case is a direct population mirror of the paper’s main hardness result, Theorem 4.1. This theorem is proved in the paper, strengthening the earlier result of Bredereck et al. (2019): for every \(\varepsilon\in(0,1/2)\), it is NP-hard to find a JR committee with welfare within a factor \(k^{1/2-\varepsilon}\) of the best JR committee, even when \(k=n/2\).
A plausible high-multiplicity setting is a large professional association or public organisation choosing \(k\) representatives from \(m\) candidates. Millions of members vote, but their approval ballots come from a relatively small menu of recurring role-, region-, or policy-based profiles. A type is one complete approval ballot \(A_t\subseteq C\); \(\mu_t\) is the fraction of members with that ballot. Thus \(n\) may be enormous while \(\tau\), the number of distinct ballot types, is much smaller. This is not a probability model or a fractional committee: it is a deterministic population measure, while the committee remains an ordinary \(k\)-element subset of candidates.
My lead continuous problem is:
JR-Welfare\(_\infty\). An instance consists of candidates \(C\), a committee size \(k\), finitely many nonempty approval types \(A_t\subseteq C\), and rational masses \(\mu_t\ge 0\) summing to \(1\). For a committee \(W\subseteq C\), define its normalized social welfare by \(\mathrm{sw}_\mu(W)=\sum_t\mu_t|A_t\cap W|\). Define the unrepresented mass approving candidate \(c\) by \(u_c(W)=\sum_{t:\,c\in A_t,\;A_t\cap W=\varnothing}\mu_t\). The committee satisfies \(\mathrm{JR}_\infty\) if \(u_c(W)<1/k\) for every candidate \(c\). The task is to find a size-\(k\) committee satisfying \(\mathrm{JR}_\infty\) and maximizing \(\mathrm{sw}_\mu(W)\); in the approximation version, for fixed \(\varepsilon\in(0,1/2)\), output \(W\) with \(\mathrm{sw}_\mu(W)\ge \mathrm{OPT}_{\mathrm{JR}}(\mu)/k^{1/2-\varepsilon}\).
The JR condition is not an arbitrary relaxation. In the discrete problem, JR fails exactly when there is a group of at least \(n/k\) voters who all approve some candidate \(c\), while none of them approves a member of \(W\). In the distributional model, the set of such voters has mass \(u_c(W)\). Hence the discrete condition translates exactly to \(u_c(W)<1/k\). This also avoids the awkward phrase “some voter in the group” in an atomless setting: a violation is precisely an unrepresented cohesive mass of at least \(1/k\).
The mirror should be recognisable to the authors. Every ingredient of their optimization problem survives unchanged: candidates, approval intersections, committee size, JR, and utilitarian welfare. Only voter counts become masses. It does not make the question easier by fractionalizing the committee or replacing JR with an average constraint; those would be outcome-space or objective changes outside the programme’s scope.
I expect this problem to be Class B: the hardness transfers. Given a discrete election with \(n_t\) voters of type \(A_t\), set \(\mu_t=n_t/n\). Then \(\mathrm{sw}_\mu(W)=\mathrm{sw}(W)/n\), the JR-feasible committees are exactly the same, and approximation ratios are unchanged. Therefore an algorithm for the continuous problem would solve the search problem in Theorem 4.1. The reduction’s combinatorics live in the candidate–approval incidence structure and the choice of the committee, not in the individuality of voters. Duplicating every voter \(R\) times creates an arbitrarily large population with the same distribution, so the mirror remains meaningful in a genuine high-multiplicity scenario.
This mirror covers Theorem 4.1 emphatically, but not every result in the paper. It naturally generates follow-up questions: whether the same formulation for EJR remains hard; whether the \(\sqrt{k}\)-type welfare price persists with masses; whether bounded \(\tau\), bounded \(k\), or one-dimensional approval structure yields fixed-parameter or polynomial algorithms; and whether the paper’s Theorem 4.5 extends to weighted voter types in the 1D-VCR domain.
The weakest point is that Theorem 4.1 itself does not prove hardness with a fixed small number of types. Its reduction may use many distinct ballots, and cloning voters increases multiplicity without reducing the support size \(\tau\). Thus this is a convincing continuous high-multiplicity formulation and a likely Class B problem, but not yet evidence that the continuous model produces a new tractability gain. A stronger follow-up would establish hardness or an algorithmic boundary parameterized by \(\tau\), explicitly separating population multiplicity from the approval-pattern combinatorics.
The proponent’s anchor is difficult to defeat honestly. Theorem 4.1 is a genuine computational result, and its population mirror is mathematically exact. Approval ballots are complete voter types for every quantity used here: both welfare and JR are anonymous. For a committee \(W\), the largest unrepresented cohesive group approving \(c\) is precisely the mass
\[ u_c(W)=\sum_{t:c\in A_t,\;A_t\cap W=\varnothing}\mu_t. \]
Thus \(W\) satisfies JR exactly when \(u_c(W)<1/k\) for every \(c\). For rational masses \(\mu_t=n_t/n\), this is equivalent to the paper’s discrete definition, while welfare is merely rescaled by \(1/n\). Replicating every voter any number of times produces an arbitrarily large population with the same feasible committees and approximation ratios. There is no identity-dependent objective, no vanishing individual effect, and no need to invent an implausible type: members of a large organisation can genuinely share recurring approval profiles.
The strongest negative argument is therefore narrower. The proposed mirror does not expose a new continuous optimization structure. The committee remains an integral \(k\)-subset, and the distribution contributes only coefficients to a weighted approval-election problem. The theorem’s reduction can be transferred verbatim because its combinatorial content lies in candidates and approval incidences. Moreover, the proponent has not shown hardness with bounded support \(\tau\), so the mirror does not yet demonstrate that population multiplicity—not merely a large approval-pattern hypergraph—is doing any computational work. If one insists on a genuinely compressed high-multiplicity regime with small \(\tau\), the claimed hardness transfer is unproved.
But this does not defeat the mirror under the programme’s rules. A weighted/high-multiplicity formulation is precisely the intended object, and a Class B result is explicitly valuable even when continuity does not make the problem easier. The absence of a new tractability gain is not an admissible objection. One could fairly say that the proponent overstates what Theorem 4.1 establishes: it validates the model and gives an immediate hardness baseline, but leaves the worthwhile question—what happens as a function of \(\tau\), or under structured approval types—untouched.
So the honest negative case is weak. This anchor survives: there is a sensible continuous population mirror, and no principled argument shows that it is not worth studying.
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.