Complexity and Approximability of Egalitarian and Nash Product Social Welfare Optimization in Multiagent Resource Allocation

摘要

Multiagent resource allocation deals with distributing (bundles) of resources to agents that specify utility functions over bundles. A natural and important problem in this field is social welfare optimization. We assume resources to be indivisible and nonshareable and that utility functions are represented by the kadditive form or as straight-line programs. We prove NP-completeness for egalitarian and Nash product social welfare optimization for straight-line program representation of utility functions. In addition, we show that social welfare optimization by the Nash product in the 1-additive form is hard to approximate, yet we also give fully polynomial-time approximation schemes for egalitarian and Nash product social welfare optimization in the 1-additive form with a fixed number of agents.