Fair Division of Chores with Budget Constraints
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913569021362176 |
|---|---|
| author | Elkind, Edith Igarashi, Ayumi Teh, Nicholas |
| author_facet | Elkind, Edith Igarashi, Ayumi Teh, Nicholas |
| contents | We study fair allocation of indivisible chores to agents under budget constraints, where each chore has an objective size and disutility. This model captures scenarios where a set of chores need to be divided among agents with limited time, and each chore has a specific time needed for completion. We propose a budget-constrained model for allocating indivisible chores, and systematically explore the differences between goods and chores in this setting. We establish the existence of an EFX allocation. We then show that EF2 allocations are polynomial-time computable in general; for many restricted settings, we strengthen this result to EF1. For divisible chores, we develop an efficient algorithm for computing an EF allocation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23979 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fair Division of Chores with Budget Constraints Elkind, Edith Igarashi, Ayumi Teh, Nicholas Computer Science and Game Theory Theoretical Economics We study fair allocation of indivisible chores to agents under budget constraints, where each chore has an objective size and disutility. This model captures scenarios where a set of chores need to be divided among agents with limited time, and each chore has a specific time needed for completion. We propose a budget-constrained model for allocating indivisible chores, and systematically explore the differences between goods and chores in this setting. We establish the existence of an EFX allocation. We then show that EF2 allocations are polynomial-time computable in general; for many restricted settings, we strengthen this result to EF1. For divisible chores, we develop an efficient algorithm for computing an EF allocation. |
| title | Fair Division of Chores with Budget Constraints |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2410.23979 |