Efficiently Computing Equilibria in Budget-Aggregation Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912923706720256 |
|---|---|
| author | Becker, Patrick Fries, Alexander Greger, Matthias Segal-Halevi, Erel |
| author_facet | Becker, Patrick Fries, Alexander Greger, Matthias Segal-Halevi, Erel |
| contents | Budget aggregation deals with the social choice problem of distributing an exogenously given budget among a set of public projects, given agents' preferences. Taking a game-theoretic perspective, we study budget-aggregation games where each agent has virtual decision power over some fraction of the budget. We investigate the structure and show efficient computability of Nash equilibria for various common preference models in this setting. In particular, we show that equilibria for Leontief utilities can be found in polynomial time, solving an open problem from Brandt et al. [2023], and give an explicit polynomial-time algorithm for computing equilibria for $\ell_1$ preferences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08767 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficiently Computing Equilibria in Budget-Aggregation Games Becker, Patrick Fries, Alexander Greger, Matthias Segal-Halevi, Erel Computer Science and Game Theory Computational Complexity Budget aggregation deals with the social choice problem of distributing an exogenously given budget among a set of public projects, given agents' preferences. Taking a game-theoretic perspective, we study budget-aggregation games where each agent has virtual decision power over some fraction of the budget. We investigate the structure and show efficient computability of Nash equilibria for various common preference models in this setting. In particular, we show that equilibria for Leontief utilities can be found in polynomial time, solving an open problem from Brandt et al. [2023], and give an explicit polynomial-time algorithm for computing equilibria for $\ell_1$ preferences. |
| title | Efficiently Computing Equilibria in Budget-Aggregation Games |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2509.08767 |