Coalitions and announcements

ABSTRACT

Two currently active strands of research on logics for multi-agent systems are dynamic epistemic logic, focusing on the epistemic consequences of actions, and logics of coalitional ability, focusing on what coalitions of agents can achieve by cooperating strategically. In this paper we make a first attempt to bridge these topics by considering the question: "what can a coalition achieve by public announcements?". We propose, first, an extension of public announcement logic with constructs of the form <G>φ, where G is a set of agents, with the intuitive meaning that G can jointly make an announcement such that φ will be true afterwards. Second, we consider a setting where all agents can make (truthful) announcements at the same time, and propose a logic with a construct <[G]>φ, meaning that G can jointly make an announcement such that no matter what the other agents announce, φ will be true. The latter logic is closely related to Marc Pauly's Coalition Logic.

REFERENCES

• 1: T. Ågotnes. Action and knowledge in alternating-time temporal logic. Synthese (KRA), 149(2):377--409, 2006.
• 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: P. Balbiani , A. Baltag , H. van Ditmarsch , A. Herzig , T. Hoshi , T. de Lima, What can we achieve by arbitrary announcements?: A dynamic take on Fitch's knowability, Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge, June 25-27, 2007, Brussels, Belgium [doi>10.1145/1324249.1324259]
• 4: B. Brogaard and J. Salerno. Fitch's paradox of knowability. In E. Zalta, editor, The Stanford Encycl. of Philosophy. 2004.
• 5: Robert Goldblatt, Axiomatising the Logic of Computer Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 6: W. Jamroga. Some remarks on alternating temporal epistemic logic. In Proc. FAMAS'03, pages 133--140, 2003.
• 7: W. Jamroga and T. Ågotnes. Constructive knowledge: what agents can achieve under imperfect information. Journal of Applied Non-Classical Logics, 17(4):423--475, 2007.
• 8: Wojciech Jamroga , Wiebe van der Hoek, Agents that Know How to Play, Fundamenta Informaticae, v.63 n.2-3, p.185-219, May 2004
• 9: M. Pauly. A modal logic for coalitional power in games. Journal of Logic and Computation, 12(1):149--166, 2002.
• 10: J. Plaza. Logics of public communications. In Proc. of the 4th Intern. Symp. on Methodologies for Intel. Systems, pp. 201--216. Oak Ridge National Laboratory, 1989.
• 11: J. van Benthem. What one may come to know. Analysis, 64(2):95--105, 2004.
• 12: H. van Ditmarsch. The russian cards problem. Studia Logica, 75:31--62, 2003.
• 13: H. van Ditmarsch, W. van der Hoek, and B. Kooi. Dynamic Epistemic Logic. Springer, 2007.

INDEX TERMS

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

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

General Terms:
Theory

Keywords:
coalition logic, dynamic epistemic logic, public announcements