| paper | The Complexity of Learning Approval-Based Multiwinner Voting Rules |
| authors | Ioannis Caragiannis, Karl Fehrs |
| 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 |
Theorem 14
statement extracted from the paper’s text layer
Given \(m,k\), a rational distribution \(\mu\) over nonempty approval types \(\sigma\subseteq\Sigma\), and a \(k\)-committee \(A\), decide whether there exists a non-trivial monotone ABCS scoring function \(f\) such that \(A\in\arg\max_{|C|=k}\sum_{\sigma}\mu_{\sigma}f(|C\cap\sigma|,|\sigma|)\).
The population consists of approval-ballot types \(\sigma\subseteq\Sigma\) with masses \(\mu_{\sigma}\); committees remain integral \(k\)-subsets, while the decision variable is the non-trivial monotone scoring function \(f\), and the objective is to make \(A\) a co-winner.
The mirror directly covers TARGETABCS and TARGETSEQTHIELE, including Theorems 14, 21, and 23. The PAC sample-complexity results in Theorems 5 and 22 are suggested as extensions but are not fully formalized as separate continuous learning problems.
The strongest positive case is a conservative one: this paper has a faithful high-multiplicity mirror, although its principal hardness results are likely to survive continuization rather than disappear. My lead anchor is Theorem 14.
The natural population is an approval electorate. Let \(\Sigma\) be the \(m\) alternatives, and let each voter type be a nonempty approval set \(\sigma\subseteq\Sigma\). A society is a rational distribution
\[ \mu=(\mu_\sigma)_{\sigma\in 2^\Sigma\setminus\{\varnothing\}}, \qquad \mu_\sigma\ge 0,\quad \sum_\sigma \mu_\sigma=1. \]
Here \(\mu_\sigma\) is the fraction of the electorate with approval ballot \(\sigma\). The effective number of types is \(r=|\{\sigma:\mu_\sigma>0\}|\); the intended regime is a very large electorate with \(n\gg r\), such as millions of users or members repeatedly expressing a relatively small number of approval patterns over a fixed catalogue of alternatives. This is particularly plausible for the paper because voter identities do not matter to ABCS or Thiele rules: only approval sets and their multiplicities enter the score.
The committee remains a discrete \(k\)-subset. The continuous object is only the population. For an ABCS scoring function \(f\), define
\[ S_f(C;\mu) = \sum_{\sigma} \mu_\sigma f(|C\cap\sigma|,|\sigma|). \]
Thus the decision variable is the scoring rule \(f\), subject to the paper’s non-negativity, monotonicity, and non-triviality conditions. The objective is exactly the paper’s objective: make a designated committee \(A\) a co-winner. This is not fractional committee selection or probabilistic voting; \(A\) is still an ordinary committee.
The key fidelity identity is exact. If a finite profile \(P\) contains \(n_\sigma\) voters of type \(\sigma\), set \(\mu_\sigma=n_\sigma/n\). Then
\[ \operatorname{sc}_f(C,P) = n\,S_f(C;\mu). \]
Therefore the winning committees under \(P\) and under \(\mu\) are identical for every \(f\). Conversely, every rational \(\mu\) can be represented by a finite profile after clearing denominators. The continuous problem is consequently the paper’s anonymous approval-profile problem in its high-multiplicity form, not a simplified surrogate.
My lead continuous problem is therefore:
\[ \textsc{Continuous-TargetABCS}_\infty. \]
An instance consists of \(m,k\), a rational mass distribution \(\mu\) over approval types, and a \(k\)-committee \(A\). The question is whether there exists a non-trivial ABCS rule \(f\in F_{m,k}\) such that
\[ A\in\arg\max_{|C|=k} S_f(C;\mu). \]
A solution is the scoring vector \(f\). This is precisely the one-sample consistency problem underlying the paper’s learning task, with a finite profile replaced by a population distribution.
The anchor is Theorem 14, proved in this paper: TARGETABCS parameterized by \(k\) is coW[1]-hard. The hardness transfers directly to \(\textsc{Continuous-TargetABCS}_\infty\), because the reduction’s finite profile can be normalized without changing any committee comparison. More importantly, the reduction’s combinatorics live in the alternatives: the graph is encoded through candidate pairs, the target committee, and competing committees. They do not depend on indivisible voter identities. I would therefore expect this mirror to be Class B. Unless the relevant parameterized collapses occur, continuous masses do not yield an FPT algorithm parameterized by \(k\).
This is still a meaningful positive case for the programme. It gives a precise continuous computational question and a clean answer to the central classification question: in this problem, continuization does not dissolve the hardness, because the hardness is agenda-side rather than multiplicity-side.
A second, independent mirror uses the paper’s sequential Thiele results. Define
\[ S_s(B;\mu) = \sum_\sigma \mu_\sigma s(|B\cap\sigma|), \]
where \(s(0)=0\), \(s(1)\le\cdots\le s(k)\), and \(s(k)\ge1\). The problem is:
\[ \textsc{Continuous-TargetSeqThiele}_\infty. \]
Given \(\mu\) and a target committee \(A\), determine whether there exist a scoring function \(s\) and an ordering \(a_1,\ldots,a_k\) of \(A\) such that, for every step \(i\),
\[ S_s(\{a_1,\ldots,a_i\};\mu) \ge S_s(\{a_1,\ldots,a_{i-1}\}\cup\{b\};\mu) \]
for every alternative \(b\notin\{a_1,\ldots,a_i\}\). A solution is the pair \((s,a_1,\ldots,a_k)\).
The anchor here is Theorem 23, proved in this paper: TARGETSEQTHIELE is NP-hard. Again, if \(P\) is a finite profile and \(\mu\) its normalized type distribution, every sequential score and every greedy comparison is multiplied by the same factor \(n\). Hence the structured-3SAT reduction survives exactly. This is another Class B mirror in ordinary complexity.
The same continuous problem also inherits the paper’s positive parameterized result, Theorem 21, proved here: TARGETSEQTHIELE is in FPT parameterized by \(k\). For each of the \(k!\) possible orders of \(A\), one solves a linear program in \(s(1),\ldots,s(k)\); replacing voter counts by rational masses merely changes the coefficients. Thus the continuous version has the same mixed status as the discrete one: NP-hard when \(k\) is part of the input, but solvable in \(k!\operatorname{poly}(m,r,L)\) time when parameterized by committee size.
At the learning level, the corresponding continuous sample would be a pair \((\mu,W)\), where \(\mu\) is a society distribution and \(W\) is the observed set of winning committees. The target is an ABCS or sequential Thiele rule. The sign-pattern arguments behind Theorems 5 and 22 should extend because committee-score differences remain linear functions of the rule parameters, with the population masses appearing only as coefficients. So the paper naturally suggests a distinction between low statistical sample complexity and computationally hard rule identification on continuous societies.
The weakest point is that these mirrors are conservative. For rational masses, they are almost a change of representation: every continuous instance has a finite-profile realization, and every finite profile embeds into the simplex. The paper therefore offers no strong reason to expect a new Class A algorithm, and the type space can still have size \(2^m-1\). I would not claim that its hardness “dissolves.” The defensible positive claim is narrower: approval-based rule learning is inherently a population-level, anonymous problem; its high-multiplicity version is mathematically natural, faithful to the authors’ definitions, and yields a legitimate Class B boundary case for continuization.
The strongest negative case is that this paper has no population-sensitive computational core. Its voters are anonymous from the outset: every score depends only on the histogram of approval ballots. Replacing that histogram by normalized masses therefore introduces no new optimization variable, limit phenomenon, or uncertainty. It merely changes counts into proportions.
That objection, however, does not defeat Theorem 14. For every profile \(P\) with \(n_\sigma\) voters of approval type \(\sigma\), setting \(\mu_\sigma=n_\sigma/n\) gives
\[ \operatorname{sc}_f(C,P) = n\sum_\sigma \mu_\sigma f(|C\cap\sigma|,|\sigma|). \]
All committee comparisons are therefore identical. The reduction proving coW[1]-hardness uses voter multiplicities only as coefficients; its graph structure is encoded in candidates and approval sets, not voter identities. Thus the normalized distribution is a faithful high-multiplicity instance. Calling it “only a re-encoding” is a real reservation, but the programme explicitly treats faithful high-multiplicity mirrors as worthwhile Class B cases. The fact that the hardness survives is not an admissible objection.
The same defeats the second anchor. For sequential Thiele rules,
\[ \operatorname{sc}_s(B;\mu) = \sum_\sigma \mu_\sigma s(|B\cap\sigma|), \]
and every greedy comparison in Theorems 21 and 23 is preserved exactly under normalization. The \(k!\) linear programs proving FPT membership simply acquire rational mass coefficients. The NP-hardness reduction likewise survives. There is no identity-sensitive quantity, and no cost or score collapses when the electorate becomes nonatomic. A stronger version with rational distributions of arbitrary finite support remains well-defined and computational. Allowing arbitrary real masses would create an encoding problem, not a substantive obstruction.
The learning results provide the best negative reservation. PAC learning samples whole profiles, not individual voters: its distribution \(D\) is already a distribution over societies. Replacing each profile by \(\mu\) therefore adds a second layer of notation without making population multiplicity statistically central. The sign-pattern arguments behind Theorems 5 and 22 already depend only on aggregate score differences. If continuous examples are represented explicitly by rational masses, the learning problem is again extensionally identical; if they are represented by arbitrary measures, the computational input model is unspecified.
That makes these mirrors conservative rather than transformative. They offer no obvious Class A algorithm and no continuum-specific hardness mechanism. But that is insufficient for the requested universal negative verdict. The paper has named computational theorems, its approval voters admit a natural many-voters-per-type interpretation, and the continuous formulations preserve the exact winning problem. The honest negative conclusion is therefore only that the mirrors are likely Class B re-expressions, not that no worthwhile continuous mirror exists. Under the programme’s stated standards, the proponent’s anchors survive.
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.