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.

在过去的二十年中，算法和复杂性理论的结果和见解有许多例子，这些算法和复杂性是由其他科学中的重要研究方面促进的：量子计算，马尔可夫链蒙特·卡洛和算法游戏理论是例子。 该项目涉及计算研究的目的是将灯光放到游戏理论和经济学，网络和生物学中的主要问题。这项工作的各个方面涉及为近似NASH均衡的算法设计算法，或者确定对任务的计算障碍；更好地理解学习和分布的计算平衡算法的力量和局限性；从Thealgorithmic的角度探索NASH平衡概念的改进，以及在过去的五十年中研究人员在游戏理论中发展的均衡选择过程的改进；在过去的五十年中；出现了新的，引人入胜的，令人信服的和计算动机的解决方案概念；确定对表征最佳多对象拍卖表征的核心问题的复杂性理论障碍，以及在theSost一般环境和新颖的市场特殊情况下计算价格平衡问题的算法和下型问题。 该项目在网络领域的进一步目标包括研究最近确定的一类模型``游戏网络''；确定复杂的定价方案可以提高自私路由的效率的程度；以及分析两种新型网络模型的类型：一种用于社会网络，一种用于金融市场。在生物学中，最近的结果表明，重组下的自然选择可以优化不健身，就像数十年一样，但是我们称之为“混合性”的新型指标，应通过设计数学上的技术来遵循这项工作，以在数学上证明这种效果，并在其上对进化的影响以及构成了与之相互构建的影响，并可能探索了与之相互构建，并可能建立了与构成的关系，并可能构成了与构造的关系，并可能构成了与构造的关系。洞悉计算和目标学科（游戏理论，网络，进化论）以及新的数学技术。 在算法游戏理论中，它试图在一些最深层，最重要的问题上取得进步，同时还可以识别该领域的新的令人兴奋的研究界和方向。在进化论中，努力是阐明这项重要学科的一些最基本和最古老的问题。这项工作的见解将用于研究中的洞察力和研究生级的研究生和研究生级。 该项目的很大一部分旨在旨在提高和改善全球信息环境（Theinternet，Worldwide Web和它们可启用的数字社交网络），这是人类最有价值的资源之一。