David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
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)|
|Through your library||Configure|
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.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Total downloads1 ( #301,885 of 1,013,923 )
Recent downloads (6 months)0
How can I increase my downloads?