A Mechanism for Participatory Budgeting with Funding Constraints and Project Interactions

The strongest positive case is a genuine population mirror of the paper’s welfare-maximization problem. It does not make the problem easier by fractionalizing projects: the society becomes continuous, but the funded bundle remains deterministic and integral.

Let \(P\) be the projects, with costs \(c_j\), groups \(Z=\{z_1,\ldots,z_r\}\), and budget \(B\). A voter type \(\theta\) is a complete PBPI vote \(v^\theta=(f^\theta,s^\theta,\eta^\theta)\): group funding levels, approved projects, and complementarity indicators. A continuous society is a rational distribution \(\mu\) over such types, with \(\mu_\theta\ge 0\) and \(\sum_\theta\mu_\theta=1\). Its welfare for an integral bundle \(Q\subseteq P\) is

\[ U_\mu(Q)=\sum_{\theta}\mu_\theta u_\theta(Q), \]

where \(u_\theta\) is exactly the utility in Definition 1 of the paper. Thus \(\mu_\theta\) is the fraction of residents with that complete vote type; a finite population with \(N\mu_\theta\) such voters has the same maximizing bundle, since the paper’s welfare is merely multiplied by \(N\).

The natural regime is a large municipal PB electorate, or a delegated PB process in which wards or representatives speak for large cohorts. Residents sharing a ward, demographic, institutional, or delegated preference profile have the same approval sets, group funding levels, and interaction declarations. The number of residents \(N\) may be millions while the number of distinct vote types \(\tau\) is moderate. This is exactly the kind of high-multiplicity regime the paper itself gestures toward when it discusses weighted distinct votes.

My lead anchor is the paper’s numbered Observation 5, proved here in Appendix A.1: “SWM-PB is NP-hard.” Here \(\mathrm{SWM\text{-}PB}\) is the problem of finding a social-welfare-maximizing integral project bundle under the overall budget constraint, with the PBPI utility function and no additional funding constraints. The proof is a reduction from Maximum Set Coverage.

The corresponding continuous problem is \(\mathrm{CSWM\text{-}PB}_\infty\):

Given \(P\), project costs, groups, budget \(B\), a rational distribution \(\mu\) over complete PBPI voter types, and the same valid-bundle restrictions as PBPI, output an integral bundle \(Q\) maximizing \(U_\mu(Q)\). Equivalently, in the decision version, given a rational threshold \(K\), decide whether some valid \(Q\) satisfies \(U_\mu(Q)\ge K\).

This is not a weakened interaction-free reformulation. The full problem permits complementary, substitute, independent, and contradictory groups. The reduction only uses a valid special case of that problem. Given a Maximum Set Coverage instance with universe \(A\), sets \(D_1,\ldots,D_m\), and quota \(k\), create one unit-cost project \(p_j\) for each \(D_j\), budget \(B=k\), and one voter type \(\theta_a\) for each \(a\in A\), with mass \(\mu_{\theta_a}=1/|A|\). Put all projects in one non-contradictory group, set \(f^{\theta_a}=1\), declare the projects substitutes, and let \(\theta_a\) approve exactly those \(p_j\) for which \(a\in D_j\). Then

\[ U_\mu(Q)=\frac{\left|\bigcup_{p_j\in Q}D_j\right|}{|A|}. \]

Hence an optimizer for \(\mathrm{CSWM\text{-}PB}_\infty\) solves Maximum Set Coverage, even when every type has equal mass. The expected classification is therefore Class B: hardness transfers to the continuous population problem. The combinatorics live in the project-selection dimension, not in the number of named voters, so continuization does not dissolve this hardness.

This mirror should be acceptable to the authors because it preserves their underlying question exactly: the same projects, costs, PBPI utility, interaction language, and deterministic integral outcome remain in place. Only the sum over individually indexed voters becomes an average over voter types. The result is not a claim that continuity creates tractability; it is a precise test showing where it does not.

A useful further question is whether some restricted PBPI families become tractable when parameterized by the number \(\tau\) of voter types, group-interaction width, or a suitable approximation parameter, despite the general hardness result. One can also ask whether high multiplicity yields additive or multiplicative approximation schemes when the type distribution is given compactly.

My supporting anchor is Theorem 4, proved in Section 4.1. It states that, under Assumption 2—that all projects in a ballot group have the same funding labels—\(\mathrm{FC\text{-}SWM\text{-}PB}\) is fixed-parameter tractable with respect to \((\log B,s_{\max})\), where \(s_{\max}\) is the maximum group size. The proof gives a recursive dynamic program over budget allocations to groups, enumerating subsets within each group; it also shows that the result does not actually require the 1-laminarity assumption.

The corresponding continuous problem is \(\mathrm{FC\text{-}CSWM\text{-}PB}_\infty\):

Given the same continuous society \(\mu\), project groups, costs, budget, and minimum/maximum funding constraints on project labels, with every group satisfying Assumption 2, output an integral feasible bundle \(Q\) maximizing \(U_\mu(Q)\). The parameter is \((\log B,s_{\max})\).

The expected classification is Class A. In the paper’s recursion, every group-subset value is computed by summing voter utilities. With a continuous society, that operation becomes

\[ \sum_{\theta}\mu_\theta u_\theta(Q), \]

so the same dynamic program operates on \(\tau\) types rather than \(N\) individually listed voters. After exact rational arithmetic, its running time is of the form

\[ f(\log B,s_{\max})\operatorname{poly}(\tau,r,L), \]

and the paper’s explicit \(O(nrB2^{s_{\max}})\)-style bound becomes the corresponding bound with \(\tau\) in place of \(n\). This is a real high-multiplicity gain: the running time depends on the number of distinct complete vote types, not on the population size represented by their masses.

The paper’s Theorem 5, also proved here, reinforces the regime plausibility: under Assumptions 2 and 3, it gives an FPT algorithm parameterized by the number of distinct votes, with each vote carrying a frequency or weight. I would not use Theorem 5 as a separate anchor because it is already very close to the finite weighted version of the proposed mirror. I regard it instead as evidence that the authors would recognize \(\mu\)-weighted populations as their problem rather than as an alien reinterpretation.

The scope is deliberately limited. These mirrors cover Observation 5 and Theorem 4, not the paper’s strategyproofness results or its Nash-equilibrium results. That is appropriate for ChoCo’s computational focus.

The weakest point is that the continuous formulation is close to something the paper already discusses: Theorem 5 explicitly permits weighted distinct votes. Thus this paper should not be presented as having independently invented continuization, and the mirror has limited novelty as a model. The positive case is nevertheless sound: the underlying PBPI problem has a precise continuous-population form, its hardness anchor survives by an explicit uniform-mass reduction, and its FPT algorithm naturally compresses from individual voters to voter types. The ChoCo contribution would be to make that discrete–continuous dictionary explicit and chart which PB problems behave like these two anchors.