Abstract
In AAMAS 2014, Bouveret and Lemaitre (2014) presented a hierarchy of fairness concepts for allocation of indivisible objects. Among them CEEI (Competitive Equilibrium with Equal Incomes) was the strongest. In this note, we settle the complexity of computing a discrete CEEI assignment by showing it is strongly NP-hard. We then highlight a fairness notion (CEEI-FRAC) that is even stronger than CEEI for discrete assignments, is always Pareto optimal, and can be verified in polynomial time. We also show that computing a CEEI-FRAC discrete assignment is strongly NP-hard in general but polynomial-time computable if the utilities are zero or one.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.