How to Fairly Allocate Easy and Difficult Chores

Soroush Ebadian, Dominik Peters () and Nisarg Shah
Additional contact information
Soroush Ebadian: DCS - Department of Computer Science [University of Toronto] - University of Toronto
Dominik Peters: LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision - Université Paris Dauphine-PSL - PSL - Université Paris Sciences et Lettres - CNRS - Centre National de la Recherche Scientifique
Nisarg Shah: DCS - Department of Computer Science [University of Toronto] - University of Toronto

Post-Print from HAL

Abstract: A major open question in fair allocation of indivisible items is whether there always exists an allocation of chores that is Pareto optimal (PO) and envy-free up to one item (EF1). We answer this question affirmatively for the natural class of bivalued utilities, where each agent partitions the chores into easy and difficult ones, and has cost > 1 for chores that are difficult for her and cost 1 for chores that are easy for her. Such an allocation can be found in polynomial time using an algorithm based on the Fisher market. We also show that for a slightly broader class of utilities, where each agent can have a potentially different integer , an allocation that is maximin share fair (MMS) always exists and can be computed in polynomial time, provided that each is an integer. Our MMS arguments also hold when allocating goods instead of chores, and extend to another natural class of utilities, namely weakly lexicographic utilities.

Date: 2022-05
New Economics Papers: this item is included in nep-des and nep-upt
Note: View the original document on HAL open archive server: https://hal.science/hal-03834514v1
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Published in 21st International Conference on Autonomous Agents and Multiagent Systems, May 2022, Auckland, New Zealand. ⟨10.5555/3535850.3535893⟩

Downloads: (external link)
https://hal.science/hal-03834514v1/document (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:hal:journl:hal-03834514

DOI: 10.5555/3535850.3535893

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().