Truthful Aggregation of Budget Proposals with Proportionality Guarantees

Caragiannis, Ioannis, Christodoulou, George and Protopapas, Nicos ORCID: 0000-0002-6130-3641
(2022) Truthful Aggregation of Budget Proposals with Proportionality Guarantees. [Preprint]

[thumbnail of 2203.09971v1.pdf] Text
2203.09971v1.pdf - Submitted version

Download (309kB) | Preview


We study a participatory budgeting problem, where a set of strategic agents wish to split a divisible budget among different projects, by aggregating their proposals on a single division. Unfortunately, the straight-forward rule that divides the budget proportionally is susceptible to manipulation. In a recent work, Freeman et al. [arXiv:1905.00457] proposed a class of truthful mechanisms, called moving phantom mechanisms. Among others, they propose a proportional mechanism, in the sense that in the extreme case where all agents prefer a single project to receive the whole amount, the budget is assigned proportionally. While proportionality is a naturally desired property, it is defined over a limited type of preference profiles. To address this, we expand the notion of proportionality, by proposing a quantitative framework which evaluates a budget aggregation mechanism according to its worst-case distance from the proportional allocation. Crucially, this is defined for every preference profile. We study this measure on the class of moving phantom mechanisms, and we provide approximation guarantees. For two projects, we show that the Uniform Phantom mechanism is the optimal among all truthful mechanisms. For three projects, we propose a new, proportional mechanism which is virtually optimal among all moving phantom mechanisms. Finally, we provide impossibility results regarding the approximability of moving phantom mechanisms.

Item Type: Preprint
Additional Information: 30 pages, 12 figures, 2 tables. A preliminary version appeared in the 36th AAAI Conference in Artificial Intelligence
Uncontrolled Keywords: cs.GT, cs.GT
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 04 Apr 2022 07:58
Last Modified: 25 Mar 2024 21:07
DOI: 10.48550/arxiv.2203.09971
Related URLs: