License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.1
URN: urn:nbn:de:0030-drops-146944
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14694/
Go to the corresponding LIPIcs Volume Portal

Bhaskar, Umang ; Sricharan, A. R. ; Vaish, Rohit

On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources

pdf-format:
LIPIcs-APPROX1.pdf (0.8 MB)

Abstract

We study the fair allocation of undesirable indivisible items, or chores. While the case of desirable indivisible items (or goods) is extensively studied, with many results known for different notions of fairness, less is known about the fair division of chores. We study envy-free allocation of chores and make three contributions. First, we show that determining the existence of an envy-free allocation is NP-complete even in the simple case when agents have binary additive valuations. Second, we provide a polynomial-time algorithm for computing an allocation that satisfies envy-freeness up to one chore (EF1), correcting a claim in the existing literature. A modification of our algorithm can be used to compute an EF1 allocation for doubly monotone instances (where each agent can partition the set of items into objective goods and objective chores). Our third result applies to a mixed resources model consisting of indivisible items and a divisible, undesirable heterogeneous resource (i.e., a bad cake). We show that there always exists an allocation that satisfies envy-freeness for mixed resources (EFM) in this setting, complementing a recent result of Bei et al. [Bei et al., 2021] for indivisible goods and divisible cake.

BibTeX - Entry

@InProceedings{bhaskar_et_al:LIPIcs.APPROX/RANDOM.2021.1,
  author =	{Bhaskar, Umang and Sricharan, A. R. and Vaish, Rohit},
  title =	{{On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14694},
  URN =		{urn:nbn:de:0030-drops-146944},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.1},
  annote =	{Keywords: Fair Division, Indivisible Chores, Approximate Envy-Freeness}
}

Keywords: Fair Division, Indivisible Chores, Approximate Envy-Freeness
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI