Nash Social Welfare in Multiagent Resource Allocation
Sara Ramezani Khorshid Doost
Abstract:
Multiagent resource allocation studies the distribution of resources
among agents in different ways depending on the criteria that are to
be satisfied. The allocation of resources can be carried out in a
centralized or distributed manner. The resources may be discrete or
continuous, sharable or not, and the criteria may range over a wide
array of different requirements, for instance optimizing various
social welfare functions or fairness criteria. Many such problems have
been studied extensively in the literature.
The Nash social welfare function (also referred to as the Nash
collective utility function) is the product of the utilities of
individual agents. Because of its mathematical structure, increasing
NSW gives a balance between increasing the utilitarian welfare of the
society, which is the sum of the utilities of agents, and fairness
among agents. This dissertation aims at studying multiagent resource
allocation with indivisible unsharable goods with regard to Nash
social welfare. We study various properties of the Nash collective
utility function in this context such as convergence of agent
negotiation, communication and computational complexity. We also
devise and implement a new heuristic algorithm for solving the problem
of optimizing Nash social welfare, carry out some experiments in this
regard and analyze their results.