Tractable Fragments of the Maximum Nash Welfare Problem
share
We study the problem of maximizing Nash welfare (MNW) while allocating indivisible goods to asymmetric agents. The Nash welfare of an allocation is the weighted geometric mean of agents' utilities, and the allocation with maximum Nash welfare is known to satisfy several desirable fairness and efficiency properties. However, computing such an MNW allocation is APX-hard (hard to approximate) in general, even when agents have additive valuation functions. Hence, we aim to identify tractable classes which either admit a polynomial-time approximation scheme (PTAS) or an exact polynomial-time algorithm. To this end, we design a PTAS for finding an MNW allocation for the case of asymmetric agents with identical, additive valuations, thus generalizing a similar result for symmetric agents. Our techniques can also be adapted to give a PTAS for the problem of computing the optimal p-mean welfare. We also show that an MNW allocation can be computed exactly in polynomial time for identical agents with k-ary valuations when k is a constant, where every agent has at most k different values for the goods. Next, we consider the special case where every agent finds at most two goods valuable, and show that this class admits an efficient algorithm, even for general monotone valuations. In contrast, we show that when agents can value three or more goods, maximizing Nash welfare is APX-hard, even when agents are symmetric and have additive valuations. Finally, we show that for constantly many asymmetric agents with additive valuations, the MNW problem admits a fully polynomial-time approximation scheme (FPTAS).
READ FULL TEXT