Welfare vs. Representation in Participatory Budgeting

The strongest honest positive case is a narrow Class B mirror for PAV. It is also important to state the source-gate problem plainly: the paper has no numbered Theorem, Lemma, Corollary, or Proposition asserting NP-hardness, membership in P, FPT, or a related complexity classification. Its closest computational statement is the unnumbered sentence in Section 3.1, “Solving PAV is NP-hard [2],” cited from Aziz et al. rather than proved here. Proposition 4.1, proved in this paper, is a welfare-guarantee result, not a complexity result. Thus this is a salvageable positive case only if that cited PAV-hardness statement is accepted as the anchor.

My lead problem would be High-Multiplicity PAV-PB Winner, denoted \(\mathrm{PAV}_\infty\)-WINNER.

An instance consists of a finite project set \(P\), rational project costs \(c_p>0\), a rational budget \(L\), and a finite set of approval types \(\mathcal T\subseteq 2^P\). Each type \(A\in\mathcal T\) has rational mass \(\mu_A\ge 0\), with \(\sum_{A\in\mathcal T}\mu_A=1\). A feasible outcome is an indivisible project bundle \(B\subseteq P\) satisfying \(\sum_{p\in B}c_p\le L\). The task is to output a feasible bundle maximizing

\[ \mathrm{PAV}_\mu(B) = \sum_{A\in\mathcal T} \mu_A H(|A\cap B|), \qquad H(k)=\sum_{j=1}^{k}\frac1j. \]

Equivalently, the decision version asks whether some feasible \(B\) has \(\mathrm{PAV}_\mu(B)\ge q\). Ties should be handled exactly as in the paper: either return any PAV-optimal bundle, or impose the paper’s worst-case welfare or representation tie-breaking when studying guarantees.

This is a genuine population continuization. The type is a complete approval set; mass is the fraction of residents with that approval pattern; the decision variable remains the binary choice of funded projects; and the objective is precisely the paper’s PAV objective with voter sums replaced by population averages. Projects are not made divisible, and the budget constraint is unchanged. This is therefore a continuous society, not outcome-space continuity.

The regime is plausible in the paper’s own terms. A city may have hundreds of thousands of residents but only a few dozen or few hundred recurring approval profiles induced by districts, neighbourhoods, party lists, or organized community groups. The paper’s district example and party-list data already point toward this regime. If \(\mu_A=n_A/N\), then the finite election with \(n_A\) voters of type \(A\) has exactly the same PAV maximizers, since the mass objective is the discrete objective divided by \(N\). Conversely, every rational-mass instance expands to a finite election by choosing a common denominator.

The expected classification is Class B. Set every project cost to \(1\) and \(L=k\); the problem becomes the ordinary multi-winner PAV winner problem referred to in Section 3.1 as NP-hard [2]. The reduction therefore embeds directly into \(\mathrm{PAV}_\infty\)-WINNER. Moreover, cloning every voter \(K\) times leaves the approval types and optimal bundles unchanged while making the population \(K\) times larger. Hence the hardness is compatible with a many-agent, few-type regime. The combinatorics live in the indivisible project bundle, not in the number of named voters, so continuity of the population does not dissolve the hardness.

This mirror would cover the PAV portions of the paper, including the definition in Section 3.1, the welfare guarantee in Proposition 4.1, and the corresponding PAV entries in Table 3. Proposition 4.1 is useful supporting evidence: its proof already depends on aggregate approval counts and harmonic scores, which translate naturally into \(\mu\)-weighted sums. The mirror does not claim to cover every rule or every experimental conclusion; AV, CC, sPAV, and Rule X would require separate formulations.

It also generates worthwhile questions: is \(\mathrm{PAV}_\infty\)-WINNER fixed-parameter tractable in the number \(\tau=|\mathcal T|\) of approval types? What happens when costs are unit, bounded, or encoded in unary? Can the paper’s welfare and representation guarantees be characterized as infima over mass distributions rather than voter counts? How much approximation error results when \(\mu\) is estimated from samples? These are computational population questions, not merely a restatement of the empirical model.

The weakest point is substantial: a strict referee may reject this paper as a ChoCo anchor because the only hardness statement is unnumbered and cited, while the paper’s own numbered propositions concern guarantees rather than complexity. A second objection is that the mirror preserves discrete project selection, so it demonstrates hardness transfer rather than a new tractable continuous optimization phenomenon. I think that objection is not fatal to the mirror itself—Class B is an explicit ChoCo outcome—but it does make this a modest positive example. I would present it as a faithful high-multiplicity hardness mirror of the paper’s PAV problem, while conceding that the paper is not strong evidence for a Class A continuization programme under the strict numbered-anchor rule.