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 research whose 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 and distributed algorithms for computing equilibria; exploring from the algorithmic standpoint the refinements of the Nash equilibrium concept, as well as of equilibrium selection processes, which have been developed 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 lower bounds for the problem of computing price equilibria in both the most 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 social networks, 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 Computation and 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 to identify new exciting research fronts and directions in this field. In the Theory of Evolution, the effort is to shed light on some of the most fundamental and old questions of this important discipline. The insights from this work will be used in the development of graduate and undergraduate courses. A substantial part of this project aims at understanding and improving the global information environment (the Internet, the worldwide web, and the digital social networks they enable), which is one of Humankind's most valuable resources.
