| paper | Time-Constrained Participatory Budgeting Under Uncertain Project Costs |
| authors | Dorothea Baumeister, Linus Boes, Christian Laußmann |
| venue | IJCAI 2022 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 7
statement extracted from the paper’s text layer
Given a rational instance with projects \(A\), approval types \(T\subseteq 2^A\), mass vector \(\mu\), budget \(\ell\), durations \(\delta\), deadline \(\tau\), and a known finite-support joint cost law \(\mathcal D\), decide for threshold \(\sigma\) whether a nonanticipating policy \(\Pi\) exists that is punctual, satisfies conditional \(\alpha\)-risk assessment on every observed history, and for every \(\omega\in\operatorname{supp}(\mathcal D)\) achieves \(u_\mu(B_{\Pi,\omega})\ge \sigma^{-1}\max_{B\subseteq A:c_\omega(B)\le\ell}u_\mu(B)\), where \(u_\mu(B)=\sum_{t\in T}\mu_t|t\cap B|\).
Approval types are \(t\subseteq A\) with population mass \(\mu_t\); policy decisions are history-dependent project launch sets, exact costs are revealed on completion, and the objective is the minimum worst-case ratio against offline knapsack subject to risk and deadline constraints. The additive objective compresses \(\mu\) to project weights \(w_a=\sum_{t:a\in t}\mu_t\), making the mirror a Class-B-style high-multiplicity restatement.
Theorem 7 gives a competitive-ratio lower bound rather than an explicit running-time classification, so its status as the computational anchor depends on treating competitive lower bounds as inapproximability results.
fatal: False
The mirror covers Theorem 7 and the surrounding online competitive-ratio results, while leaving the EJR and BPJR-L axioms, incompatibility results, and BEE/BEP experiments outside the computational mirror.
Strictly speaking, this paper contains no numbered theorem asserting NP-hardness, membership in \(\mathrm{P}\), parameterized hardness, or a similar complexity classification. Its named results are online impossibility theorems, competitive-ratio bounds, and axiomatic guarantees. So the positive case cannot honestly claim that the paper already supplies a ChoCo complexity anchor. It can, however, supply a faithful continuous-population version of its online computational model.
The natural mirror is approval-based rather than ranking-based. Let \(A\) be the finite project set and let \(T\subseteq 2^A\) be the set of approval types. A type \(t\) is a complete approval signature, and \(\mu_t\) is its population mass, with \(\sum_t\mu_t=1\). For a bundle \(B\subseteq A\), normalized satisfaction is \(u_\mu(B)=\sum_{t\in T}\mu_t|t\cap B|\). Projects remain indivisible: the continuum is only in the electorate, not in the project set.
A plausible regime is a city-wide or national participatory-budgeting round with hundreds of thousands or millions of residents, perhaps \(m\) in the tens and \(\tau=|T|\) in the tens or hundreds. Repeated approval signatures can arise from neighbourhoods, demographic cohorts, or standardized survey responses. The cost uncertainty is naturally project-level: the train project has one eventual cost, regardless of how many residents approve it. Thus this is genuinely a high-multiplicity version of the authors’ model, not a fractionalization of projects.
The action variable is still their budgeting log, now generated by a history-dependent policy \(\Pi\). At each time step, \(\Pi\) chooses which unstarted projects to launch; costs are revealed only when projects finish, and launched projects cannot be cancelled. A precise input consists of \(A,T,\mu\), rational cost bounds and a rational finite-support joint distribution over exact project-cost vectors, the budget \(\ell\), durations \(\delta\), deadline \(\tau\), and risk parameter \(\alpha\). The policy must satisfy the paper’s conditional \(\alpha\)-risk-assessment rule. For rational \(\mu_t=n_t/n\), this is exactly the original instance after dividing all voter satisfactions and coalition sizes by \(n\).
My lead mirror is Continuous Competitive Uncertain-Cost Budgeting, anchored on Theorem 7, proved in this paper. Given such an instance, ask for the smallest \(\sigma\) for which there exists an \(\alpha\)-risk-assessing, punctual online policy satisfying, for every cost realization \(\omega\), \(u_\mu(B_\Pi(\omega))\ge \frac{1}{\sigma}\max_{B:c_\omega(B)\le \ell}u_\mu(B)\). Equivalently, the output is an explicit policy together with a certificate that its worst-case competitive ratio is at most \(\sigma\).
Theorem 7 transfers directly. Take one approval type \(t=A\) with \(\mu_t=1\), so \(u_\mu(B)=|B|\). Let \(m\) projects have \(c_{\min}(a)=1\), \(c_{\max}(a)=m\), budget \(\ell=m\), and duration \(\delta(a)=\tau\). Each project independently costs \(m\) with probability \(\alpha\) and \(1\) otherwise. The risk condition prevents two projects from being started together, while the duration prevents later additions. If the first project realizes at cost \(m\), the online policy obtains one project, whereas the offline solution takes the remaining \(m-1\) cheap projects. The \(\Omega(m)\) lower bound therefore survives with a continuous electorate, even with \(\tau=1\).
I expect this problem to exhibit a Class-B-style obstruction, not continuum-specific hardness: the difficulty lives in indivisible project selection and online cost revelation, not in population multiplicity. The continuous aggregation removes the irrelevant factor \(n\), but it does not dissolve the project-level lower bound. The natural further questions are the exact competitive frontier as a function of \(\alpha\), uncertainty width, and \(\tau\), and whether bounded uncertainty yields a compact polynomial-time policy rather than merely an existential guarantee.
A second, genuinely population-facing mirror is Continuous Rule-X EJR, anchored on Theorem 15, proved here. A coalition is represented by a mass vector \(q\) with \(0\le q_t\le\mu_t\), and total mass \(q(S)=\sum_tq_t\). For a realized bundle \(B\), define \(c'_B(a)=c(a)\) for \(a\in B\) and \(c'_B(a)=c_{\max}(a)\) otherwise. Continuous ex-post EJR requires that, for every nonzero coalition \(q\) and every unanimously approved project set \(S\subseteq\bigcap_{q_t>0}t\) satisfying \(c'_B(S)\le\ell q(S)\), some type with \(q_t>0\) receives at least \(|S|\) approved projects in \(B\).
The continuous problem is: given the uncertain-cost budgeting instance, output an online policy satisfying \(0\)-risk-assessment and continuous ex-post EJR. The direct analogue of RX gives such a policy. Each type \(t\) has a remaining per-capita budget \(b_t\), initially \(\ell\). A project \(a\) is evaluated by the smallest \(\rho\) satisfying \(\sum_{t:a\in t}\mu_t\min(b_t,\rho)=c_{\max}(a)\); the project with smallest such value is started. When its exact cost is revealed, the corresponding equation is solved with \(c(a)\), and each approving type’s budget is reduced by \(\rho\), capped at zero.
This is not an arbitrary new rule. It is the exact high-multiplicity limit of the paper’s per-voter Rule X: the infinitesimal voters’ budgets are represented by per-capita type budgets, and sums over voters become mass-weighted sums over types. Theorem 15’s accounting proof also transfers from voter counts to mass. I expect the per-state computation to be Class-A-like: it is a monotone piecewise-linear calculation over the \(\tau\) types. A separate question is whether the entire contingent policy tree has a compact representation; I would not claim a global \(\mathrm{P}\) theorem without fixing that encoding.
The complementary mirror is Continuous Punctual EJR Feasibility, anchored on Theorem 16, also proved here. Given the same input, ask whether there exists a policy satisfying \(\alpha\)-risk-assessment, punctuality, and continuous ex-post EJR simultaneously.
The theorem’s two-project counterexample remains valid with a continuum population. Let \(A=\{a_1,a_2\}\), \(\ell=3\), \(\delta(a_1)=\delta(a_2)=\tau\), \(c_{\min}(a_i)=1\), \(c_{\max}(a_i)=2\), and let every unit of population have approval type \(\{a_1,a_2\}\). Choose the cost distribution so that \(P(c(a_1)+c(a_2)\le3)<1-\alpha\). Starting both projects violates risk-assessment. Starting neither violates EJR. Starting one can be forced to reveal cost \(1\), after which the full two-project set is affordable under the ex-post test but the selected bundle gives the population only one approved project. Hence no such policy exists. This is a structural infeasibility result, not Class-C hardness, and it shows that replacing voter counts by mass does not make proportionality vacuous.
The mirror covers the paper’s online satisfaction and proportionality results, especially Theorems 7, 15, and 16. It does not claim to continuize every experimental aspect of BEE or BEP, nor does it manufacture a complexity theorem absent from the paper.
The weakest point is that the lead lower bound already holds for a single voter type. Population continuity is therefore not doing the main mathematical work in Theorem 7; the uncertainty and indivisibility of projects are. The defence is that this is still a legitimate high-multiplicity regime, and the Rule-X/EJR mirror makes nontrivial use of population masses. But to become a stronger ChoCo contribution, the next step would need to study compact policy synthesis, approximation, or welfare/proportionality optimization as a function of \((T,\mu)\), and then establish an actual \(\mathrm{P}\), hardness-transfer, or continuum-specific complexity result.
The decisive objection is upstream: this paper contains no numbered complexity result of the kind ChoCo is meant to continuize. Theorems 7, 15, and 16 concern competitive ratios, axiomatic guarantees, and incompatibility of desiderata. They do not classify a computational problem, give an exact or approximation algorithm, or establish parameterized hardness. Any computational mirror therefore has to be invented alongside the continuous model; it is not a continuization of a computational result in the paper.
Theorem 7 is the weakest anchor. In the paper’s model, voters never act separately, have no individual costs or information, and affect the outcome only through additive approval satisfaction. For any approval-type distribution \(\mu\), define
\[ w_a=\sum_{t:a\in t}\mu_t. \]
Then for every bundle \(B\),
\[ u_\mu(B)=\sum_{a\in B}w_a. \]
Thus the entire voter distribution can be replaced exactly by \(m\) weighted project values. Cost revelation, durations, risk assessment, and the online policy depend only on projects and cost histories. This is not the objection that “continuity does not help”; it is more basic: for this objective, the population distribution is not part of the computational object after aggregation. No choice of a richer approval-type space changes that sufficient-statistic reduction. Making costs or eligibility type-dependent would make types computationally relevant, but would be a different budgeting problem rather than a mirror of Theorem 7.
The proponent’s \(\Omega(m)\) construction makes this especially clear: it uses one approval type with mass \(1\). The lower bound is entirely a project-level online-knapsack phenomenon. That is a legitimate high-multiplicity instance, but it does not provide a continuous-population question. Moreover, “find the smallest competitive ratio over policies” is not a problem defined in the paper. The paper does not specify an input encoding for joint cost distributions or for contingent policy trees. Supplying those choices could produce an interesting new online-policy-synthesis problem, but that would be a new contribution, not a computational mirror anchored by Theorem 7.
Theorem 15 is the strongest possible positive case, but it is precisely an axiomatic continuization, which the ChoCo scope excludes. The type-level Rule X construction is mathematically coherent: voter sums become \(\mu\)-weighted sums and individual budgets become per-capita type budgets. I would not object that this is an invalid high-multiplicity regime.
The problem is what it contributes. Theorem 15 is an accounting proof of ex-post EJR, not a complexity theorem. The continuous version merely compresses identical voters from \(n\) individual accounts to \(\tau\) type accounts. Its piecewise-linear affordability calculation is an implementation detail, not a classification of a continuous computational problem. One could ask for minimum-cost EJR bundles, EJR verification, or compact online-policy synthesis, but none of those questions is present in the paper or implied by its theorem. They would be new weighted participatory-budgeting problems, with their value coming from newly added optimization questions rather than from continuizing this result.
Theorem 16 does no better. The proposed continuum counterexample is valid, but it is an impossibility theorem about simultaneous axioms, not a computational result. In fact, its witness has one approval type and two projects, so the population measure contributes no structure at all. Recasting it as “does a policy satisfying these conditions exist?” is again a newly introduced policy-feasibility problem. With finite cost support, that becomes a finite contingent-planning problem with weighted fairness constraints; with another encoding, its complexity may change. The paper gives no reason to privilege one such formulation, and the continuous population is not what generates the difficulty.
The honest concession is that national participatory budgeting is a sensible high-multiplicity setting, and the mass version of Rule X is a reasonable mathematical object. But that is not enough for this programme. Theorem 7 reduces to weighted project selection, Theorem 15 is an out-of-scope axiomatic reformulation, and Theorem 16 is an out-of-scope impossibility witness. A worthwhile ChoCo project could be built by adding a new question about compact policy synthesis or weighted proportionality. It would, however, be a new computational social-choice paper, not a continuous mirror of a computational result in this one.
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.