| paper | Refined Characterizations of Approval-Based Committee Scoring Rules |
| authors | — |
| venue | AAAI 2024 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Red under the stated gate: Theorem 1, Theorem 2, and Propositions 1–3 are axiomatic characterizations, while the paper’s complexity statements are unnumbered related-work claims. The proposed high-multiplicity winner-determination problem is credible, but it is not a computational result of this paper to anchor. Thus bit (a) fails despite a useful latent ChoCo question.
fails bit a — no named computational result to mirror
The proposed mirror covers high-multiplicity winner determination for Thiele and related ABC scoring rules; it does not mirror the paper’s named axiomatic results under the computational-anchor requirement.
The strongest honest conclusion is that this paper has no eligible computational anchor, so it cannot support a fully compliant ChoCo case for a continuous mirror.
Its numbered results are all axiomatic:
None asserts membership in P, NP-hardness, FPT, W[1]-hardness, or any other computational classification. The sentence that “all Thiele rules but AV are NP-hard to compute” is unnumbered related-work prose, attributed to Aziz et al. (2015) and Skowron, Faliszewski, and Lang (2016), not a result proved or stated as a named computational theorem in this paper. Therefore there is no valid anchor and, strictly speaking, no required “one continuous problem per anchor” to provide.
There is nevertheless a plausible latent mirror. If the anchor restriction were relaxed, my lead would be High-Multiplicity ABC-Thiele Winner Determination:
Given candidates \(C\), committee size \(k\), a rational Thiele scoring function \(s\), and a finite-support distribution \(\mu\) over approval types \(A\subseteq C\), output all committees
\[ W\in\binom{C}{k} \]
maximizing
\[ \operatorname{score}_{\mu}(W) =\sum_A \mu_A\,s(|A\cap W|). \]
Here a type is a complete approval ballot, \(\mu_A\) is the fraction of users with that ballot, and the decision variable is the winning committee. A convincing regime would be a large city-council or recommendation population with millions of users but comparatively few recurring approval patterns.
This is genuinely the high-multiplicity version of the paper’s ABC scoring problem: a discrete profile with \(n_A\) voters of type \(A\) becomes \(\mu_A=n_A/n\), and multiplying the continuous score by \(n\) recovers the discrete score. AV is polynomial by selecting the \(k\) candidates with largest approval mass. For PAV, CCAV, and other non-AV Thiele rules, the known discrete winner-determination hardness transfers directly through this encoding; that would be Class B rather than a continuum-specific tractability gain. Fixed \(m\) would make the problem trivial by enumeration, so the meaningful regime has variable \(m\) and many voters relative to the number of supported types.
The paper’s own use of “continuity” helps motivate this interpretation: its axiom studies what happens when electorates are replicated. But that is an axiomatic condition on finite profiles, not a continuous-population computational result, and axiomatic continuization is explicitly outside ChoCo’s scope.
The weakest point is therefore decisive: this proposed problem is a sensible new computational companion to the paper, but it is not a mirror of any named computational result the paper proves. The paper should be recorded as containing no eligible computational anchor—not as evidence that no continuous mirror exists.
The proponent wins the narrow bookkeeping point: this paper contains no numbered computational theorem. Theorem 1, Theorem 2, and Propositions 1–3 are axiomatic characterizations, and the complexity claim in related work is not a result established by the paper. I would not pretend otherwise, or present those theorems as eligible ChoCo anchors.
But that does not support the universal conclusion that no worthwhile continuous mirror exists. The proposed high-multiplicity ABC-Thiele Winner Determination is a genuine computational object:
\[ \max_{|W|=k}\sum_A \mu_A\,s(|A\cap W|). \]
Approval ballots are complete types for every rule in question; voter identity is irrelevant to the objective; and large council electorates or recommendation platforms with recurring approval patterns are entirely credible high-multiplicity regimes. The continuum does not degenerate: changing a positive fraction of one ballot type changes committee scores by a positive amount.
The fact that PAV, CCAV, and other Thiele rules remain hard is not a defect. Class B is explicitly one of ChoCo’s desired outcomes. Moreover, the compressed representation creates a real parameterized landscape: if the society has \(q\) supported approval types, each candidate can be represented by its \(q\)-bit incidence pattern, and dynamic programming over the \(q\) approval counts gives polynomial-time algorithms for fixed \(q\). Thus the continuous formulation exposes dependence on support complexity rather than merely on the raw number of voters. AV is easy, but that only makes the contrast with non-additive Thiele rules sharper.
A stronger mirror would study continuous winner robustness or campaigning for these same rules: the minimum mass of approval types that must be converted, at specified costs, to make a target committee win. The winning constraints are linear in the post-intervention distribution, while the committee and type spaces retain the combinatorial pricing questions that make the problem interesting. This is directly within ChoCo’s stated scope and has a natural interpretation as persuading population segments.
So the correct verdict is mixed: the paper is not a fully compliant source of a named computational anchor, and should be marked down for that reason. But the proposed mirror is not worthless or merely an inert restatement. The universal “no worthwhile mirror in any scenario” claim is substantially too strong.
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.