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.