| paper | Auditing for Core Stability in Participatory Budgeting |
| authors | Kamesh Munagala, Yiheng Shen, Kangning Wang |
| venue | WINE 2022 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
Given a finite candidate set \(C\) of unit-cost projects, budget \(k\), audited committee \(W\subseteq C\), and finite approval-type support \(T\) with rational masses \(\mu_t\ge0\) summing to \(1\), where type \(t\) approves \(A_t\subseteq C\), define \(u_t(D)=|A_t\cap D|\) and \(M_\mu(D;W)=\sum_{t:u_t(D)>u_t(W)}\mu_t\). Ask for the exact value, or an \(\alpha\)-approximation, of \(\theta_c^\infty(W)=\inf_{D\subseteq C:M_\mu(D;W)>0}|D|/(kM_\mu(D;W))\); equivalently, decide or approximate whether some integral committee \(D\) satisfies \(|D|\le\theta kM_\mu(D;W)\).
A finite-support society of approval types \(t\), each carrying mass \(\mu_t\), with an integral deviating committee \(D\subseteq C\). The objective is the project cost-to-benefiting-mass ratio \(|D|/(kM_\mu(D;W))\), while projects remain indivisible and only the population is continuous.
The reductions use essentially one approval type per coverage element or graph vertex, so they do not test the programme's genuinely compressed small-\(\tau\) frontier; this limits the new computational insight of the mirrors.
fatal: False
The mirror directly covers the approval-election core-auditing hardness results in Theorems 3.1 and 3.2. It does not claim separate mirrors for the LP approximation and integrality-gap results, Lindahl priceability, sub-core auditing, arbitrary utilities and sizes, or fractional committees.
The strongest honest case is a continuous-population version of the paper’s core-auditing problem, with projects still indivisible. I would make the approximation-hardness result the lead anchor.
Let \(C\) be unit-cost projects, let \(k\) be the budget, and let \(W\subseteq C\) be the committee being audited. A voter type \(t\) is an approval set \(A_t\subseteq C\), with utility \(u_t(D)=|A_t\cap D|\) for a committee \(D\). The society is a rational distribution \(\mu=(\mu_t)_{t\in T}\), where \(\mu_t\) is the population fraction of type \(t\).
For a proposed deviating committee \(D\), define its dissatisfied mass by
\[ M_\mu(D;W)=\sum_{t:\,u_t(D)>u_t(W)}\mu_t. \]
The continuous core-auditing value is
\[ \theta_c^\infty(W) = \inf_{D\subseteq C:\,M_\mu(D;W)>0} \frac{|D|}{k\,M_\mu(D;W)}. \]
Equivalently, \(W\) lies in the \(\theta\)-approximate continuous core exactly when there is no committee \(D\) with
\[ |D|\le \theta k\,M_\mu(D;W) \]
that strictly improves every member of the deviating population. A solution consists of the value \(\theta_c^\infty(W)\), or an approximation to it, together with a witnessing committee \(D\) and the types whose mass benefits from \(D\).
This is a genuine population continuization. Projects and committees remain integral; only the population becomes divisible. If \(\mu_t=n_t/N\), then
\[ M_\mu(D;W)=\frac{|\{i:u_i(D)>u_i(W)\}|}{N}, \]
so
\[ \theta_c^\infty(W) = \frac{N}{k} \min_D \frac{|D|}{|\{i:u_i(D)>u_i(W)\}|}, \]
which is exactly the paper’s \(\theta_c\). Thus finite elections embed into the continuous problem, while the continuous input can represent an electorate of enormous size using only \(\tau=|T|\) type masses.
The natural regime is a city-wide participatory-budgeting election with hundreds of thousands or millions of residents but a much smaller collection of recurring approval profiles: neighbourhoods, civic organisations, issue coalitions, or demographic groups that approve the same project bundles. Each member of a type has the same approval set and entitlement; a deviating coalition is measured by population mass, not by the number of individually targetable residents. This is precisely the high-multiplicity interpretation of the paper’s voters.
My lead anchor is Theorem 3.2, proved in this paper. It states:
For every constant \(\gamma>0\), approximating the approval-election core-auditing value \(\theta_c\) within a factor \(1+\frac1e-\gamma\) is NP-hard.
The theorem concerns unit-sized candidates and binary approval utilities. Its proof is given here; it reduces from the cited regular maximum-coverage result in Lemma 3.3. The corresponding continuous problem is:
\(\textsc{Continuous-Core-Audit-Approx}\). Given \(C,k,W\), an explicit finite support of approval types \((A_t,\mu_t)\), and rational masses summing to \(1\), output \(\widehat{\theta}\) satisfying
\[ \theta_c^\infty(W) \le \widehat{\theta} \le \alpha\,\theta_c^\infty(W) \]
for the requested approximation factor \(\alpha\).
The expected classification is Class B: hardness transfers. A discrete election with voter multiplicities \(n_t\) is represented by \(\mu_t=n_t/N\), with exactly the same value and witnesses. The underlying reduction chooses project subsets and exploits approval incidence; it does not fundamentally require named voters. The continuous question therefore asks whether the paper’s hardness survives the high-multiplicity representation, rather than replacing the paper’s problem with an easier fractional-project problem.
The important qualification is that Theorem 3.2, as proved, does not establish hardness when \(\tau\) is fixed or very small. Its reduction can use many distinct approval types, including private dummy-project structure. The continuous mirror is nevertheless meaningful: one may duplicate every represented type arbitrarily many times without changing \(\mu\) or \(\theta_c^\infty\), so the physical electorate can be vastly larger than the type support. The open question is whether the same hardness persists in genuinely compressed regimes such as \(\tau\ll N\).
A second, complementary anchor is Theorem 3.1, also proved here in Appendix A.1. It states:
Deciding whether a committee \(W\) does not lie in the core, equivalently whether \(\theta_c\le 1\), is NP-hard even when every voter approves at most six candidates and every candidate belongs to at most two approval sets.
The source used inside the proof is Lemma A.1, cited as Corollary 2.4 of Corneil; the theorem itself is proved in this paper.
Its continuous counterpart is the decision problem:
\(\textsc{Continuous-Core-Test}\). Given the same type-mass society and committee \(W\), decide whether there exists a committee \(D\subseteq C\) such that
\[ |D|\le k\,M_\mu(D;W). \]
For the bounded-incidence version, require every type to approve at most six projects and every project to occur in at most two distinct type approval sets. A yes-certificate is the deviating committee \(D\) together with the dissatisfied mass \(M_\mu(D;W)\).
This should again be Class B. The reduction’s combinatorics live in the project-incidence graph: projects encode edges, voter types encode vertices, and the existence of a profitable deviation captures the existence of a regular subgraph. Nothing depends on distinguishing otherwise identical members of a type. Indeed, after constructing the hard type distribution, every type can represent an arbitrarily large cohort of residents.
The mirror covers the paper’s approval-election core-auditing results, both its constant-factor inapproximability and its bounded-degree exact hardness. I would not claim here to mirror the appendix’s fractional-committee result, because making projects fractional would continuize the outcome space rather than the population. Nor would I claim that these arguments automatically cover Lindahl priceability, arbitrary additive utilities, or the sub-core; those would require separate mirrors.
The weakest point is that the paper’s reductions do not by themselves prove hardness in the most compressed high-multiplicity regime. In particular, the approximation reduction uses type distinctions that may scale with the number of projects and coverage elements. The positive case therefore should not claim “continuous populations preserve all of the paper’s hardness even with constant \(\tau\).” The defensible claim is narrower: the paper’s central auditing problem has a natural, exact continuous-population formulation; its discrete results transfer to that formulation in the unrestricted type-support model; and the genuinely new programme questions concern the boundary between hardness in \(m\) and tractability when the electorate is represented by a small number of high-multiplicity types.
The strongest negative case is that both proposed anchors admit a continuous notation but not a genuinely new continuous-population problem. In both reductions, the combinatorial content is carried by project-incidence structure; voter masses merely weight already explicit approval sets.
For Theorem 3.2, the proposed value
\[
\theta_c^\infty(W)=\inf_D\frac{|D|}{k\,M_\mu(D;W)}
\]
is semantically correct, and rational cloning gives exact equality with the finite value. That makes it a valid mirror, but also exposes its weakness. In the reduction, the important voters are essentially all different types: the first group has disjoint dummy approvals, while the second group contains one approval pattern per coverage element. Thus \(\tau\) grows with the coverage instance, and the hard instances do not exploit repeated population types. Replacing individuals by rational masses is only a weighted normalization.
The obvious stronger versions do not repair this. Allowing a deviating coalition to take fractional mass changes nothing: for any fixed committee \(D\), an entire type either benefits or does not, so an optimal coalition always takes the type’s full mass. Merging types destroys the coverage incidence that the reduction needs. Giving the dummy voters a common profile helps only with irrelevant padding. Making projects fractional would produce a different, outcome-continuous problem, not a better population mirror. An implicitly described demographic space would merely move the computational difficulty into the distribution representation.
Theorem 3.1 has the same defect. Its reduction turns graph vertices into voter types and graph edges into projects. Equal type masses preserve the reduction exactly, but generally every graph vertex has its own approval neighbourhood. Arbitrarily cloning those types produces a large electorate without changing the instance’s substance. Interpreting “each candidate is approved by at most two” as “at most two support types” is a reasonable continuous restatement, but it is still just the original graph certificate with weights attached. Interpreting it as a bound on voter mass is not stable under a continuum and would make the promised restriction meaningless.
This is not an objection based on the answer: a Class B transfer would still be a legitimate result. The objection is that neither anchor supplies evidence of a population-driven computational phenomenon, an LP over population mass, or a new boundary created by continuization. The only robust formulation is an explicit weighted version of the same finite set-system problem. That may be useful as a preprocessing or high-multiplicity representation, but it is scientifically thin.
Still, the universal negative case does not hold. Core auditing is already a group-and-count property, not an identity-sensitive one; approval sets are complete voter types; and the rational-mass formulation preserves utilities, strict improvement, entitlements, witnesses, and thresholds exactly. High-multiplicity participatory-budgeting scenarios are also quite plausible. The paper therefore has two defensible direct Class B mirrors. The honest negative verdict is consequently weak: it can downgrade the mirrors as normalization-heavy and potentially low-payoff, but it cannot show that no worthwhile continuous question exists.
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.