The Core of Approval-Based Committee Elections with Few Seats

The strongest honest case is a qualified yes. This paper is unusually favorable to a continuous mirror because it has already written down the relevant high-multiplicity representation: its profile \(P\) is a distribution over approval types. That is evidence for the mirror’s legitimacy, not a novelty claim.

The mirror keeps the committee discrete and continuizes only the voter population. Let \(C\) be the candidates, let \(\mathcal A=2^C\setminus\{\emptyset\}\) be the approval types, and let \(\mu_A\) be the fraction of voters with approval set \(A\). For a committee \(W\), define

\[ b_\mu(W,T)=\sum_{A:\,|A\cap T|>|A\cap W|}\mu_A . \]

Then \(W\) is core-stable exactly when

\[ b_\mu(W,T)<\frac{|T|}{k} \]

for every nonempty \(T\subseteq C\) with \(|T|\le k\). The decision variable is the integral committee \(W\), and the objective is to find any committee satisfying this condition. PAV remains the same objective,

\[ F_\mu(W)=\sum_{A\in\mathcal A}\mu_A H(|A\cap W|). \]

Thus this is population continuization, not fractional committees or lotteries.

A plausible regime is a large civic or electoral process with millions of voters but recurring approval packages generated by neighbourhoods, parties, issue blocs, or a constrained voting interface. One might have \(n\) in the millions but only \(\tau\) distinct approval types in the hundreds or low thousands. Every type is a complete description of the voter for this problem, exactly as high multiplicity requires. The authors should find this mirror natural: they already define \(P(A)\) as a rational fraction and repeatedly exploit the fact that their results hold independently of \(n\).

My lead anchor is Theorem 4.1, proved in this paper: when \(k\le 7\), every local PAV committee is in the core. The corresponding problem is:

*Continuous Local-PAV Core Search\(_\infty\).* Given \(C\), a fixed \(k\le7\), a finite support \(\mathcal S\subseteq\mathcal A\), and rational masses \((\mu_A)_{A\in\mathcal S}\) summing to one, return a committee \(W\) of size \(k\) that is core-stable.

I expect this to be Class A. Remark 4.2 supplies the algorithmic bridge: with \(\varepsilon=0.1/k^2\), every \(\varepsilon\)-local-swap-stable committee is core-stable, and such a committee can be found using \(O(k^2\ln k)=O(1)\) improving swaps. For a swap \(x\in W\), \(y\notin W\), its gain is computable directly from the type masses:

\[ \Delta_{\mu,x,y} = \sum_{A\in\mathcal S}\mu_A \left( H(|A\cap W_{xy}|)-H(|A\cap W|) \right). \]

Each scan of all swaps takes polynomial time in \(m\), \(\tau\), and the encoding length of the masses. The paper states the corresponding discrete bound as \(O(m^2n)\); aggregation replaces \(n\) by the number of represented types. This is a particularly clean ChoCo result: the theorem’s structural insight survives unchanged, while the continuous representation makes the population size irrelevant.

A second worthwhile anchor is Theorem 4.5, also proved here: when \(k=8\), some global PAV committee is in the core. The precise mirror is:

*Continuous Core-PAV-8 Search\(_\infty\).* Given \(C\), rational type masses \(\mu\), and \(k=8\), return a committee \(W\) such that

\[ W\in\arg\max_{|U|=8}F_\mu(U) \]

and \(W\) is core-stable.

This is again Class A for fixed \(k=8\). Enumerate all \(\binom{m}{8}\) committees, compute their exact PAV scores, and test core stability by enumerating all \(T\) with \(|T|\le8\). Theorem 4.5 guarantees that the intersection between the global-PAV set and the core is nonempty. This is a faithful mirror because neither the approval utilities nor the core quota changes, and the output remains a committee of eight actual candidates.

For an honest boundary, the paper also reports the cited result Brill et al. [2022, Theorem 5.3], that checking whether a given committee is in the core is coNP-complete. Its continuous counterpart is:

*Continuous Core Audit\(_\infty\).* Given \(C\), \(k\), a rational distribution \(\mu\) over approval types, and a committee \(W\), decide whether \(W\) is core-stable; equivalently, determine whether there exists a \(T\) with

\[ b_\mu(W,T)\ge\frac{|T|}{k}. \]

I expect coNP-completeness, so Class B. A violating \(T\) is a polynomial certificate, while any discrete profile maps directly to \(\mu_A=n_A/n\) without changing the answer. The hardness therefore lives in the candidate and committee combinatorics, not in voter multiplicity. The same transfer applies to the paper’s cited NP-hardness of global PAV winner determination, Aziz et al. [2015, Corollary 1].

The mirror covers the paper’s normal Hare-quota core, local and global PAV, and the small-\(k\) existence results. Theorem 5.3 gives further supporting evidence for the same model when \(m\le15\), although I would not use it as a main anchor: with \(m\) fixed, exhaustive enumeration already makes the complexity claim comparatively weak. I would also keep the Droop-core discussion separate; Theorem 6.1 shows that PAV can fail the Droop core, but that is a result about a different stability quota, not a reason to reject the population mirror.

The weakest point is that this is not a new act of continuization. Peters’s paper already uses normalized ballot frequencies and LPs over them. A ChoCo paper should therefore not claim novelty merely for replacing \(n_A\) by \(\mu_A\). The positive case is instead that the paper validates the high-multiplicity regime, supplies clear Class A points, and exposes a Class B boundary. The genuinely new programme would ask for the broader landscape: variable \(k\), minimum-mass changes needed to create or destroy a core objection, campaigning or bribery between approval types, robustness of a committee under mass perturbations, and parameterized complexity in \(k\), \(\tau\), or approval-set structure.