| paper | An Experimental View on Committees Providing Justified Representation |
| authors | Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, R. Niedermeier |
| venue | IJCAI 2019 |
| 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{NP}\text{-complete}\); also \(\mathrm{W}[1]\text{-hard}\) parameterized by \(k\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), a rational distribution \(\mu=(\mu_A)_{A\subseteq C}\) over approval types, and a rational threshold \(q\), decide whether there exists \(W\subseteq C\) with \(|W|=k\), \(b_\mu(c,W)<1/k\) for every \(c\in C\), and \(\operatorname{cov}_\mu(W)=\sum_{A:A\cap W\neq\varnothing}\mu_A\ge q\).
Approval-set types \(A\subseteq C\) carry population masses \(\mu_A\); the decision variable is an integral committee \(W\subseteq C\) with \(|W|=k\); JR requires \(b_\mu(c,W)=\sum_{A:c\in A,\ A\cap W=\varnothing}\mu_A<1/k\); the objective is coverage, or analogously satisfaction \(\operatorname{sat}_\mu(W)=\sum_A\mu_A|A\cap W|\).
The mirror covers the paper's computational results on JR-constrained satisfaction and coverage, counting JR/PJR/EJR committees, and necessary JR/PJR/EJR membership. It leaves the experimental sampling, empirical election generators, voting-rule comparisons, and noncomputational discussion untouched.
The strongest honest case is a weighted approval-profile mirror. It probably lands in Class B rather than revealing a new tractable continuum problem, but it is a genuine continuous-population version of the paper’s computational questions.
Let \(C\) be the candidate set and \(k\) the committee size. A voter type is an approval set \(A\subseteq C\). A society is a rational distribution \(\mu=(\mu_A)_{A\subseteq C}\), where \(\mu_A\) is the fraction of voters with approval type \(A\). The committee remains an integral set \(W\subseteq C\) with \(|W|=k\); only the population is continuous.
For \(c\in C\) and \(W\), define the mass of voters who approve \(c\) but approve no committee member by
\[ b_\mu(c,W)=\sum_{\substack{A\subseteq C\\c\in A,\ A\cap W=\varnothing}}\mu_A. \]
The continuous committee \(W\) satisfies JR exactly when
\[ b_\mu(c,W)<\frac1k \qquad\text{for every }c\in C. \]
This is the direct mass analogue of the paper’s \(n/k\)-large, \(1\)-cohesive groups. Likewise, the normalized versions of the paper’s two quality measures are
\[ \operatorname{sat}_\mu(W)=\sum_A\mu_A|A\cap W| \]
and
\[ \operatorname{cov}_\mu(W)=\sum_{A:A\cap W\neq\varnothing}\mu_A. \]
They are respectively the average voter satisfaction and the fraction of the population covered.
The natural regime is a large electorate, perhaps a national association or federation choosing \(k\) projects from a moderate candidate slate. Many members belong to the same organizational, professional, geographic, or ideological blocs and therefore have the same approval ballot. Thus \(n\) may be in the millions while the number \(\tau\) of distinct approval types is only tens or hundreds. The paper’s own \(p\)-impartial-culture and Euclidean generators support this interpretation: as \(n\) grows, the empirical frequencies of approval ballots converge to a distribution \(\mu\). In a Euclidean model, \(\mu_A\) is the population mass of locations inducing approval set \(A\).
This is not fractionalizing the committee or replacing candidates by divisible goods. Every unit of population still receives an ordinary integral committee, and \(W\) is still a \(k\)-element set. Only voter counts become masses.
My lead anchor is Theorem 5. The paper states:
“MIN SATISFACTION (COVERAGE) JR COMMITTEE and MAX SATISFACTION (COVERAGE) JR COMMITTEE are all NP-hard, and W[1]-hard when parameterized by the committee size \(k\).”
The surrounding text adds that the same intractability applies to the PJR and EJR versions. This is an in-paper theorem, not an external result cited from elsewhere; the supplied conference text states it but omits its proof.
The continuous problem I would hand to a prover is:
MAX-COVERAGE Continuous-JR Committee. An instance consists of \(C\), \(k\), a rational approval-type distribution \(\mu\), and a rational threshold \(q\). Decide whether there exists \(W\subseteq C\) such that \(|W|=k\), \(W\) satisfies continuous JR, and
\[ \operatorname{cov}_\mu(W)\ge q. \]
The optimization version asks for a continuous-JR committee maximizing \(\operatorname{cov}_\mu(W)\). This is plainly the paper’s question about finding the best-covered JR committee, with voter counts replaced by population mass. The analogous satisfaction version replaces \(\operatorname{cov}_\mu(W)\) by \(\operatorname{sat}_\mu(W)\); minimum versions reverse the inequality.
The discrete-to-continuous correspondence is exact. Given a finite election with \(n\) voters, set
\[ \mu_A=\frac{|\{i:A_i=A\}|}{n}. \]
Then
\[ \operatorname{cov}_\mu(W)=\frac{\operatorname{score}_{CC}(W)}{n} \quad\text{and}\quad \operatorname{sat}_\mu(W)=\frac{\operatorname{score}_{AV}(W)}{n}, \]
and \(W\) is discrete-JR precisely when it satisfies the mass condition above. A discrete threshold \(x\) becomes \(q=x/n\). Hence the NP-hardness and W[1]-hardness transfer directly. I would expect this mirror to be Class B: the hardness lives mainly in selecting candidates and satisfying the representation constraints, not in the multiplicity of named voters.
The second anchor is Theorem 1. It states:
“\(\#\mathrm{JR\ COMMITTEES}\), \(\#\mathrm{PJR\ COMMITTEES}\), and \(\#\mathrm{EJR\ COMMITTEES}\) are \(\#\mathrm P\)-hard.”
This theorem is proved in the paper. The displayed proof gives the JR case by reducing from \(\#\mathrm{PERFECT\ MATCHINGS}\); the theorem asserts the corresponding hardness for PJR and EJR as well.
The corresponding continuous problem is:
\(\#\)Continuous-JR Committees. Given \(C\), \(k\), and a rational approval-type distribution \(\mu\), output
\[ \left|\left\{W\subseteq C: |W|=k,\ W\text{ satisfies continuous JR}\right\}\right|. \]
This is a natural continuous version of the paper’s central quantitative question: how many committees meet the representation requirement, and therefore what fraction of all \(k\)-committees would satisfy it under uniform random selection? The output is still an integer because committees remain discrete; the population is the continuous object.
Again, every finite election maps exactly to such a distribution, so the \(\#\mathrm P\)-hardness transfers. The expected classification is therefore Class B. The interesting follow-up is whether the problem remains \(\#\mathrm P\)-hard under genuinely compressed regimes with \(\tau\ll n\), whether approximate counting becomes possible, and whether the problem is fixed-parameter tractable in parameters such as \(\tau\), \(m\), or \(k\).
The third anchor is Theorem 2. It states:
“The problem of checking if a candidate is a necessary JR member for a given election is coNP-hard, and co-W[1]-hard when parameterized by the committee size \(k\). The same holds for PJR and EJR.”
This is again the paper’s own theorem, not an externally cited result; the supplied text states it without including the proof.
The continuous mirror is:
Necessary Continuous-JR Member. Given \(C\), \(k\), a rational approval-type distribution \(\mu\), and a candidate \(p\in C\), decide whether every size-\(k\) committee satisfying continuous JR contains \(p\).
Equivalently, decide whether there is no continuous-JR committee \(W\) with \(p\notin W\). This preserves the paper’s exact semantic question: is \(p\) unavoidable among all representation-valid committees? It is not a softened question about expected membership or fractional committee selection.
The discrete hardness transfers for the same reason: normalizing voter multiplicities preserves exactly which committees are JR. I would again classify this as Class B, with the same coNP-hardness and co-W[1]-hardness parameterized by \(k\). A further question is whether the corresponding continuous necessary-member problems for PJR and EJR behave differently when mass is genuinely compressed.
The paper’s authors should recognize these as their problems because the mirror changes neither the approval language, the committee, the JR condition, nor the quality criteria. It only replaces repeated voter identities by their empirical distribution. In fact, the paper already treats election families probabilistically and reports frequencies of approval patterns, so the population-limit interpretation is close to the statistical object underlying its experiments.
The weakest point is that this mirror does not promise a tractability payoff. For these three anchors, the most credible prediction is that hardness survives: the continuous model exposes that the difficult combinatorics lie in the candidate set and the family of possible committees, not in counting individual voters. If the programme required every mirror to produce a new polynomial-time algorithm, this would be a weak case. But the programme explicitly includes Class B. Here the continuous questions are precise, high-multiplicity versions of the paper’s own counting, necessity, and committee-quality problems, and they show where continuization stops helping.
The strongest negative case is that all three anchors collapse to the same objection: the proposed continuum is only a lossless histogram of approval ballots. The paper’s computational difficulty lies in choosing the \(k\)-element committee, while voter identities never matter.
For any rational distribution \(\mu\), choose a common denominator \(D\) and create \(D\mu_A\) voters of each approval type \(A\). Conversely, every finite election induces such a \(\mu\). For every committee \(W\),
\[ b_\mu(c,W)=\frac{1}{D} \left|\{i:c\in A_i,\ A_i\cap W=\varnothing\}\right|, \]
so \(W\) satisfies continuous JR exactly when it satisfies ordinary JR. Likewise,
\[ \operatorname{cov}_\mu(W)=\frac{\operatorname{score}_{CC}(W)}{D}, \qquad \operatorname{sat}_\mu(W)=\frac{\operatorname{score}_{AV}(W)}{D}. \]
Thus the proposed MAX/MIN SATISFACTION and COVERAGE mirrors of Theorem 5 do not expose a new representation problem. They merely replace explicit voter lists by weighted approval ballots. A Euclidean population does not improve the situation: once locations are used only to induce approval sets, its measure can be pushed forward to the same finite distribution over approval types. Retaining the geometry would produce a different spatial-voting problem, not a mirror of this paper.
The same objection applies to Theorem 1. The output of \(\#\mathrm{JR\ COMMITTEES}\) is a count of candidate subsets, not a count or optimization over population mass. The continuous population only changes the predicate tested for each \(W\). The \(\#\mathrm P\)-hardness reduction can also be made genuinely high-multiplicity by duplicating every voter type the same number of times; the JR threshold and the set of valid committees are unchanged. Nothing about the continuum creates a new source of structure in the counting problem.
Theorem 2 is no better as a source of a distinct continuous question. Necessary JR membership asks whether every valid committee contains \(p\), and validity depends only on the aggregate approval masses. Replacing named voters by masses preserves the quantification over committees exactly. There is no measure-zero degeneration: the relevant threshold remains the positive mass \(1/k\). The PJR and EJR variants require some care in translating “a group” and “some voter” to measurable mass, but the JR version already gives the proposed anchor, so that technical issue cannot rescue the negative case.
This is the best argument against the mirrors: they are not continuizations in which new continuous optimization machinery becomes relevant. They are weighted, compressed forms of the same finite-candidate problems. If “worthwhile” required a continuum-specific algorithmic phenomenon, these anchors would fail.
But under ChoCo’s stated standard, that objection is insufficient. The programme explicitly treats high multiplicity as a legitimate continuous population regime, explicitly allows Class B outcomes, and regards hardness surviving continuization as a valuable boundary result. The compressed representation can also be exponentially shorter than the expanded election when multiplicities are large, so it is not merely a syntactic change from a complexity-theoretic perspective.
Consequently, I cannot honestly sustain the universal negative claim. The proponent has three valid mirrors, and Theorem 5 is especially robust: approval types, aggregate satisfaction, coverage, and JR are all exactly the objects the paper studies. The negative case can show that these mirrors are likely Class B and should not be oversold as new tractable phenomena, but it cannot show that they are not worthwhile under the programme’s own rules.
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.