| paper | The Complexity of Proportionality Degree in Committee Elections |
| authors | Łukasz Janeczko, Piotr Faliszewski |
| 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 |
Corollary 2
Given a finite candidate set \(C\), committee size \(k\), and rational finite-support distribution \(\mu=(\mu_A)_{A\subseteq C}\) over approval types \(A\subseteq C\), decide whether there exists \(W\subseteq C\) with \(|W|=k\) such that, for every \(\ell\in[k]\) and every subpopulation \(x\) satisfying \(0\le x_A\le\mu_A\), \(\sum_A x_A\ge\ell/k\), and \(x_A>0\Rightarrow R\subseteq A\) for some \(R\subseteq C\) with \(|R|\ge\ell\), we have \(\sum_A x_A|A\cap W|/\sum_A x_A\ge1\).
Approval types \(A\subseteq C\) are the only voter attributes; \(\mu_A\) is type mass, \(x_A\) is subpopulation mass, \(W\) is an integral \(k\)-committee, and feasibility requires minimum average satisfaction \(\operatorname{sat}_W(x)=\sum_A x_A|A\cap W|/\sum_Ax_A\) at least \(1\).
The UNIT reduction's hardness is driven by the candidate–type incidence structure and uses essentially one type per original voter, so it does not yet demonstrate a population-multiplicity-specific phenomenon; this limits the payoff, but ChoCo explicitly permits faithful Class B mirrors.
fatal: False
It mirrors UNIT-PD-COMMITTEE through Theorem 6 and Corollary 2, and gives a CI/VI weighted analogue of Theorem 10; it does not cover the \(\#\mathrm{COHESIVE\text{-}GROUP}\) results, general PD-FAILURE or PD-VERIFICATION beyond the stated restrictions, or the FPT and structured counting theorems.
The strongest mirror is a literal high-multiplicity version of the approval society. A voter type is an approval set \(A\subseteq C\); a society is a rational distribution \(\mu=(\mu_A)_{A\subseteq C}\), given by its finite support. Here \(\mu_A\) is the fraction of voters with approval set \(A\), and \(\tau\) is the number of supported types. A subpopulation is a vector \(x\) with \(0\le x_A\le \mu_A\). Its mass is \(|x|=\sum_A x_A\).
Call \(x\) \(\ell\)-cohesive if \(|x|\ge \ell/k\) and some set \(R\subseteq C\), \(|R|\ge\ell\), is approved by every type used by \(x\): \(x_A>0\Rightarrow R\subseteq A\). For a committee \(W\), its average satisfaction on \(x\) is \(\operatorname{sat}_W(x)=\sum_A x_A|A\cap W|/|x|\). This is exactly the finite definition after replacing voter counts by population mass. The committee remains an ordinary \(k\)-element subset of \(C\); only the population is continuous.
My lead problem is \(\mathrm{UNIT\text{-}PD\text{-}COMMITTEE}_\infty\):
Given \(C\), \(k\), and \(\mu\), does there exist a committee \(W\subseteq C\), \(|W|=k\), such that \(\operatorname{sat}_W(x)\ge1\) for every \(\ell\in[k]\) and every \(\ell\)-cohesive subpopulation \(x\)?
A solution is the committee \(W\). The objective is feasibility of unit proportionality degree, not fractional committee selection.
This mirrors the paper’s Theorem 6, which proves that UNIT-PD-COMMITTEE is NP-hard, and Corollary 2, which records NP-completeness using Theorem 5. The result is proved in this paper, through a reduction from RX3C.
The reduction transfers cleanly. Given an RX3C instance with universe \(U\) of size \(3k\), create one approval type \(A_i\) for each element \(u_i\), where \(A_i\) consists of the candidate sets containing \(u_i\), and assign it mass \(1/(3k)\). Each candidate is approved by exactly three types, so its total approving mass is exactly \(1/k\). Consequently, a \(1\)-cohesive subpopulation sharing that candidate must contain all of its approving mass: fractional splitting cannot evade the reduction. No \(\ell\)-cohesive group exists for \(\ell\ge2\), since every common candidate has mass only \(1/k<\ell/k\). Thus a unit-PD committee exists exactly when the RX3C instance has an exact cover.
I therefore expect this continuous problem to be Class B: hardness transfers from the discrete problem. The combinatorics live in the candidate-set incidence structure, not in the granularity of the population. That is still a meaningful outcome for ChoCo: it identifies a natural continuous population model whose first hardness boundary is inherited rather than artificially introduced by the relaxation.
The regime is also sensible independently of the reduction. In a recommendation or search system, millions of users can be grouped into a finite catalogue of stable approval personas: users who approve the same candidate slate, topic bundle, or content category. A society might have \(N\gg\tau\), with \(\tau\) in the hundreds or thousands. Since approval sets are the only voter attributes used by PD, this is a genuine type in the programme’s sense, not an illicit identification of otherwise different agents. Mass is the honest quantity: a cohort representing \(16\%\) of users should be treated as \(16\%\), not as an arbitrary collection of named individuals.
A second useful mirror is the paper’s Theorem 10, which proves that PD-FAILURE is in P for candidate-interval and voter-interval elections. Define \(\mathrm{PD\text{-}FAILURE}^{\mathrm{CI/VI}}_\infty\) as follows. The input is \(C,k,\mu\), a size-\(k\) committee \(W\), a cohesiveness level \(\ell\), and a rational threshold \(y\). The question is whether there exists an \(\ell\)-cohesive subpopulation \(x\) with \(\operatorname{sat}_W(x)<y\). In the CI variant, every supported approval set is an interval in a supplied order of candidates. In the VI variant, the supported types are ordered population blocks and the types approving each candidate form an interval.
I expect this continuous problem to remain in P. In the CI case, enumerate consecutive blocks of \(\ell\) candidates. For each block, collect the mass of types approving it and take mass \(\ell/k\) from the least-satisfied types, allowing a fractional amount of the boundary type. In the VI case, enumerate relevant intervals of ordered type blocks and perform the same weighted minimum-average calculation. These are direct weighted versions of the scans in Theorem 10, polynomial in \(m\), \(\tau\), and the encoding length of the masses. This gives a Class A mirror on a structured domain, with the population continuum producing weighted optimization rather than changing the committee problem.
The scope is deliberately limited. I would not claim that the paper’s Theorem 2, the \(\#P\)-completeness of counting cohesive groups, has a straightforward continuous mirror: once subpopulations may be split continuously, there are generally infinitely many groups to count. One would need a different object, such as counting minimal common-approval regions or computing their measure, and that would no longer be the paper’s stated counting problem.
The weakest point is that the Theorem 6 reduction itself has essentially one type per voter, so it does not demonstrate a complexity improvement when \(N\gg\tau\). It proves that the mirror is a faithful Class B object, not that population multiplicity dissolves the hardness. The opposing analyst can therefore say that this is a weighted reformulation of an approval election. I concede that limitation. But it does not undermine the mirror’s plausibility: the continuous model is still the literal high-multiplicity version of the paper’s definitions, supports realistic large-cohort societies, preserves the paper’s hardness in a transparent way, and also yields a natural tractable weighted analogue of Theorem 10. The next questions are whether arbitrary-support PD-FAILURE or PD-VERIFICATION is Class B or Class C, whether fractional type boundaries create new hardness, and whether \(\mathrm{UNIT\text{-}PD\text{-}COMMITTEE}_\infty\) admits useful approximation or parameterized algorithms when \(\tau\) is small.
The strongest negative case is that both proposed mirrors collapse to finite weighted approval elections, with no population-level structure beyond the vector of masses. For a fixed committee \(W\), cohesiveness level \(\ell\), and common approved set \(R\), every admissible subpopulation is supported on
\[
B_R=\{A:R\subseteq A\}.
\]
Its worst average satisfaction is obtained by taking \(\ell/k\) units of mass from \(B_R\), beginning with the types having smallest \(|A\cap W|\). Thus the continuous problem is a finite weighted order-statistic problem. The continuum introduces fractional boundary mass, but no new group structure.
For the UNIT-PD anchor, this is especially clear. The RX3C construction uses one type per universe element, so \(\tau=3k\), and its hardness is entirely in the candidate–type incidence hypergraph. Replicating every type \(q\) times produces \(N=3kq\) voters while leaving \(\mu\) unchanged. Hence even an arbitrarily large population has exactly the same computational object. Seeking a better high-multiplicity scenario with large cohorts does not alter this: it merely gives the same weighted approval profile a more plausible story. The proposed mirror therefore supplies no evidence that population continuization exposes a distinct phenomenon.
That is a real limitation, but it is not quite a permissible objection under ChoCo’s rules. The programme explicitly treats faithful Class B transfers as worthwhile, and existing high-multiplicity work is supporting evidence rather than a collision. The RX3C argument does provide a legitimate continuous problem, and fractional splitting genuinely fails to destroy the reduction because each candidate has exactly \(1/k\) supporting mass.
Theorem 10 is harder to attack. In the candidate-interval case, the proponent’s weighted scan is sound: for each consecutive block of \(\ell\) candidates, one takes the least-satisfied mass, allowing a fractional final type. An atomless version changes only the integration over finitely many approval-pattern cells. In the voter-interval case, either the order is merely a certificate and identical approval types can be aggregated—in which case the model again reduces to a weighted finite profile—or location is itself relevant, in which case the problem has acquired a population-coordinate attribute absent from PD-FAILURE. That would be a new problem, but not a faithful mirror of the paper’s verification task.
Consequently, the universal negative claim cannot honestly be sustained. There is no identity obstruction, no degeneracy, no absence of a computational theorem, and no existing continuous treatment that closes the question. The best criticism is that the proposed mirrors are likely to be Class B or straightforward weighted versions, with limited evidence of a distinctive continuous payoff. But “the continuum does not help” and “the weighted algorithm is easy” are expressly not disqualifications. The UNIT-PD mirror alone is a valid high-multiplicity computational question, so the opposing case does not defeat every anchor.
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.