More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules

The strongest positive case is that this paper already studies a natural high-multiplicity object: approval profiles whose voters contribute only through their approval sets and Thiele satisfaction values. The continuous mirror should preserve the indivisible candidate set and the discrete committee decision; only the population is replaced by mass.

Let \(C\) be the candidates and let a type \(t\) consist of an approval set \(A_t\subseteq C\). For a fixed Thiele function \(f\), with \(f(0)=0\) and non-increasing marginal values \(\lambda_j=f(j)-f(j-1)\), define a society by rational masses \(\mu_t\ge 0\), \(\sum_t\mu_t=1\). Its score for a committee \(S\subseteq C\) is

\(F_\mu(S)=\sum_{t\in T}\mu_t f(|S\cap A_t|)\).

PAV is the canonical example, with \(\lambda_j=1/j\). If voter-specific Thiele functions are allowed, they can simply be included in the type: \(t=(A_t,\lambda^t)\).

This is not outcome-space fractionalization. \(S\) remains a genuine set of \(k\) indivisible candidates. Mass means the fraction of voters in each approval bloc. A rational society \(\mu_t=a_t/N\) clears exactly to \(a_t\) cloned voters, and

\(N F_\mu(S)=\sum_t a_t f(|S\cap A_t|)\),

which is precisely the paper’s discrete score. Winner comparisons, optimal committees, ties, and approximation ratios are therefore preserved exactly under denominator clearing.

The regime is a large institutional election with many repeated ballot types: for example, a national professional association or university system in which departmental or organizational cohorts use standardized shortlists of nominees. One might have \(N\) in the hundreds of thousands or millions but only \(\tau\) distinct approval types, with \(\tau\) in the hundreds or thousands. The paper’s own university story need not be used; its mathematical approval-profile model supports this more convincing high-multiplicity scenario.

There is one important modelling choice. To preserve the paper’s literal \(K_{d,d}\)-free condition after cloning, I would work in the stable short-list regime

\(|A_t|\le d-1\quad\text{for every }t\text{ with }\mu_t>0.\)

Then every denominator-cleared profile is automatically \(K_{d,d}\)-free, because no voter has \(d\) approved candidates. This is a genuine subregime of the paper’s class: the paper explicitly presents bounded approval lists as a meaningful special case, and its theorems apply to it. I would not silently collapse repeated voters into one vertex and call an arbitrary support graph \(K_{d,d}\)-free; that would change the paper’s predicate.

My lead anchor is Theorem 2, proved in this paper. It states that, for \(K_{d,d}\)-free profiles, MAX SUBMOD-MWE admits a parameter-preserving \((1-\epsilon)\)-approximate kernel with at most \((dk/\epsilon)^{O(d^2)}\) candidates and \((dk/\epsilon)^{O(d^3)}\) voters.

The continuous question I would put forward is:

Continuous Lossy Kernel for Approval-Mass Multiwinner Selection. Given \(C\), a rational distribution \(\mu\) over approval types \(T\), a committee size \(k\), and \(\epsilon\in(0,1)\), construct in time polynomial in the input bit length a reduced weighted instance \((C',T',\mu',k)\) and a lifting procedure such that

\(|C'|\le (dk/\epsilon)^{O(d^2)}\)

and

\(|T'|\le (dk/\epsilon)^{O(d^3)},\)

and such that every \(\beta\)-approximate committee for the reduced instance lifts to a committee \(S\subseteq C\) of size at most \(k\) satisfying

\(F_\mu(S)\ge (1-\epsilon)\beta\operatorname{OPT}_\mu(k).\)

The reduced society must still be represented by rational masses, with polynomially bounded encoding length. The committee, not its characteristic vector, is the solution.

I expect this question to be Class A. The paper’s two kernelization operations have an especially natural population interpretation. Candidate reduction identifies candidates that are interchangeable for approximation, while voter reduction replaces many repeated approval blocs by a small weighted representative population. In the continuous formulation, the latter is no longer an artificial rounding of integer multiplicities: it is exactly the task of compressing a distribution while preserving every relevant \(k\)-committee score.

This mirror is author-recognizable. It retains their candidates, approval lists, Thiele objective, committee size, biclique-free profile restriction, and multiplicative approximation guarantee. The only change is replacing a list of repeated voters by their rational type masses. In fact, Theorem 2 is arguably more naturally expressed in this language than in terms of an enormous explicit electorate.

The main follow-up questions are whether the stated bounds are tight for weighted populations, whether an exact rather than lossy type kernel is possible, and whether one can obtain a kernel whose size depends on \(k\) and \(d\) but not on \(m\). A particularly worthwhile question is whether the type-compression procedure can preserve all optimal committees rather than merely preserve the optimum value up to \(1-\epsilon\).

The second anchor is Theorem 1, also proved in this paper. It gives an algorithm for SM-MWE on \(K_{d,d}\)-free profiles running in time

\((dk/\epsilon)^{O(d^2k)}n^{O(1)}\)

and producing a \(k\)-sized solution of score at least \((1-\epsilon)t\) whenever the threshold-\(t\) instance is feasible.

The corresponding continuous problem is:

Continuous FPT Approximation for Thiele Approval Masses. Given candidates \(C\), a rational type distribution \(\mu\), integers \(k\) and a rational threshold \(\theta\), and \(\epsilon>0\), determine whether there is a committee \(S\) with \(|S|\le k\) and \(F_\mu(S)\ge\theta\). If the answer is yes, output a committee \(\widehat S\) with \(|\widehat S|\le k\) and

\(F_\mu(\widehat S)\ge (1-\epsilon)\theta.\)

The desired running time is

\((dk/\epsilon)^{O(d^2k)}\operatorname{poly}(m+\tau+L),\)

where \(L\) is the bit length of the rational masses and scores. Equivalently, for the optimization version, one seeks a committee with score at least \((1-\epsilon)\operatorname{OPT}_\mu(k)\).

I again expect Class A. The proof of Theorem 1 is driven by structural properties of the profile graph: sunflower-based candidate reduction in the low-threshold case and restriction to high-score candidates in the high-threshold case. Those arguments do not depend conceptually on naming each voter. In the mass version, repeated voters can be aggregated, scores become rational weighted sums, and the polynomial factor should depend on the number of types and their encoding length rather than on the potentially enormous clone count \(N\).

This is not claiming that the paper already proves the high-multiplicity bit-complexity statement. The paper’s \(n^{O(1)}\) factor is polynomial in explicitly listed voters. A continuous result would need weighted versions of the reduction and sunflower bookkeeping, together with a proof that rational masses can be handled in time polynomial in \(L\), not by expanding them into \(N\) clones. But that is a credible algorithmic extension of their proof, not a different voting problem.

The exact optimization problem should not be expected to become easy merely because voters are aggregated. With Chamberlin–Courant-style satisfaction and approval sets of size two, the objective already contains weighted maximum \(k\)-vertex-cover/max-coverage structure over the candidates. Thus candidate-side combinatorics can survive as Class B hardness. The continuous mirror is valuable even if its exact version remains hard: Theorem 1 and Theorem 2 concern approximation and compression of the population representation, precisely where high multiplicity should help.

I am deliberately not using the paper’s introductory NP-hardness and W[1]/W[2]-hardness statements as anchors. They are attributed to earlier papers and are not numbered results proved here. The two anchors above are numbered, computational, and proved in this paper.

My weakest point is the \(K_{d,d}\)-free restriction. In a genuine high-multiplicity limit, repeatedly cloning a type with \(d\) approved candidates would itself create a \(K_{d,d}\), so the literal restriction forces the short-list regime \(|A_t|<d\). That means my mirror does not cover every \(K_{d,d}\)-free instance in the paper. It covers a narrower but explicit and plausible regime that the authors themselves identify as part of their framework. The second soft spot is that replacing \(n\) by \(\tau\) in the running time requires a new weighted implementation proof.

Those limitations keep this from being a claim that the paper’s entire theory has already been continuized. They do not defeat the positive case: Theorem 2 gives a particularly strong population-compression question, Theorem 1 gives the associated approximation question, and both preserve the paper’s actual social-choice object rather than replacing it with fractional committees or a different notion of satisfaction.