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

doi:10.1007/978-3-642-04428-1_9

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

Information Systems IE&IS

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

50 Citations (Scopus)

1 Downloads (Pure)

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 language	English
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
Publisher	Springer
Pages	98-110
ISBN (Electronic)	978-3-642-04428-1
ISBN (Print)	978-3-642-04427-4
DOIs	https://doi.org/10.1007/978-3-642-04428-1_9
Publication status	Published - 2009

Publication series

Name	LNCS
Volume	5783

Access to Document

10.1007/978-3-642-04428-1_9

Cite this

de Keijzer, B., Bouveret, S., Klos, T. B., & Zhang, Y. (2009). On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In F. Rossi , & A. Tsoukias (Eds.), Algorithmic Decision Theory: First International Conference, ADT 2009, Venice, Italy, October 20-23, 2009. Proceedings (pp. 98-110). (LNCS; Vol. 5783). Springer. https://doi.org/10.1007/978-3-642-04428-1_9

de Keijzer, Bart ; Bouveret, Sylvain ; Klos, Tomas B. et al. / On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. Algorithmic Decision Theory: First International Conference, ADT 2009, Venice, Italy, October 20-23, 2009. Proceedings. editor / F. Rossi ; A. Tsoukias . Berlin : Springer, 2009. pp. 98-110 (LNCS).

@inproceedings{b0c226f8cda34646bb633543045b901a,

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

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.",

author = "{de Keijzer}, Bart and Sylvain Bouveret and Klos, {Tomas B.} and Yingqian Zhang",

year = "2009",

doi = "10.1007/978-3-642-04428-1_9",

language = "English",

isbn = "978-3-642-04427-4",

series = "LNCS",

publisher = "Springer",

pages = "98--110",

editor = "{Rossi }, F. and {Tsoukias }, A.",

booktitle = "Algorithmic Decision Theory",

address = "Germany",

}

de Keijzer, B, Bouveret, S, Klos, TB & Zhang, Y 2009, On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. in F Rossi & A Tsoukias (eds), Algorithmic Decision Theory: First International Conference, ADT 2009, Venice, Italy, October 20-23, 2009. Proceedings. LNCS, vol. 5783, Springer, Berlin, pp. 98-110. https://doi.org/10.1007/978-3-642-04428-1_9

On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. / de Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas B. et al.
Algorithmic Decision Theory: First International Conference, ADT 2009, Venice, Italy, October 20-23, 2009. Proceedings. ed. / F. Rossi ; A. Tsoukias . Berlin: Springer, 2009. p. 98-110 (LNCS; Vol. 5783).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - de Keijzer, Bart

AU - Bouveret, Sylvain

AU - Klos, Tomas B.

AU - Zhang, Yingqian

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-04428-1_9

DO - 10.1007/978-3-642-04428-1_9

M3 - Conference contribution

SN - 978-3-642-04427-4

T3 - LNCS

SP - 98

EP - 110

BT - Algorithmic Decision Theory

A2 - Rossi , F.

A2 - Tsoukias , A.

PB - Springer

CY - Berlin

ER -

de Keijzer B, Bouveret S, Klos TB, Zhang Y. On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In Rossi F, Tsoukias A, editors, Algorithmic Decision Theory: First International Conference, ADT 2009, Venice, Italy, October 20-23, 2009. Proceedings. Berlin: Springer. 2009. p. 98-110. (LNCS). doi: 10.1007/978-3-642-04428-1_9

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

Abstract

Publication series

Access to Document

Fingerprint

Cite this