×

A formal analysis of interest-based negotiation. (English) Zbl 1186.68477

Summary: 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.

MSC:

68T42 Agent technology and artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI Link

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 · Zbl 1148.68498
[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) · Zbl 1002.68172 · doi:10.1023/A:1014490210693
[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) · Zbl 1135.68581
[4] Amgoud, L., Prade, H.: Handling threats, rewards and explanatory arguments in a unified setting. Int. J. Intell. Syst. 20(12), 1195–1218 (2005) · Zbl 1085.68155 · doi:10.1002/int.20109
[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) · Zbl 1152.91455
[6] Cohen, S.: Negotiating Skills for Managers. MacGraw-Hill, New York (2002)
[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)
[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) · Zbl 1147.91018 · doi:10.1016/j.tcs.2008.01.031
[10] Dunne, P.E., Wooldridge, M., Laurence, M.: The complexity of contract negotiation. Artif. Intell. 164(1–2), 23–46 (2005) · Zbl 1132.68539 · doi:10.1016/j.artint.2005.01.006
[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)
[12] Endris, U., Maudet, N., Sadri, F., Toni, F.: Negotiating socially optimal allocations of resources. J. Artif. Intell. Res. 25, 315–348 (2006)
[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) · Zbl 01856166 · doi:10.1016/S0004-3702(02)00290-4
[15] Fung, T., Kowalski, R.: The IFF proof procedure for abductive logic programming. J. Log. Program. 33(1), 151–165 (1997) · Zbl 0890.68029 · doi:10.1016/S0743-1066(97)00026-5
[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)
[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) · Zbl 0989.90082 · doi:10.1016/S0377-2217(00)00179-X
[19] Hiltrop, J., Udall, S.: The Essence of Negotiation. Prentice Hall, Englewood Cliffs (1995)
[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) · doi:10.1023/A:1008746126376
[21] Kraus, S., Sycara, K., Evenchik, A.: Reaching agreements through argumentation: a logical model and implementation. Artif. Intell. 104(1–2), 1–69 (1998) · Zbl 0908.68033 · doi:10.1016/S0004-3702(98)00078-2
[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) · Zbl 05387304 · doi:10.1023/B:AGNT.0000019690.28073.04
[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)
[25] Parsons, S., Sierra, C., Jennings, N.: Agents that reason and negotiate by arguing. J. Log. Comput. 8(3), 261–292 (1998) · Zbl 0904.68061 · doi:10.1093/logcom/8.3.261
[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)
[28] Rahwan, I.: Interest-based negotiation in multi-agent systems. Ph.D. thesis, Department of Information Systems, University of Melbourne, Melbourne (2004)
[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) · Zbl 1117.68513
[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) · Zbl 1135.68591
[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) · Zbl 02178810 · doi:10.1017/S0269888904000098
[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)
[34] Raiffa, H.: The Art and Science of Negotiation. Harvard University Press, Cambridge (1982)
[35] Ramchurn, S.D., Sierra, C., Godo, L., Jennings, N.R.: Negotiating using rewards. Artif. Intell. 171(10–15), 805–837 (2007) · Zbl 1168.68570 · doi:10.1016/j.artint.2007.04.014
[36] Rosenschein, J., Zlotkin, G.: Rules of Encounter: Designing Conventions for Automated Negotiation among Computers. MIT, Cambridge (1994)
[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)
[39] Wolfstetter, E.: Auctions: an introduction. J. Econ. Surv. 10, 367–420 (1996) · doi:10.1111/j.1467-6419.1996.tb00018.x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.