| paper | Participatory Budgeting with Donations and Diversity Constraints |
| authors | Jiehua Chen, Martin Lackner, Jan Maly |
| venue | AAAI 2022 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 10
statement extracted from the paper’s text layer
Given indivisible projects \(C\), costs \(c_j\), budget \(B\), and a finite voter-type set \(\Theta\) with rational masses \(\mu_\theta\) summing to \(1\), where each type has an approval vector \(a_\theta\in\{0,1\}^{m}\), a feasible bundle \(A\subseteq C\) satisfies \(\sum_{j\in A}c_j\le B\). Decide whether \(A\) is co-winning under \(R_{\Sigma}^{\max}\), i.e. whether \(W_\mu(A)\ge W_\mu(A')\) for every feasible bundle \(A'\), where \(W_\mu(A)=\sum_{\theta\in\Theta}\mu_\theta\max_{j\in A}a_\theta(j)\) and \(W_\mu(\varnothing)=0\).
Indivisible-project participatory budgeting with a finite distribution of complete approval types: the input gives type masses \(\mu_\theta\), project costs, and a public budget; the decision variable is a feasible discrete bundle \(A\), and the objective is the population-weighted \(R_{\Sigma}^{\max}\) score.
The mirror directly covers Theorem 10's winner-determination hardness and plausibly extends Theorem 13's donation hardness to coordinated positive-mass cohorts; it leaves the paper's axiomatic results and unanchored complexity refinements outside the mirror.
Yes. The strongest honest mirror is a high-multiplicity PB model in which projects remain indivisible and only the population of voters is continuized.
My lead anchor is Theorem 10, proved in the paper: for each \(R\in\{R_{\min}^{\max},R_{\min}^{+},R_{\Sigma}^{\max}\}\), and for the sequential and Pareto variants, \(R\)-WINNER is coNP-hard even with unit-cost projects, no diversity constraints, no donations, and dichotomous preferences.
The corresponding continuous problem is:
\(\mathrm{HM}\text{-}R_{\Sigma}^{\max}\text{-WINNER}\). An instance consists of \(m\) indivisible projects \(C\), a budget \(B\), and a finite set of voter types \(\Theta\). Type \(\theta\) has mass \(\mu_\theta\in\mathbb{Q}_{\ge 0}\), with \(\sum_{\theta}\mu_\theta=1\), and an approval vector \(a_\theta\in\{0,1\}^{m}\). A bundle \(A\subseteq C\) is feasible when \(\sum_{j\in A}c_j\le B\). Its continuous \(R_{\Sigma}^{\max}\)-score is
\[ W_\mu(A)=\sum_{\theta\in\Theta}\mu_\theta\max_{j\in A}a_\theta(j), \]
with the value \(0\) for the empty bundle. Given a feasible bundle \(A\), decide whether \(A\) is co-winning, that is, whether
\[ W_\mu(A)\ge W_\mu(A') \]
for every feasible bundle \(A'\). A “yes” instance is therefore a bundle that maximizes the weighted population score; a “no” instance has a competing feasible bundle with strictly larger score.
This is not an outcome-space relaxation. The projects, budget, and bundle remain discrete exactly as in the paper. The only change is that the named voters are replaced by masses of indistinguishable voters.
A convincing regime is a large citywide PB process. Millions of residents may fall into a few dozen or few hundred survey-defined types: each type has the same approval vector over the proposed projects, and—if donations are included—the same donation possibilities. The type is therefore a complete description for the rule, not merely a preference class. The intended regime has \(n\gg\tau\): millions of residents but comparatively few distinct preference profiles.
The bridge is exact for rational masses. If \(n_\theta\) voters have type \(\theta\), set \(\mu_\theta=n_\theta/n\). Conversely, multiplying by a common denominator expands a rational continuous profile into a discrete electorate. Cloning every voter profile many times produces arbitrarily high multiplicity without changing the winner. Thus the continuous question is genuinely the high-multiplicity version of the paper’s winner problem.
I expect this mirror to be Class B: hardness transfers. Theorem 10’s combinatorics live in the choice of an indivisible project bundle, not in the number of separately named voters. Continuizing the electorate does not remove that combinatorial search. The result is therefore a useful boundary case for ChoCo: population continuity is compatible with the model, but it does not guarantee tractability.
A second, more ambitious mirror reaches the paper’s donation problem. Theorem 13, also proved in the paper, shows that \(R\)-DONATION is \(\Sigma_2^P\)-hard for every global rule \(R\in\mathcal R\setminus\{R_{\min}^{\max}\}\), even with unit-cost projects, zero public budget, diversity constraints, and dichotomous preferences. Together with Theorem 12, this gives the advertised \(\Sigma_2^P\) picture for the global rules.
The continuous version should be a type-cohort donation problem, not an infinitesimal individual deviation:
\(\mathrm{Cohort}\text{-}R_{\Sigma}^{+}\text{-DONATION}_{\infty}\). The instance contains projects \(C\), costs \(c_j\), a public budget \(B\), project-type vectors \(q_j\), diversity bounds \(\ell,u\), voter types \(\Theta\) with masses \(\mu_\theta\), satisfaction values \(s_\theta(j)\), and baseline per-capita donation vectors \(b_\theta\). One type \(\theta^\star\), of positive mass, is designated as the strategic donor cohort. It may choose a per-capita donation vector \(x\) satisfying
\[ x_j\ge 0 \qquad\text{and}\qquad \sum_{j\in C}x_j\le\delta . \]
The resulting aggregate donation to project \(j\) is
\[ D_j(x)= \sum_{\theta\ne\theta^\star}\mu_\theta b_\theta(j) +\mu_{\theta^\star}x_j. \]
A bundle is feasible when
\[ \sum_{j\in A}\max\{0,c_j-D_j(x)\}\le B \]
and
\[ \ell[z]\le\sum_{j\in A}q_j[z]\le u[z] \]
for every project type \(z\). The global rule \(R_{\Sigma}^{+}\) maximizes
\[ W_\mu(A)= \sum_{\theta\in\Theta}\mu_\theta \sum_{j\in A}s_\theta(j). \]
The question is whether there exists an admissible \(x\) such that the winning bundle after the donation gives the strategic type strictly higher utility than the baseline bundle:
\[ \sum_{j\in R_{\Sigma}^{+}(I[x])}s_{\theta^\star}(j) > \sum_{j\in R_{\Sigma}^{+}(I[b_{\theta^\star}])}s_{\theta^\star}(j). \]
This is plausible for a large neighbourhood association, union, school district, or other organized cohort whose members share a preference and donation policy and coordinate a common per-capita pledge. The project side is unchanged: projects are indivisible, diversity quotas remain discrete, and the rule still globally optimizes a PB objective.
I would expect this version also to be Class B rather than continuum-specifically hard. Theorem 13’s reductions use the combinatorics of projects, clauses, and diversity constraints. Rational type masses can reproduce the corresponding voter multiplicities, while the existential donation choice and the global winner test remain. Natural follow-up questions are whether the \(\Sigma_2^P\)-hardness survives when every voter type has large multiplicity, and whether donation vectors admit a finite threshold compression because only finitely many project-cost boundaries matter.
The weakness is clear: the paper asks whether one named voter can improve her outcome, whereas a positive-mass type-level action is a coordinated cohort deviation. In a literal atomless population, one individual has zero influence, so the individual R-DONATION problem has no direct continuum limit. That is why I would not make Theorem 13 the foundation of the case. Theorem 10 avoids this issue entirely: winner determination is anonymous from the start and has a clean, exact high-multiplicity interpretation.
So the positive case rests most securely on Theorem 10’s continuous winner problem, with Theorem 13 providing a plausible extension to type-level campaigning. The mirror covers the paper’s computational results, not its axiomatic results: the latter concern properties of discrete donation mechanisms and do not need to be continuized to establish this case.
The strongest negative case is that both anchors replace the paper’s finite voter list by weights without creating a genuinely new population-level computational object. That case is not strong enough here.
Theorem 10’s proposed mirror is completely legitimate. With dichotomous preferences and no donations or diversity constraints, a type is simply an approval set \(S_\theta\), and the objective is
\[ W_\mu(A)=\sum_{\theta}\mu_\theta\mathbf{1}[A\cap S_\theta\neq\varnothing]. \]
This is a weighted high-multiplicity version of the paper’s rule. Rational masses expand exactly into voter counts, and cloning every type yields \(n\gg\tau\) without changing the outcome. A citywide referendum with many residents sharing a comparatively small number of approval profiles is a plausible regime. There is no identity dependence, no vanishing effect, and no formal obstacle.
One can weaken the anchor by observing that its hardness may be carried by the project choices and by the number of distinct approval profiles, rather than by multiplicity. If \(\tau\) is fixed, the problem admits finite enumeration or dynamic programming over project signatures; if \(\tau\) is part of the input, the problem is essentially weighted maximum coverage with indivisible projects. But these are algorithmic answers, not objections to the mirror. The programme explicitly treats both tractability and transferred hardness as worthwhile outcomes. Calling this a weighted restatement therefore does not defeat it.
Theorem 13 is less secure. The literal individual-donation problem has no atomless limit: one voter has measure zero and cannot affect the winning bundle. The proponent’s cohort repair, however, removes that defect. If a type of mass \(\alpha>0\) coordinates a per-capita donation \(x\), its aggregate pledge is \(\alpha x\), and every cohort member has the same utility. For rational \(\alpha\), this can reproduce the discrete donation amounts by rescaling the per-capita budget. A neighbourhood association, union, or organized resident cohort is a plausible high-multiplicity scenario. It is a new strategic variant, but the programme expressly permits a better re-modelling when the paper’s literal individual story does not survive.
Thus I would reject Theorem 13 as the primary anchor because it requires an additional coordination institution. I cannot honestly defeat Theorem 10: it supplies a clean, anonymous, computational high-multiplicity mirror. The requested universal negative case is therefore weak; the paper should not be rejected on continuization grounds.
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.