skip to main content
10.5555/1402298.1402317acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Quantifying over coalitions in epistemic logic

Published: 12 May 2008 Publication History

Abstract

Some natural epistemic properties which may arise in applications can only be expressed in standard epistemic logic by formulae which are exponentially long in the number of agents in the system. An example is the property "at least m agents know that at most n agents know ϕ". We present Epistemic Logic with Quantification over Coalitions (ELQC), where the standard common knowledge operator has been replaced allowing expressions of the form <ϕ> and [P]cϕ where P is a coalition predicate, meaning that there is a coalition satisfying P which have common knowledge of ϕ and that all coalitions satisfying P have common knowledge of ϕ, respectively; and similarly for distributed knowledge and everybody-knows. While the language is no more expressive than standard epistemic logic, it is exponentially more succinct. We give a sound and complete axiomatisation for ELQC, and characterise the complexity of its model checking problem.

References

[1]
T. Ågotnes, W. van der Hoek, and M. Wooldridge. Quantified coalition logic. In Proc. IJCAI-07, 2007.
[2]
E. M. Clarke, O. Grumberg, and D. A. Peled. Model Checking. MIT Press, 2000.
[3]
R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning About Knowledge. MIT Press, 1995.
[4]
J. Y. Halpern and Y. Moses. A guide to completeness and complexity for modal logics of knowledge and belief. Artif. Intell., 54:319--379, 1992.
[5]
B. Kooi. Dynamic term-modal logic. In A Meeting of the Minds, pages 173--186, College Publications, 2007.
[6]
F. Laroussinie, N. Markey, and Ph. Schnoebelen. Model checking CTL+ and FCTL is hard. In Proc. FoSSaCS'01, pages 318--331. Springer-Verlag, 2001.
[7]
C. Lutz. Complexity and succinctness of public announcement logic. In Proc. AAMAS-2006, 2006.
[8]
J.-J. Ch. Meyer and W. van der Hoek. Epistemic Logic for Al and Computer Science. Cambridge UP, 1995.
[9]
C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
[10]
F. Raimondi and A. Lomuscio. Automatic verification of multi-agent systems by model checking via ordered binary decision diagrams. Jnl of Appl. Logic, 5:235--251, 2007.
[11]
H. van Ditmarsch, W. van der Hoek, and B. Kooi. Dynamic Epistemic Logic, volume 337 of Synthese Library. Springer-Verlag, 2007.

Cited By

View all
  • (2014)On the relative succinctness of modal logics with union, intersection and quantificationProceedings of the 2014 international conference on Autonomous agents and multi-agent systems10.5555/2615731.2615788(341-348)Online publication date: 5-May-2014

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2
May 2008
673 pages
ISBN:9780981738116

Sponsors

In-Cooperation

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 12 May 2008

Check for updates

Author Tags

  1. complexity
  2. epistemic logic
  3. expressivity
  4. model checking
  5. succinctness

Qualifiers

  • Research-article

Conference

AAMAS08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2014)On the relative succinctness of modal logics with union, intersection and quantificationProceedings of the 2014 international conference on Autonomous agents and multi-agent systems10.5555/2615731.2615788(341-348)Online publication date: 5-May-2014

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media