Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T20:32:06.044Z Has data issue: false hasContentIssue false
  • English
  • Français

REASONING WITH PROTOCOLS UNDER IMPERFECT INFORMATION

Published online by Cambridge University Press:  23 September 2011

ERIC PACUIT  and
SUNIL SIMON
ERIC PACUIT*
Affiliation:
Tilburg Institute for Logic and Philosophy of Science (TiLPS) Department of Philosophy, Tilburg University
SUNIL SIMON*
Affiliation:
Centrum voor Wiskunde & Informatica (CWI)
*
*TILBURG INSTITUTE FOR LOGIC AND PHILOSOPHY OF SCIENCE, TILBURG UNIVERSITY, TILBURG, 5000LE, THE NETHERLANDS. E-mail:[email protected]
†CENTRUM FOR WISKUNDE & INFORMATICA, SCIENCE PARK 123, AMSTERDAM, 1098XG, THE NETHERLANDS. E-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce and study a PDL-style logic for reasoning about protocols, or plans, under imperfect information. Our paper touches on a number of issues surrounding the relationship between an agent’s abilities, available choices, and information in an interactive situation. The main question we address is under what circumstances can the agent commit to a protocol or plan, and what can she achieve by doing so?

Type
Research Article
Information
The Review of Symbolic Logic , Volume 4 , Issue 3 , September 2011 , pp. 412 - 444
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

BIBLIOGRAPHY

Balbiani, P., Herzig, A., & Troquard, N. (2007). Alternative axiomatics and complexity of deliberative STIT theories. Journal of Philosophical Logic, 37(4), 387–406.Google Scholar
Blackburn, P., de Rijke, M., & Venema, Y. (2002). Modal Logic. Cambridge: Cambridge University Press.Google Scholar
Bratman, M. (1987). Intention, Plans and Practical Reason. Cambridge: Harvard University Press.Google Scholar
Bratman, M. (1999). Faces of Intention. Cambridge: Cambridge University Press.Google Scholar
Broersen, J. (2008). A logical analysis of the interaction between ‘obligation-to-do’ and ‘knowingly doing’. In van der Torre, L., and van der Meyden, R., editors. Proceedings 9th International Workshop on Deontic Logic in Computer Science (DEON’08), Vol. 5076 of LNCS. Berlin: Springer, pp. 140–154.Google Scholar
Carr, D. (1979). The logic of knowing how and ability. Mind, 88, 394–409.CrossRefGoogle Scholar
Cohen, P. R., & Levesque, H. (1990). Intention is choice with committment. Artificial Intelligence, 42(3), 213–261.CrossRefGoogle Scholar
Cross, C. B. (1986). ‘Can’ and the logic of ability. Philosophical Studies, 50(1), 53–64.Google Scholar
Elgesem, D. (1997). The modal logic of agency. Nordic Journal of Philosophical Logic, 2(2), 1–46.Google Scholar
Fagin, R., Halpern, J., Moses, Y., & Vardi, M. (1995). Reasoning about Knowledge. Boston: The MIT Press.Google Scholar
Fagin, R., Halpern, J., Moses, Y., & Vardi, M. (1997). Knowledge-based programs. Distributed Computing, 10(4), 199–225.CrossRefGoogle Scholar
Fantl, J. (2008). Knowing-how and knowing-that. Philosophy Compass, 3(3), 451–470.CrossRefGoogle Scholar
Gilbert, M. (1989). On Social Facts. Princeton: Princeton University Press.Google Scholar
Goranko, V., & Jamroga, W. (2004). Comparing semantics of logics for multi-agent systems. Synthese: Knowledge, Rationality, and Action, 139(2), 241–280.Google Scholar
Governatori, G., & Rotolo, A. (2005). On the axiomatization of elgesem’s logic of agency and ability. Journal of Philosophical Logic, 34(4), 403–431.CrossRefGoogle Scholar
Halpern, J., & Fagin, R. (1989). Modelling knowledge and action in distributed systems. Distributed Computing, 3(4), 159–177.Google Scholar
Halpern, J., & Moses, Y. (1990). Knowledge and common knowledge in a distributed environment. Journal of the ACM, 37(3), 549–587.CrossRefGoogle Scholar
Halpern, J. Y., van der Meyden, R., & Vardi, M. Y. (2004). Complete axiomatizations for reasoning about knowledge and time. SIAM Journal on Computing, 33(3), 674–703.CrossRefGoogle Scholar
Harel, D., Kozen, D., & Tiuryn, J. (2000). Dynamic Logic. Boston: The MIT Press.CrossRefGoogle Scholar
Herzig, A., Long, J., Longin, D., & Polacsek, T. (2000). A logic for planning under partial observability. In Proceedings of the Seventeenth National Conference on Artificial Intelligence. Austin, Texas: AAAI Press, pp. 768–773.Google Scholar
Herzig, A., & Troquard, N. (2006). Knowing how to play: Uniform choices in logics of agency. In AAMAS ’06: Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems. Hakodate, Japan: ACM, pp. 209–216.CrossRefGoogle Scholar
Horty, J. (2001). Agency and Deontic Logic. Oxford: Oxford University Press.CrossRefGoogle Scholar
Hoshi, T. (2009). Epistemic dynamics and protocol information. PhD Thesis, Stanford University.Google Scholar
Icard, T., Pacuit, E., & Shoham, Y. (2010). Joint revision of beliefs and intentions. In Proceedings of KR 2010, 572–574.Google Scholar
Jamroga, W., & Agotnes, T. (2007). Constructive knowledge: What agents can achieve under imperfect information. Journal of Applied Non-Classical Logics, 17(4), 423–475.CrossRefGoogle Scholar
Kozen, D., & Parikh, R. (1981). An elementary proof of the completeness of PDL. Theoretical Computer Science, 14, 113–118.CrossRefGoogle Scholar
Lesperance, Y., Levesque, H., Lin, F., & Scherl, R. (2000). Ability and knowing how in the situation calculus. Studia Logica, 65, 165–186.CrossRefGoogle Scholar
Lorini, E., & Herzig, A. (2008). A logic of intention and attempt. Synthese, 163(1), 45–77.CrossRefGoogle Scholar
Lorini, E., Schwarzentruber, F., & Herzig, A. (2009). Epistemic games in modal logic: joint actions, knowledge and preferences all together. In Proceedings of LORI’09. Berlin: Springer-Verlag, pp. 212–226.Google Scholar
Meyer, J.-J., van der Hoek, W., & van Linder, B. (1999). A logical approach to the dynamics of commitments. Artificial Intelligence, 113, 1–40.CrossRefGoogle Scholar
Meyer, J.-J., & Veltman, F. (2007). Intelligent agents and common sense reasoning. In Blackburn, P., van Benthem, J., and Wolter, F., editors. Handbook of Modal Logic. Amsterdam: Elsevier, pp. 991–1029.CrossRefGoogle Scholar
Mukund, M., & Sohoni, M. (1997). Keeping track of the latest gossip in a distributed system. Distributed Computing, 10(3), 137–148.CrossRefGoogle Scholar
Nicola, R. D. (1987). Extensional equivalences for transition systems. Acta Informatica, 24, 211–237.Google Scholar
Parikh, R. (1985). The logic of games and its applications. In Topics in the Theory of Computation (Borgholm, 1983), Vol. 102 of North-Holland Math. Stud. Annals of Discrete Mathematics, 24 (1985) 111–140.Google Scholar
Parikh, R., & Ramanujam, R. (2003). A knowledge based semantics of messages. Journal of Logic, Language and Information, 12, 453–467.CrossRefGoogle Scholar
Peleg, D. (1987). Concurrent dynamic logic. Journal of the ACM, 34(2), 450–479.CrossRefGoogle Scholar
Ramanujam, R. (1996). Local knowledge assertions in a changing world. In Proceedings of TARK. San Francisco: Morgan Kaufmann, pp. 1–17.Google Scholar
Ramanujam, R., & Simon, S. (2009). Dynamic logic of tree composition. In Perspectives in Concurrency Theory. India: Universities Press, pp. 408–430.Google Scholar
Roy, O., & Pacuit, E. (2011). Substantive assumptions in interaction: A logical perspective. Manuscript.Google Scholar
Ryle, G. (1949). The Concept of Mind. Chicago: The University of Chicago Press.Google Scholar
Schmidt, R., & Tishkovsky, D. (2008). On combinations of propositional dynamic logic and doxastic modal logics. Journal of Logic, Language and Information, 17, 109–129.CrossRefGoogle Scholar
Searle, J. (1990). Collective intentions and actions. In Cohen, P., Morgan, J., and Pollack, M., editors. Intentions in Communication. Boston: The MIT Press, pp. 401–415.Google Scholar
Singh, M. P. (1999). Know-how. In Wooldridge, M., and Rao, A., editors. Foundations of Rational Agency. Berlin: Springer, pp. 105–132.Google Scholar
Stanley, J., & Williamson, T. (2001). Knowing how. Journal of Philosophy, 98, 411–444.CrossRefGoogle Scholar
Sugden, R. (2003). The logic of team reasoning. Philosophical Explorations, 6(3), 165–181.Google Scholar
Tuomela, R. (2010). The Philosophy of Sociality. Oxford: Oxford University Press.Google Scholar
van Benthem, J. (2001a). Extensive games as process models. Journal of Logic, Language and Information, 11, 289–313.Google Scholar
van Benthem, J. (2001b). Games in dynamic epistemic logic. Bulletin of Economic Research, 53(4), 219–248.Google Scholar
van Benthem, J. (2008). In Praise of Strategies. Technical report, ILLC Technical Reports.Google Scholar
van Benthem, J. (2011). Logical Dynamics of Information and Interaction. Cambridge: Cambridge University Press.Google Scholar
van Benthem, J., Gerbrandy, J., Hoshi, T., & Pacuit, E. (2009). Merging frameworks for interaction. Journal of Philosophical Logic, 38(5), 491–526.Google Scholar
van Benthem, J., & Pacuit, E. (2006). The tree of knowledge in action: Towards a common perspective. In Governatori, G., Hodkinson, I., and Venema, Y., editors. Proceedings of Advances in Modal Logic, Vol. 6. London: King’s College Press, pp. 87–106.Google Scholar
van der Hoek, W., van Linder, B., & Meyer, J.-J. (1998). Formalising abilities and opportunities of agents. Fundamenta Informaticae, 34, 1–49.Google Scholar
van der Hoek, W., & Wooldridge, M. (2003a). Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications. Studia Logica, 75, 125–157. doi:10.1023/A:1026185103185.CrossRefGoogle Scholar
van der Hoek, W., & Wooldridge, M. (2003b). Towards a logic of rational agency. Logic Journal of the IGPL, 11(2), 135–160.Google Scholar
van der Meyden, R. (1996). Finite state implementations of knowledge-based programs. In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science, Vol. 1180 of Lecture Notes in Computer Science. Berlin: Springer, pp. 262–273.Google Scholar
van Eijk, J., Kuppusamy, L., & Wang, Y. (2009). Verifying epistemic protocols under common knowledge. In Heifetz, A., editor. Proceedings of TARK. Stanford: ACM, pp. 257–266.Google Scholar
van Otterloo, S. (2005). A strategic analysis of multi-agent protocols. PhD Thesis, ILLC University of Amsterdam.Google Scholar
Wang, Y. (2010). Epistemic modelling and protocol dynamics. PhD Thesis, CWI.Google Scholar
Williams, J. (2008). Propositional knowledge and know-how. Synthese, 165, 107–125.Google Scholar
Zielonka, W. (1987). Notes on finite asynchronous automata. RAIRO Informatique Théorique et Applications, 21(2), 99–135.CrossRefGoogle Scholar