Complexity and Approximation Schemes for Social Welfare Maximization in the High-Multiplicity Setting

Authors:
Open Access
Publisher website
Google Scholar
Abstract
We study the social welfare maximization problem in the high-multiplicity setting where agents and/or items are available in multiple types, provided that the numbers of types are small. We focus on the egalitarian and Nash social welfare maximization problems, and show that they are NP-hard even when the number of item types is a constant. Furthermore, we present two polynomial-time approximation schemes (PTAS), one for egalitarian social welfare with two item types, and one for Nash social welfare with any constant number of agent types. The first PTAS can be applied to the unrelated machine scheduling problem, thus partially solving an open question raised by Jansen and Maack in 2019. The second PTAS significantly improves upon the existing PTAS for identical agents.

This publication has 13 references indexed in Scilit: