  We study the problem of approximating maximum Nash social welfare (NSW) when
allocating m indivisible items among n asymmetric agents with submodular
valuations. The NSW is a well-established notion of fairness and efficiency,
defined as the weighted geometric mean of agents' valuations. For special cases
of the problem with symmetric agents and additive(-like) valuation functions,
approximation algorithms have been designed using approaches customized for
these specific settings, and they fail to extend to more general settings.
Hence, no approximation algorithm with factor independent of m is known either
for asymmetric agents with additive valuations or for symmetric agents beyond
additive(-like) valuations.
  In this paper, we extend our understanding of the NSW problem to far more
general settings. Our main contribution is two approximation algorithms for
asymmetric agents with additive and submodular valuations respectively. Both
algorithms are simple to understand and involve non-trivial modifications of a
greedy repeated matchings approach. Allocations of high valued items are done
separately by un-matching certain items and re-matching them, by processes that
are different in both algorithms. We show that these approaches achieve
approximation factors of O(n) and O(n log n) for additive and submodular case
respectively, which is independent of the number of items. For additive
valuations, our algorithm outputs an allocation that also achieves the fairness
property of envy-free up to one item (EF1).
  Furthermore, we show that the NSW problem under submodular valuations is
strictly harder than all currently known settings with an e/(e-1) factor of the
hardness of approximation, even for constantly many agents. For this case, we
provide a different approximation algorithm that achieves a factor of e/(e-1),
hence resolving it completely.
