Szczegóły publikacji
Opis bibliograficzny
Robustness of participatory budgeting outcomes: complexity and experiments / Niclas Boehmer, Piotr FALISZEWSKI, Łukasz JANECZKO, Andrzej KACZMARCZYK // W: Algorithmic Game Theory : 16th international symposium, SAGT 2023 : Egham, UK, September 4–7, 2023 : proceedings / eds. Argyrios Deligkas, Aris Filos-Ratsikas. — Cham : Springer Nature Switzerland, cop. 2023. — (Lecture Notes in Computer Science ; ISSN 0302-9743 ; vol. 14238). — ISBN: 978-3-031-43253-8; e-ISBN: 978-3-031-43254-5. — S. 161–178. — Bibliogr., Abstr. — Publikacja dostępna online od: 2023-09-04
Autorzy (4)
Dane bibliometryczne
| ID BaDAP | 148412 |
|---|---|
| Data dodania do BaDAP | 2023-09-20 |
| DOI | 10.1007/978-3-031-43254-5_10 |
| Rok publikacji | 2023 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Wydawca | Springer |
| Konferencja | International Symposium on Algorithmic Game Theory |
| Czasopismo/seria | Lecture Notes in Computer Science |
Abstract
We study the robustness of approval-based participatory budgeting (PB) rules to random noise in the votes. First, we analyze the computational complexity of the #FLIP-BRIBERY problem, where given a PB instance we ask for the number of ways in which we can flip a given number of approvals in the votes, so that a specific project is selected. This problem captures computing the funding probabilities of projects in case random noise is added. Unfortunately, it is intractable even for the simplest PB rules. Second, we analyze the robustness of several prominent PB rules (including the basic greedy rule and the Method of Equal Shares) on real-world instances from Pabulib. Using sampling, we quantify the extent to which simple, greedy PB rules are more robust than proportional ones, and we identify three types of (very) non-robust projects in real-world PB instances.