David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Logic, Language and Information 15 (4):425-452 (2006)
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||complexity epistemic logic game theory imperfect information knowledge protocol strategy|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
Jaakko Hintikka (1962). Knowledge and Belief. Ithaca, N.Y.,Cornell University Press.
John von Neumann & Oskar Morgenstern (1945). Theory of Games and Economic Behavior. Journal of Philosophy 42 (20):550-554.
Wiebe van der Hoek & Michael Wooldridge (2003). Cooperation, Knowledge, and Time: Alternating-Time Temporal Epistemic Logic and its Applications. Studia Logica 75 (1):125-157.
Citations of this work BETA
No citations found.
Similar books and articles
David 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):183-203.
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.
Added to index2009-01-28
Total downloads9 ( #363,863 of 1,907,219 )
Recent downloads (6 months)3 ( #276,350 of 1,907,219 )
How can I increase my downloads?