Knowledge condition games
Journal of Logic, Language and Information 15 (4) (2006)
| 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. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesDavid H. Sanford (1976). The Direction of Causation and the Direction of Conditionship. Journal of Philosophy 73 (8):193-207.
Cristina Bicchieri (1988). Backward Induction Without Common Knowledge. PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:329 - 343.
Johan Van Benthem (2003). Logic Games Are Complete for Game Logics. Studia Logica 75 (2):183 - 203.
Johan van Benthem (2003). Logic Games Are Complete for Game Logics. Studia Logica 75 (2).
Gerard van Der Laan & René van Den Brink (2002). A Banzhaf Share Function for Cooperative Games in Coalition Structure. Theory and Decision 53 (1):61-86.
Christoph Kelp (2009). Knowledge and Safety. Journal of Philosophical Research 34:21-31.
Luciano Floridi (2005). Consciousness, Agents and the Knowledge Game. Minds and Machines 15 (3):415-444.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads1 ( #274,830 of 549,088 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
