| paper | Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules |
| authors | Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu |
| venue | IJCAI 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 8
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), a supplied set \(D\subseteq C\), approval types \(A_1,\ldots,A_\tau\subseteq C\) with rational masses \(\mu_i\ge0\) summing to \(1\), and a threshold \(R\), where deleting \(D\) makes every \(A_i\cap(C\setminus D)\) an interval on one common axis, decide whether some \(W\subseteq C\) with \(|W|=k\) satisfies \(\sum_i\mu_i\mathbf{1}[A_i\cap W=\varnothing]\le R\).
A finite distribution of anonymous approval types with masses \(\mu\); the decision variable is an integral committee \(W\) of size \(k\), and the objective is the fraction of population whose approval set contains no member of \(W\). The candidate-deletion set \(D\) and interval promise are retained exactly.
The mirror covers Theorem 8, including its \(O^*(2^d)\) algorithm and SETH-based lower bound for Approval-CC with a supplied candidate-deletion set. It leaves the single-peaked algorithm of Theorem 6, Observation 7, and the Thiele and generalized-Thiele results of Theorems 10–13 largely untouched.
The strongest honest case is built around the paper’s Theorem 8, proved in this paper, although the authors note that the result was previously presented by Misra et al. The theorem gives an \(O^*(2^d)\)-time algorithm for Chamberlin–Courant with a given candidate-deletion set \(D\) of size \(d\), and proves under SETH that no \(O^*((2-\varepsilon)^d)\)-time algorithm exists, even for approval ballots.
I would call the mirror Approval-CC Candidate-Deletion\(_\infty\). An instance consists of candidates \(C\), committee size \(k\), a supplied candidate-deletion set \(D\subseteq C\), and a finite list of distinct approval types \(A_1,\ldots,A_\tau\subseteq C\) with rational masses \(\mu_1,\ldots,\mu_\tau\ge 0\), where \(\sum_i\mu_i=1\). The instance has the same promise as the paper: after deleting \(D\), the approval types are single-peaked, equivalently there is an order of \(C\setminus D\) in which every \(A_i\cap(C\setminus D)\) is an interval.
The decision problem is: given a rational threshold \(R\), does there exist a committee \(W\subseteq C\) with \(|W|=k\) such that
\[ \sum_{i=1}^{\tau}\mu_i\mathbf{1}[A_i\cap W=\varnothing]\le R? \]
Equivalently, the optimization version asks for a size-\(k\) committee minimizing the fraction of society left unrepresented. This is exactly approval Chamberlin–Courant with voter counts replaced by population masses. The committee remains discrete; only the population is continuized.
A natural regime is a large electorate, or a large population choosing \(k\) public projects, facilities, or representatives. A type is a complete approval pattern: two residents have the same type when the problem treats them identically with respect to which candidates represent them. Mass \(\mu_i\) is the fraction of residents with that pattern. For example, residents may fall into many large neighbourhood, occupational, or demographic cohorts, each having a common shortlist of acceptable projects. The intended regime is \(N\gg\tau\): millions of residents but relatively few distinct approval types. Repeating every type arbitrarily many times gives a finite realization with the same \(\mu\), so this is genuinely a high-multiplicity interpretation rather than a change to the decision problem.
The match to the paper is unusually clean. The paper’s approval-CC objective is the number of voters whose approval set is missed by the committee. Aggregating identical approval ballots gives
\[ \mu_i=\frac{n_i}{n}, \]
and therefore
\[ \sum_i \mu_i\mathbf{1}[A_i\cap W=\varnothing] = \frac{1}{n}\sum_i n_i\mathbf{1}[A_i\cap W=\varnothing]. \]
Thus every discrete instance maps exactly to a rational-mass instance, with the threshold scaled by \(1/n\). Candidate deletion, the parameter \(d\), the single-peaked promise, committee size, and the solution \(W\) are all preserved. No part of the problem has been dumbed down: we have not fractionalized the committee, replaced approval with an easier utility, or removed the nearly single-peaked structure.
I expect this mirror to be Class B: hardness transfers. The SETH lower bound in Theorem 8 survives the embedding above, giving no \(O^*((2-\varepsilon)^d)\)-time algorithm for the continuous problem unless SETH fails. The algorithmic side should also lift to \(O^*(2^d)\operatorname{poly}(m,\tau,L)\) under rational arithmetic: guess the committee members chosen from \(D\), modify the weighted approval instance, and solve the remaining single-peaked weighted CC problem. Making that lifting fully bit-complexity precise would itself be a worthwhile result.
This mirror generates several follow-up questions. Does the lower bound remain when every positive-mass type represents a very large cohort, or when \(\tau\) is substantially smaller than \(m\)? Can the \(2^d\) dependence be improved under additional restrictions on the mass vector or the approval intervals? What is the complexity when \(D\) is not supplied and must be found? And can the same population formulation extend to the generalized Thiele setting of Theorem 12?
The weakest point is that this is not a flagship example where continuization makes an NP-hard problem tractable. It is essentially weighted Max \(k\)-Coverage with a nearly interval structure, and the hardness in Theorem 8 lives in the candidate side, not in the number of voters. If the paper’s authors wanted a new algorithmic phenomenon caused by continuous population mass, they might regard this as a faithful reformulation rather than a breakthrough.
Nevertheless, it is a strong positive case for the programme’s broader claim. It gives a precise, natural high-multiplicity society; it preserves the paper’s actual computational question; and it demonstrates a meaningful boundary where continuization does not dissolve combinatorial hardness. That boundary is explicitly part of ChoCo’s remit.
The strongest negative case is that Theorem 8 does not yield a genuinely new continuous-population problem, even though it admits a formally correct mass formulation.
For rational masses, write \(\mu_i=a_i/q\). Then
\[ \sum_i \mu_i\mathbf 1[A_i\cap W=\varnothing] = \frac{1}{q}\sum_i a_i\mathbf 1[A_i\cap W=\varnothing]. \]
Thus the proposed instance is exactly the ordinary Approval-CC instance obtained by replacing each type with \(a_i\) cloned voters. Conversely, every ordinary profile can be grouped by approval ballot. Multiplying \(q\) by any factor makes every cohort arbitrarily large without changing the optimization problem. The “continuum” therefore contributes no population-side state: it is a succinct weighted encoding of an anonymous additive objective.
This matters because the paper’s computational content remains entirely finite and candidate-side. The committee is integral, \(D\) is a set of candidates, and the single-peaked promise concerns approval intervals after deleting candidates. There is no mass transfer, population perturbation, or continuous feasible region. The \(O^*(2^d)\) algorithm and its SETH lower bound are simply carried over with weighted sums. The only possible extra issue is bit-complexity for rational weights, which looks like a lifting lemma rather than a new optimization or pricing phenomenon.
The stronger versions do not repair this cleanly. Requiring genuinely few types or lower-bounded type masses makes the model more population-specific, but Theorem 8 provides no hardness result for that restricted regime; its approval profiles may contain essentially one distinct type per voter. Allowing fractional committees, mass deletion, or manipulation would create interesting ChoCo problems, but they would be new intervention problems, not continuizations of the theorem proved here.
That is the best negative argument—but it does not defeat the anchor under the programme’s rules. Approval-CC is anonymous, so identity is irrelevant; large cohorts with common approval patterns are a natural high-multiplicity setting; normalization does not degenerate; and the paper has a named computational theorem. No existing continuous treatment answers this population-computational question. The high-multiplicity literature supports, rather than collides with, the formulation.
So I cannot honestly sustain the universal negative claim. The proposed mirror is probably not a flagship Class A result, but it is a valid Class B boundary case and a clean test of the discrete-to-continuous dictionary.
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.