Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.11797 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929718211641344 |
|---|---|
| author | Kraiczy, Sonja Robinson, Isaac Elkind, Edith |
| author_facet | Kraiczy, Sonja Robinson, Isaac Elkind, Edith |
| contents | Participatory budgeting (PB) is a form of citizen participation that allows citizens to decide how public funds are spent. Through an election, citizens express their preferences on various projects (spending proposals). A voting mechanism then determines which projects will be approved. The Method of Equal Shares (MES) is the state of the art algorithm for a proportional, voting based approach to participatory budgeting and has been implemented in cities across Poland and Switzerland. A significant drawback of MES is that it is not \textit{exhaustive} meaning that it often leaves a portion of the budget unspent that could be used to fund additional projects. To address this, in practice the algorithm is combined with a completion heuristic - most often the ``add-one" heuristic which artificially increases the budget until a heuristically chosen threshold. This heuristic is computationally inefficient and will become computationally impractical if PB is employed on a larger scale. We propose the more efficient \textsc{add-opt} heuristic for Exact Equal Shares (EES), a variation of MES that is known to retain many of its desirable properties. We solve the problem of identifying the next budget for which the outcome for EES changes in $O(mn)$ time for cardinal utilities and $O(m^2n)$ time for uniform utilities, where $m$ is the number of projects and $n$ is the number of voters. Our solution to this problem inspires the efficient \textsc{add-opt} heuristic which bypasses the need to search through each intermediary budget. We perform comprehensive experiments on real-word PB instances from Pabulib and show that completed EES outcomes usually match the proportion of budget spent by completed MES outcomes. Furthermore, the \textsc{add-opt} heuristic matches the proportion of budget spend by add-one for EES. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11797 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Streamlining Equal Shares Kraiczy, Sonja Robinson, Isaac Elkind, Edith Computer Science and Game Theory Participatory budgeting (PB) is a form of citizen participation that allows citizens to decide how public funds are spent. Through an election, citizens express their preferences on various projects (spending proposals). A voting mechanism then determines which projects will be approved. The Method of Equal Shares (MES) is the state of the art algorithm for a proportional, voting based approach to participatory budgeting and has been implemented in cities across Poland and Switzerland. A significant drawback of MES is that it is not \textit{exhaustive} meaning that it often leaves a portion of the budget unspent that could be used to fund additional projects. To address this, in practice the algorithm is combined with a completion heuristic - most often the ``add-one" heuristic which artificially increases the budget until a heuristically chosen threshold. This heuristic is computationally inefficient and will become computationally impractical if PB is employed on a larger scale. We propose the more efficient \textsc{add-opt} heuristic for Exact Equal Shares (EES), a variation of MES that is known to retain many of its desirable properties. We solve the problem of identifying the next budget for which the outcome for EES changes in $O(mn)$ time for cardinal utilities and $O(m^2n)$ time for uniform utilities, where $m$ is the number of projects and $n$ is the number of voters. Our solution to this problem inspires the efficient \textsc{add-opt} heuristic which bypasses the need to search through each intermediary budget. We perform comprehensive experiments on real-word PB instances from Pabulib and show that completed EES outcomes usually match the proportion of budget spent by completed MES outcomes. Furthermore, the \textsc{add-opt} heuristic matches the proportion of budget spend by add-one for EES. |
| title | Streamlining Equal Shares |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.11797 |