Participatory Budgeting Project Strength via Candidate Control
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. 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.
BibTeX
@inproceedings{ijcai2025_participatorybud,
title = {Participatory Budgeting Project Strength via Candidate Control},
author = {Piotr Faliszewski and Łukasz Janeczko and Dušan Knop and Jan Pokorný and Šimon Schierreich and Mateusz Słuszniak and Krzysztof Sornat},
booktitle = {IJCAI 2025},
year = {2025}
}