AF: Medium: Algorithmic Research in Game Theory, Networks, and Biology

AF：媒介：博弈论、网络和生物学的算法研究

• 批准号: 0964033
• 负责人: Christos Papadimitriou
• 金额: $ 120万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-04-15 至 2015-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0964033&HistoricalAwards=false
• 关键词: AF; Medium; Algorithmic; Research; Game

Over the past two decades there have been many examples of results and insights in the Theory of Algorithms and Complexity that are motivated by,and inform, important research fronts in other sciences: Quantum Computing, Markov chain Monte Carlo, and Algorithmic Game Theory are examples. This project is about computational researchwhose purpose is to shed light to a broad front of central problems in Game Theory and Economics, Networking, and Biology. Aspects of this work involve devising algorithms for approximating Nash equilibria, or identifying computational impediments to the task;understanding better the power and limitations of learning anddistributed algorithms for computing equilibria; exploring from thealgorithmic standpoint the refinements of the Nash equilibrium concept, aswell as of equilibrium selection processes, which have beendeveloped by researchers in Game Theory over the past fifty years;coming up new, compelling, and computationally motivated solution concepts; identifying complexity-theoretic impediments to the central problem of characterizing the optimal multi-object auction, as well as developing algorithms and lowerbounds for the problem of computing price equilibria in both themost general setting and in novel special cases of markets. Further goals of this project in the realm of Networking include studying a recently identified class of models known as ``networks of games;'' determining the extent to which sophisticated pricing schemes can improve the efficiency of selfish routing; and the analyzing two new genres of network models: One for socialnetworks, and one for financial markets. In Biology, a recent result established that natural selection under recombination optimizes not fitness, as it had been assumed for decades, but a novel metric which we call ``mixability;'' this project shall follow on this work by devising techniques for proving mathematically this effect, as well as gauging rigorously its impact on Evolution, and and by exploring the relationship between recombination, mixability, and genetic modularity.This project is likely to produce new insights into both Computationand the target disciplines (Game Theory, Networking, Theory of Evolution), as well as new mathematical techniques. In Algorithmic Game Theory, it seeks to make progress on some of the deepest and most looked at problems, but also toidentify new exciting research fronts and directions in this field.In the Theory of Evolution, the effort is to shed light on some ofthe most fundamental and old questions of this important discipline.The insights from this work will be used in the development of graduate andundergraduate courses. A substantial part of this project aims atunderstanding and improving the global information environment (theInternet, the worldwide web, and the digital social networks theyenable), which is one of Humankind's most valuable resources.

在过去的二十年里，算法和复杂性理论中有许多结果和见解的例子，这些例子是由其他科学的重要研究前沿激发并提供信息的：量子计算、马尔可夫链蒙特卡罗和算法博弈论都是例子。 该项目是关于计算研究的，其目的是阐明博弈论和经济学、网络和生物学中广泛的核心问题。这项工作的各个方面涉及设计近似纳什均衡的算法，或识别任务的计算障碍；更好地理解计算均衡的学习和分布式算法的威力和局限性；以及从算法的角度探索纳什均衡概念的改进，以及博弈论研究人员在过去五十年中开发的均衡选择过程；提出新的、引人注目的、计算驱动的解决方案概念；确定描述最优多对象拍卖的核心问题的复杂性理论障碍，以及开发在最一般的环境和市场的新颖特殊情况下计算价格均衡问题的算法和下限。 该项目在网络领域的进一步目标包括研究最近确定的一类称为“游戏网络”的模型；确定复杂的定价方案可以在多大程度上提高自私路由的效率；以及确定复杂的定价方案可以在多大程度上提高自私路由的效率。并分析两种新类型的网络模型：一种用于社交网络，一种用于金融市场。在生物学中，最近的一项结果表明，重组下的自然选择优化的不是几十年来人们所假设的适应性，而是一种我们称之为“可混合性”的新指标；该项目将通过设计数学证明技术来继续这项工作这种效应，以及严格衡量其对进化的影响，并通过探索重组、可混合性和遗传模块化之间的关系。该项目可能会对计算和目标学科产生新的见解（游戏理论、网络、进化论）以及新的数学技术。 在算法博弈论中，它寻求在一些最深层次和最受关注的问题上取得进展，同时也确定该领域新的令人兴奋的研究前沿和方向。在进化论中，它的努力是阐明一些最重要的问题。这一重要学科的基础和老问题。这项工作的见解将用于研究生和本科生课程的开发。 该项目的很大一部分旨在理解和改善全球信息环境（互联网、万维网和可用的数字社交网络），这是人类最宝贵的资源之一。