Almost Group Envy-free Allocation of Indivisible Goods and Chores

Haris Aziz; Simon Rey

IJCAI 2020poster0 citations

Almost Group Envy-free Allocation of Indivisible Goods and Chores

Abstract

We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established in the literature and present stronger and relaxed versions that are especially suitable for the allocation of indivisible items. Of particular interest is a concept called group envy-freeness up to one item (GEF1). We then present a clear taxonomy of the fairness concepts. We study which fairness concepts guarantee the existence of a fair allocation under which preference domain. For two natural classes of additive utilities, we design polynomial-time algorithms to compute a GEF1 allocation. We also prove that checking whether a given allocation satisfies GEF1 is coNP-complete when there are either only goods, only chores or both.

Agent-based and Multi-agent Systems: Computational Social ChoiceAgent-based and Multi-agent Systems: Resource Allocation

BibTeX

@inproceedings{ijcai2020p6,
  title     = {Almost Group Envy-free Allocation of Indivisible Goods and Chores},
  author    = {Aziz, Haris and Rey, Simon},
  booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
               Artificial Intelligence, {IJCAI-20}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Christian Bessiere},
  pages     = {39--45},
  year      = {2020},
  month     = {7},
  note      = {Main track},
  doi       = {10.24963/ijcai.2020/6},
  url       = {https://doi.org/10.24963/ijcai.2020/6},
}