On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences

Bart de Keijzer, Sylvain Bouveret, Tomas B. Klos, Yingqian Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

29 Citations (Scopus)

Abstract

We study the problem of allocating a set of indivisible goods to a set of agents having additive preferences. We introduce two new important complexity results concerning efficiency and fairness in resource allocation problems: we prove that the problem of deciding whether a given allocation is Pareto-optimal is coNP-complete, and that the problem of deciding whether there is a Pareto-efficient and envy-free allocation is Σ p 2 -complete.
Original languageEnglish
Title of host publicationAlgorithmic Decision Theory
Subtitle of host publicationFirst International Conference, ADT 2009, Venice, Italy, October 20-23, 2009. Proceedings
EditorsF. Rossi , A. Tsoukias
Place of PublicationBerlin
PublisherSpringer
Pages98-110
ISBN (Electronic)978-3-642-04428-1
ISBN (Print)978-3-642-04427-4
DOIs
Publication statusPublished - 2009

Publication series

NameLNCS
Volume5783

Fingerprint

Dive into the research topics of 'On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences'. Together they form a unique fingerprint.

Cite this