A Modal Characterization of Nash Equilibrium

• Autorzy: Harrenstein P. , Van der Hoek W. , Meyer J.-J. , Witteveen C.
• Języki publikacji: EN

Abstrakty

EN

Multi-agent systems comprise entities whose individual decision making behavior may depend on one another's. Game-theory provides apposite concepts to reason in a mathematically precise fashion about such interactive and interdependent situations. This paper concerns a logical analysis of the game-theoretical notions of Nash equilibrium and its subgame perfect variety as they apply to a particular class of extensive games of perfect information. Extensive games are defined as a special type of labelled graph and we argue that modal languages can be employed in their description. We propose a logic for a multi-modal language and prove its completeness with respect to a class of frames that correspond with a particular class of extensive games. In this multi-modal language (subgame perfect) Nash equilibria can be characterized. Finally, we show how this approach can formally be refined by using Propositional Dynamic Logic ( PDL), though we leave completeness as an open question.

Słowa kluczowe

EN

modal logic; dynamic logic; game theory; Nash equilibrium

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 57, nr 2-4
• Strony: 281--321
• Opis fizyczny: Bibliogr. 31 poz.

Twórcy

autor

Harrenstein P.

• Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80089, 3508 TB Utrecht, The Netherlands

autor

Van der Hoek W.

• Computer Science Department, The University of Liverpool, Liverpool, United Kingdom

autor

Meyer J.-J.

• Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80089, 3508 TB Utrecht, The Netherlands

autor

Witteveen C.

• Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, the Netherlands

Bibliografia

• [1] Aumann, R. J.: Game Theory, in: Game Theory (J. Eatwell, M. Milgate, P. Newman, Eds.), The New Palgrave, Macmillan, London and Basingstoke, 1997, 1-54.
• [2] Baltag, A.: A Logic for Games, Proceedings of the ILLC Workshop on Logic and Games, Held in Amsterdam, November 19-20, 1999 (M. Pauly, A. Baltag, Eds.), number PP-1999-25 in ILLC Prepublications Series, ILLC, Amsterdam, November 1999 1999.
• [3] Benthem, J.F.A.K. van: Logic and Games. Lecture Notes, ILLC, Amsterdam, 2001.
• [4] Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic, vol. 53 of Cambridge Tracts in Theoretical Computer Science, Cambridge U.P., Cambridge, 2001.
• [5] Bonanno, G.: Branching Time Logic, Perfect Information Games and Backward Induction, Department of Economics, University of California, 1998.
• [6] Boutilier, C., Shoham, Y., Wellman, M. P.: Economic Principles of Multi-Agent Systems, Artificial Intelligence, 94, 1997, 1-6.
• [7] Fudenberg, D., Tirole, J.: Game Theory, The MIT Press, Cambridge, Mass., 1991.
• [8] Goldblatt, R.: Logics of Time and Computation, vol. 7 of CSLI Lecture Notes, 2nd edition, CSLI Publications, Stanford, 1992.
• [9] Harel, D., Kozen, D., Tiuryn, J.: Dynamic Logic, MIT Press, Cambridge, Mass. & London, 2001.
• [10] Harrenstein, B. P., van der Hoek, W., Meyer, J.-J., Witteveen, C.: Subgame Perfect Nash-Equilibria in Dynamic Logic, Proceedings of the ILLC Workshop on Logic and Games, Held in Amsterdam, November 19-20, 1999 (M. Pauly, A. Baltag, Eds.), number PP-1999-25 in ILLC Prepublications Series, ILLC, Amsterdam, 1999.
• [11] Harrenstein, B. P., van der Hoek, W., Meyer, J.-J., Witteveen, C.: A Modal Interpretation of Nash-Equilibria and Some Related Concepts, Proceedings of the Fourth Conference on Logic and the Foundations of Game and Decision Theory (LOFT4), June 30-July 2, 2000 (B. Giacomo, E. Colombatto, W. van der Hoek, Eds.), ICER, Torino, 2000.
• [12] Harrenstein, B. P., van der Hoek, W., Meyer, J.-J., Witteveen, C.: On Modal Logic Interpretations of Games, ECAI 2002, 15th European Conference on Artificial Intelligence, July 21-26 2002, Lyon, France (F. van Harmelen, Ed.), 77, IOS Press, Amsterdam, 2002, ISSN 0922-6389.
• [13] Jongh, D. de, Veltman, F.: Intensional Logics, FdW, University of Amsterdam, Amsterdam, 1995.
• [14] Kozen, D.: Results in the Propositional μ-Calculus, Theoretical Computer Science, 27, 1983, 333-354.
• [15] Kreps, D. M.: Nash Equilibrium, in: Game Theory (J. Eatwell, M. Milgate, P. Newman, Eds.), The New Palgrave, Macmillan, London and Basingstoke, 1997, 157-177.
• [16] Kuhn, H. W.: Extensive Games and the Problem of Information, in: Contributions to the Theory of Games, Volume II (H. W. Kuhn, A. W. Tucker, Eds.), number 28 in Annals of Mathematics Studies, Princeton U.P., Princeton, N.J., 1953, 1-54, Reprinted in [17].
• [17] Kuhn, H. W., Ed.: Classics in Game Theory, Princeton U.P., Princeton, N.J., 1997.
• [18] Luce, R. D., Raiffa, H.: Games and Decisions. Introduction and Critical Survey, John Wiley & Sons, New York, 1957.
• [19] Myerson, R. B.: Game Theory, Analysis of Conflict, Harvard U.P., Cambridge, Mass., 1991.
• [20] Nash, J.: Equilibrium Points in η-Person Games, PNAS, 36, 1950, 48-49, Reprinted in [17].
• [21] Nash, J.: Non-Cooperative Games, Annals of Mathematics, 54, 1951, 286-295, Reprinted in [17].
• [22] Neumann, J. von, Morgenstern, O.: Theory of Games and Economic Behavior, Princeton U.P., Princeton, N.J., 1944.
• [23] Osborne, M. J., Rubinstein, A.: A Course in Game Theory, MIT Press, Cambridge, Mass., 1994.
• [24] Parikh, R.: Logics of Knowledge, Games and Dynamic Logic, in: Foundations of Software Technology and Theoretical Computer Science (M. Joseph, R. Shyamasundar, Eds.), number 181 in Lecture Notes in Computer Science, Springer, New York, 1984, 202-222.
• [25] Parikh, R.: The Logic of Games and its Applications, in: Topics in the Theory of Computation, FCT’83, Borgholm, Sweden, August 21-27, 1983 (M. Karpinski, J. van Leeuwen, Eds.), number 14 in Annals of Discrete Mathematics, North-Holland, Amsterdam, 1985, 111-140.
• [26] Pauly, M.: Logic for Social Software, Ph.D. Thesis, Institute for Logic, Language and Information, Amsterdam, 2001.
• [27] Popkorn, S.: First Steps in Modal Logic, Cambridge U.P., Cambridge, 1994.
• [28] Schelling, T. C.: The Strategy of Conflict, Harvard U.P., Cambridge, Mass., 1960.
• [29] Selten, R.: Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetr¨agheit, Zeitschrift für die gesamte Staatswissenschaft, 121, 1965.
• [30] Stirling, C.: Games and Modal Mu-Calculus, in: Proceedings of Second International Workshop on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’96) (T. Margaria, B. Steffen, Eds.), number 1055 in Lecture Notes in Computer Science, Springer, New York, 1996, 298-312.
• [31] Zermelo, E.: Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, Proceedings of the Fifth International Congress of Mathematicians (E. W. Hobson, A. E. H. Love, Eds.), II, Cambridge U.P., Cambridge, 1913.