A belief revision approach for argumentation-based negotiation agents

Pilotti, P. ; Casali, A. ; Chesñevar, C.

International Journal of Applied Mathematics and Computer Science, Tome 25 (2015) no. 3, pp. 455-470.

Résumé

Negotiation is an interaction that happens in multi-agent systems when agents have conflicting objectives and must look for an acceptable agreement. A typical negotiating situation involves two agents that cannot reach their goals by themselves because they do not have some resources they need or they do not know how to use them to reach their goals. Therefore, they must start a negotiation dialogue, taking also into account that they might have incomplete or wrong beliefs about the other agent’s goals and resources. This article presents a negotiating agent model based on argumentation, which is used by the agents to reason on how to exchange resources and knowledge in order to achieve their goals. Agents that negotiate have incomplete beliefs about the others, so that the exchange of arguments gives them information that makes it possible to update their beliefs. In order to formalize their proposals in a negotiation setting, the agents must be able to generate, select and evaluate arguments associated with such offers, updating their mental state accordingly. In our approach, we will focus on an argumentation-based negotiation model between two cooperative agents. The arguments generation and interpretation process is based on belief change operations (expansions, contractions and revisions), and the selection process is a based on a strategy. This approach is presented through a high-level algorithm implemented in logic programming. We show various theoretical properties associated with this approach, which have been formalized and proved using Coq, a formal proof management system. We also illustrate, through a case study, the applicability of our approach in order to solve a slightly modified version of the well-known home improvement agents problem. Moreover, we present various simulations that allow assessing the impact of belief revision on the negotiation process.

Détail

Keywords: argumentation based negotiation, collaborative agents, belief revision, multi-agent system

Bibliographie

[1] Alchourrón, C., Gärdenfors, P. and Makinson, D. (1985). On the logic of theory change: Partial meet contraction and revision functions, Journal of Symbolic Logic 50(2): 510–530.

[2] Amgoud, L., Dimopoulos, Y. and Moraitis, P. (2007). A unified and general framework for argumentation-based negotiation, 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007), Honolulu, HI, USA, p. 158.

[3] Amgoud, L., Parsons, S. and Maudet, N. (2000). Arguments, dialogue and negotiation, inW. Horn (Ed.), Proceedings of the European Conference on Artificial Intelligence (ECAI 2000), IOS Press, Berlin, pp. 338–342.

[4] Amgoud, L. and Vesic, S. (2011). A formal analysis of the outcomes of argumentation-based negotiations, 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan, pp. 1237–1238.

[5] Bonanno, G., Delgrande, J., Lang, J. and Rott, H. (2009). Special issue on formal models of belief change in rational agents, Journal of Applied Logic 7(4): 363.

[6] Dix, J., Hansson, S.O., Kern-Isberner, G. and Simari, G.R. (2013). Belief change and argumentation in multi-agent scenarios (Dagstuhl seminar 13231), Dagstuhl Reports 3(6): 1–21.

[7] Dung, P.M. (1995). On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77(2): 321–357.

[8] Falappa, M., Garcia, A., Kern-Isberner, G. and Simari, G. (2011). On the evolving relation between belief revision and argumentation, Knowledge Engineering Review 26(1): 35–43.

[9] Fermé, E., Saez, K. and Sanz, P. (2003). Multiple kernel contraction, Studia Logica: An International Journal for Symbolic Logic 73(2): 183–195.

[10] Hansson, S. (1994). Kernel contraction, The Journal of Symbolic Logic 59(3): 845–859.

[11] Hansson, S. (1999). A Textbook of Belief Dynamics: Theory Change and Database Updating, Applied Logic Series, Kluwer Academic Publishers, Dordrecht.

[12] Jennings, N.R., Faratin, P., Lomuscio, A.R., Parsons, S., Sierra, C. and Wooldridge, M. (2001). Automated negotiation: Prospects, methods and challenges, International Journal of Group Decision and Negotiation 10(2): 199–215.

[13] Kraus, S., Sycara, K. and Evenchik, A. (1998). Reaching agreements through argumentation: A logical model and implementation, Artificial Intelligence 104(1–2): 1–69.

[14] Parsons, S., Sierra, C. and Jennings, N.R. (1998). Agents that reason and negotiate by arguing, Journal of Logic and Computation 8(3): 261–292.

[15] Pasquier, P., Hollands, R., Rahwan, I., Dignum, F. and Sonenberg, L. (2011). An empirical study of interest-based negotiation, Autonomous Agents and Multi-Agent Systems 22(2): 249–288.

[16] Pilotti, P., Casali, A. and Chesñevar, C. (2014). Incorporating object features in collaborative argumentation-based negotiation agents, Brazilian Conference on Intelligent Systems (BRACIS)/Encontro Nacional de Inteligencia Artificial e Computacional (ENIAC), Sao Carlos, SP, Brazil, pp. 31–37.

[17] Rahwan, I., Pasquier, P., Sonenberg, L. and Dignum, F. (2007). On the benefits of exploiting underlying goals in argument-based negotiation, 22nd Conference on Artificial Intelligence (AAAI), Vancouver, Canada, pp. 116–121.

[18] Rahwan, I., Ramchurn, S.D., Jennings, N.R., Mcburney, P., Parsons, S. and Sonenberg, L. (2003). Argumentation-based negotiation, Knowledge Engineering Review 18(4): 343–375.

[19] Ramchurn, S.D., Jennings, N.R. and Sierra, C. (2003). Persuasive negotiation for autonomous agents: A rhetorical approach, Proceedings of the IJCAI Workshop on Computational Models of Natural Argument, Acapulco, Mexico, pp. 9–17.

[20] Rosenschein, J.S. and Zlotkin, G. (1994). Rules of Encounter: Designing Conventions for Automated Negotiation among Computers, MIT Press, Cambridge, MA.

[21] Sadri, F., Toni, F. and Torroni, P. (2001). Logic agents, dialogues and negotiation: An abductive approach, Proceedings of the AISB’01 Convention, York, UK, pp. 5–12.

[22] Sakama, C. (2011). Dishonest reasoning by abduction, 22nd International Joint Conference on Artificial Intelligence, Barcelona, Spain, pp. 1063–1064.

[23] Sierra, C. and Debenham, J.K. (2007). The logic negotiation model, 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007), Honolulu, HI, USA, p. 243.

[24] Zhang, D. (2010). A logic-based axiomatic model of bargaining, Artificial Intelligence 174(16–17): 1307–1322.

[25] Zhang, D., Foo, N., Meyer, T. and Kwok, R. (2004). Negotiation as mutual belief revision, Proceedings of AAAI04, San Jose, CA, USA, pp. 317–322.