Research Training Site GLoRiClass
Research Training Site GLoRiClass: The Main Themes
The Main Themes
People
PhD Defenses
Opening Event
Halftime Event
Farewell Event
GLoRiClass Seminar
Events
Guests

The Main Themes

GaMath (Games in Mathematics).

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.

Recent Publications.

GaCS (Games in Computer Science).

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.

Recent Publications.

GaLing (Games in Linguistics).

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.

Recent Publications.

GaSocI (Games and Social Interaction).

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.

Recent Publications.