On optimal outcomes of negotiations over resources

ABSTRACT

We analyse scenarios in which self-interested agents negotiate with each other in order to agree on deals to exchange resources. We consider two variants of the framework, one where agents can use money to compensate other agents for disadvantageous deals, and one where this is not possible. In both cases, we analyse what types of deals are necessary and sufficient to guarantee an optimal outcome of negotiation. To assess whether a given allocation of resources should be considered optimal we borrow two concepts from welfare economics: maximal social welfare in the case of the framework with money and Pareto optimality in the case of the framework without money. We also show how conditions for optimal outcomes can change depending on properties of the utility functions used by agents to represent the values they ascribe to certain sets of resources.

REFERENCES

• 1: Martin Andersson , Tuomas Sandholm, Contract Type Sequencing for Reallocative Negotiation, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.154, April 10-13, 2000
• 2: K. J. Arrow. Social Choice and Individual Values. John Wiley and Sons, 2nd edition, 1963.
• 3: S. J. Brams and A. D. Taylor. Fair Division: From Cake-cutting to Dispute Resolution. Cambridge University Press, 1996.
• 4: Issues in Agent Communication, January 2000
• 5: U. Endriss, N. Maudet, F. Sadri, and F. Toni. Resource Allocation in Egalitarian Agent Societies. In Secondes Journées Francophones sur les Modèles Formels d'Interaction (MFI-2003), 2003. To appear.
• 6: Sarit Kraus, Strategic negotiation in multiagent environments, MIT Press, Cambridge, MA, 2001
• 7: Peter McBurney , Simon Parsons , Michael Wooldridge, Desiderata for agent argumentation protocols, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544836]
• 8: H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988.
• 9: J. Rawls. A Theory of Justice. Oxford University Press, 1971.
• 10: J. S. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994.
• 11: Fariba Sadri , Francesca Toni , Paolo Torroni, Dialogues for Negotiation: Agent Varieties and Dialogue Sequences, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.405-421, August 01-03, 2001
• 12: T. W. Sandholm. Contract Types for Satisficing Task Allocation: I Theoretical Results. In AAAI Spring Symposium: Satisficing Models, 1998.
• 13: R. G. Smith. The Contract Net Protocol: High-level Communication and Control in a Distributed Problem Solver. IEEE Transactions on Computers, C-29(12):1104--1113, 1980.

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
      Subjects: Economics

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

General Terms:
Theory

Keywords:
negotiation, resource allocation, welfare economics