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.

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