Participatory Budgeting Project Strength via Candidate Control DOI: 10.1613/jair.1.xxxxx Volume: 4 6 8 Note: An extended abstract of this work has been published in the Proceedings of the 34th International Joint Conference on Artificial Intelligence ( Faliszewski et al. 2025 ) .
Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, Krzysztof Sornat · 2026
Read Participatory Budgeting Project Strength via Candidate Control DOI: 10.1613/jair.1.xxxxx Volume: 4 6 8 Note: An extended abstract of this work has been published in the Proceedings of the 34th International Joint Conference on Artificial Intelligence ( Faliszewski et al. 2025 ) . by Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, Krzysztof Sornat (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16511.txt.
Introduction
Piotr Faliszewski and four coauthors study who can be added to swing a budget vote. Their 2026 preprint deals with shared budget votes by groups. In such votes, funds go to the plans with most back. A chief may add or drop names to force a set win. That chief act is called candidate control in vote maths.
The team weighs how hard that control is to sum. Hard sums mean the vote is safe from chief tricks in real use. Easy sums mean guards must block such adds by rule. Shared funds touch real towns and groups each year. The work maps safe and weak vote forms.
Catalog record
| CREATOR | Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, Krzysztof Sornat |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 118 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-16511
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Participatory Budgeting Project Strength via Candidate Control DOI: 10.1613/jair.1.xxxxx Volume: 4 6 8 Note: An extended abstract of this work has been published in the Proceedings of the 34th International Joint Conference on Artificial Intelligence ( Faliszewski et al. 2025 ) . Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, Krzysztof Sornat Abstract . We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP -hard to solve for many participatory budgeting voting rules, including Phragmén and Equal-Shares , but there are natural cases with polynomial-time algorithms (e.g., for the GreedyAV rule and projects with costs encoded in unary). We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects, and we support this view with experiments. \JAIRAE Insert JAIR AE Name \JAIRTrack 1. Introduction Participatory budgeting is a recent democratic innovation where cities allow their inhabitants to decide about a certain fraction of their budgets ( Cabannes 2004 ; Goel et al. 2019 ; Rey and Maly 2023 ) . Specifically, some of the community members propose possible projects to be implemented and, then, all the citizens get a chance to vote as to which of them should be funded. Most commonly, such elections use approval ballots, where people indicate which projects they would like to see funded, and the GreedyAV rule, which selects the most approved projects (subject to not exceeding the budget). However, there also are more advanced rules, such as Phragmén ( Brill et al. 2024 ; Los et al. 2022 ) or Equal-Shares ( Peters and Skowron 2020 ; Peters et al. 2021 ) , which produce arguably more fair—or, to be precise, more proportional—decisions ( Faliszewski et al. 2023 ) . Yet, with more advanced rules come issues about understanding the results. Indeed, recently Boehmer et al. 2024 have argued that proposers whose projects were rejected may find it quite difficult to understand the reason for this outcome. To alleviate this problem, they introduced a number of performance measures—mostly based on the bribery family of problems ( Faliszewski et al. 2009 ; Faliszewski and Rothe 2016 ) —that attempt to answer the following question: As a proposer of a project that was not funded, what could I have done differently to have it funded? For example, they ask if the project would have been funded if its cost were lower (see also the work of Baumeister et al. 2021 ), or if its proposer convinced more people to vote for it, or if the proposer motivated some voters to only approve his or her project. Similar bribery-style problems were also used to evaluate the robustness of election results ( Shiryaev et al. 2013 ; Bredereck et al. 2021 ; Baumeister and Hogrebe 2021 ; Boehmer et al. 2021 ; Boehmer et al. 2023 ) , or the margin of victory for the winners ( Magrino et al. 2011 ; Xia 2012 ) . In this paper, we follow-up on these ideas, but using candidate control. The main difference is that instead of focusing on circumstances that depend on a project’s proposer (indeed, the project’s cost is his or her choice, and it is his or her choice what support campaign he or she runs), we focus on external ones, independent of his or her actions (such as some other projects being submitted or not 1 1 1 We disregard the possibility that a proposer might try to discourage other people from proposing projects, albeit we acknowledge that this may happen. In fact, this might even be quite benign: A group of activists focused on making their city more green may discuss among themselves which projects to submit and which to withhold. ). We believe that looking at both types of reasons for a project’s rejection gives a more complete view of its performance. Candidate Control. The idea of the control-in-elections family of problems is that we are given a description of an election, a designated candidate, and we ask if it is possible to ensure that this candidate is a winner (in constructive control) or ceases to be a winner (in destructive control) by modifying the structure of the election ( Bartholdi III et al. 1992 ; Faliszewski and Rothe 2016 ) . Specifically, researchers consider control by adding or deleting either candidates or voters (some papers—including the one that introduced election control ( Bartholdi III et al. 1992 ) —also consider various forms of arranging run-off elections as a type of control). So far, election control was mostly studied theoretically, with a focus on the complexity analysis ( Bartholdi III et al. 1992 ; Hemaspaandra et al. 2007 ; Meir et al. 2008 ; Liu et al. 2009 ; Erdélyi et al. 2015a ; Yang 2019 ) , but some empirical results exist as well ( Erdélyi et al. 2015b ) . We study candidate control in participatory budgeting, that is, we ask if it is possible to ensure funding of a given project (or, preclude its funding) by either adding new projects—from some a’priori known set of projects—or by deleting them. Our results are theoretical and focus on the complexity of our problems, but we motivate them by project performance analysis. As our performance analysis is based on control by deleting projects, we pay most attention to results regarding this variant of control, and we include the addition case for the sake of completeness and to be in sync with the preceding literature. Performance Analysis. Let us now discuss how one could use control by deleting candidates to analyze the performance of projects in participatory budgeting (we will use the terms projects and candidates interchangeably, e.g., using “candidates” in the names of control problems). Consider a participatory budgeting election and some not-funded project p . One basic measure of its performance is the smallest number of other projects that have to be removed from the election for p to be funded. The lower this number, the closer was the project to winning: Indeed, perhaps some proposers only managed to submit their projects in the last minute and it was possible that they would have missed the deadline, or some projects were close to be removed from the election due to formal reasons, but the city officials were not strict in this regard. However, it is more likely that such issues would affect cheaper projects than the more expensive ones—which, likely, had more careful proposers—so instead of asking for a smallest set of projects to delete, we may ask for a set with the lowest total cost. Another way of using control by deleting projects to assess a project’s performance is to use a probabilistic approach, along the lines of the one taken by Boehmer et al. 2021 , Boehmer et al. 2023 , and Baumeister and Hogrebe 2021 for bribery: We ask for the probability that project p is funded assuming that