How equitable is rational negotiation?

ABSTRACT

Notions of fairness have recently received increased attention in the context of resource allocation problems, pushed by diverse applications where not only pure utilitarian efficiency is sought. In this paper, we study a framework where allocations of goods result from distributed negotiation conducted by autonomous agents implementing very simple deals. Assuming that these agents are strictly self-interested, we investigate how equitable the outcomes of such negotiation processes are. We first discuss a number of methodological issues raised by this study, pertaining in particular to the design of suitable payment functions as a means of distributing the social surplus generated by a deal amongst the participating agents. By running different experiments, we finally identify conditions favouring equitable outcomes.

REFERENCES

• 1: K. J. Arrow, A. K. Sen, and K. Suzumura, editors. Handbook of Social Choice and Welfare. North-Holland, 2002.
• 2: 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]
• 3: S. J. Brams and A. D. Taylor. Fair Division: From Cake-cutting to Dispute Resolution. Cambridge University Press, 1996.
• 4: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 5: Paul E. Dunne , Michael Wooldridge , Michael Laurence, The complexity of contract negotiation, Artificial Intelligence, v.164 n.1-2, p.23-46, May 2005 [doi>10.1016/j.artint.2005.01.006]
• 6: Ulle Endriss , Nicolas Maudet, On the Communication Complexity of Multilateral Trading: Extended Report, Autonomous Agents and Multi-Agent Systems, v.11 n.1, p.91-107, July 2005 [doi>10.1007/s10458-005-1080-2]
• 7: U. Endriss, N. Maudet, F. Sadri, and F. Toni. Negotiating socially optimal allocations of resources. Journal of Artificial Intelligence Research, 2006. To appear.
• 8: A. Giovannucci, J. A. Rodríguez-Aguilar, A. Reyes, F. X. Noria, and J. Cerquides. iBundler: An agent-based decision support service for combinatorial negotiations. In Proc. AAAI-2004. AAAI Press, 2004.
• 9: G. Jonker, J.-J. Meyer, and F. Dignum. Efficiency and fairness in air traffic control. In Proc. 17th Belgian-Dutch Conf. on Artificial Intelligence, 2005.
• 10: M. Lemaître, G. Verfaillie, F. Jouhaud, J.-M. Lachiver, and N. Bataille. Selecting and scheduling observations of agile satellites. Aerospace Sciences and Technology, 6:367--381, 2002.
• 11: Kevin Leyton-Brown , Mark Pearson , Yoav Shoham, Towards a universal test suite for combinatorial auction algorithms, Proceedings of the 2nd ACM conference on Electronic commerce, p.66-76, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352879]
• 12: H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988.
• 13: R. Porter, Y. Shoham, and M. Tennenholtz. Fair imposition. Journal of Economic Theory, 118(2):209--228, 2004.
• 14: J. S. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994.
• 15: T. W. Sandholm. Contract types for satisficing task allocation: I Theoretical results. In Proc. AAAI Spring Symposium: Satisficing Models, 1998.
• 16: Tuomas W. Sandholm, Distributed rational decision making, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 17: Michael Woolridge , Michael J. Wooldridge, Introduction to Multiagent Systems, John Wiley & Sons, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Economics, Experimentation, Theory

Keywords:
fair division, multiagent resource allocation, negotiation, social welfare