| paper | Bounded Approval Ballots: Balancing Expressiveness and Simplicity for Multiwinner Elections |
| authors | — |
| venue | AAMAS 2023 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered theorem, lemma, corollary, or proposition asserting computational complexity. Its sole winner-determination NP-hardness claim is an unnumbered observation in §2.2, whereas all named results are axiomatic or expressiveness statements. Although the proposed distribution-over-ballot-types formulation is a credible continuous-population mirror, it cannot qualify under the stipulated anchoring rule.
fails bit a — no named computational result to mirror
The counterfactual mirror would cover only the unnumbered winner-determination claim and would leave Theorems 3–9 and Propositions 10–13 alone.
There is a clean continuous-population version of the paper’s winner-determination question, but the paper supplies no named computational result to serve as a qualifying anchor. Its numbered results—Theorems 3–9 and Propositions 10–13—are axiomatic or expressiveness statements, not P/NP-hardness/FPT results. The sole complexity claim appears unnumbered in §2.2: winner determination for each proposed scoring function is NP-hard unless P = NP; for the \(\varphi\)-based rules this is derived from the cited NP-hardness of approval Chamberlin–Courant, while for \(\mathrm{score}_{app}\) the authors say Exact Cover by 3-Sets yields the claim. Thus, strictly under the requested anchoring rule, this paper cannot support a formally eligible positive case.
If the unnumbered result is admitted as an anchor, however, it is a very plausible Class-B continuization—and it is the strongest honest positive case here.
Call the lead question Continuous Bounded-Approval Welfare Maximization\(_\infty\). An instance consists of a candidate set \(A\), committee size \(k\), a finite set \(T\) of bounded-approval ballot types, rational masses \(\mu_t\geq 0\) summing to one, and one of the paper’s scoring functions, say \(\mathrm{score}_{tot}\) (or any of the four \(\varphi\)-based functions). A type is a complete bounded ballot: its collection of approval sets and their lower, saturation, and upper bounds. For a size-\(k\) committee \(W\), define
\[ V_\mu(W)=\sum_{t\in T}\mu_t\,\mathrm{score}(t,W). \]
The task is to return a committee maximizing \(V_\mu(W)\), or, in decision form, decide whether some size-\(k\) committee has value at least a rational threshold \(q\). Nothing about the committee has been fractionally relaxed: the population, not the outcome, is continuous.
This is exactly the authors’ question with a profile represented as a distribution of ballot types. A discrete profile maps to it by setting \(\mu_t\) equal to the fraction of voters submitting ballot \(t\); normalization scales every committee’s score by the same positive constant and therefore preserves the winners. Conversely, rational masses can be realized as a high-multiplicity profile after clearing denominators.
The natural regime is a large participatory-budgeting or association-wide committee selection exercise, with many thousands of respondents but a modest number of recurring preference packages: for example, members of local service-user, professional, or neighbourhood coalitions repeatedly endorse the same bundles of projects, regard alternatives as substitutes, or demand particular combinations. The types need not be “all possible ballots”; they are the complete preference-and-bound descriptions actually recurring in the population. A city with 100,000 participants and tens or hundreds of organized preference types is a substantially more credible high-multiplicity object than the paper’s small illustrative company committee. This is also not a change of meaning: incompatibility, dependency, and substitution remain entirely inside each voter type, precisely where the paper places them.
I would expect hardness to transfer. For the \(\varphi\)-based rules, restrict every type to one bounded set with lower bound \(1\), saturation point \(1\), and upper bound equal to the approved set’s size. On this domain, each represented voter contributes one unit exactly when the committee contains at least one approved candidate—approval Chamberlin–Courant. Hence the cited discrete NP-hardness embeds in Continuous Bounded-Approval Welfare Maximization\(_\infty\) by replacing voter counts with rational masses. This is not a failed continuization: it is the programme’s intended Class B boundary, where the combinatorics live in candidate/committee selection rather than in population multiplicity.
The mirror covers only the paper’s unnumbered winner-determination claim; it does not turn Theorem 8’s axiomatic impossibility, or the expressiveness propositions, into computational results. Useful follow-ups would be parameterized complexity in \(k\), candidate count, number of ballot types, and maximum bounded-set size, plus approximation guarantees under sparse or disjoint bounded sets.
The weakest point is also decisive for this assignment: the relevant hardness statement is not numbered as a theorem, lemma, corollary, or proposition. Substantively, the mirror is strong and exact; procedurally, the paper lacks the required named computational anchor, so it cannot be offered as a fully compliant positive case.
On the stipulated anchoring rule, this paper has no eligible continuous mirror. Its numbered results are axiomatic adequacy/impossibility theorems or expressiveness propositions, not complexity results. The one winner-determination hardness claim in §2.2 is explicitly unnumbered. That is decisive procedurally: there is no named computational result to continuize.
I cannot make the stronger substantive negative case honestly. If the unnumbered claim is allowed as an anchor, the proponent’s construction is an exact high-multiplicity formulation, not a superficial “fractional outcome” reformulation. A bounded ballot is a complete voter type; aggregating identical ballots into rational masses preserves every committee’s relative welfare exactly. Nothing depends on named voter identities, and large participatory-budgeting or association elections with recurring preference packages supply a credible multiplicity regime. The discrete problem embeds after clearing denominators.
Nor is it an objection that the resulting problem likely retains the original candidate-side hardness: that is a legitimate Class-B result, not evidence that the continuous question is malformed. The paper’s internal dependencies, incompatibilities, and substitutions are all type-level preferences, so mass aggregation loses no relevant information.
Thus the only defensible negative verdict is formal rather than conceptual: reject it because it lacks the required named computational anchor. If the reader waives that requirement, this paper should be greenlit; there is no sound universal argument that its bounded-approval winner-determination problem lacks a worthwhile continuous-population 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.