Exact Optimization of Social Welfare by the Nash Product is DP-Complete∗ Nhan-Tam Nguyen

An important task in multiagent resource allocation, which provides mechanisms to allocate bundles of (indivisible and nonshareable) resources to agents, is to maximize social wel-fare. We study the computational complexity of exact social welfare optimization by the Nash product, which can be seen as a sensible compromise between the well-known notions of utilitarian and egalitarian social welfare. When utility func-tions are represented in the bundle or the k-additive form, for k ≥ 3, we prove that the corresponding computational prob-lems are DP-complete (where DP denotes the second level of the boolean hierarchy over NP), thus confirming two conjec-tures raised by Roos and Rothe (2010) in the affirmative