| paper | d4-conf-ecai-2024-0491 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-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: For \(\lambda(j)=1\) throughout, both variants are in \(\mathsf{P}\). For every other fixed admissible \(\lambda\), the exact variant is \(\mathsf{NP}\)-hard and \(\mathsf{coNP}\)-hard, and the greedy variant is \(\mathsf{NP}\)-complete. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given a candidate set \(C\), committee size \(k\), distance bound \(\ell\), a Thiele rule with OWA function \(\lambda\), and a binary-rational distribution \(\mu\) over pairs of nonempty ballots \((A,B)\), define the stage marginals \(\mu^0_A=\sum_B\mu_{A,B}\) and \(\mu^1_B=\sum_A\mu_{A,B}\). Given a size-\(k\) committee \(S\) maximizing the stage-0 score, does there exist a size-\(k\) committee \(S'\) maximizing the stage-1 score \(F_\lambda(\mu^1,S')=\sum_B\mu^1_B\sum_{j=1}^{|S'\cap B|}\lambda(j)\) with \(k-|S\cap S'|\le\ell\)? For the greedy variant, replace score maximizers with committees obtainable by greedy marginal-score choices, allowing any tie resolution.
The society is a distribution \(\mu\) over complete two-stage approval trajectories \((A,B)\); \(\tau\) is its support size. Scores and greedy marginal scores are weighted sums over this support, while candidates and committees remain discrete. The decision asks whether a stage-1 winning committee lies within distance \(\ell\) of a stage-2 winner.
The population distribution is fixed input data, so there is no mass-transfer variable and no evident LP or convex-optimization gain; the mirror remains a weighted committee-search problem.
fatal: False
The mirror covers the Thiele-rule dichotomy of Theorem 3.3 and the greedy hardness result of Theorem 4.2; parameterized results could also be reformulated over type distributions. It does not turn the committee into a divisible outcome or make the paper’s experiments computational guarantees.
The strongest mirror here is the population version of the paper’s two-election problem. I would use two anchors: Theorem 3.3 as the lead, since it gives the ordinary Thiele-rule classification, and Theorem 4.2 for the separate greedy-rule result.
Consider a large association or town constituency voting for a fixed slate of candidates at two successive elections. A type is a member’s pair of nonempty approval ballots \((A,B)\): what they approve at the first election and what they approve at the second. Members with the same pair are indistinguishable for this problem. If there are hundreds of thousands of members but only hundreds or thousands of distinct ballot trajectories, let \(\mu_{A,B}\) be the fraction of the population with trajectory \((A,B)\). The support size \(\tau\) may then be much smaller than the population. This is a plausible regime for a large electorate with recurring constituencies and shared approval patterns; it is not a claim that every election has low support.
Here is the lead problem, Continuous Thiele-RCE\(_\lambda\). An instance gives a candidate set \(C\), committee size \(k\), distance bound \(\ell\), a fixed Thiele rule with OWA function \(\lambda\), and a binary-rational distribution \(\mu\) over pairs of nonempty ballots, with total mass one. Write \(\mu^0_A=\sum_B\mu_{A,B}\) and \(\mu^1_B=\sum_A\mu_{A,B}\) for the two election marginals. The instance also gives a first-stage winning committee \(S\). At either stage, a committee \(X\) has score
\[
F_\lambda(\mu^r,X)=\sum_D\mu^r_D\sum_{j=1}^{|X\cap D|}\lambda(j).
\]
The question is whether there is a size-\(k\) committee \(S'\) maximizing \(F_\lambda(\mu^1,\cdot)\) such that \(k-|S\cap S'|\le\ell\). A solution is such a committee \(S'\). The relevant input measures include \(m=|C|\), \(\tau\), and the bit length \(L\) of the masses, as well as \(k,\ell\).
Theorem 3.3, proved in this paper, says: if \(\lambda(i)=1\) for every positive integer \(i\), then Thiele-RCE is polynomial-time solvable; otherwise it is coNP-hard and coW[1]-hard parameterized by \(k\). The hardness holds for every fixed \(\ell\) in the theorem’s stated range \([k-s]\), where \(s\) is the smallest positive integer with \(\lambda(s+1)<1\), and even when the two elections differ by one approval operation. This is my lead anchor because it supplies both the boundary case and the hardness question the continuous mirror should investigate.
For the greedy rules, define the weighted marginal score at stage one, for example, by
\[
g_{\mu^0}(c\mid X)=\sum_A\mu^0_A[c\in A]\lambda(|X\cap A|+1).
\]
A greedy winning committee is one obtainable by repeatedly selecting a candidate with maximum marginal score, allowing any resolution of ties. The named problem Continuous Greedy-RCE\(_\lambda\) uses the same instance format and overlap question, with winners defined by these greedy sequences at each stage. A solution is a qualifying second-stage committee, attainable by some greedy tie resolution.
Theorem 4.2, also proved in this paper, says that for every greedy unit-decreasing Thiele rule and every committee-distance bound \(\ell\in[k-1]\), Greedy-RCE is NP-hard, even when the election profiles differ by one approval operation. The proof reduces from the paper’s Candidate Inclusion problem. This anchor matters on its own: easy computation of one greedy winner does not make the task of finding a close winner after the update easy.
The authors should recognize both mirrors. They retain the two election stages, approval preferences, fixed-size committees, the exact Thiele scoring rule, parallel-universe tie-breaking, and the overlap objective. Only the population description changes: it records proportions of temporal ballot types instead of listing voters. The committee remains a discrete object. A voter’s trajectory type is the complete description relevant to these questions, so grouping identical trajectories is precisely the high-multiplicity assumption.
The hardness results should transfer, rather than dissolve. Given an ordinary instance with \(n\) voters, set \(\mu_{A,B}\) to the number of voters with that ballot trajectory divided by \(n\). Every weighted score is the corresponding discrete score divided by \(n\), so winners, ties, and the answer to the overlap question are unchanged. In the one-approval subcases, the changed trajectory simply has mass \(1/n\). The reductions use polynomially many distinct ballot types, with rational masses of polynomial bit length, so they remain polynomial-size instances under the \((m,\tau,L)\) representation. I therefore expect Class B hardness for the non-AV Thiele and greedy anchors. The AV side remains tractable: compute second-stage candidate scores from the masses, then choose a winning committee with maximum overlap with \(S\), as in Proposition 3.1.
The weakest point is that a one-voter change becomes mass \(1/n\), which tends to zero along a growing-electorate sequence. The mirror does not make that individual perturbation macroscopic; it represents it exactly as rational mass. More broadly, the experiments’ spatially generated ballots may have support close to the voter count, so they are not by themselves evidence for a low-support regime. The positive case rests on the distinct, plausible constituency regime above, and on the fact that the paper’s computational question itself depends on ballot types and committee winners, not on voter identities.
The case against is weak at the point it needs to be strongest. The paper has named computational results, and its voters are anonymous: for committee scores and overlap, voter identity carries no information. A large electorate with recurring approval patterns is plausible. Neither Theorem 3.3 nor Theorem 4.2 can be dismissed on the grounds that the paper has no computational problem or that its agents cannot be grouped into types.
For Theorem 3.3, the faithful mirror is clear. Give the two elections as distributions over approval ballots, or use a distribution over ballot pairs if the connection between stages matters. Weighted Thiele scores preserve the winning committees, and a change affecting a positive fraction of the electorate avoids the concern that one person’s mass vanishes in a population limit. The fact that the paper’s hardness construction works after one approval change does not defeat this version: the mirrored problem can allow arbitrary changes, including positive-mass ones.
The strongest objection is about payoff, not whether the question is coherent. In this problem the population distribution is input data. There is no population mass to transfer or optimize over: the task is to find a close committee among those winning under weighted scores. The mirror therefore offers no obvious foothold for the continuous optimization technology that motivates ChoCo. But that observation does not make the question unworthy. Binary-rational masses can be represented compactly even when expanding them into repeated voters would be costly, and studying that weighted high-multiplicity version is squarely within the programme’s stated aims.
Theorem 4.2 has the same limitation and the same defense. Weighted ballot masses determine the greedy marginal scores; the committee and the sequence of greedy choices remain discrete. Ties can still be resolved in parallel, and positive-mass updates can still be modeled. So there is no clear continuous optimization structure to exploit, but the population mirror itself remains well-posed.
One could introduce a more explicitly continuous problem: minimize the mass whose approvals must change in order to obtain a close winning committee. That gives mass a decision variable, but it changes the anchored question. The paper’s theorems concern finding a close winner for two given elections; they do not establish the complexity of this new minimum-change problem. It might be a worthwhile follow-on, but it cannot be used to disqualify the faithful mirrors.
So the best negative case is that these anchors look like weighted-profile problems with limited immediate use for continuous optimization methods. It does not defeat either anchor. Given the programme’s explicit interest in high-multiplicity questions, I cannot honestly make the universal claim that no scenario yields a worthwhile mirror.
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.