The Main Themes
Pure mathematics is one of the most abstract and formal areas of the sciences. In order to deal with the abstract objects involved in pure mathematics, mathematicians often use visualizations via games. In Foundations of Mathematics, we find infinite two-player perfect information games at the core of the axiomatization of mathematics. By results of Martin, Moschovakis, Harrington, Steel and Woodin, these games provide a calibration of higher set-theoretic axioms for the foundations of mathematics. At a more fine-grained level, we find games in the foundations of higher recursion theory (the theory of inductive definitions), and again as a calibrating principle for the axiomatics of second-order arithmetic with lots of connections of fixed-point logics (Moschovakis, Steel, Tanaka, Möllerfeld, Bradfield et al.). In recent years, the investigation of perfect information games has been extended to imperfect information games. The ILLC researchers Vervoort and Löwe have proved (together with Martin and Neeman) that an imperfect information approach to foundations of mathematics allows an analysis very similar to the classical set-theoretical analysis. Löwe has also investigated extensions of set-theoretic games to more than two players. Moving towards algebra and algebraic logic, Amsterdam researchers (most prominently Venema) have looked at algebras of game operations.
Our research focus will be on extending techniques and methods from set theory, recursion theory and modal logic to wider classes of games as normally used in applications from economics and statistics (e.g.}, cooperative games, games with many players, etc.). Research questions include set-theoretic strength of the resulting axioms, proof-theoretic strength, modelling infinite games by modal logic, connections to intuitionistic logic and combinatorial consequences. We also expect that there are interesting applications to IF-logic and the foundations of mathematics. Ongoing collaborations with Belfast, Bonn, Bristol, Denton, Helsinki, Lausanne, Los Angeles, Münster, Neuchâtel, New York, and Torino will be extended.
- Johan van Benthem, Logic games are complete for game logics, Studia Logica 75 (2003), p.183-203.
- Stefan Bold, Benedikt Löwe, A Simple Inductive Measure Analysis for Cardinals under the Axiom of Determinacy, submitted
- Donald A. Martin, Itay Neeman, Marco Vervoort, The Strength of Blackwell Determinacy, Journal of Symbolic Logic 68 (2003), p.615-636.
- Benedikt Löwe, The Simulation Technique and its Consequences for Infinitary Combinatorics under the Axiom of Blackwell Determinacy, Pacific Journal of Mathematics 214 (2004), p.335-358
- Benedikt Löwe, The Length of the Full Hierarchy of Norms, Rendiconti del Seminario Matematico dell'Università e del Politecnico di Torino 63 (2005), p. 161-168
- Benedikt Löwe, The pointwise view of Determinacy: Arboreal forcings, measurability, and weak measurability, Rocky Mountain Journal of Mathematics 35 (2005), p. 1233-1249
- Benedikt Löwe, A global wellordering of norms defined via Blackwell games, to appear in: Order 22 (2005)
- Benedikt Löwe, Brian T. Semmes, The extent of combinatorial labellings, in: Costas Dimitracopoulos (ed.), Proceedings of the 5th Panhellenic Logic Symposium, July 25-28, 2005, Athens, Greece, Dedicated to Yiannis N. Moschovakis upon his retirement from the University of Athens, Athens 2005, p. 93-98
- Yde Venema, Representation of game algebras, Studia Logica 75 (2003), p.239-256.
Phrasing computation as a game has been used in Complexity Theory (Papadimitriou, Feigenbaum) to give game-theoretic characterizations of complexity classes, and in the theory of algorithms to understand the interplay between algorithms, automata and logics via games. In automata theory, we reencounter the use of fixed-point logics in connection with games (Bosse, Kolaitis, Abiteboul, Vianu, Grohe, Gurevich, Shelah et al.). The fixed-point logics of Theoretical Computer Science can be seen as propositional (modal) fragments of the fixed-point investigations of higher recursion theory in GaMath. The main directions on research in this Main Theme will be complexity issues of game models (as represented by the recent research of van Emde Boas and Sevenster), social choice mechanisms and analysis of strategic games (with recent results by Apt), and game-theoretic modelling in Information Retrieval.
We intend to move towards game models from the classical theory that have not yet been used in computer science, incorporating imperfect information, lack of knowledge of the game structure itself, more than two players, and random events in the game into the computational models. Combinatorial and implementation questions, including the study of the underlying distributed algorithms, concerned with the multi-agent systems and 'mechanism design' with applications to analysis of election methods, design of electronic voting systems, electronic trading, and design of combinatorial auctions will offer a connection to GaSocI. The game-theoretic understanding of linguistic exchanges developed in GaLing shall be used in implementing game-theoretic approaches to language interpretation in new versions of question answering technology (building on the highly successful programs for question answering developed by the ILPS group in Amsterdam). This research is part of collaborations with Helsinki, Liverpool, London, Nancy, New York, Saarbr\"ucken, Singapore and Tilburg.
- Krzysztof R. Apt, Francesca Rossi, K. Brent Venable, CP-nets and Nash equilibria, in: Proceedings of the Third International Conference on Computational Intelligence, Robotics and Autonomous Systems (CIRAS '05)
- Krzysztof R. Apt, Order Independence and Rationalizability, in: Ron van der Meyden (ed.), Proceedings of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2005), Singapore, June 10-12, 2005, p.22-38.
- Krzysztof R. Apt, Uniform Proofs of Order Independence for Various Strategy Elimination Procedures, Contributions to Theoretical Economics 4 (2004), Article 5, 48 pages.
- Johan van Benthem, Extensive games as process models, Journal of Logic, Language and Information 11 (2002), p.289-313.
- Johan van Benthem, An Essay on Sabotage and Obstruction, in: Dieter Hutter, Werner Stephan (eds.), Mechanizing Mathematical Reasoning, Essays in Honor of Jörg H. Siekmann on the Occasion of His 60th Birthday, Lecture Notes in Computer Science 2605, p.268-276
- Johan van Benthem, The Epistemic Logic of IF games, to appear in: L. Hahn (ed.), Jaakko Hintikka, Library of Living Philosophers.
- Ulle Endriss, Nicolas Maudet, On the Communication Complexity of Multilateral Trading: Extended Report, Journal of Autonomous Agents and Multiagent Systems, 11 (2005), p.91-107.
- Theo M.V. Janssen, Independent choices and the interpretation of IF-logic, Journal of Logic, Language and Information 11 (2002), p.367-387.
The effectiveness of everyday communication has always been puzzling if you compare it with the difficulties we encounter when trying to formalize the rules of communication. Game theory helps solving this puzzle in two ways: by offering models for interpretation and for evolution. The traditional division of labour between (truth conditional) semantics and (Gricean) pragmatics has given way over the last years to a more unified account of how interpretation, in particular in conversational settings, works. Game theory and optimality theory provide new tools for thinking about language use, both in production and in interpretation, as a truly interactive, co-operative enterprise.
Recently, game-theoretic models of rational behaviour had an impact on theories of natural language interpretation. These models have been used by ILLC researchers Dekker, van Rooij, and Stokhof to give feasible notions of relevance, useful information and explain the difference between explicit and implicit utterances.
Our research will focus on extending the empirical base of the application of game-theoretical concepts and will connect resulting models to non-monotonic logics as used in research in artificial intelligence, in order to allow the game approach to account for the complete range of conversational implicatures. Formal methods used will be dynamic semantics and update logic of communication in close cooperation with the work done in GaSocI. We shall also focus on applications of evolutionary games used in the theory of language evolution, seeking experimental corroboration from work based on implemented artificial life simulations of evolutionary games. An exciting challenge is to apply these techniques to natural language processing such as NLP-interfaces. ILLC researchers collaborate with experts in Berlin, Brussels, Helsinki, Los Angeles, Nancy, Osnabrück, Stanford and Stuttgart.
- Paul Dekker, Robert van Rooij, Optimality Theory and Game Theory: Some Parallels, to appear in: Journal of Semantics
- Robert van Rooij, Being polite is a handicap: Towards a game theoretical analysis of polite linguistic behavior, in: M. Tennenholtz (ed.), Proceedings of TARK 9, 2003.
- Robert van Rooij, Evolution of conventional meaning and conversational principles, Synthese (Knowledge, Rationality and Action) 139 (2004), p.331-366.
- Robert van Rooij, Cooperative versus argumentative communication, Philosophia Scientia (2004), p.195-209
- Robert van Rooij, Utility, informativity and protocols, Journal of Philosophical Logic 33 (2004), p.389-419.
- Robert van Rooij, Merlijn Sevenster, Different faces of risky speech, to appear in: Anton Benz, Gerhard Jäger, Robert van Rooij (eds.), Pragmatics and Game Theory
- Willem Zuidema, Gert Westermann, Evolution of an Optimal Lexicon under Constraints from Embodiment, Artificial Life 9 (2003), p.387-402
Games can model all sorts of interaction. Indeed, ILLC's standing interest in dynamic logics of information update and general communication mechanisms provides an excellent starting point for linking up game theory with logic analysis. More ambitiously, one can look in this same way at any sort of social interactive procedure. Parikh has coined the phrase 'social software' in his seminal 2002 Synthese paper. In this area, techniques from computer science meet those of game theory, and following the ILLC PhD graduate Marc Pauly, we shall also use logical methods for designing new games of conversation, signalling, and other forms of interaction. The literature on games in economics, the social sciences and nonlinguistic communication reaches from concrete economical problems or concrete social processes to applications in the humanities (games in philosophy of mind and cognitive sciences); recent applications of this theoretical area of research include programs for internet auctioning, internet advertising (Parikh, Jennings, Wooldridge, van der Hoek, Pauly et al..
Based on the mentioned research, the fellows in this Main Theme will develop integrated logical frameworks for game analysis and information update, which will allow them to analyze the fine-structure of reasoning by players inside games, as well as that of external observers. Besides update, games also involve belief revision, and it is possible to employ logical systems from this tradition to make the picture more realistic. In game design, new games can be created to achieve desired social effects, involving a mixture of action, knowledge, and ignorance of players. Applications of these projects range from implementation of e-voting procedures and game-driven web-bots to connections to commercial computer game software. This research will be done together with our international collaboration partners in Liverpool, Maastricht, Nancy, New York, Otago and Stanford.
- Johan van Benthem, Games in dynamic-epistemic logic, Bulletin of Economic Research 53 (2001), p.219-248.
- Johan van Benthem, Cognition as Interaction, to appear in: Gerlof Bouma, Irene Krämer (eds.), Proceedings Colloquium "Cognitive Foundations of Interpretation", Transactions KNAW, Amsterdam.
- Johan van Benthem, Rational Dynamics and Epistemic Logic in Games, to appear in: International Journal of Game Theory
- Johan van Benthem, Jan van Eijck, Barteld Kooi, Logics of Communication and Change, in: Ron van der Meyden (ed.), Proceedings of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2005), Singapore, June 10-12, 2005, p.253-261.
- Johan van Benthem, One is a Lonely Number, to appear in: Peter Koepke et al. (eds.), Logic Colloquium & Colloquium Logicum, Münster 2002.
- Johan van Benthem, Fenrong Liu, Diversity of Agents in Games, Philosophia Scientiae 8 (2004).
- Marc Pauly, On the complexity of coalitional reasoning, International Game Theory Review 4 (2002), p.237-254.
- Olivier Roy, What does game theory have to do with plans?, preprint