Abstract: How should one divide $m$ goods between $n$ agents, given the utility each agent has when allocated a subset of goods? Allocations which maximize the Nash Social Welfare --- the product of agent utilities for their allocation --- are known to possess a number of natural and agreeable properties. Unfortunately, maximizing the Nash Social Welfare is known to be APX-hard, even when agent utility functions are additive over the set of goods.
We present an algorithm that for the general case of subadditive utility functions for the agents, obtains an $O(n)$-approximation to the optimal Nash Social Welfare, given value oracle access to the utility functions. This improves upon a previous $O(n log n)$ algorithm for submodular utilities (SODA '20). Our approximation ratio is tight for subadditive utilities and for value oracle access.
This is joint work with Siddharth Barman, Anand Krishna, and Ranjani Sundaram.
