[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A formal analysis of interest-based negotiation

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

In multi-agent systems (MAS), negotiation provides a powerful metaphor for automating the allocation and reallocation of resources. Methods for automated negotiation in MAS include auction-based protocols and alternating offer bargaining protocols. Recently, argumentation-based negotiation has been accepted as a promising alternative to such approaches. Interest-based negotiation (IBN) is a form of argumentation-based negotiation in which agents exchange (1) information about their underlying goals; and (2) alternative ways to achieve these goals. However, the usefulness of IBN has been mostly established in the literature by appeal to intuition or by use of specific examples. In this paper, we propose a new formal model for reasoning about interest-based negotiation protocols. We demonstrate the usefulness of this framework by defining and analysing two different IBN protocols. In particular, we characterise conditions that guarantee their advantage (in the sense of expanding the set of individual rational deals) over the more classic proposal-based approaches to negotiation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Amgoud, L., Bonnefon, J.-F., Prade, H.: The logical handling of threats, rewards, tips, and warnings. In: Mellouli, K. (ed.) Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 9th European Conference, ECSQARU 2007, Proceedings, pp. 235–246, Hammamet, 31 October–2 November 2007

  2. Amgoud, L., Cayrol., C.: A reasoning model based on the production of acceptable arguments. Ann. Math. Artif. Intell. 34(1–3), 197–215 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  3. Amgoud, L., Dimopoulos, Y., Moraitis, P.: A unified and general framework for argumentation-based negotiation. In: AAMAS ’07: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems. ACM, New York (2007)

    Google Scholar 

  4. Amgoud, L., Prade, H.: Handling threats, rewards and explanatory arguments in a unified setting. Int. J. Intell. Syst. 20(12), 1195–1218 (2005)

    Article  MATH  Google Scholar 

  5. Chevaleyre, Y., Dunne, P.E., Endriss, U., Lang, J., Lemaître, M., Maudet, N., Padget, J., Phelps, S., Rodríguez-Aguilar, J.A., Sousa, P.: Issues in multiagent resource allocation. Informatica 30, 3–31 (2006)

    MATH  Google Scholar 

  6. Cohen, S.: Negotiating Skills for Managers. MacGraw-Hill, New York (2002)

    Google Scholar 

  7. Conitzer, V., Sandholm, T.: Computational criticisms of the revelation principle. In: Proceedings of the 5th ACM Conference on Electronic Commerce (EC-04), pp. 262–263 (2004)

  8. Cox, J.S., Durfee, E.: Discovering and exploiting synergy between hierarchical planning agents. In: Rosenschein, J., Sandholm, T., Wooldridge, M.J., Yokoo, M. (eds.) Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2003), pp. 281–288. ACM, New York (2003)

    Chapter  Google Scholar 

  9. Dunne, P.E., Chevaleyre, Y.: The complexity of deciding reachability properties of distributed negotiation schemes. Theor. Comp. Sci. 396(1-3), 113–144 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  10. Dunne, P.E., Wooldridge, M., Laurence, M.: The complexity of contract negotiation. Artif. Intell. 164(1–2), 23–46 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  11. Elvang-Gøransson, M., Krause, P., Fox, J.: Dialectic reasoning with inconsistent information. In: Heckerman, D., Mamdani, A. (eds.) Proceedings of the 9th Conference on Uncertainty in Artificial Intelligence, pp. 114–121. Morgan Kaufmann, Washington D.C. (1993)

    Google Scholar 

  12. Endris, U., Maudet, N., Sadri, F., Toni, F.: Negotiating socially optimal allocations of resources. J. Artif. Intell. Res. 25, 315–348 (2006)

    Google Scholar 

  13. Erol, K., Hendler, J., Nau, D.: Semantics for hierarchical task network planning. Technical Report CS-TR-3239, UMIACS-TR-94-31, Department of Computer Science, University of Maryland (1994)

  14. Faratin, P., Sierra, C., Jennings, N.R.: Using similarity criteria to make trade-offs in automated negotiations. Artif. Intell. 142(2), 205–237 (2002)

    Article  MathSciNet  Google Scholar 

  15. Fung, T., Kowalski, R.: The IFF proof procedure for abductive logic programming. J. Log. Program. 33(1), 151–165 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  16. Gal, Y., Pfeffer, A.: Modeling reciprocity in human bilateral negotiation. In: National Conference on Artificial Intelligence (AAAI), Vancouver (2007)

  17. Grosz, B., Kraus, S., Talman, S., Stossel, B., Havlin, M.: The influence of social dependencies on decision-making: initial investigations with a new game. In: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - (AAMAS 2004), vol. 2, pp. 294–301. IEEE Computer Society, New York (2004)

    Google Scholar 

  18. Heiskanen, P., Ehtamo, H., Hamalaien, R.: Constraint proposal method for computing Pareto solutions in multi-party negotiations. Eur. J. Oper. Res. 133(1), 44–61 (2001)

    Article  MATH  Google Scholar 

  19. Hiltrop, J., Udall, S.: The Essence of Negotiation. Prentice Hall, Englewood Cliffs (1995)

    Google Scholar 

  20. Jennings, N.R., Faratin, P., Lomuscio, A.R., Parsons, S., Sierra, C., Wooldridge, M.J.: Automated negotiation: prospects, methods and challenges. Int. J. Group Decis. Negot. 10(2), 199–215 (2001)

    Article  Google Scholar 

  21. Kraus, S., Sycara, K., Evenchik, A.: Reaching agreements through argumentation: a logical model and implementation. Artif. Intell. 104(1–2), 1–69 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  22. Lesser, V., Decker, K., Wagner, T., Carver, N., Garvey, A., Horling, B., Neiman, D., Podorozhny, R., NagendraPrasad, M., Raja, A., Vincent, R., Xuan, P., Zhang, X.: Evolution of the GPGP/TAEMS domain-independent coordination framework. Auton. Agents Multi-Agent Syst. 9(1), 87–143 (2004)

    Article  Google Scholar 

  23. Lin, R., Kraus, S., Wilkenfeld, J., Barry, J.: An automated agent for bilateral negotiation with bounded rational agents with incomplete information. In: Proc. of the 17th European Conference on Artificial Intelligence (ECAI), pp. 270–274 (2006)

  24. Mas-Colell, A., Whinston, M.D., Green, J.R.: Microeconomic Theory. Oxford University Press, New York (1995)

    Google Scholar 

  25. Parsons, S., Sierra, C., Jennings, N.: Agents that reason and negotiate by arguing. J. Log. Comput. 8(3), 261–292 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  26. Pasquier, P., Hollands, R., Dignum, F., Rahwan, I., Sonenberg, L.: An empirical study of interest-based negotiation. In: Gini, M.L., Kauffman, R.J., Sarppo, D., Dellarocas, C., Dignum, F. (eds.) Proceedings of the Ninth International Conference on Electronic Commerce (ICEC), pp. 339–348, University of Minnesota, Minneapolis, USA. ACM, New York (2007)

  27. Pruitt, D.G.: Negotiation Behavior. Academic, New York (1981)

    Google Scholar 

  28. Rahwan, I.: Interest-based negotiation in multi-agent systems. Ph.D. thesis, Department of Information Systems, University of Melbourne, Melbourne (2004)

    Google Scholar 

  29. Rahwan, I., Larson, K.: Mechanism design for abstract argumentation. In: Padgham, L., Parkes, D., Mueller, J., Parsons, S. (eds.) 7th International Joint Conference on Autonomous Agents & Multi Agent Systems, AAMAS’2008, Estoril, pp. 1031–1038 (2008)

  30. Rahwan, I., McBurney, P., Sonenberg, L.: Bargaining and argument-based negotiation: some preliminary comparisons. In: Rahwan, I., Moraitis, P., Reed, C. (eds.) Argumentation in Multi-Agent Systems, First International Workshop, ArgMAS 2004, New York, NY, USA, 19 July 2004. Revised Selected and Invited Papers. Lecture Notes in Artificial Intelligence, vol. 3366, pp. 176–191. Springer, Berlin (2004)

    Google Scholar 

  31. Rahwan, I., Pasquier, P., Sonenberg, L., Dignum, F.: On the benefits of exploiting underlying goals in argument-based negotiation. In: Holte, R.C., Howe, A. (eds.) Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-2007), pp. 116–121. Menlo Park (2007)

  32. Rahwan, I., Ramchurn, S.D., Jennings, N.R., McBurney, P., Parsons, S., Sonenberg, L.: Argumentation based negotiation. Knowl. Eng. Rev. 18(4), 343–375 (2003)

    Article  Google Scholar 

  33. Rahwan, I., Sonenberg, L., Dignum, F.: Towards interest-based negotiation. In: Rosenschein, J., Sandholm, T., Wooldridge, M.J., Yokoo, M. (eds.) Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2003), pp. 773–780. ACM, New York (2003)

    Chapter  Google Scholar 

  34. Raiffa, H.: The Art and Science of Negotiation. Harvard University Press, Cambridge (1982)

    Google Scholar 

  35. Ramchurn, S.D., Sierra, C., Godo, L., Jennings, N.R.: Negotiating using rewards. Artif. Intell. 171(10–15), 805–837 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  36. Rosenschein, J., Zlotkin, G.: Rules of Encounter: Designing Conventions for Automated Negotiation among Computers. MIT, Cambridge (1994)

    Google Scholar 

  37. Sadri, F., Toni, F., Torroni, P.: Logic agents, dialogues and negotiation: an abductive approach. In: Stathis, K., Schroeder, M. (ed.) Proceedings of the AISB 2001 Symposium on Information Agents for E-Commerce (2001)

  38. Sandholm, T.W.: Distributed rational decision making. In: Weiss, G. (ed.) Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, pp. 201–258. MIT, Cambridge (1999)

    Google Scholar 

  39. Wolfstetter, E.: Auctions: an introduction. J. Econ. Surv. 10, 367–420 (1996)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Informatics, The British University in Dubai, P.O. Box 502216, Dubai, United Arab Emirates

    Iyad Rahwan

  2. School of Informatics, University of Edinburgh, Edinburgh, UK

    Iyad Rahwan

  3. School of Interactive Art and Technology, Simon Fraser University, Vancouver, Canada

    Philippe Pasquier

  4. Dept. of Information Systems, University of Melbourne, Parkville, Victoria, 3010, Australia

    Liz Sonenberg

  5. Dept. of Information & Computing Sciences, Utrecht University, Utrecht, The Netherlands

    Frank Dignum

Authors
  1. Iyad Rahwan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Philippe Pasquier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Liz Sonenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Frank Dignum
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Iyad Rahwan.

Additional information

This is a revised and expanded version of a paper that appeared in the proceedings of AAAI 2007 [31].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rahwan, I., Pasquier, P., Sonenberg, L. et al. A formal analysis of interest-based negotiation. Ann Math Artif Intell 55, 253 (2009). https://doi.org/10.1007/s10472-009-9145-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10472-009-9145-6

Keywords

Mathematics Subject Classifications (2000)

Search

Navigation