REVIEW
Algorithms for Candidate Control in Greedy Participatory Budgeting Rules
Computer Science and Game Theory · Submitted 28 Jul 2026 · 48 references
Pith's verdict: First parameterized map of candidate control for GreedyAV/GreedyCost, but the q-hardness box in Figure 1 is not proven by the sketched reduction and too many central theorems are only starred sketches.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
The paper classifies the parameterized complexity of candidate control under the GreedyAV and GreedyCost participatory budgeting rules and proves a near-tight inapproximability bound for the optimization versions.
The reading
What carries the argument
The load-bearing machinery is a decomposition of greedy rule executions into cost-and-score sub-blocks. Under the cheaper-first tie-breaking convention, GreedyAV processes projects in blocks of equal score and, within each block, in sub-blocks of equal cost; there are at most $(n+1)c$ non-empty sub-blocks. The paper's structural lemma (Lemma 1) says that in a minimum deletion set every sub-block is either left with enough budget to fund all its remaining projects or is left unaffordable, so the algorithm guesses one of $2^{(n+1)c}$ behaviors and encodes the remaining choice as an integer linear program with $O(nc)$ variables and constraints, solved using Lenstra's fixed-dimension ILP theorem. A second mechanism, for the $c+r$ and $q+c$ parameters, is a dynamic program over states $(p_\ell, \mathbf{r}, \beta)$ recording the first unaffordable project of each cost, the deletion-count vector, and the remaining budget; because the first unaffordable cost strictly decreases along every transition, the state tree has depth at most $c+1$ and total size $r^{O(c^2)}$. For the hardness and inapproximability directions, the paper encodes graph problems (Perfect Code, in which each vertex's closed neighborhood contains exactly one chosen vertex, and Restricted Exact Cover by 3-Sets, an exact cover problem with each element in exactly three sets) into project costs, so that a successful control action corresponds exactly to a perfect code or exact cover.
Extended reading notes
Core claim
The paper's central claim is the parameterized classification depicted in its Figure 1. For GreedyAV and GreedyCost, destructive control by deleting projects is W[1]-hard when parameterized by the number $r$ of deleted projects or by the number $q$ of unaffected projects, even if there are only $n=2$ voters, and constructive control by deleting projects is W[1]-hard for $r$ even with $n=3$ voters. In contrast, both constructive and destructive deletion control are fixed-parameter tractable for the combined parameter $c+n$, where $c$ is the number of distinct project costs and $n$ the number of voters, provided ties are broken so that projects of equal score and equal cost are processed consecutively (e.g., cheaper-first); the same problems are FPT for $c+r$ and for $q+c$ without that tie-breaking condition, and XP when parameterized by $c$ alone. For the optimization versions of deletion control, no polynomial-time algorithm can achieve an approximation factor of $m^{1-\epsilon}$ for any $\epsilon>0$ unless P=NP, and an $m/c$-approximation always exists, making the bound essentially tight. The broader claim, covering addition of projects as well, is that the trivial XP and FPT observations for the number of projects $m$, the number of controlled projects $r$, and the number of unaffected projects $q$ cannot be improved in general, but combined cost-structure parameters unlock exact algorithms.
Load-bearing premise
The FPT result for the combined parameter $c+n$ applies only when ties are broken so that projects with equal score and equal cost are processed consecutively (for example, cheaper-first); under arbitrary tie-breaking the paper establishes no such fixed-parameter algorithm for that parameter, and the structural lemma behind the ILP is only sketched.
Editorial extensions
If this is right
- With few voters and few distinct costs, both constructive and destructive project-deletion control are solvable in $2^{O(nc\log(nc))}\cdot m^{O(1)}$ time under the consecutive tie-breaking convention, so these control problems become practical exactly when $n$ and $c$ are small.
- With few distinct costs and a small number of controlled projects, the dynamic program gives $r^{O(c^2)}\cdot m^{O(1)}$ time without any tie-breaking restriction, covering arbitrary deterministic tie-breakers.
- The W[1]-hardness for $r$ and $q$ means no general $f(r)\cdot m^{O(1)}$ or $f(q)\cdot m^{O(1)}$ algorithm exists unless FPT=W[1], so parameterized algorithms must use combined parameters or the cost structure.
- The $m^{1-\epsilon}$ inapproximability for the optimization versions rules out approximation as a practical alternative, leaving exact parameterized algorithms as the recommended route for project-strength measures.
- The XP result for $c$ gives polynomial-time algorithms with exponent depending on $c$ even when the number of voters and projects is unbounded, as long as the number of distinct costs is fixed.
Reading between the lines
- A direct implication not drawn by the paper: when the deployed tie-breaking rule is not cheaper-first, the $c+r$ dynamic program is the safe FPT choice among the paper's algorithms, because it alone does not depend on the consecutive sub-block assumption.
- Although the paper motivates its parameters with real-world participatory budgeting data, it contains no experiments; a natural next step is to benchmark the ILP and DP algorithms on such data and compare which parameter combination is actually smallest in practice.
- The hardness reductions use only two or three voters, which suggests that voter-count parameters are not a promising route to tractability; the informative structure is the cost profile of the projects.
- The ILP sub-block idea may transfer to other sequential budgeting rules whose orderings split into few groups of equal score and cost, giving FPT results for the same combined parameters, but that extension is not claimed in the paper.
Original abstract
We study the problem of candidate control in participatory budgeting elections. Our focus is on two prominent sequential welfare-based rules---GreedyAV and GreedyCost---which are widely used in practice. Candidate control asks whether we can strategically modify the set of available candidates so as to either ensure that a preferred candidate $p$ is selected or prevent $p$ from being selected. Since all variants of candidate control under the two rules we consider are known to be NP-hard, we analyze the problems through the lens of parameterized complexity and approximability. Under the first lens, we provide a comprehensive classification with respect to natural parameters such as the number of voters, the number of controlled candidates, and the number of distinct costs, as well as their combinations. Within the second perspective, we establish a tight approximability bound.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
We study the problem of candidate control in participatory budgeting elections. Our focus is on two prominent sequential welfare-based rules---GreedyAV and GreedyCost---which are widely used in practice. Candidate control asks whether we can strategically modify the set of available candidates so as to either ensure that a preferred candidate $p$ is selected or prevent $p$ from being selected. Since all variants of candidate control under the two rules we consider are known to be NP-hard, we analyze the problems through the lens of parameterized complexity and approximability. Under the first lens, we provide a comprehensive classification with respect to natural parameters such as the number of voters, the number of controlled candidates, and the number of distinct costs, as well as their combinations. Within the second perspective, we establish a tight approximability bound.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study the problem of candidate control in participatory budgeting elections. | background 0.56 | 0.78 | 0.03 | asserted 0.85 |
| s1 | Our focus is on two prominent sequential welfare-based rules---GreedyAV and GreedyCost---which are widely used in practice. | background 0.75 | 0.30 | 0.03 | asserted 1.00 |
| s2 | Candidate control asks whether we can strategically modify the set of available candidates so as to either ensure that a preferred candidate $p$ is selected or prevent $p$ from being selected. | background 1.00 | 0.05 | 0.04 | asserted 0.98 |
| s3 | Since all variants of candidate control under the two rules we consider are known to be NP-hard, we analyze the problems through the lens of parameterized complexity and approximability. | method 0.55 | 0.27 | 0.08 | asserted 1.00 |
| s4 | Under the first lens, we provide a comprehensive classification with respect to natural parameters such as the number of voters, the number of controlled candidates, and the number of distinct costs, as well as their combinations. | contribution 0.85 | 0.95 | 0.15 | asserted 1.00 |
| s5 | Within the second perspective, we establish a tight approximability bound. | result 0.81 | 0.94 | 0.20 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2607.25723 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.