Research in Games, Fixpoints, and Approximation

博弈、不动点和近似研究

• 批准号: 0728736
• 负责人: Mihalis Yannakakis
• 金额: $ 36万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728736&HistoricalAwards=false
• 关键词: Research; Games; Fixpoints; 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.

理论计算机科学的主要功能之一是确定计算机科学中不同计算问题和现象的核心计算概念和算法原理，以及跨不同学科。 这个项目研究了一些基本的模型和问题，这些模型和问题在不同的领域已经被研究过：计算纳什均衡和其他均衡;计算最优策略和竞争博弈的值（随机和其他游戏）;分析基本的随机模型的演变，如分支过程，并为语言，如随机上下文无关语法;以及包含概率和递归（如递归马尔可夫链）的基本原语的模型。 这些模型和问题中的大多数已经被数学研究了很长时间，导致了丰富的理论的发展。然而，他们的一些最基本的算法问题仍然没有解决。尽管这些问题的广泛多样性，有迹象表明，有一个共同的线程贯穿其中。 拟议研究的目标和智力价值是确定这些问题和其他类似问题的核心的共同基本算法原则。 此外，该项目力求为其中许多问题制定有效的解决办法，或严格描述获得这种解决办法的障碍。 预计这项研究将对各个领域产生广泛影响。所研究的概念和模型是各个学科的基础，包括经济学、博弈论、生物学和计算机科学的各个领域。描述模型的计算特性，并尽可能为其分析提供有效的算法，将是非常有益的。