Knowledge condition games

Journal of Logic, Language and Information 15 (4):425-452 (2006)
  Copy   BIBTEX

Abstract

Understanding the flow of knowledge in multi-agent protocols is essential when proving the correctness or security of such protocols. Current logical approaches, often based on model checking, are well suited for modeling knowledge in systems where agents do not act strategically. Things become more complicated in strategic settings. In this paper we show that such situations can be understood as a special type of game – a knowledge condition game – in which a coalition “wins” if it is able to bring about some epistemic condition. This paper summarizes some results relating to these games. Two proofs are presented for the computational complexity of deciding whether a coalition can win a knowledge condition game with and without opponents (Σ2P-complete and NP-complete respectively). We also consider a variant of knowledge condition games in which agents do not know which strategies are played, and prove that under this assumption, the presence of opponents does not affect the complexity. The decision problem without opponents is still NP-complete, but requires a different proof.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2009-01-28

Downloads
37 (#375,012)

6 months
1 (#1,042,085)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Citations of this work

Reasoning About Preference Dynamics.Fenrong Liu - 2011 - Dordrecht, Netherland: Springer Verlag.

Add more citations