| paper | Participatory Budgeting with Multiple Degrees of Projects and Ranged Approval Votes |
| authors | Gogulapati Sreedurga |
| venue | IJCAI 2023 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 1
statement extracted from the paper’s text layer
Given projects \(P\), degree sets \(D_j\) with costs \(c_{jd}\) including \(c_{j0}=0\), budget \(b\), complete voter types \(\Theta\) with rational masses \(\mu_\theta\) summing to \(1\), and interval reports \((\ell_\theta(j),h_\theta(j))\), decide whether there exists one \(d_j\in D_j\) per project such that \(\sum_j c_{jd_j}\le b\) and \(\sum_j c_{jd_j}\sum_{\theta:\ell_\theta(j)\le c_{jd_j}\le h_\theta(j)}\mu_\theta\ge K\).
High-multiplicity ranged-approval PB: \(\Theta\) is the set of complete interval-report types, \(\mu\) is their population mass, \(d=(d_j)\) chooses one discrete degree per project, feasibility uses the original budget constraint, and the objective is \(U_\mu(d)=\sum_j c_{jd_j}\sum_{\theta:\ell_\theta(j)\le c_{jd_j}\le h_\theta(j)}\mu_\theta\).
The best residual objection is that \(R_c(S)\) uses the type distribution only through acceptance masses \(a_{jd}\), so the mirror has little type-space geometry or population-specific structure; this bounds its scientific richness but does not invalidate the high-multiplicity formulation.
fatal: False
The mirror covers the \(R_c(S)\) results in Proposition 1, Theorem 2, and Proposition 3. It leaves the other PB rules, the axiomatic propositions, and continuity of projects, outcomes, or time untouched.
The strongest mirror is a high-multiplicity version of the paper’s cost-utility rule \(R_c(S)\). I would treat this as one continuous problem viewed at three computational resolutions: exact, approximate, and parameterized exact.
The scenario is a large municipal participatory-budgeting process. There may be \(n\) hundreds of thousands of residents but only \(\tau\) recurring preference types: for example, standardized neighbourhood, household, or demographic profiles that submit the same complete vector of acceptable cost intervals. A type \(\theta\) is the full collection \((\ell_\theta(j),h_\theta(j))_{j\in P}\), so agents of the same type are indistinguishable for the rule. Its mass \(\mu_\theta\) is the fraction of residents of that type. This is a genuine population continuization: projects and their permissible degrees remain discrete, and only the electorate becomes a distribution.
For each project \(j\), let \(D_j\) be its permissible degrees, with costs \(c_{jd}\), including \(c_{j0}=0\). A feasible outcome chooses one degree \(d_j\in D_j\) for every project and satisfies \(\sum_j c_{jd_j}\le b\). Define the acceptance mass of degree \(d\) for project \(j\) by \(a_{jd}=\sum_{\theta:\ell_\theta(j)\le c_{jd}\le h_\theta(j)}\mu_\theta\). The continuous cost-utility of an outcome \(d\) is \(U(d)=\sum_j c_{jd_j}a_{jd_j}\). Thus each project-degree option has a rational expected utility, while the budget and degree choices remain exactly those of the paper.
My lead anchor is Proposition 1: “For an instance \(I\) and a value \(s\), it is NP-hard to check if \(R_c(S)\) outputs a set with at least a total utility \(s\).” This proposition is proved in the paper, using the earlier hardness framework of Talmon and Faliszewski. Its continuous counterpart is the following exact problem.
Continuous Cost-Utility PB\(_\infty\)-Decision. Given the projects, permissible costs, budget \(b\), type distribution \(\mu\), ranged approvals, and a rational threshold \(K\), does there exist a feasible degree vector \(d\) with \(U(d)\ge K\)? A solution is the selected degree for every project.
I expect NP-hardness to transfer. Any discrete instance maps to \(\mu_\theta=n_\theta/n\), preserving every objective value up to the harmless normalization by \(n\). The reduction’s combinatorics live in choosing projects and degrees under a knapsack budget, not in the individuality of voters. This is therefore a Class B mirror: the continuous population does not dissolve the underlying project-selection hardness. The unrestricted continuous problem is also visibly a multiple-choice knapsack with rational profits \(c_{jd}a_{jd}\).
The main further question is whether hardness remains when \(\tau\) is bounded or very small relative to \(n\). Proposition 1 alone does not establish that: its embedding may use many distinct types. That is a genuine research question rather than a defect in the mirror.
The second anchor is Theorem 2: “There is an FPTAS for \(R_c(S)\).” This theorem is proved in the paper. Its continuous counterpart is:
Continuous Cost-Utility PB\(_\infty\)-Approximation. Given the same instance and \(\varepsilon\in(0,1)\), output a feasible degree vector \(d\) satisfying \(U(d)\ge(1-\varepsilon)\operatorname{OPT}\), where \(\operatorname{OPT}\) is the maximum continuous cost-utility.
I expect an FPTAS, hence tractability at the approximation level. After aggregating the type masses, this is a multiple-choice knapsack with rational profits. Profit scaling and dynamic programming give a running time polynomial in \(m\), \(\tau\), the number of degrees, the encoding length of the rational data, and \(1/\varepsilon\). The paper’s integer-score proof does not transfer literally—the continuous scores are rational rather than bounded integers—but its approximation idea does.
This is a useful mirror because it distinguishes exact from approximate computation without changing the social-choice question. The exact rule remains hard, while a referee would recognize the FPTAS problem as the natural approximation version of precisely the same PB rule.
The third anchor is Proposition 3: “For any instance \(I\), computing a subset \(S\in V\) that is selected under \(R_c(S)\) is in FPT w.r.t. scalable limit \(\delta\).” This proposition is also proved in the paper. The corresponding continuous problem is:
Scalable-Limit Cost-Utility PB\(_\infty\). Given a continuous cost-utility instance with integer project costs and budget, let \(g\) be the greatest common divisor of all positive costs and \(b\), and let \(\delta=\max_{j,d}c_{jd}/g\). Compute an exactly optimal feasible degree vector, parameterized by \(\delta\).
I expect this version to be FPT in \(\delta\), even with arbitrary rational type masses. Scale costs by \(g\), then use a dynamic program indexed by total cost rather than total voter score. There are at most \(m\delta\) relevant cost states, and each transition compares the \(t_j\) degrees of one project. The running time is polynomial in \(m\), \(\tau\), the encoding length, and \(\delta\). This is a Class A island inside the otherwise hard continuous problem: coarse project-cost granularity restores exact tractability.
The mirror covers the paper’s computational Section 3 for the rule \(R_c\): its exact hardness, approximation scheme, and scalable-limit parameterization. It does not attempt to continuize the axioms in Section 4, nor does it turn projects or budgets divisible; those would be different kinds of continuity and are outside the programme’s scope.
The authors should recognize this as their problem rather than a tractable simplification. The complete ranged-approval ballot is retained, every project still has several discrete sophistication levels, the budget constraint is unchanged, and the objective is exactly the population-average version of their utility. The only compression is replacing repeated identical voters by their mass, which is precisely the high-multiplicity interpretation.
My weakest point is the plausibility of a small type space for full ranged approvals. If every resident independently supplies a different interval for every project, then \(\tau\) may be nearly \(n\), and the high-multiplicity interpretation loses force. The mirror is strongest for recurring PB programmes with standardized project menus and stable constituency profiles. Even there, I would not claim that continuization makes the exact problem easy. The honest claim is narrower: this paper supplies a natural population-distribution version whose exact, approximate, and parameterized complexity questions are all faithful, nontrivial, and directly connected to its named results.
The strongest negative case is that the proposed mirror is not really population-continuous in the sense ChoCo seeks. For \(R_c(S)\), all voter information collapses immediately to
\[ a_{jd}=\sum_{\theta:\ell_\theta(j)\le c_{jd}\le h_\theta(j)}\mu_\theta, \]
and the objective is
\[ U(d)=\sum_j c_{jd_j}a_{jd_j}. \]
Thus two societies with entirely different type distributions but the same \(a_{jd}\) values are indistinguishable to the rule. The type space, its geometry, and the distribution \(\mu\) have no independent role. The proposed mirror is therefore a multiple-choice knapsack instance with rational profits, obtained by renaming voter-score coefficients. Any richer population structure—mass transfers, type-dependent interventions, correlations between projects, or endogenous participation—would be a new problem rather than a mirror of this paper.
That is the best substantive objection, but it cannot defeat the first anchor under the programme’s stated rules. Proposition 1 does have a legitimate high-multiplicity interpretation. Given rational masses, clearing denominators produces cloned voters, and the finite objective is exactly \(nU(d)\). Feasible outcomes, utility comparisons, and thresholds are preserved after scaling. A type can naturally be the complete vector of interval reports over the project menu. Standardized neighbourhood or demographic profiles provide a plausible repeated-type scenario. The fact that arbitrary instances may have \(\tau\) close to \(n\) weakens the empirical story, but it does not eliminate the high-multiplicity regime.
Nor can the first anchor be defeated by observing that the hardness is project-side. That would merely classify the mirror as Class B, which the programme explicitly regards as a valid outcome. Proposition 1 therefore survives as a faithful continuous decision problem, even if the population continuity contributes little to the source of hardness.
Theorem 2 is also harder to dislodge than the proponent suggests, but for the opposite reason: the continuous approximation problem is perfectly well-defined. After aggregation, it is a multiple-choice knapsack with rational profits \(c_{jd}a_{jd}\). Standard profit scaling yields an FPTAS with polynomial dependence on the encoding length of the masses and on \(1/\varepsilon\). The paper’s integer-score proof need not transfer literally; a rational-profit formulation is the natural version. Calling this “ordinary knapsack” does not invalidate it. The programme permits a continuous mirror whose answer is a familiar algorithmic problem, provided the population interpretation is faithful.
Proposition 3 likewise survives the rational-mass generalization. With integer project costs, scale by the common divisor and index a dynamic program by total scaled cost. At each cost state, store the maximum rational utility achieved. Rational arithmetic has polynomial bit complexity, so the DP remains fixed-parameter tractable in \(\delta\), with polynomial dependence on the input encoding and the number of types. The proponent’s proposed algorithm is therefore not merely heuristic: it is a valid continuous analogue, even though \(\delta\) measures project-cost granularity rather than population structure.
The only remaining negative argument is one of research value. All three anchors concern the same aggregated knapsack object, and the paper itself already computes the sufficient statistics \(s(P_j^t)\). A ChoCo project built around this mirror would likely discover no analogue of type-space pricing, mass-transfer geometry, or continuum-specific barriers. But this is a novelty and priority concern, not a fundamental failure of continuization. It cannot be converted into the forbidden objection that continuity “does not help.”
Consequently, the universal negative claim is not supportable here. The mirror is population-faithful, identity-free, nondegenerate, and connected to three named computational results. The honest negative case can argue that it is too elementary to deserve priority, but it does not defeat any anchor.
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.