| paper | Participatory Budgeting Project Strength via Candidate Control |
| authors | Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, Krzysztof Sornat |
| venue | IJCAI 2025 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given a finite project set \(P\), integer costs \(c(q)\), budget \(B\), target \(p\), deletion bound \(r\), fixed tie-breaking order, and rational masses \(\mu_A\) over approval types \(A\subseteq P\), does there exist \(D\subseteq P\setminus\{p\}\) with \(|D|\le r\) such that aggregated PHRAGMÉN on the types \(A\cap(P\setminus D)\), with funding events satisfying \(\sum_{A:q\in A}\mu_A b_A=c(q)\), funds \(p\)?
A high-multiplicity participatory-budgeting election with indivisible projects, integer costs, and discrete budget; voter types are complete approval sets \(A\subseteq P\) with rational masses \(\mu_A\), while PHRAGMÉN maintains one balance \(b_A\) per unit mass and uses aggregate support balance \(\sum_{A:q\in A}\mu_A b_A\). The control action deletes at most \(r\) projects.
The mirror covers the constructive and destructive PHRAGMÉN candidate-deletion results of Theorem 3, including the unit-cost restriction, but leaves the GREEDYAV, GREEDYCOST, and EQUAL-SHARES results and the experimental measures aside.
My lead mirror is a direct high-multiplicity version of constructive PHRAGMÉN candidate control by deletion.
A voter type is a complete approval set \(A\subseteq P\), where \(P\) is the finite project set. The society is a rational distribution \(\mu=(\mu_A)\) over the listed approval types, with \(\mu_A\) the fraction of residents approving exactly \(A\). Projects remain indivisible, retain their original costs, and the budget remains discrete. The control action is also unchanged: choose a set \(D\subseteq P\setminus\{p\}\) of at most \(r\) projects to delete. The objective is to make the initially unfunded target project \(p\) funded under PHRAGMÉN.
Call this problem \(\mathrm{PHRAGM\acute{E}N}\text{-}\mathrm{CCDC}_\infty\). An instance consists of \(P\), project costs \(c(q)\), budget \(B\), a fixed tie-breaking order, target \(p\), deletion bound \(r\), and rational masses \(\mu_A\). For a deletion set \(D\), run PHRAGMÉN on \(P\setminus D\), replacing each approval set \(A\) by \(A\cap(P\setminus D)\). The target succeeds exactly when \(p\) belongs to the resulting funded set.
The population-level PHRAGMÉN dynamics are exact aggregation, not a new fractional funding rule. Let \(b_A\) be the account balance per unit of normalized mass of type \(A\). Initially \(b_A=0\). Between funding events, every \(b_A\) increases at rate \(1\). A project \(q\) becomes fundable when
\[ \sum_{A:q\in A}\mu_A b_A=c(q). \]
The first project to reach this threshold is funded, all balances \(b_A\) for its supporting types are reset to zero, and projects that no longer fit within \(B\) are removed. Ties use the fixed order. Thus only the voter population has been continuized; the project set, funding decisions, costs, and budget remain discrete. The continuous time here is merely the internal time variable already present in the paper’s definition of PHRAGMÉN.
This mirrors a plausible participatory-budgeting regime: a city may have \(10^5\) or more residents voting on a standardized slate of perhaps tens or hundreds of projects, with many residents sharing approval patterns because they belong to recurring neighbourhood, association, or demographic cohorts. In such a regime \(n\gg\tau\), where \(\tau\) is the number of distinct approval types. Deleting a project represents exactly the paper’s external circumstance—another proposal misses a deadline, is ruled ineligible, or is withdrawn—not a new voter intervention.
The anchor is Theorem 3, proved in this paper: both PHRAGMÉN-CCDC and PHRAGMÉN-DCDC are NP-complete even when every project has unit cost. I am anchoring on its constructive half, \(\mathrm{PHRAGM\acute{E}N}\text{-}\mathrm{CCDC}_\infty\). The expected classification is Class B: hardness transfers.
The transfer is exact. Given a finite election with \(n_A\) voters of each approval type \(A\), set \(\mu_A=n_A/n\). If \(z_A(t)\) is the common per-voter balance of type \(A\), define \(b_A(s)=n z_A(s/n)\). Then, between events,
\[ \frac{d b_A}{d s}=1 \]
and
\[ \sum_A\mu_A b_A(s) = \sum_A n_A z_A(s/n). \]
Therefore every project reaches its funding threshold at exactly the same relative event as in the finite election; resets, budget exhaustion, tie-breaking, and the final funded set also coincide. Clearing denominators in a rational mass distribution therefore recovers a finite duplicated electorate. Conversely, every finite PHRAGMÉN instance is represented by such a distribution. Since Theorem 3 already uses unit-cost projects, the hardness does not rely on binary-encoded project prices.
This is a direct mirror of the paper’s result, not a new coalition-control or fractional-budget problem. It covers Theorem 3 and, by the same formulation, its destructive counterpart, but not the paper’s GREEDYAV, GREEDYCOST, or EQUAL-SHARES results.
The mirror naturally raises parameterized questions: is the problem fixed-parameter tractable in \(\tau\), \(r\), or the number of approval types supporting the target? Is minimum-cost project deletion approximable when deletion weights are introduced? How hard is it to count successful deletion sets or estimate the probability that \(p\) wins after random project deletions under the continuous population model?
The weakest point is that this is principally a faithful Class-B recoding: the hardness lives in project interactions and candidate deletion, not in population multiplicity. Thus continuization may compress a large electorate without making the problem easier. Also, the paper’s experiments establish large voter populations but do not report the number of distinct approval types, so the \(n\gg\tau\) regime is a plausible scenario rather than an empirical conclusion of the paper. Still, the rule’s balance dynamics make type aggregation exact, and the resulting problem is recognizably the authors’ candidate-control question with the society itself represented continuously.
I cannot honestly defeat this anchor. The negative case is weak, and every stronger objection runs into one of the programme’s explicit exclusions.
Theorem 3 is a named computational result: constructive PHRAGMÉN candidate control by deletion is NP-complete even with unit-cost projects. Its population axis is also natural. Participatory budgeting routinely has many residents voting on a relatively small project slate, and repeated approval sets among neighbourhood, association, or demographic cohorts are entirely plausible. There is no identity-sensitive objective: PHRAGMÉN uses voters only through approval-set membership and account balances.
The proposed aggregation is exact. For a type \(A\) with mass \(\mu_A=n_A/n\), the project-affordability quantity is
\[ \sum_A \mu_A b_A. \]
After rescaling time and balances, this is precisely the finite electorate’s aggregate balance. Project deletion merely maps \(A\) to \(A\cap(P\setminus D)\), merging types when necessary. Resets, affordability events, tie-breaking, and the funded set are preserved. Unit costs also eliminate any objection based on numerical scaling.
The stronger variants do not rescue the negative case. Weighted deletion, project addition, minimum-cost control, random deletion, and counting successful controls all retain the same aggregated population representation. One can use the full type space \(2^P\), or a smaller empirically supported space of recurring approval patterns; neither loses information relevant to PHRAGMÉN.
The best sceptical objection is that this mirror is an exact high-multiplicity recoding and may yield Class B rather than a new tractable continuum-specific phenomenon. But that is expressly not a valid objection here: “continuization does not help” is itself a legitimate result, and existing high-multiplicity structure supports rather than undermines the model.
Thus the proponent’s PHRAGMÉN anchor survives. A universal negative case would require claiming either that large repeated voter populations are implausible in participatory budgeting or that exact aggregation is not worthwhile; neither claim is defensible under the programme’s stated standards.
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.