Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.05708 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908355800334336 |
|---|---|
| author | Schmidt-Kraepelin, Ulrike Suksompong, Warut Utke, Markus |
| author_facet | Schmidt-Kraepelin, Ulrike Suksompong, Warut Utke, Markus |
| contents | We study a budget aggregation setting where voters express their preferred allocation of a fixed budget over a set of alternatives, and a mechanism aggregates these preferences into a single output allocation. Motivated by scenarios in which the budget is not perfectly divisible, we depart from the prevailing literature by restricting the mechanism to output allocations that assign integral amounts. This seemingly minor deviation has significant implications for the existence of truthful mechanisms. Specifically, when voters can propose fractional allocations, we demonstrate that the Gibbard-Satterthwaite theorem can be extended to our setting. In contrast, when voters are restricted to integral ballots, we identify a class of truthful mechanisms by adapting moving-phantom mechanisms to our context. Moreover, we show that while a weak form of proportionality can be achieved alongside truthfulness, (stronger) proportionality notions derived from approval-based committee voting are incompatible with truthfulness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05708 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Discrete Budget Aggregation: Truthfulness and Proportionality Schmidt-Kraepelin, Ulrike Suksompong, Warut Utke, Markus Computer Science and Game Theory Theoretical Economics We study a budget aggregation setting where voters express their preferred allocation of a fixed budget over a set of alternatives, and a mechanism aggregates these preferences into a single output allocation. Motivated by scenarios in which the budget is not perfectly divisible, we depart from the prevailing literature by restricting the mechanism to output allocations that assign integral amounts. This seemingly minor deviation has significant implications for the existence of truthful mechanisms. Specifically, when voters can propose fractional allocations, we demonstrate that the Gibbard-Satterthwaite theorem can be extended to our setting. In contrast, when voters are restricted to integral ballots, we identify a class of truthful mechanisms by adapting moving-phantom mechanisms to our context. Moreover, we show that while a weak form of proportionality can be achieved alongside truthfulness, (stronger) proportionality notions derived from approval-based committee voting are incompatible with truthfulness. |
| title | Discrete Budget Aggregation: Truthfulness and Proportionality |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2505.05708 |