Research in Games, Fixpoints, and Approximation

One of the main functions of theoretical computer science is to identify the central computational concepts and the algorithmic principles that underlie different computational problems and phenomena both within computer science, and across different disciplines. This project investigates some fundamental models and problems that arise and have been studied in different areas: computing Nash and other equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); analysing basic stochastic models for evolution, like branching processes, and for language, like stochastic context-free grammars; and models that incorporate the fundamental primitives of probability and recursion like recursive Markov chains. Most of these models and problems have been studied mathematically for a long time, leading to development of rich theories. Yet, some of their most basic algorithmic questions are still not resolved. Despite the broad diversity of these problems, there are indications that there is a common thread that runs through them. The goal and intellectual merit of the proposed research is to identify the common underlying algorithmic principles that are at the heart of these problems and others like them. Furthermore, the project seeks to develop efficient solutions for many of these problems, or to characterize rigorously the obstacles in obtaining such solutions. This research is expected to have a broad impact on a variety of areas. The concepts and models under investigation are fundamental in various disciplines, including economics, game theory, biology, and various areas of computer science. Characterizing the computational properties of the models, and providing efficient algorithms for their analysis, whenever possible, will be greatly beneficial.