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

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

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.