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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agotness, T., 2004, “A note on syntactic characterization of incomplete information in ATEL”. in: S. van Otterloo, P. McBurney, W. van der Hoek and M. Wooldridge (eds.): Proceedings of the First Knowledge and Games Workshop. University of Liverpool, pp. 34–42.
Alur, R., Henzinger, T. A., and Kupferman, O., 2002, “Alternating-time temporal logic”, Journal of the ACM 49(5), 672–713.
Aumann, R., 1995, “Backward induction and common knowledge of rationality”, Games and Economic Behaviour 8, 6–19.
Baltag, A., Moss, L., and Solecki, S., 2002, “The logic of public announcements, common knowledge and private suspicions”, Originally presented at TARK 98, accepted for publication in Annals of Pure and Applied Logic.
Bonanno, G., 2004, “Memory implies von Neumann-Morgenstern games”, Knowledge Rationality and Action, to appear.
Cormen, T., Leiserson, C., and Rivest, R., 1990, Introduction to Algorithms. The MIT Press: Cambridge, MA.
de Bruin, B.: 2004, “Explaining games- on the logic of game theoretic explanations”. Ph.D. Thesis, University of Amsterdam, Amsterdam. ILLC series DS-2004-03.
Fagin, R., Halpern, J., Moses, Y. and Vardi, M.: 1995, Reasoning About Knowledge. The MIT Press: Cambridge, MA.
Halpern, J. Y. and Vardi, M. Y., 1989, “The complexity of reasoning about knowledge and time. I. Lower bounds”. Journal of Computer and System Sciences 38, 195–237.
Harrenstein, B., van der Hoek, W., Meyer, J.-J. C., and Witteveen, C., 2003, “A modal characterization of Nash Equilibrium”, Fundamenta Informaticae 57(2–4), 281–321.
Hintikka, J., 1962, Knowledge and Belief: An Introduction to the Logic of the Two Notions. Cornell University Press: Ithaca, NY.
Holzmann, G., 1991, Design and Validation of Computer Protocols. Prentice Hall International: Hemel Hempstead, England.
Jamroga, W. and van der Hoek, W., 2003, “Some remarks on alternating-time temporal epistemic logic”, submitted.
Jonker, G., 2003, “Feasible strategies in alternating-time temporal epistemic logic”, Universiteit Utrecht Master Thesis.
Koller, D. and Pfeffer, A., 1995, “Generating and solving imperfect information games”, in: Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI), Montreal, pp. 1185–1192.
Meyer, J.-J. C. and van der Hoek, W., 1995, Epistemic Logic for AI and Computer Science, Cambridge University Press: Cambridge, England.
Osborne, M. J. and Rubinstein, A., 1994, A Course in Game Theory, The MIT Press: Cambridge, MA.
Papadimitriou, C., 1994, Computational Complexity, Addison Wesley Longman.
Pauly, M., 2001, “Logic for Social Software”. Ph.D. Thesis, University of Amsterdam, ILLC Dissertation Series 2001-10.
Roberts, M., van der Hoek, W., and Wooldridge, M., 2005, “Knowledge and social laws”. in Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Utrecht.
Schelling, T. C., 1960, The Strategy of Conflict, Cambridge, Mass.: Harvard U.P.
Schneier, B., 1996, Applied Cryptography, John Wiley & Sons.
Schobbens, P.-Y., 2004, “Alternating-time logic with imperfect recall”, in W. van der Hoek, A. Lomuscio, E. de Vink, and M. Wooldrige (eds.): Electronic Notes in Theoretical Computer Science, Vol. 85, Elsevier.
Selten, R., 1975, “Reexamination of the perfectness concept for equilibrium points in extensive games”, International Journal of Game Theory 4, 25–55.
van Benthem, J., 2001, “Games in dynamic-epistemic logic”, Bulletin of Economic Research 53(4), 219–248.
van der Hoek, W. and Wooldridge, M., 2002, “Tractable multiagent planning for epistemic goals”, in Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2002). Bologna, Italy, pp. 1167–1174.
van der Hoek, W. and Wooldridge, M., 2003, “Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications”, Studia Logica 75(4), 125–157.
van der Meyden, R., and Su, K., 2004, “Symbolic model checking the knowledge of the dining cryptographers”, under review.
van Ditmarsch, H. P., 2000, “Knowledge games”, Ph.D. Thesis, University of Groningen, Groningen.
van Ditmarsch, H. P.: 2003, “The Russian cards problem”, Studia Logica 75(4), 31–62.
van Otterloo, S., and Jonker, G., 2004, “On epistemic temporal strategic logic”, in Proceedings of the Second Workshop on Logic and Communication in Multi Agent Systems (LCMAS).
van Otterloo, S., van der Hoek, W., and Wooldridge, M., 2003, “Model checking a knowledge exchange scenario”, in Proceedings of Model Checking and Artificial Intelligence(MoChArt) Acapulco, pp. 37–44.
van Otterloo, S., van der Hoek, W., and Wooldridge, M., 2004, “Preferences in game logics”, in AAMAS 2004, New York.
von Neumann, J. and Morgenstern, O., 1944, Theory of Games and Economic Behaviour, Princeton University Press: Princeton, NJ.
von Neumann, J. and Morgenstern, O., 1953, Theory of Games and Economic Behaviour, Princeton University Press: Princeton, NJ, 3rd edition.
Wooldridge, M. and Rao, A., (eds.), 1999, Foundations of Rational Agency, Kluwer Academic Publishers: Dordrecht, The Netherlands.
Author information
Authors and Affiliations
Corresponding author
Additional information
Sieuwert van Otterloo thanks the Institute for Logic, Language and Information in Amsterdam for its hospitality during the period that this paper was finalized.
Rights and permissions
About this article
Cite this article
van Otterloo, S., Van Der Hoek, W. & Wooldridge, M. Knowledge Condition Games. JoLLI 15, 425–452 (2006). https://doi.org/10.1007/s10849-006-9014-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10849-006-9014-1