Fair Division of Chores with Budget Constraints

Edith Elkind, Ayumi Igarashi and Nicholas Teh

Papers from arXiv.org

Abstract: 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.

Date: 2024-10
New Economics Papers: this item is included in nep-des and nep-mic
References: Add references at CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2410.23979 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2410.23979

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().