| paper | The Distortion of Public-Spirited Participatory Budgeting |
| authors | Mark Bedaywi, Bailey Flanigan, Mohamad Latifian, Nisarg Shah |
| venue | AAAI 2025 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered theorem asserting hardness, polynomial-time solvability, FPT, or another qualifying computational result. Theorem 2 and Theorems 9–11 are distortion or information-theoretic statements, which the rubric explicitly excludes. PB is a credible high-multiplicity domain and the proposed mirrors are author-recognizable, but bit (a) fails.
fails bit a — no named computational result to mirror
The proposed mirrors cover Theorems 2, 10, and 11; the remaining distortion bounds, ballot-format comparisons, empirical evaluation, and public-spirit questions are left alone.
The strongest honest case is that this paper has a very natural population-continuization, but its anchors are approximation and information-theoretic results rather than NP-hardness or P-versus-NP classifications. If “computational result” is interpreted literally as a named complexity classification, the paper has no qualifying theorem. Under the programme’s broader approximation-algorithm interpretation, it has three good anchors.
The continuous society should retain the paper’s exact semantics. There are projects \(A\), rational costs \(c(a)\), budget \(1\), and a finite set of complete voter types \(\theta\). A type contains an additive utility vector \(u_\theta\) and public-spirit level \(\gamma_\theta\), with rational mass \(\mu_\theta\). Let
\[ \bar u(a)=\sum_\theta \mu_\theta u_\theta(a),\qquad v_\theta(a)=(1-\gamma_\theta)u_\theta(a)+\gamma_\theta\bar u(a). \]
A type ranks projects and bundles by its \(v_\theta\)-values. The chosen object remains an indivisible feasible bundle \(S\subseteq A\); only the population is continuous. Its objective is
\[ \operatorname{SW}_\mu(S)=\sum_\theta\mu_\theta u_\theta(S). \]
The mechanism sees only the mass-weighted ordinal ballots, not the latent \(u_\theta\) or \(\gamma_\theta\); those define the welfare benchmark and induce the ballots. This information restriction is essential. Giving the mechanism the latent utilities would no longer mirror the paper.
This is a credible high-multiplicity regime for municipal PB: thousands or millions of residents, but a much smaller number of recurring need profiles—neighbourhoods, income or age cohorts, transport corridors, household types—and perhaps a small number of deliberative public-spirit levels. Exact clones are an idealization, but they are no stranger than the paper’s own utility-matrix model. If \(\mu_\theta=n_\theta/n\), replacing each type by \(n_\theta\) identical voters recovers the finite instance exactly: weighted pairwise counts become ordinary pairwise counts divided by \(n\), and welfare ratios are unchanged.
My lead anchor is Theorem 10, proved in this paper. It states
\[ \operatorname{dist}_{\mathrm{rank}\to\mathrm{rank\mbox{-}b(TCB)}}(\mathrm{Copeland}) =O\!\left(\frac{\log m}{\gamma_{\min}^4}\right). \]
The corresponding continuous problem is Continuous TCB Public-Spirited PB. An instance consists of \(A,c\), a rational type distribution \(\mu\), and the induced first-round rankings of projects. Partition projects into the paper’s cost tiers \(T_0,\ldots,T_L\), where \(L=\lceil\log_2m\rceil\). From the weighted first-round rankings, use weighted Iterative Copeland to choose \(t_\ell\) projects from each tier, with
\[ t_\ell=\left\lfloor\min\{|T_\ell|,\max(1,m/2^\ell)\}\right\rfloor. \]
Let \(P_\ell\) be the resulting bundle and \(P=\{P_0,\ldots,P_L\}\). In round two, each type ranks the bundles in \(P\) by \(v_\theta(S)\). The mechanism must output one feasible \(S\in P\), using weighted Copeland on the second-round mass profile. A solution is the returned bundle together with the guarantee that, for every latent type distribution inducing the observed ballots,
\[ \frac{\max_{S^\star\in F}\operatorname{SW}_\mu(S^\star)} {\operatorname{SW}_\mu(S)} =O\!\left(\frac{\log m}{\gamma_{\min}^4}\right). \]
This is expected to be Class A for execution. All weighted pairwise scores are sums over \(\tau\) types; the tier construction and both Copeland computations are polynomial in \(m,\tau\) and the ballot representation. The theorem’s guarantee transfers exactly by rational cloning. The continuous question is therefore not “fractional PB”; it is the same public-spirited, additive, indivisible PB problem with a high-multiplicity electorate.
It also generates a useful computational question of its own: can the logarithmic distortion or the \(\gamma_{\min}^{-4}\) dependence be improved when the society is represented by types, and can the second-round bundle family be constructed from a compressed type profile rather than explicit voters?
A second worthwhile anchor is Theorem 11, also proved here:
\[ \operatorname{dist}_{\mathrm{rank}\to\mathrm{rank\mbox{-}b(EB)}}(\mathrm{Copeland}) =O(1/\gamma_{\min}^4). \]
The continuous problem, Continuous EB Public-Spirited PB, uses the same type distribution and first-round ballots. For every cost tier \(T_\ell\) and every \(r\in\{0,1,2,4,\ldots,2^{\lfloor\log_2m\rfloor}\}\), weighted Iterative Copeland selects a bundle \(P_{\ell,r}\subseteq T_\ell\) of size \(r\). For every valid vector \(\mathbf t=(t_0,\ldots,t_L)\) whose union
\[ P_{\mathbf t}=\bigcup_\ell P_{\ell,t_\ell} \]
is feasible, include \(P_{\mathbf t}\) in \(P\). Types rank all bundles in \(P\) in round two, and weighted Copeland returns a feasible bundle.
The requested solution is again the final bundle, with constant distortion relative to the best feasible integral bundle under \(\operatorname{SW}_\mu\). The rational-clone argument gives an exact continuous mirror of the theorem.
Its expected classification is more qualified. The population aggregation is easy, but \(|P|\) can be
\[ O\!\left(m^{O(\log\log m)}\right), \]
so explicit execution is quasipolynomial rather than polynomial. The remaining obstacle is not voter multiplicity; it is the large family of candidate bundles. Thus the continuous version exposes a genuine follow-up: is there a succinct representation or separation procedure that realizes the constant-distortion guarantee in polynomial time? That would be a meaningful Class-A result. As stated, this anchor reaches a representation boundary rather than a continuum-specific hardness result.
The third anchor is the negative boundary, Theorem 2, proved in this paper:
\[ \operatorname{dist}_{\mathrm{rank}}(f) \in\Omega(m/\gamma_{\min}) \]
for every deterministic PB rule \(f\).
The corresponding problem, Continuous Rank-Only PB Design, is: given rational costs and a rational mass profile over project rankings, design a deterministic rule mapping that weighted ranking profile to an indivisible feasible bundle, minimizing the worst-case ratio
\[ \sup_{\text{latent }(u,\gamma)\text{ inducing the profile}} \frac{\max_{S^\star\in F}\operatorname{SW}_\mu(S^\star)} {\operatorname{SW}_\mu(f)}. \]
Theorem 2 says that no such rank-only rule can guarantee \(o(m/\gamma_{\min})\). This lower bound transfers to the continuous model by duplicating each finite voter type equally many times. It is not a complexity classification, but an information-theoretic impossibility that survives high multiplicity. It is therefore not Class C: continuity does not create the obstruction, and it does not remove it either. The actual computational execution of any fixed rule remains polynomial; the limitation is the information supplied by project rankings.
These mirrors cover the paper’s central theoretical results: the polynomial-size tiered-bundle protocol of Theorem 10, the constant-distortion exhaustive-bundle protocol of Theorem 11, and the rank-ballot impossibility of Theorem 2. They deliberately do not continuize the projects, the budget, or the feasible bundles. Nor do they use the paper’s empirical Section 6 as an anchor.
The weakest point is that the paper’s real difficulty is not population multiplicity. Its results concern what information ballots reveal about cardinal welfare, and the continuous version mostly replaces repeated voters by rational masses. A referee could reasonably say that Theorem 10 is an exact weighted restatement, not a new continuous-computational phenomenon. The hidden-cardinal-utility interface is another delicate point: if the latent type distribution were handed directly to the algorithm, the mirror would be invalid.
That weakness does not destroy the case. Public budgeting is one of the clearest settings in which a high-multiplicity society is substantively honest, and the paper’s rules depend on voters only through pairwise comparisons and aggregate welfare. The continuous versions are therefore author-recognizable, exact population mirrors. Their value for ChoCo would be to ask which of these weighted-profile protocols admit compact polynomial algorithms, where the quasipolynomial bundle barrier begins, and whether the rank-only impossibility remains unchanged under every sensible type compression.
The strongest negative starts before the modelling details: this paper has no named computational result in ChoCo’s strict sense. Theorem 2 and Theorems 9–11 are distortion and information-theoretic statements about voting rules and ballot formats. They do not classify a computational problem, give an exact or approximation algorithm for an optimization problem, or establish hardness. The fact that Copeland and the bundle protocols can be executed does not turn their distortion guarantees into computational results. Thus the proposed continuous problems are analyst-created wrappers around the paper, rather than continuous mirrors of named computational problems.
Even granting the proponent’s broader interpretation, the paper’s population mirror is only a weighted restatement. PB is genuinely a plausible high-multiplicity setting: millions of residents and recurring demographic or neighbourhood profiles are credible. Rational cloning also works exactly. But that establishes fidelity, not a worthwhile ChoCo problem.
There is a deeper information-model difficulty. A complete type must contain the cardinal utilities and public-spirit level, because those determine the welfare benchmark and the public-spirited rankings. If the continuous input contains \((u_\theta,\gamma_\theta,\mu_\theta)\), then the mechanism has been handed the latent information that the paper explicitly hides. If the mechanism sees only the induced weighted rankings, then the “society distribution” is not actually its computational input; it is hidden data used by the analyst to evaluate distortion. If types contain only rankings, they are incomplete: two populations with the same ranking types can have arbitrarily different social welfare. A small recurring type catalogue is possible as a new restricted model, but it no longer represents the paper’s unrestricted-utility distortion theorem.
Theorem 10 is the proponent’s strongest anchor, but it does not survive as a worthwhile continuous-computational result. Every operation in the tiered protocol is already an aggregate operation on voters: pairwise Copeland scores are sums of comparison indicators, and the same is true of the second-round bundle rankings. Replacing voter counts by rational masses changes those sums to weighted sums and leaves the proof unchanged. A compressed implementation can run in time polynomial in the number of ranking types and the encoding length of their masses, but this is merely the obvious weighted implementation of an already explicit, simple voting rule. There is no population-sized optimization problem, separation oracle, or complexity boundary to discover.
The proposed question about improving the \(\log m\) or \(\gamma_{\min}^{-4}\) factors is a question about the paper’s distortion analysis and project/bundle construction, not about continuization. It may be good PB theory, but it would remain the same question with weighted ballots. Calling this “Class A” also overstates what has been shown: the continuous version has not produced a tractable continuous optimization formulation; it has only evaluated a fixed rule on a weighted profile.
Theorem 11 is weaker still. Its exhaustive-bundle protocol is quasipolynomial because it explicitly constructs a large family of candidate bundles indexed by tier-size vectors. Weighting the electorate does nothing to that family. A proposed succinct representation would require a new model for how voters rank implicitly represented bundles, probably through comparison or separation oracles. That changes the elicitation and access model: a compact description of bundles does not supply the rankings of all those bundles or the weighted Copeland tournament over them. Designing such an oracle model could be worthwhile, but it would be a new bundle-representation and elicitation problem, not a consequence of making the population continuous. Replacing EB by a different polynomial-size family would likewise be a new ballot format.
Theorem 2 cannot rescue the case. It is an information-theoretic lower bound saying that no deterministic rule using project rankings can avoid large distortion. The proposed “continuous rank-only PB design” is not a computational problem from the paper; it is the analyst’s reformulation of the space of all possible rules. Its lower bound transfers under cloning because the relevant welfare and voting inequalities are linear in voter contributions. That is precisely why it supplies no new continuum phenomenon. The construction already uses only a small number of relevant voter classes in its proof sketch, so it is not exposing a difficulty caused by population multiplicity. Asking whether the same impossibility holds under a specially restricted type catalogue could be a robustness exercise, but not a computational mirror of Theorem 2.
Nor do the other distortion results improve the situation. The randomized bounds, approval-ballot bounds, and HLB/TCB/EB comparisons all concern what ordinal information can guarantee about a hidden cardinal objective. They are naturally invariant under duplicating voters and therefore translate mechanically to masses. No result in the paper asks whether a high-multiplicity society admits a faster algorithm, whether a continuous LP has a separation problem, or whether population multiplicity creates or removes hardness.
The honest concession is that PB itself is an excellent domain for a future high-multiplicity paper. One could study succinct typed ballot profiles, estimated masses, hidden utility distributions, or optimal bundle-family design. But each of those would add a new objective or access model. This paper offers a clean weighted implementation of its voting rules, not a computational question whose continuous population version belongs in ChoCo. Under the programme’s named-result and computational-object criteria, the negative case is therefore strong; it becomes weak only if “continuous mirror” is broadened to include any exact high-multiplicity rewriting of an information-theoretic distortion theorem.
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.