When is Truthfully Allocating Chores no Harder than Goods?
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909676614975488 |
|---|---|
| author | Li, Bo Tao, Biaoshuai Wang, Fangxiao Wu, Xiaowei Yang, Mingwei Zhou, Shengwei |
| author_facet | Li, Bo Tao, Biaoshuai Wang, Fangxiao Wu, Xiaowei Yang, Mingwei Zhou, Shengwei |
| contents | We study the problem of fairly and efficiently allocating a set of items among strategic agents with additive valuations, where items are either all indivisible or all divisible. When items are goods, numerous positive and negative results are known regarding the fairness and efficiency guarantees achievable by truthful mechanisms, whereas our understanding of truthful mechanisms for chores remains considerably more limited. In this paper, we discover various connections between truthful good and chore allocations, greatly enhancing our understanding of the latter via tools from the former.
For indivisible chores with two agents, by leveraging the observation that a simple bundle-swapping operation transforms several properties for goods including truthfulness to the corresponding properties for chores, we characterize truthful mechanisms and derive tight guarantees of various fairness notions achieved by truthful mechanisms. Moreover, for homogeneous divisible chores, by generalizing the above transformation to an arbitrary number of agents, we characterize truthful mechanisms with two agents, show that every truthful mechanism with two agents admits an efficiency ratio of $0$, and derive a large family of strictly truthful, envy-free (EF), and proportional mechanisms for an arbitrary number of agents. Finally, for indivisible chores with an arbitrary number of agents having bi-valued cost functions, we give an ex-ante truthful, ex-ante Pareto optimal, ex-ante EF, and ex-post envy-free up to one item mechanism, improving the best guarantees for bi-valued instances by prior works. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01629 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | When is Truthfully Allocating Chores no Harder than Goods? Li, Bo Tao, Biaoshuai Wang, Fangxiao Wu, Xiaowei Yang, Mingwei Zhou, Shengwei Computer Science and Game Theory We study the problem of fairly and efficiently allocating a set of items among strategic agents with additive valuations, where items are either all indivisible or all divisible. When items are goods, numerous positive and negative results are known regarding the fairness and efficiency guarantees achievable by truthful mechanisms, whereas our understanding of truthful mechanisms for chores remains considerably more limited. In this paper, we discover various connections between truthful good and chore allocations, greatly enhancing our understanding of the latter via tools from the former. For indivisible chores with two agents, by leveraging the observation that a simple bundle-swapping operation transforms several properties for goods including truthfulness to the corresponding properties for chores, we characterize truthful mechanisms and derive tight guarantees of various fairness notions achieved by truthful mechanisms. Moreover, for homogeneous divisible chores, by generalizing the above transformation to an arbitrary number of agents, we characterize truthful mechanisms with two agents, show that every truthful mechanism with two agents admits an efficiency ratio of $0$, and derive a large family of strictly truthful, envy-free (EF), and proportional mechanisms for an arbitrary number of agents. Finally, for indivisible chores with an arbitrary number of agents having bi-valued cost functions, we give an ex-ante truthful, ex-ante Pareto optimal, ex-ante EF, and ex-post envy-free up to one item mechanism, improving the best guarantees for bi-valued instances by prior works. |
| title | When is Truthfully Allocating Chores no Harder than Goods? |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2505.01629 |