Participatory Budgeting: Data, Tools and Analysis

The honest answer is that this paper has no qualifying named computational anchor. In the supplied full text there is no numbered Theorem, Lemma, Corollary, or Proposition asserting an algorithmic or complexity result. The closest statements are the unnumbered claim that Utilitarian Greedy is optimal up to one project, cited to Dantzig [1957], and the proportionality properties of Method of Equal Shares, cited to Peters and Skowron and Peters et al. Neither is a result proved and numbered in this paper. The data analyses, tables, and empirical conclusions are not computational anchors under the programme’s rule.

That blocks a strict positive verdict, but the strongest salvageable mirror is still quite good at the level of the paper’s central computational objects. My lead candidate would be Continuous PB Outcome-and-Metrics Evaluation, \( \mathrm{CPB\text{-}Eval}_\infty \).

An instance contains a finite project set \(P\), rational project costs \(q_p\), a rational budget \(b\), a fixed tie-breaking order, and finitely many voter types \(t\in T\) with rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). A type is a complete ballot over every project, together with district or eligibility information when the districtwise scheme is being modelled. Its score vector is \(s_t:P\to\mathbb{Q}_{\ge 0}\). Projects remain indivisible: a feasible outcome is \(W\subseteq P\) with \(\sum_{p\in W}q_p\le b\). Thus only the population is continuized.

For score utilities take \(u_t(p)=s_t(p)\); for cost utilities take \(u_t(p)=s_t(p)q_p\). The continuous Utilitarian Greedy outcome \(W^{\mathrm{UG}}_\infty\) sorts projects by

\[ \frac{\sum_t\mu_tu_t(p)}{q_p} \]

and scans them in that order, selecting a project whenever it fits. The continuous Method-of-Equal-Shares outcome \(W^{\mathrm{MES}}_\infty\) starts type \(t\) with aggregate endowment \(r_t=b\mu_t\). For each unelected project \(p\), it finds the least \( \alpha\ge 0 \) satisfying

\[ \sum_t \min\!\bigl(r_t,\alpha\mu_tu_t(p)\bigr)=q_p. \]

If no such \( \alpha \) exists, \(p\) is unaffordable. The affordable project with minimum \( \alpha \) is selected, each type pays

\[ x_{t,p}=\min\!\bigl(r_t,\alpha\mu_tu_t(p)\bigr), \]

and \(r_t\) is reduced accordingly. The \(U\)-completion can then be applied by running Utilitarian Greedy on the remaining projects and residual budget.

The task is to output both outcomes exactly, together with the exact continuous versions of the paper’s metrics: average utility

\[ \bar u(W)=\sum_t\mu_t\sum_{p\in W}u_t(p), \]

exclusion ratio, and power inequality. For the latter, define the normalized per-capita share of type \(t\) by

\[ \sigma_t(W)=\sum_{p\in W} \frac{s_t(p)}{\sum_r\mu_rs_r(p)}q_p, \]

with zero-denominator terms treated as zero, and return

\[ \mathrm{PI}(W)=\frac{1}{b}\sum_t\mu_t\lvert \sigma_t(W)-b\rvert . \]

A decision version may ask whether \( \mathrm{PI}(W^{\mathrm{MES}}_\infty)\le \mathrm{PI}(W^{\mathrm{UG}}_\infty) \), or whether the MES outcome beats UG by a specified utility or exclusion threshold.

This is a plausible high-multiplicity regime. In the paper’s Wrocław and Zabrze-style formats, voters choose only one local and one citywide project. With \(m\) projects, there are then at most roughly \(m^2\) ballot types, while a city may have hundreds of thousands or millions of voters. District identity and local/citywide eligibility can be included in the type, so two voters are interchangeable exactly when the paper’s rules treat them identically. Clearing denominators gives \(n_t=n\mu_t\) cloned voters and reproduces the discrete MES and UG computations exactly. The model is therefore a direct high-multiplicity reformulation of the rules, not a fractional-project relaxation.

I would expect \( \mathrm{CPB\text{-}Eval}_\infty \) to be in Class A. UG is obtained by weighted aggregation and sorting. Each MES affordability test is a piecewise-linear equation with at most \( \tau \) breakpoints, and there are at most \(m\) selection rounds. Exact rational arithmetic should therefore give a polynomial-time algorithm in \(m\), \(\tau\), and the encoding length, independently of the number \(n\) of cloned voters. If one replaces the greedy completion by an optimal completion, knapsack hardness reappears through the project set; that would be Class B hardness from project combinatorics, not population multiplicity.

The mirror covers only the paper’s UG/MES rule execution and its utility, exclusion, power-inequality, and districtwise-versus-citywide comparisons. It does not cover Pabulib, Pabutools, Pabustats, the maps, or the empirical claim that MES is universally fairer. Further questions would include whether any fairness dominance holds for restricted ballot domains, how Add1 completion should be normalized continuously, and what approximation guarantees relate the mass computation to finite elections with rounded proportions.

The weakest point is decisive: this would establish a new computational question inspired by the paper, not continuize one of its numbered results. Moreover, the basic algorithm may be viewed as an obvious weighted implementation rather than a substantial new complexity problem. The positive case is therefore that the paper’s central PB rules admit a faithful, exact, and computationally useful high-multiplicity formulation; it is not that this paper itself supplies a qualifying theorem for ChoCo’s mirror catalogue.