The Core of the Participatory Budgeting Problem

The strongest positive case is a high-multiplicity mirror of the paper’s core-allocation problem, led by Theorem 2.2. The paper contains no named NP-hardness or other hardness result for its underlying PB problem, so there is no hardness anchor to prefer; the appropriate anchors are its algorithmic theorems.

The continuous society is a finite distribution \(\mu\) over voter types \(T\), with \(\sum_{t\in T}\mu_t=1\). A type includes everything relevant to utility: its coefficient vector \(u_t\), its project approvals or intensities, and any other parameters. There are \(k\) public projects, costs or sizes \(s_j\), and total budget \(B\). The common decision variable is a public allocation \(x\in\mathbb{R}_{\ge 0}^k\), with \(\sum_jx_j\le B\). A coalition is now a submass \(\sigma_t\le\mu_t\), of mass \(a=\sum_t\sigma_t\), which may deviate to an allocation \(y\) costing at most \(aB\). It blocks \(x\) if every type with \(\sigma_t>0\) strictly prefers \(y\) to \(x\). A solution is an allocation with no blocking submass.

This is a sensible regime for participatory budgeting: a city may have hundreds of thousands of residents but only a few dozen projects, with voters using repeated \(K\)-approval ballots or a finite menu of utility profiles. Thus the number of agents can be much larger than the number \(\tau=|T|\) of distinct types. For approval ballots, a type can simply be a vector in \(\{0,1\}^k\); repeated neighbourhood, demographic, or campaign-generated ballot patterns make \(\tau\ll n\) plausible. This is a population continuization, not an argument based on the paper’s already-fractional project allocations.

My lead anchor is Theorem 2.2, proved in this paper. It states that when \(U_i(x)=\sum_j u_{ij}f_j(x_j)\), where each \(f_j\) is differentiable, strictly increasing, concave, and satisfies the paper’s non-satiation condition that \(x f_j'(x)\) is monotonically increasing and zero at \(x=0\), the Lindahl equilibrium, and therefore a core solution, can be computed as the solution to a convex program.

The corresponding continuous problem is:

Continuous Non-Satiating Core. Given \(B\), \(k\), a finite type set \(T\), rational masses \(\mu_t\), coefficient vectors \(u_t\), and admissible functions \(f_j\), find an allocation \(x\) with no blocking submass under utilities
\[ U_t(x)=\sum_j u_{tj}f_j(x_j). \]
Equivalently, find \(x\) satisfying the continuum Lindahl conditions
\[ \sum_{t\in T}\mu_t \frac{u_{tj}f_j'(x_j)} {\sum_{\ell}u_{t\ell}x_\ell f_\ell'(x_\ell)} \le \frac1B \]
for every project \(j\), with equality whenever \(x_j>0\).

The paper’s convex program lifts directly. Set \(z_j=x_jf_j'(x_j)\), let \(h_j\) be the inverse of \(x\mapsto xf_j'(x)\), and define \(R_j'(z_j)=1/f_j'(h_j(z_j))\). Then maximize the concave potential
\[ \Phi_\mu(z)= \sum_{t\in T}\mu_t \log\!\left(\sum_j u_{tj}z_j\right) -\frac1B\sum_jR_j(z_j). \]
A maximizer gives \(x_j=h_j(z_j)\). The finite sum over named voters has simply become an expectation over types. Under the same numerical representation assumptions used by the paper, this is a Class A problem, with complexity governed by \(k\), \(\tau\), and numerical precision rather than by the number of duplicated voters. The obvious further questions are whether one can obtain sharper bit-complexity bounds, handle implicitly represented type spaces, and quantify the discrete-to-continuous rounding error.

My second anchor is Theorem 3.1, also proved here. It states that for saturating utilities
\[ U_i(x)=\sum_j u_{ij}\min(x_j/s_j,1), \]
if \(s=\min_j s_j\), then for every \(\epsilon>0\) an \(\alpha\)-approximate multiplicative core can be computed efficiently, where
\[ \alpha=\frac1\epsilon\left(\frac Bs\right)^\epsilon+1-\frac1\epsilon. \]
Taking \(\epsilon=\ln(B/s)\) gives an \(O(\ln(B/s))\)-approximation.

The matching continuous problem is:

Continuous Saturating Core Approximation. Given \(k\) projects with sizes \(s_j\), budget \(B\), a type distribution \(\mu\), and saturating type utilities
\[ U_t(x)=\sum_j u_{tj}\min(x_j/s_j,1), \]
output an allocation \(x\) such that there is no submass \(\sigma\) of mass \(a\) and deviation \(y\) with \(\sum_jy_j\le aB\) satisfying
\[ U_t(y)>\alpha U_t(x) \]
for every type represented in \(\sigma\), with \(\alpha\) as above.

The paper’s proof extends immediately because it is pointwise in each utility type and then aggregates over voters. It replaces the saturating function by
\[ g_j(q)= \begin{cases} q/s_j,&q\le s_j,\\[2mm] \frac1\epsilon(q/s_j)^\epsilon+1-\frac1\epsilon,&q>s_j, \end{cases} \]
solves the resulting non-satiating convex program, and transfers the guarantee back to the original utilities. I would again expect Class A for the stated approximation problem. Exact computation for the saturating continuum core, and the effect of requiring integral project funding, remain separate questions; the paper’s heuristic and empirical observations do not establish either.

The authors should recognize both questions as their problems. They preserve the same public-good allocation, the same Lindahl/core fairness notion, the same utility families, and the same coalition budget rule. Only the electorate is represented by masses of indistinguishable types. In fact, the paper’s central equations depend on voters through sums such as \(\sum_i\), making the replacement by \(\int d\mu\) mathematically natural. The paper’s \(n\gg k\) motivation and approval-ballot data also provide evidence that this is not an artificial reinterpretation.

The mirror deliberately does not cover the paper’s Theorem 4.9 on approximately truthful randomized mechanisms. Dominant-strategy manipulation by one individual becomes degenerate for measure-zero agents in an atomless society, so that result needs a different continuum formulation, perhaps with strategic type blocs rather than individual agents. Nor does the mirror claim to cover the empirical comparisons between core and welfare allocations.

The weakest point is that the first mirror can look almost too easy: the paper already uses aggregate sums and already allows fractional public-good allocations. If the authors’ utility reports are genuinely idiosyncratic, \(\tau\ll n\) may be implausible, and the continuum theorem may appear to add notation more than mathematics. The positive case survives because high multiplicity is a regime, not a claim about every PB election. Repeated approval profiles or finite utility templates give a concrete scenario in which the population itself, rather than merely the outcome, is the continuous object; and the two theorems then become genuine high-multiplicity computational questions with a clear Class A expectation.