As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
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 k-additive 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.