2009-11-13
On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
Publication
Publication
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 Σp2 -complete.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1007/978-3-642-04428-1_9, hdl.handle.net/1765/131491 | |
|
De Keijzer, B., Bouveret, S., Klos, T., & Zhang, Y. (2009). On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences. doi:10.1007/978-3-642-04428-1_9 |
|