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

点击翻译按钮获取中文摘要

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.