REVIEW 3 major objections 4 minor 7 references
Project Submission Games in Participatory Budgeting
T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read Proposers in participatory budgeting games often have no stable strategy, and detecting one is computationally hard.
desk verdict New and worthwhile model with a plausible complexity landscape, but the proof of the main positive result (Thm 5.1) is under-supported and the experiments lack reproducibility details. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the project submission game (PSG): each proposer owns a set of projects, chooses a nonempty subset to submit, and earns the total cost of their submitted projects selected by a fixed resolute participatory budgeting rule. The proof architecture uses normal-form gadgets with best-response cycles to show non-existence, subset-sum and 3-SAT reductions to show hardness, and — for the positive single-project result — a sequential-rule property claiming that removing an unfunded project leaves earlier rounds unchanged. In the unit-cost multiwinner setting, full submission is dominant for BasicAV because the committee size is fixed.
What would settle it
The sequential property asserted in the proof of Theorem 5.1 is directly testable: if $W$ is the set of projects selected in the first $i$ rounds and $c \notin W$, deleting $c$ and rerunning the rule must leave the first $i$ rounds unchanged. A single BasicAV, Phragmén, or MES election where this fails gives a concrete counterexample to the load-bearing step, and the profile built by the algorithm would not be guaranteed to be a Nash equilibrium.
Extended reading notes
Core claim
For each of BasicAV, Phragmén, and MES, the paper constructs project submission games with no pure Nash equilibrium (for BasicAV and MES even with a single voter, and for Phragmén with party-list voters), and shows NE EXISTENCE is simultaneously NP-hard and coNP-hard, with best-response computation NP-hard in the general model. The positive side is structural: in the unit-cost multiwinner model, BasicAV always has an NE computable in polynomial time because submitting all projects is a dominant strategy; Phragmén and MES regain polynomial-time equilibria when preferences are party-list; and if each proposer is limited to one project, every multiwinner PSG/1 has a polynomial-time NE for all t
Load-bearing premise
The positive single-project result depends on an unproved sequential-rule property: for BasicAV, Phragmén, and MES, deleting a project that was not funded cannot change which projects are funded in earlier rounds; if that property fails, the polynomial-time equilibrium construction breaks.
Editorial extensions
If this is right
- In general participatory budgeting, proposers can face a matching-pennies-style cycle with no pure Nash equilibrium, so unrestricted project submission invites strategic instability.
- Checking whether an equilibrium exists is NP-hard and coNP-hard, so no efficient universal verification procedure exists under arbitrary project costs.
- Under unit costs, BasicAV is settled: submitting all projects is a dominant strategy and an equilibrium is easy to find.
- For Phragmén and MES in the multiwinner setting, party-list preferences guarantee an equilibrium via full submission, but general multiwinner profiles remain intractable.
- When each proposer can submit exactly one project, all three rules have polynomial-time Nash equilibria in the multiwinner setting, and best responses are polynomial-time computable, enabling practical stability checks.
Reading between the lines
- Extension: because proposers can deliberately withdraw attractive projects to steer the outcome, equilibrium outcomes may systematically underfund popular projects; a simulation comparing funded-cost totals against full-submission outcomes would test this directly.
- Extension: the paper's hardness results presume complete information; with poll-based uncertainty, proposers face a Bayesian game, where equilibria may be more fragile or require different solution concepts.
- Extension: the sequential-rule condition asserted in the proof of Theorem 5.1 is stated without proof; a computational search across small BasicAV, Phragmén, and MES elections could check whether deleting an unfunded project ever changes earlier rounds.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces project submission games (PSGs) for participatory budgeting and multiwinner elections, in which each proposer owns a set of projects, chooses a nonempty subset to submit, and maximizes the total cost (or number, in the multiwinner setting) of funded projects. It analyzes pure Nash equilibrium existence and the complexity of NE existence and best responses for BasicAV, Phragmén, and MES under arbitrary costs, unit costs, party-list preferences, and the single-project-per-proposer restriction. The main theoretical findings are: (i) NE may fail to exist, even for party-list profiles and, for BasicAV and MES, even with a single voter; (ii) NE existence is both NP-hard and coNP-hard for the three rules in the general PB model, and for Phragmén and MES also in the multiwinner model; (iii) positive tractability results for BasicAV in the multiwinner setting, for Phragmén/MES with party-list multiwinner preferences, and for all three rules in multiwinner single-project games. The paper also reports an empirical study on Pabulib PB instances showing that equilibria are common and that simple best-response dynamics typically find them.
Significance. If the results hold, the paper provides a valuable complexity map of strategic project submission in approval-based PB, a topic that has received relatively little game-theoretic attention compared with strategic voting and strategic candidacy. The hardness results are natural and fit the existing literature on candidacy games; the single-project multiwinner positive result is a useful contrast and the empirical section gives evidence that the worst-case hardness is not the typical case. The paper does not supply machine-checked proofs or code, but the reductions are standard and the experimental protocol is clearly described. Overall, this is a solid conceptual contribution, provided the load-bearing proof gaps identified below are fixed.
major comments (3)
- [Section 5, Theorem 5.1] The proof rests entirely on the 'sequential-rule property' stated without proof: if W is the outcome after the first i rounds and c is a project not in W, then deleting c and rerunning leaves the first i rounds unchanged. This is not immediate for Phragmén and MES, where removing an unelected project can alter the order in which remaining projects become affordable or are dropped. The polynomial-time NE construction applies this property iteratively to remove every unelected project, and also needs it for the final outcome when choosing strategies for proposers who would otherwise be unelected. Please supply a proof for each of BasicAV, Phragmén, and MES, or a counterexample. The statement that the first selected project is a 'dominant strategy' is stronger than what is proved and should be replaced by the precise property needed.
- [Section 4, Theorem 4.2] The subset-sum reduction appears arithmetically inconsistent as printed. P0 has projects ci with costs summing to the chosen subset (total T) and a project c* of cost 15T-14, with budget B=15T. If P0 submits the subset summing to T together with c*, the total cost is 16T-14, which exceeds B for T>14. If P0 submits only the subset, the utility is T, not the claimed 15T. Thus the claim that a subset-sum solution gives P0 utility 15T is not feasible under the stated constants. Please correct the construction (e.g., adjust the cost of c* and the budget consistently) and re-verify both the NP-hardness proof and the coNP-hardness variant in Appendix A, which inherits the same constants.
- [Section 4, Theorem 4.4] The party-list multiwinner existence proof for Phragmén and MES relies on the assertion that after a proposer withdraws one selected project, 'the only change in the outcome is the removal of c and either adding some other project...' This structural claim is not proved. For sequential rules, deleting a project can change the entire course of later rounds, so this is not a routine observation. A rigorous proof is needed; if the claim fails, the existence guarantee for Party-list PSGs collapses. The 'one-by-one' argument does not by itself establish the claimed replacement property.
minor comments (4)
- [Throughout] Several typos and grammatical slips: 'existance', 'stategy', 'thet', 'commments', 'there there would be an NE'. A careful proofreading pass is advised.
- [Section 6] The text says 'For BasicAV, we present our results in Table 4', but the BasicAV results appear in Table 2; Tables 3 and 4 are in Appendix D. Please correct the cross-reference.
- [Appendix A, Theorem 4.3 proof] The Phragmén gadget analysis is still somewhat compressed: the normal-form table in Figure 3 gives utilities, but the derivation of these values from the voter groups in Figure 2 is not fully spelled out. Providing the voter counts and the tie-breaking details explicitly would improve reproducibility.
- [Section 5, Theorem 5.1] The phrase 'dominant strategy' is used for the proposer whose project is selected in the first round, but the proof only shows a conditional optimality given the iterative construction. The argument would be clearer if the terms 'dominant' vs. 'best response in the subgame' were separated.
Circularity Check
No circularity: hardness reductions are independent, and the only flagged issue is an unproved but non-circular sequential-rule observation in Theorem 5.1.
full rationale
I walked the derivation chain and found no exhibited circular reduction. The hardness results (Theorems 4.2, 4.3, 4.5, Appendix A) reduce from Subset Sum, 3-SAT, and X3C; the correctness arguments tie the existence/non-existence of NE to the external instance, not to the theorem being proved. The BasicAV multiwinner claim follows directly from the rule's definition (selecting top-B projects), so it is a consequence of the definition, not a self-definitional loop. Theorem 4.4's party-list NE result is a direct deviation/withdrawal argument for the all-submit profile; no fitted quantity is renamed as a prediction. The one load-bearing gap I want to flag explicitly is in Theorem 5.1: the proof states, 'Note that all our rules are sequential and satisfy the following condition: If W is the outcome computed in the first i rounds and c is a project not in W, then if we removed c from the election and rerun the rule, the first i rounds would select the same projects as with c present.' This property is asserted without proof and is essential for the polynomial-time PSG/1 equilibrium construction for Phragmén and MES. However, this is a missing justification / correctness risk, not a circularity: the property is not the theorem's conclusion, and the construction is not defining the equilibrium as the property itself. The same proof also calls the first selected project a 'dominant strategy', which is stronger than needed, but that overstatement does not make the derivation circular. The paper's self-citations (e.g., Pabulib data, the cost-utility MES variant, related strategic-cost work) are used for data attribution, variant definition, and related-work context, not as the sole support for a theorem. There is no imported uniqueness theorem and no ansatz smuggled in via citation. The manuscript also openly notes limitations (e.g., MES non-exhaustiveness 'we disregard this issue for simplicity'; open questions about party-list MES-PSGs), which are not circularity. Overall, the central claims have independent content and the reductions stand on their own; score 0.
Assumptions & free parameters
assumptions (7)
- domain assumption Tie-breaking order over projects is fixed and known.
- domain assumption Proposers have full knowledge of voter approvals.
- domain assumption Voter approvals are independent of other projects.
- domain assumption The rules BasicAV, Phragmen, and MES are defined as sequential rules given in Section 2.
- ad hoc to paper The sequential-rule property asserted in Theorem 5.1: removing a non-selected project after i rounds leaves the first i rounds unchanged.
- standard math Standard complexity-theoretic framework (P, NP, coNP) and reductions.
- domain assumption Pabulib dataset is representative of real PB elections.
Cite this review
Pith. "Pith review of Project Submission Games in Participatory Budgeting." pith.science (2026). https://pith.science/paper/UA3F57U2
@misc{pith2026250809741,
author = {Pith},
title = {Pith review of: Project Submission Games in Participatory Budgeting},
year = {2026},
howpublished = {\url{https://pith.science/paper/UA3F57U2}},
note = {Machine review of arXiv:2508.09741}
}
read the original abstract
We introduce the framework of project submission games, capturing the behavior of project proposers in participatory budgeting (and multiwinner elections). Here, each proposer submits a subset of project proposals, aiming at maximizing the total cost of those that get funded. We focus on finding conditions under which pure Nash equilibria (NE) exist in our games, and on the complexity of checking whether they exist. We also seek algorithms for computing best responses for the proposers
Reference graph
Works this paper leans on
-
[1]
Every BasicAV-PSG has an NE computable in polynomial time
-
[2]
Phragm ´en-NE E XISTENCE and MES-NE E XISTENCE are both NP-hard and coNP-hard . Proof. In the main text, we presented the NE existence proof for BasicA V and the reduction from 3-SAT to show that Phragm´en-NE E XISTENCE is coNP-hard. Here we will first describe the gadget used in the reduction in more detail, in particular, showing that there is indeed no...
-
[3]
NP-hard for MES and Phragm´en in the multiwinner model,
-
[4]
NP-hard for BasicAV , Phragm´en, and MES, in the general PB model, even with party-list prefer- ences,
-
[5]
Polynomial-time solvable for BasicAV in the multiwinner model,
-
[7]
All” we give the numbers of considered instances. In the columns “Full-NE
Polynomial-time solvable for MES and Phragm ´en in the multiwinner model with party-list prefer- ences. Proof. Points 2 and 4 follow directly from our NE constructions in Theorem 4.3 and Theorem 4.4 (in which players have dominant strategies). Point 1 follows from an analogous construction as in Theo- rem 4.2 where we ask for a best response for player P0...
work page 2021
-
[2013]
Proceedings 6. Springer, 13–25. G. Lisowski. 2022. Strategic Nominee Selection in Tournament Solutions. In European Conference on Multi-Agent Systems. Springer, 239–256. 13 G. Lisowski, M. Ramanujan, and P. Turrini. 2022. Equilibrium computation for knockout tournaments played by groups. In Proceedings of the International Conference on Autonomous Agents ...
arXiv 2022
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.