Nash Social Welfare in Multiagent Resource Allocation
Sara Ramezani, Ulle Endriss

Abstract:
We study different aspects of the multiagent resource allocation
problem when the objective is to find an allocation that maximizes
Nash social welfare, the product of the utilities of the individual
agents.  The Nash solution is an important welfare criterion that
combines efficiency and fairness considerations. We show that the
problem of finding an optimal outcome is NP-hard for a number of
different languages for representing agent preferences; we establish
new results regarding convergence to Nash-optimal outcomes in a
distributed negotiation framework; and we design and test algorithms
similar to those applied in combinatorial auctions for computing such
an outcome directly.