Infinitesimal nash transfers for resource allocation in strong social alliances

ABSTRACT

We introduce a distributed and tractable mechanism for the allocation of continuously divisible resources to agents, that locally maximises the (Nash) product of their individual welfare. The mechanism involves specific m-resources-at-a-time multilateral deals over bits of resources, termed infinitesimal Nash transfers. It provides an effective way of building "strong social alliances", where in a social alliance agents fully cooperate for the global interest of society, and a strong social alliance has near-optimal utilitarian and egalitarian social welfare, as understood in social choice and welfare economics. The mechanism is scalable, can be distributed amongst agents and can be used to support, e.g., fair trade.

REFERENCES

• 1: Sylvain Bouveret , Michel Lemaître , Hélène Fargier , Jérôme Lang, Allocation of indivisible goods: a general model and some complexity results, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082747]
• 2: U. Endriss, N. Maudet, F. Sadri, and F. Toni. Negotiating socially optimal allocations of resources. Journal of Artificial Intelligence Research, 25:315--348, 2006.
• 3: J. Harsanyi. Rational Behavior and Bargaining Equilibrium in Games and Social Situations. Cambridge Univ. Press, 1977.
• 4: P.-A. Matt and F. Toni. The distributed negotiation of egalitarian allocations. In 1st International Workshop on Computational Social Choice, 2006.
• 5: P.-A. Matt and F. Toni. Egalitarian allocations of indivisible resources: theory and computation. In Cooperative Information Agents, 2006.
• 6: J. Nash. Two-person cooperative games. Econometrica, 21:1:128--140, 1953.
• 7: J. Rawls. A Theory of Justice. Harvard University Press, 1971.
• 8: G. Zlotkin and J. S. Rosenschein. Negotiation and task sharing among autonomous agents in cooperative domains. In IJCAI, pages 912--917, 1989.