Participatory Budgeting Project Strength via Candidate Control

Faliszewski, Piotr; Janeczko, Łukasz; Knop, Dušan; Pokorný, Jan; Schierreich, Šimon; Słuszniak, Mateusz; Sornat, Krzysztof

doi:10.24963/ijcai.2025/425

Participatory Budgeting Project Strength via Candidate Control

Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, Krzysztof Sornat

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 3821-3829.

https://doi.org/10.24963/ijcai.2025/425

Keywords

Game Theory and Economic Paradigms: GTEP: Computational social choice

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. 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 on real-life PB instances.

Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, and Krzysztof Sornat. 2025. Participatory Budgeting Project Strength via Candidate Control. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3821–3829. https://doi.org/10.24963/ijcai.2025/425

@inproceedings{ijcai2025p425,
  title     = {Participatory Budgeting Project Strength via Candidate Control},
  author    = {Faliszewski, Piotr and Janeczko, Łukasz and Knop, Dušan and Pokorný, Jan and Schierreich, Šimon and Słuszniak, Mateusz and Sornat, Krzysztof},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {3821--3829},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/425},
  url       = {https://doi.org/10.24963/ijcai.2025/425},
}

TY  - CPAPER
TI  - Participatory Budgeting Project Strength via Candidate Control
AU  - Faliszewski, Piotr
AU  - Janeczko, Łukasz
AU  - Knop, Dušan
AU  - Pokorný, Jan
AU  - Schierreich, Šimon
AU  - Słuszniak, Mateusz
AU  - Sornat, Krzysztof
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 3821
EP  - 3829
DO  - 10.24963/ijcai.2025/425
UR  - https://doi.org/10.24963/ijcai.2025/425
ER  -