{"id":"38492593-eb27-4175-8d01-6801d77f7a42","arxiv_id":"2508.09741","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For participatory budgeting with strategic project proposers, pure Nash equilibria are generally neither guaranteed nor efficiently decidable, but become tractable in single-project multiwinner settings.","lead":"This paper introduces project submission games, where proposers in participatory budgeting choose which projects to put forward to maximize the value of what gets funded. It finds that pure Nash equilibria often do not exist and are hard to detect, except in a few structured settings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.1 rests on an unproved sequential-rule property; the property is plausible but needs a proof or a counterexample search before the poly-time NE claim is accepted.","rationale":"The reader's weakest-assumption analysis identifies exactly the gap I consider most load-bearing: Theorem 5.1's sequential-rule property is asserted without proof, and the theorem's iterative equilibrium-construction argument cannot go through without it. The property is likely true for the three rules, so this is not a claim that the theorem is false; it is a claim that the proof is incomplete at a critical point. A concrete brute-force search over small instances would settle the factual question, and a short inductive proof would settle the rigor question. I agree with the reader's CONDITIONAL verdict: the paper's central positive result should not be accepted as fully proved until the property is verified. No change to the reader's verdict is needed, so verdict_should_be is UNCHANGED.","tokens_in":19666,"tokens_out":22129,"duration_ms":278057,"concrete_test":"Brute-force check the property for all small multiwinner elections with, say, m <= 6 projects and n <= 8 voters for BasicAV, Phragmen, and MES: for every prefix i and every project c not in the prefix's outcome, delete c, rerun the rule, and compare the first i selected projects. A single counterexample refutes the property and Theorem 5.1. If no counterexample is found, supply an inductive proof from the definitions: for Phragmen, unelected projects never reset accounts; for MES, unelected projects never collect payments; for BasicAV, approval order is unchanged. This would close the gap and validate the iterative construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing point is Theorem 5.1's unproved sequential-rule property: if W is the first-i-round outcome and c is a project not in W, then deleting c and rerunning leaves the first i rounds unchanged. The polynomial-time NE construction for PSG/1 depends entirely on this property, applied iteratively to remove every unelected project of each selected proposer and then to keep arbitrary projects for unelected proposers. Yet the paper states the property as an observation with no proof and no reference. It is not immediate for Phragmen and MES: although an unelected project never spends voter money, the order in which projects become affordable, are dropped as infeasible, or lose by tie-breaking could in principle interact with the remaining projects. If the property fails for any of the three rules, the claimed poly-time equilibrium guarantee for PSG/1 collapses. The proof also labels the first selected project a 'dominant strategy,' which is stronger than needed and is not established; what is needed is only that the constructed profile elects the chosen projects, and that unselected proposers cannot profitably deviate. Both points make the positive result under-supported as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19994,"tokens_out":14764,"duration_ms":172563,"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":[{"comment":"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":"Section 5, Theorem 5.1"},{"comment":"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":"Section 4, Theorem 4.2"},{"comment":"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.","section":"Section 4, Theorem 4.4"}],"minor_comments":[{"comment":"Several typos and grammatical slips: 'existance', 'stategy', 'thet', 'commments', 'there there would be an NE'. A careful proofreading pass is advised.","section":"Throughout"},{"comment":"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.","section":"Section 6"},{"comment":"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":"Appendix A, Theorem 4.3 proof"},{"comment":"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.","section":"Section 5, Theorem 5.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is promising and the framework is likely to be of interest to the SAGT/COMSOC community. The two main issues are the unproved sequential-rule property behind Theorem 5.1 and the arithmetic bug in the Theorem 4.2 reduction; both are fixable, but they are load-bearing. I would not recommend rejection, since the overall direction is sound and the missing pieces appear to be local repairs rather than conceptual impossibility."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper deserves a serious referee. The PSG model is a natural formalization of proposer manipulation in PB, and the hardness results are meaningful. But Theorem 5.1 is the main positive result and its proof is a sketch, and the experimental section is not reproducible as written.\n\nWhat's new: the model itself, and the breadth of the complexity map across BasicAV, Phragmen, and MES. The paper clearly separates PSGs from prior strategic candidacy and cost-selection work. The reductions are standard but cover three important rules and several preference restrictions.\n\nThe main soft spot is Theorem 5.1. The sequential-rule property (if W is the first i rounds and c not in W, removing c leaves those rounds unchanged) is stated without proof. That is not immediate for Phragmen and MES; it needs a careful argument. More importantly, even if the property holds, the proof's iterative construction fixes one project per proposer and then assigns arbitrary strategies to proposers whose projects are never selected. That does not automatically rule out profitable deviations for those proposers. The claim that the first-round project is a 'dominant strategy' is also stronger than what is argued. An unselected proposer could, in principle, deviate to a different project and get elected after other projects are removed. The proof needs to address this.\n\nOther issues: the Phragmen gadget analysis in Theorem 4.3 is left as 'routine' (probably fine, but condensed). The experiments have no code, no seed, no variance, and no description of how the random assignment of projects to proposers was controlled. For a paper making empirical claims, that is a reproducibility gap, though the qualitative finding (full profiles are usually NE) is robust enough that I don't doubt it.\n\nIf you are working in this area, citing the model is likely worth it. The paper is clearly the result of serious thinking and is not a case of fitting after the fact. Send it to peer review, but the referee should require a full proof of Theorem 5.1 and a reproducibility appendix for Section 6.","headline":"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.","tokens_in":20398,"tokens_out":10142,"would_cite":true,"duration_ms":108486,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A10","91B12","91B14","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Proposers in participatory budgeting games often have no stable strategy, and detecting one is computationally hard.","keywords":["participatory budgeting","project submission games","Nash equilibrium","approval-based multiwinner voting","Phragmén rule","Method of Equal Shares","computational complexity","strategic candidacy"],"falsifier":"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.","tokens_in":19639,"feed_emoji":"🗳️","tokens_out":7537,"duration_ms":74458,"temperature":0.7,"pith_summary":"This paper introduces project submission games, in which activist groups or parties decide which projects or candidates to put forward, and gain only if their submissions are funded. It shows that for three common participation rules (BasicAV, Phragmén, and MES), pure Nash equilibria may not exist, even in very restricted party-list profiles, and deciding whether an equilibrium exists is both NP-hard and coNP-hard. In the multiwinner (unit-cost) setting, BasicAV always has an easily computable equilibrium, while Phragmén and MES remain hard in general but become tractable under party-list preferences. If each proposer can submit only one project, every multiwinner instance has an equilibrium computable in polynomial time for the three rules. Experiments on real participatory budgeting instances suggest that equilibria are frequent in practice, often attained by everyone submitting everything or by a few best-response rounds.","feed_headline":"Many participatory budgeting games have no stable outcome","feed_subtitle":"Even deciding whether one exists is provably hard, except in single-project multiwinner contests.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Phragmén rule definition and its formal properties, which the Phragmén results build on.","marker":"Brill et al., 2017"},{"why":"Defines the Method of Equal Shares and the proportionality guarantees that the MES variant inherits.","marker":"Peters and Skowron, 2020"},{"why":"Extends MES to participatory budgeting with project costs, the setting used throughout the paper.","marker":"Peters et al., 2021"},{"why":"Formalizes party-list preference profiles, which underlie several tractability and impossibility results.","marker":"Brill et al., 2018"},{"why":"Provides the real-world participatory budgeting election data used in the empirical equilibrium-frequency analysis.","marker":"Faliszewski et al., 2023"}],"fun_headline_variants":["Budget games: stable outcomes often absent","No equilibrium in many participatory budgeting games","Checking stable budgets is NP-hard, when they exist","Single-project proposers guarantee stable budgets","PB games: equilibrium existence is provably hard"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Budget games: stable outcomes often absent","No equilibrium in many participatory budgeting games","Checking stable budgets is NP-hard, when they exist","Single-project proposers guarantee stable budgets","PB games: equilibrium existence is provably hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000807,"raw_usage":{"total_tokens":3301,"prompt_tokens":590,"completion_tokens":2711,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":334,"completion_tokens_details":{"reasoning_tokens":2645}},"tokens_in":334,"tokens_out":2711,"duration_ms":23022,"temperature":1.0,"reasoning_tokens":2645,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T20:49:41.699823+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}