| paper | Justified Representation in Approval-Based Committee Voting |
| authors | H. Aziz, Markus Brill, T. Walsh |
| venue | AAAI 2014 |
| 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{coNP}\)-complete under polynomial-time many-one reductions; \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 14
Continuous-EJR-Verification: given candidates \(C\), committee size \(k\), an explicit finite support \(T\subseteq 2^C\) with rational masses \(\mu_A\) summing to \(1\), and an integral committee \(W\subseteq C\) of size \(k\), decide whether for every \(1\le \ell\le k\) and every \(S\subseteq C\) with \(|S|=\ell\), \(\sum_{A\in T:S\subseteq A,\ |A\cap W|<\ell}\mu_A<\ell/k\).
Approval types are sets \(A\subseteq C\) with masses \(\mu_A\); the proposed committee \(W\) remains an integral \(k\)-subset, and the decision tests all cohesive type mass against the EJR quota, with no fractional committee or lottery.
The residual concern is that EJR ignores voter identity, so the mirror may expose weighted-profile compression rather than a new solution concept; this limits novelty but does not defeat the computational question.
fatal: False
The mirror covers Theorem 14's EJR verification problem and Theorem 13's fixed-\(\ell\) construction, while leaving full EJR committee construction, rule characterizations, core stability, and other axiomatic results aside.
My strongest positive case is a direct high-multiplicity mirror of the paper’s EJR verification problem. The mirror is convincing, although I expect its hardness to survive: the combinatorics live in candidate approval intersections, not in the identities of voters.
Consider a large electorate choosing a \(k\)-member committee from a fixed candidate set \(C\). A type is an approval set \(A\subseteq C\); agents with the same approval set are indistinguishable. The society is an explicit finite-support rational distribution \(\mu=(\mu_A)\) over approval types, with \(\sum_A\mu_A=1\). In a plausible regime, \(n\) may be millions while the number \(\tau\) of distinct approval types is perhaps hundreds or thousands: party supporters, institutional constituencies, or recurring issue-based approval patterns. The committee remains an integral \(k\)-element subset \(W\subseteq C\); only the population has been continuized.
My lead anchor is the paper’s Theorem 14, proved in this paper: given a ballot profile \(\mathcal A\), a target committee size \(k\), and a committee \(W\) with \(|W|=k\), checking whether \(W\) provides EJR is coNP-complete. EJR fails when there are an integer \(\ell\), \(1\le \ell\le k\), and at least \(\ell n/k\) voters who jointly approve at least \(\ell\) candidates while every voter in the group approves fewer than \(\ell\) members of \(W\). The paper proves hardness by reducing Balanced Biclique: the candidate-side incidence structure encodes the bipartite graph, while repeated voter blocks enforce the EJR quota. This is Theorem 14 in the long version of the paper. ([paper PDF](https://www.cs.cmu.edu/~conitzer/justifiedSCW.pdf))
The corresponding continuous problem is:
Continuous-EJR-Verification. An instance consists of a candidate set \(C\), a committee size \(k\), an explicit support \(T\subseteq 2^C\), rational masses \(\mu_A\) for \(A\in T\), and a proposed committee \(W\subseteq C\) of size \(k\). Decide whether \(W\) satisfies continuous EJR, meaning that for every \(\ell\in\{1,\dots,k\}\) and every \(\ell\)-element candidate set \(S\subseteq C\), the mass of types satisfying \(S\subseteq A\) and \(|A\cap W|<\ell\) is strictly less than \(\ell/k\). Equivalently, decide whether
\[ \sum_{\substack{A\in T\\S\subseteq A\\|A\cap W|<\ell}}\mu_A < \frac{\ell}{k} \]
for every such pair \((\ell,S)\).
A solution is YES or NO; a NO certificate is simply \((\ell,S)\) together with the rational mass sum witnessing violation. This is exactly the authors’ EJR question, with voter counts divided by \(n\). It does not fractionalize the committee, replace candidates by lotteries, or weaken the representation requirement.
The discrete problem embeds exactly. Given a finite profile with \(n\) voters, aggregate identical ballots into types and assign each type mass equal to its multiplicity divided by \(n\). Conversely, clearing denominators of any rational distribution produces a finite cloned electorate with identical EJR comparisons. Thus the paper’s Balanced Biclique reduction transfers. In its construction, the repeated block \(N_1\) already consists of \(\ell(s-1)\) identical approval ballots, while the graph’s candidate-side structure remains intact. The continuous version therefore preserves both the natural high-multiplicity regime and the source of hardness.
I expect Continuous-EJR-Verification to be coNP-complete under explicit rational-support encoding: coNP membership follows from the \((\ell,S)\) certificate above, and coNP-hardness follows by normalization of Theorem 14. This is Class B rather than continuum-specific hardness. That is still a successful mirror: it establishes that EJR verification remains computationally difficult even when a society is represented by masses, and it identifies precisely why continuization does not remove the difficulty.
My secondary anchor is Theorem 13, also proved in the paper: a committee providing \(\ell\)-JR can be computed in time polynomial in \(n\) and \(|C|^\ell\). The paper’s \(\ell\)-GreedyAV algorithm repeatedly finds an \(\ell\)-candidate set unanimously approved by at least \(\ell n/k\) voters, adds it to the committee, removes voters who now have at least \(\ell\) representatives, and fills any remaining committee positions arbitrarily. ([paper PDF](https://www.cs.cmu.edu/~conitzer/justifiedSCW.pdf))
Its continuous counterpart is:
Continuous-\(\ell\)-JR-Committee. Given \(C\), \(k\), a rational type distribution \(\mu\), and an integer \(\ell\), output a committee \(W\) of size \(k\) such that no mass at least \(\ell/k\) consists of types sharing \(\ell\) approved candidates while every such type has fewer than \(\ell\) representatives in \(W\).
The continuous greedy algorithm maintains residual type masses. If some \(\ell\)-set \(S\) has residual mass \(\sum_{A\supseteq S}\mu_A\ge \ell/k\), it adds \(S\) to \(W\) and deletes the residual mass of every type with at least \(\ell\) approved winners. When no such \(S\) remains, it fills the committee arbitrarily. The same counting argument proves correctness: every greedy round removes at least \(\ell/k\) mass, so a violating mass of \(\ell/k\) cannot survive until termination.
With explicit support, this runs in time polynomial in \(\tau\), \(m^\ell\), and the encoding length of the masses; for every fixed \(\ell\), it is polynomial-time. This is Class A for fixed \(\ell\). It is a genuine population-level formulation because mass is the quantity tested, removed, and carried through the algorithm, while the committee itself remains integral.
The authors should recognise both questions immediately. Their definitions use only approval sets, group sizes, intersections, and committee membership; voter names play no role. The replacement \(n^*/n\mapsto\mu(B)\) is therefore the natural high-multiplicity form of their problem. It also creates useful follow-up questions: does full continuous EJR committee construction become polynomial in \((\tau,m)\), despite the paper leaving the corresponding discrete problem open? Is Continuous-EJR-Verification fixed-parameter tractable in \(\ell\), \(k\), or \(\tau\)? Does coNP-hardness remain when \(\tau\ll n\) is explicitly bounded?
The weakest point is that Theorem 14 does not show hardness dissolving in the continuum; its reduction transfers almost by normalization, and its hard combinatorics live in candidate approval incidence rather than population multiplicity. Theorem 13 gives a clean fixed-\(\ell\) algorithm, but not a full-EJR algorithm. So this is not a claim that continuization makes this paper easy. It is a strong, faithful Class-B mirror: the paper’s central verification problem remains meaningful for a genuine distribution over voter types, its discrete and continuous variants have an exact rational-clone dictionary, and the fixed-\(\ell\) constructive result survives with dependence on the number of types rather than the number of agents.
The strongest case against these mirrors is that both anchors are already exact weighted-profile problems, not problems that become different when the electorate is made continuous.
For Theorem 14, EJR verification never uses voter identity. Given a profile, replace each approval set \(A\) by its multiplicity \(n_A\), or equivalently by \(\mu_A=n_A/n\). This is a lossless quotient of the paper’s instance. The continuous condition is exactly
\[ \sum_{\substack{A\supseteq S\\ |A\cap W|<\ell}}\mu_A\ge \frac{\ell}{k} \]
for some \(\ell\) and \(S\). No individual-level information has been removed because EJR never refers to it.
This also defeats the strongest possible repair of the proposed mirror. Any distribution over approval types is already supported on the finite set \(2^C\). Refining types by party, income, identity, or any other attribute changes nothing unless that attribute enters EJR, in which case it is no longer the paper’s problem. Allowing an arbitrary measure therefore adds representation machinery, not a new social-choice object. Conversely, every rational \(\mu\) can be expanded into a cloned finite electorate. The continuous and discrete inputs are polynomially interconvertible as weighted approval profiles.
The same objection applies to Theorem 13. The \(\ell\)-GreedyAV proof uses only quantities of the form
\[ \sum_{A\supseteq S}\mu_A \]
and removes all types whose ballots have acquired \(\ell\) representatives. An implementation on integer multiplicities \(n_A\) is identical, with \(\mu_A\) replaced by \(n_A\). There is no fractional committee, fractional candidate, mass-transfer decision, or population-level optimization. The claimed replacement of dependence on \(n\) by dependence on \(\tau\) is exact aggregation of identical ballots. It is useful data compression, but not a new continuous algorithmic phenomenon.
A better version of the second mirror—full continuous EJR committee construction—does not repair this. It would be an interesting weighted version of the paper’s open problem, but its input and feasible committees remain exactly those of a finite approval election with multiplicities. The fixed-\(\ell\) theorem itself gives no genuinely new continuous object; it simply survives aggregation.
The most plausible high-multiplicity story—millions of voters belonging to a few recurring approval blocs—actually reinforces this criticism. Such a society is naturally represented by the integer or rational count vector \((n_A)\) already implicit in the paper. If the electorate is instead highly individualized, then \(\tau\) approaches the number of voters and the proposed advantage disappears. There is no intermediate modelling choice that makes population mass operationally important for these two results while preserving their definitions: EJR only sees aggregate mass, and the committee remains integral.
That is the best negative case, but it is not decisive under ChoCo’s rules. The paper contains named computational results, the approval-type distribution is a sensible high-multiplicity regime, and the continuous questions are well-posed. Exact clone-equivalence is not the same as a novelty collision, and the fact that the hardness reduction transfers is not an objection. I therefore cannot honestly defend the universal claim that no worthwhile continuous mirror exists. At most, I can argue that these particular mirrors are low-yield instances of continuization: they expose weighted-profile compression, not a new population-continuous computational landscape.
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.