Participatory Budgeting Project Strength via Candidate Control
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912843125751808 |
|---|---|
| author | Faliszewski, Piotr Janeczko, Łukasz Knop, Dušan Pokorný, Jan Schierreich, Šimon Słuszniak, Mateusz Sornat, Krzysztof |
| author_facet | Faliszewski, Piotr Janeczko, Łukasz Knop, Dušan Pokorný, Jan Schierreich, Šimon Słuszniak, Mateusz Sornat, Krzysztof |
| contents | 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 Method of 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16511 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Participatory Budgeting Project Strength via Candidate Control Faliszewski, Piotr Janeczko, Łukasz Knop, Dušan Pokorný, Jan Schierreich, Šimon Słuszniak, Mateusz Sornat, Krzysztof Computer Science and Game Theory 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 Method of 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. |
| title | Participatory Budgeting Project Strength via Candidate Control |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2601.16511 |