Game Solution, Epistemic Dynamics and Fixed-Point Logics

• Autorzy: van Benthem J. , Gheerbrant A.
• Języki publikacji: EN

Abstrakty

EN

Current methods for solving games embody a form of "procedural rationality" that invites logical analysis in its own right. This paper is a brief case study of Backward Induction for extensive games, replacing earlier static logical definitions by stepwise dynamic ones. We consider a number of analysis from recent years that look different conceptually, and find that they are all mathematically equivalent. This shows how an abstract logical perspective can bring out basic invariant structure in games. We then generalize this to an exploration of fixed-point logics on finite trees that best fit game-theoretic equilibria. We end with some open questions that suggest a broader program for merging current computational logics with notions and results from game theory. This paper is largely a program for opening up an area: an extended version of the technical results will be found in the forthcoming dissertation [26].

Słowa kluczowe

EN

Backward Induction; extensive games; Dynamic-Epistemic Logic; Fixed-Point Logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 100, nr 1/4
• Strony: 19--41
• Opis fizyczny: Bibliogr. 45 poz., wykr.

Twórcy

autor

van Benthem J.

autor

Gheerbrant A.

• Institute for Logic, Language and Computation, University of Amsterdam, P.O. Box 94242, 1090 GE Amsterdam, The Netherlands,

Bibliografia

• [1] Aumann, R.: Backward Induction and Common Knowledge of Rationality, Games and Economic Behavior, 8, 1995, 6-19.
• [2] Baltag, A., Smets, S.: Group Belief Dynamics under Iterated Revision: Fixed-Points and Cycles of Joint Upgrades, Proceedings of TARK 2009, 2009, 41-50.
• [3] Baltag, A., Smets, S., Zvesper, J.: Keep "Hoping" for Rationality: A Solution to the Backward Induction Paradox, Synthese, 169(2), 2009, 301-333.
• [4] van Benthem, J.: Extensive Games as Process Models, Journal of Logic, Language and Information, 11, 2001, 289-313.
• [5] van Benthem, J.: Games in Dynamic Epistemic Logic, Bulletin of Economic Research, 53(4), 2002, 219-248.
• [6] van Benthem, J.: Minimal Predicates, Fixed-Points, and Definability, Journal of Symbolic Logic, 70(3), 2005, 696-712.
• [7] van Benthem, J.: Modal Frame Correspondences and Fixed-Points, Studia Logica, 83(1), 2006, 133-155.
• [8] van Benthem, J.: Dynamic Logic of Belief Revision, Journal of Applied Non-Classical Logics, 17(2), 2007, 129-155.
• [9] van Benthem, J.: Rational Dynamics and Epistemic Logic in Games, International Game Theory Review (IGTR), 09(01), 2007, 13-45.
• [10] van Benthem, J.: In Praise of Strategies, to appear in J. van Eijck and R. Verbrugge, eds., Games, Actions and Social Software, College Publications, London, 2008.
• [11] van Benthem, J.: The Logic of Rational Agency, Invited Lecture, Third Indian ICLAWinter School, Chennai, 2009.
• [12] van Benthem, J.: Logical Dynamics of Information and Interaction, Cambridge University Press, Cambridge, 2010.
• [13] van Benthem, J., van Otterloo, S., Roy, O.: Modality Matters: Twenty-Five Essays in Honour of Krister Segerberg, vol. 53 of Philosophical Studies, chapter Preference Logic, Conditionals, and Solution Concepts in Games, Lagerlund, Lindström and Sliwinski, Uppsala, 2006, 61-76.
• [14] van Benthem, J., Pacuit, E.: The Tree of Knowledge in Action, Proceedings Advances in Modal Logic, 2006, 87-106.
• [15] Bicchieri, C., Schulte, O.: Common Reasoning about Admissibility, Erkenntnis, 45, 1997, 229-325.
• [16] Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic, Cambridge University Press, Cambridge, 2000.
• [17] Bonanno, G.: The Logic of Rational Play in Games of Perfect Information, Economics and Philosophy, 7, 1991, 37-65.
• [18] Boolos, G.: The Logic of Provability, Cambridge University Press, Cambridge, 1993.
• [19] de Bruin, B.: Explaining Games: on the Logic of Game Theoretic Explanations, Ph.D. Thesis, ILLC, University of Amsterdam, 2004.
• [20] Dawar, A., Gr¨adel, E., Kreutzer, S.: Inflationary Fixed-Points in Modal Logic, ACM Transactions on Computational Logic, 5, 2004, 282-315.
• [21] Dégremont, C.: The Temporal Mind. Observations on the Logic of Belief Change in Interactive Systems, Ph.D. Thesis, ILLC, University of Amsterdam, 2010.
• [22] Denecker, M., Ternovska, E.: A Logic of Nonmonotone Inductive Definitions, ACM Trans. Comput. Logic, 9(2), 2008, 1-52.
• [23] van Ditmarsch, H., van der Hoek, W., Kooi, B.: Dynamic-Epistemic Logic, Cambridge University Press, Cambridge, 2007.
• [24] Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, Springer, Berlin, 1995.
• [25] Geanakoplos, J., Polemarchakis, H.: We Can't Disagree Forever, Journal of Economic Theory, 28, 1982, 192-200.
• [26] Gheerbrant, A.: Fixed-Point Logics on Trees, Ph.D. Thesis, ILLC, University of Amsterdam, 2010.
• [27] Gurevich, Y., Shelah, S.: Fixed-Point Extensions of First-Order Logic, Annals of Pure and Applied Logic, 32, 1986, 265-280.
• [28] Halpern, J., Vardi,M.: The Complexity of Reasoning about Knowledge and Time, I: Lower Bounds, Journal of Computer and System Sciences, 38(1), 1989, 195-237.
• [29] Harrenstein, P.: Logic in Conflict, Ph.D. Thesis, Institute of Computer Science, University of Utrecht, 2004.
• [30] van der Hoek, W., Pauly, M.: Modal Logic for Games and Information, in: Handbook of Modal Logic (P. Blackburn, F. Wolter, J. van Benthem, Eds.), Elsevier, Amsterdam, 2006, 1077-1148.
• [31] Immermann, N.: Descriptive Complexity, Springer, Berlin, 1999.
• [32] Iida, H., Uiterwijk, J.W.H.M., Herik, H.J. van den, and Herschberg, I.S. (1993). Potential Applications of Opponent-Model Search. Part 1: The Domain of Applicability. ICCA Journal, Vol. 16, No. 4, pp. 201-208.
• [33] Kreutzer, S.: Expressive Equivalence of Least and Inflationary Fixed-Point Logic, Annals of Pure and Applied Logic, 130(1-3), 2004, 61-78.
• [34] Liu, F.: Changing for the Better, Preference Dynamics and Agent Diversity, Ph.D. Thesis, Illc, University of Amsterdam, 2008.
• [35] Osborne, M., Rubinstein, A.: A Course in Game Theory, The MIT Press, Cambridge (Mass.), 1994.
• [36] van Otterloo, S.: A Strategic Analysis of Multi-Agent Protocols, Ph.D. Thesis, ILLC, Amsterdam, 2005.
• [37] Pacuit, E., Roy, O.: Interactive Rationality, Lectures Notes, University of Groningen and University of Tilburg, 2010.
• [38] Samet, D.: Counterfactuals in Wonderland, Games and Economic Behavior, 51(2), 1997, 537-541.
• [39] Selten, R.: Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetr¨agheit, Zeitschrift für die gesamte Staatswissenschaft, 121, 1965, 301-324.
• [40] Selten, R.: Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games, International Journal of Game Theory, 4, 1975, 25-55.
• [41] Stalnaker, R.: Extensive and Strategic Form: Games and Models for Games, research in Economics, 53, 1999, 293-319.
• [42] Venema, Y.: Algebras and Coalgebras, in: Handbook of Modal Logic (P. Blackburn, F. Wolter, J. van Benthem, Eds.), Elsevier, 2006, 331-426.
• [43] von Wright, G. H.: The Logic of Preference, Edinburgh University Press, Edinburgh, 1963.
• [44] Zvesper, J.: Arriving at the BI Condition, Manuscript, Oxford Computing Lab, Oxford University, 2010.
• [45] Zvesper, J.: Playing with Information, Ph.D. Thesis, ILLC, University of Amsterdam, 2010.