complexity of social welfare optimization in multiagent resource allocation
We study the complexity of social welfare optimization in multiagent resource allocation. We assume resources to be indivisible and nonshareable and agents to express their utilities over bundles of resources, where utilities can be represented in either the bundle form or the k-additive form. Solving some of the open problems raised by Chevaleyre et al. [2] and confirming their conjectures, we prove that egalitarian social welfare optimization is NP-complete for both the bundle and the 1-additive form, and both exact utilitarian and exact egalitarian social welfare optimization are DP-complete, each for both the bundle and the 2-additive form, where DP is the second level of the boolean hierarchy over NP. In addition, we prove that social welfare optimization with respect to the Nash product is NP-complete for both the bundle and the 1-additive form. Finally, we brief y discuss hardness of social welfare optimization in terms of inapproximability.
social welfare optimization multiagent resource allocation auction and mechanism design economically-motivated agents computational complexity