On Truthful Mechanisms without Pareto-efficiency: Characterizations and Fairness
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908989896261632 |
|---|---|
| author | Babaioff, Moshe Morag, Noam Manaker |
| author_facet | Babaioff, Moshe Morag, Noam Manaker |
| contents | We consider the problem of allocating heterogeneous and indivisible goods among strategic agents, with preferences over subsets of goods, when there is no medium of exchange. This model captures the well studied problem of fair allocation of indivisible goods. Serial-quota mechanisms are allocation mechanisms where there is a predefined order over agents, and each agent in her turn picks a predefined number of goods from the remaining goods. These mechanisms are clearly strategy-proof, non-bossy, and neutral. Are there other mechanisms with these properties? We show that for important classes of strict ordinal preferences (as lexicographic preferences, and as the class of all strict preferences), these are the only mechanisms with these properties. Importantly, unlike previous work, we can prove the claim even for mechanisms that are not Pareto-efficient. Moreover, we generalize these results to preferences that are cardinal, including any valuation class that contains additive valuations. We then derive strong negative implications of this result on truthful mechanisms for fair allocation of indivisible goods to agents with additive valuations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11131 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Truthful Mechanisms without Pareto-efficiency: Characterizations and Fairness Babaioff, Moshe Morag, Noam Manaker Computer Science and Game Theory Theoretical Economics 91B32 We consider the problem of allocating heterogeneous and indivisible goods among strategic agents, with preferences over subsets of goods, when there is no medium of exchange. This model captures the well studied problem of fair allocation of indivisible goods. Serial-quota mechanisms are allocation mechanisms where there is a predefined order over agents, and each agent in her turn picks a predefined number of goods from the remaining goods. These mechanisms are clearly strategy-proof, non-bossy, and neutral. Are there other mechanisms with these properties? We show that for important classes of strict ordinal preferences (as lexicographic preferences, and as the class of all strict preferences), these are the only mechanisms with these properties. Importantly, unlike previous work, we can prove the claim even for mechanisms that are not Pareto-efficient. Moreover, we generalize these results to preferences that are cardinal, including any valuation class that contains additive valuations. We then derive strong negative implications of this result on truthful mechanisms for fair allocation of indivisible goods to agents with additive valuations. |
| title | On Truthful Mechanisms without Pareto-efficiency: Characterizations and Fairness |
| topic | Computer Science and Game Theory Theoretical Economics 91B32 |
| url | https://arxiv.org/abs/2411.11131 |