Competitive equilibrium with equal incomes for allocation of indivisible objects

摘要

We settle the complexity of computing a discrete CEEI (Competitive Equilibrium with Equal Incomes) 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. (C) 2015 Elsevier B.V. All rights reserved.