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.
|Title of host publication||Algorithmic Decision Theory|
|Subtitle of host publication||First International Conference, ADT 2009, Venice, Italy, October 20-23, 2009. Proceedings|
|Editors||F. Rossi , A. Tsoukias |
|Place of Publication||Berlin|
|Publication status||Published - 2009|