Metraipolis › archive › dc_c7e84f67cbcb
Strengthening Proportionality in Participatory Budgeting with Additive Utilities — arXiv:2609.08888
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.08888
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:32:15.033Z
- SHA-256 of the archived text
4a290cf992cb73dcbc6ddd99dd867782c618c2abe12dece2a7268a1df4cf66fa- Stable URL of this page
https://metraipolis.com/documento/dc_c7e84f67cbcb
How to cite
Strengthening Proportionality in Participatory Budgeting with Additive Utilities — arXiv:2609.08888 — arXiv (en), https://arxiv.org/abs/2609.08888 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c7e84f67cbcb (Metraipolis archive dc_c7e84f67cbcb, sha256 4a290cf992cb73dcbc6ddd99dd867782c618c2abe12dece2a7268a1df4cf66fa)
BibTeX
@misc{dcc7e84f67cbcb,
title = {Strengthening Proportionality in Participatory Budgeting with Additive Utilities — arXiv:2609.08888},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.08888},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c7e84f67cbcb; sha256 4a290cf992cb73dcbc6ddd99dd867782c618c2abe12dece2a7268a1df4cf66fa},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08888. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Proportional representation is a central goal in participatory budgeting, where voters select public projects subject to a shared budget. Full justified representation (FJR) accounts for groups whose members may value different projects, but computing an FJR outcome is strongly NP-hard for additive utilities. We show that FJR up to one project can be achieved in polynomial time for arbitrary nonnegative additive utilities and project costs. Our approach extends Residual-Budget Greedy and satisfies a stronger fractional axiom that can also be verified in polynomial time. For approval utilities, this axiom coincides with FJR+, providing exact FJR in that setting. We further show that every feasible completion of the algorithm's selected set preserves the representation guarantee, providing flexibility in allocating the remaining budget. In particular, we give a completion that ensures priceability at the original budget. For unit-cost projects, we strengthen the representation guarantee to the Droop quota and combine it with priceability whenever there are enough positively valued projects to fill the budget. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-09 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2609.08888 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T13:06:09.193Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).