A normal simulation of coalition logic and an epistemic extension

ABSTRACT

In this paper we show how coalition logic can be reduced to the fusion of a normal modal STIT logic for agency and a standard normal temporal logic for discrete time, and how this multi-modal system can be suitably extended with an epistemic modality. Both systems are complete, and we provide a new axiomatization for the STIT-fragment. The epistemic extension enables us to express that agents see to something under uncertainty about the present state or uncertainty about which action is being taken. In accordance with established terminology in the planning community, we call this version of STIT the 'conformant STIT'. The conformant STIT enables us to express that agents are able to perform a uniform strategy. As a final word of recommendation for this paper we want to point out that its subject is at the junction of four academic fields, viz. modal logic, philosophy, game-theory and AI-planning.

REFERENCES

• 1: 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]
• 2: {BdRV01} Patrick Blackburn, Maarten de Rijke, and Yde Venema. Modal Logic. Cambridge University Press, 2001.
• 3: {BGH⁺07} Philippe Balbiani, Olivier Gasquet, Andreas Herzig, François Schwarzentruber, and Nicolas Troquard. Coalition games over Kripke semantics. In Cédric Dégremont, Laurent Keiff, and Helge Rückert, editors, Festschrift in Honour of Shahid Rahman. College Publications, 2007.
• 4: {BHT06} Jan Broersen, Andreas Herzig, and Nicolas Troquard. A STIT-extension of ATL. In Tenth European Conference on Logics in Artificial Intelligence (JELIA'06), Liverpool, England, UK, volume 4160 of Lecture Notes in Artificial Intelligence, pages 69--81. Springer, 2006.
• 5: {BM04} A. Baltag and L. S. Moss. Logics for epistemic programs. Synthese, 139:165--224, 2004.
• 6: {BPX01} N. Belnap, M. Perloff, and M. Xu. Facing the future: agents and choices in our indeterminist world. Oxford, 2001.
• 7: {GB96} Robert P. Goldman and Mark S. Boddy. Expressive planning and explicit knowledge. In Proceedings of the 3rd International Conference on Artificial Intelligence Planning Systems (AIPS-96), pages 110--117. AAAI press, 1996.
• 8: Andreas Herzig , Nicolas Troquard, Knowing how to play: uniform choices in logics of agency, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160666]
• 9: Wojciech Jamroga , Thomas Ågotnes, What agents can achieve under incomplete information, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160672]
• 10: Wojciech Jamroga , Wiebe van der Hoek, Agents that Know How to Play, Fundamenta Informaticae, v.63 n.2-3, p.185-219, April 2004
• 11: Henry Kautz , Bart Selman, Planning as satisfiability, Proceedings of the 10th European conference on Artificial intelligence, p.359-363, August 1992, Vienna, Austria
• 12: {OR94} Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. The MIT Press, 1994.
• 13: {Pau01} Marc Pauly. Logic for Social Software. PhD thesis, University of Amsterdam, 2001. ILLC Dissertation Series 2001-10.
• 14: {Pau02} Marc Pauly. A modal logic for coalitional power in games. Journal of Logic and Computation, 12(1):149--166, 2002.
• 15: {Sch04} P. Y. Schobbens. Alternating-time logic with imperfect recall. Electronic Notes in Theoretical Computer Science, 85(2), 2004.
• 16: {Sch07} François Schwarzentruber. Master's thesis, Unviversité Toulouse 3, 2007.
• 17: Wiebe van der Hoek , Michael Wooldridge, Tractable multiagent planning for epistemic goals, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545095]