Modelling coalitions: ATL + argumentation

ABSTRACT

In the last few years, argumentation frameworks have been successfully applied to multi agent systems. Recently, argumentation has been used to provide a framework for reasoning about coalition formation. At the same time alternating-time temporal logic has been used to reason about the behavior and abilities of coalitions of agents. However, ATL operators account only for the existence of successful strategies of coalitions. They do not consider whether coalitions can be actually formed.

This paper is an attempt to combine both frameworks and to develop a logic through which we can reason at the same time (1) about abilities of coalitions of agents and (2) about the formation of coalitions. We provide a formal extension of ATL, ATL^c, in which the actual computation of the coalition is modelled in terms of argumentation semantics. We show that ATL^c's proof theory can be understood as a natural extension of the model checking procedure used in ATL.

REFERENCES

• 1: T. Ågotnes, W. van der Hoek, and M. Wooldridge. Quantified coalition logic. In IJCAI, pages 1181--1186, 2007.
• 2: Rajeev Alur , Thomas A. Henzinger , Orna Kupferman, Alternating-time temporal logic, Journal of the ACM (JACM), v.49 n.5, p.672-713, September 2002 [doi>10.1145/585265.585270]
• 3: L. Amgoud. An argumentation-based model for reasoning about coalition structures. In ArgMAS, pages 217--228, 2005.
• 4: Leila Amgoud, Towards a formal model for task allocation via coalition formation, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082685]
• 5: S. Borgo. Coalitions in action logic. In IJCAI, pages 1822--1827, 2007.
• 6: N. Bulling and W. Jamroga. A logic for reasoning about rational agents: Yet another attempt. In L. Czaja, editor, Proceedings of CS&P, 2007.
• 7: M. Caminada. Semi-stable semantics. In Intl. Conference on Computational Models of Argument (COMMA), pages 121--130, 2006.
• 8: Carlos Iván Chesñevar , Ana Gabriela Maguitman , Ronald Prescott Loui, Logical models of argument, ACM Computing Surveys (CSUR), v.32 n.4, p.337-383, Dec. 2000 [doi>10.1145/371578.371581]
• 9: Edmund M. Clarke, Jr. , Orna Grumberg , Doron A. Peled, Model checking, MIT Press, Cambridge, MA, 2000
• 10: Phan Minh Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence, v.77 n.2, p.321-357, Sept. 1995 [doi>10.1016/0004-3702(94)00041-X]
• 11: Paul E. Dunne , T. J. M. Bench-Capon, Two party immediate response disputes: properties and efficiency, Artificial Intelligence, v.149 n.2, p.221-250, October 2003 [doi>10.1016/S0004-3702(03)00076-6]
• 12: Hiromitsu Hattori , Takayuki Ito , Tadachika Ozono , Toramatsu Shintani, An Approach to Coalition Formation Using Argumentation-Based Negotiation in Multi-agent Systems, Proceedings of the 14th International conference on Industrial and engineering applications of artificial intelligence and expert systems: engineering of intelligent systems, p.687-696, June 04-07, 2001
• 13: Wojciech Jamroga , Nils Bulling, A framework for reasoning about rational agents, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329232]
• 14: W. Jamroga and N. Bulling. A logic for reasoning about rational agents. In F. Sadri and K. Satoh, editors, Proceedings of CLIMA '07, pages 54--69, Porto, Portugal, 2007. Univesidade Do Porto.
• 15: Souhila Kaci , Leendert Torre , Emil Weydert, On the Acceptability of Incompatible Arguments, Proceedings of the 9th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, October 31-November 02, 2007, Hammamet, Tunisia [doi>10.1007/978-3-540-75256-1_24]
• 16: Nishan C. Karunatillake , Nicholas R. Jennings , Iyad Rahwan , Sarvapali D. Ramchurn, Managing social influences through argumentation-based negotiation, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160710]
• 17: M. Pauly. A modal logic for coalitional power in games. J. Log. Comput., 12(1):149--166, 2002.
• 18: H. Prakken and G. Vreeswijk. Logical Systems for Defeasible Argumentation. In D. Gabbay and F. Guenther, editors, Handbook of Phil. Logic, pages 219--318. Kluwer, 2002.
• 19: Iyad Rahwan , Leila Amgoud, An argumentation based approach for practical reasoning, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160696]
• 20: I. Rahwan, P. Pasquier, L. Sonenberg, and F. Dignum. On the benefits of exploiting underlying goals in argument-based negotiation. In Proc. of AAAI Conf., pages 116--121, 2007.
• 21: Yuqing Tang , Simon Parsons, Argumentation-based dialogues for deliberation, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082557]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Theory

Keywords:
argumentation, coalition formation, game theory, logical foundations, multi-agent systems, temporal logic