AF: Medium: Algorithmic Explorations of Networks, Markets, Evolution, and the Brain

计算机科学不仅是信息技术革命背后的科学学科，也是理解我们周围世界的恰当框架。这个项目是关于应用算法的观点--以及它们的对立面复杂性--来理解各种领域的现象和挑战，包括互联网、市场、进化和大脑。为了理解互联网及其带来的网络和市场，人们必须将算法与经济学和博弈论的思想结合起来。这项研究将侧重于在线市场，特别是其动态(即多阶段)性质，改善网络路由和空中交通拥堵的激励措施，在社交网络中传播影响力的算法，以及从竞争对手(可能选择歪曲他们的数据)那里获取投入的新型算法。PI将继续他的研究，研究计算洞察力如何揭示进化中的一些关键问题，包括自然选择、机器学习和布尔逻辑问题之间的某些严格联系。最后，PI将致力于协调学习算法与神经科学的新见解。该项目包括对计算和博弈论/经济学/网络之间的某些关键问题的研究，同时继续过去使用计算概念来阐明进化和最近的神经科学的工作。PI将从计算复杂性和近似实现的角度研究经济学中的动态机制设计这一重要问题。他还将研究管理拥堵的机制，并可能将其应用于空中交通管制。该项目将探索网络创建的几个新的和有前途的博弈论模型的计算和图论特性。它将从复杂性的角度研究具有连续策略的纳什均衡，以及纳什均衡概念在效用理论之外的扩展。该项目还将探索新的和及时的计算模式，其中所有输入(最终，所有计算组件)都由自私的Rational代理提供。在进化论中，PI将探索学习算法、游戏和自然选择之间的联系，以及布尔可满足性和新颖性的出现之间的不同联系。PI还计划开发一种新的学习算法类型，使其更忠实于我们正在大脑中获得的新见解。最后，从算法和复杂性的角度，PI将考察几个计算问题，从集合覆盖问题的网络变体到线性规划和优化多元多项式。

Computer science is not just the scientific discipline behind the information technology revolution; it is also an apt framework for understanding the world around us. This project is about applying the point of view of algorithms -- and their antithesis, complexity -- to understanding phenomena and challenges in a variety of domains, including the Internet, markets, evolution, and the brain. To understand the Internet and the networks and markets it entails and enables, one must combine algorithms with ideas from economics and game theory. This research will focus on online markets and particularly their dynamic (that is, multi-stage) nature, on incentives for improving congestion in network routing and air traffic, on algorithms for propagating influence in social networks, as well as new kinds of algorithms that take their inputs from competitors (who may choose to misrepresent their data). The PI will continue his research on how computational insights can shed light on some key problems in evolution, including certain rigorous connections between natural selection, machine learning, and a problem in Boolean logic. Finally, the PI will work to reconcile learning algorithms with new insights from neuroscience.The project includes research on certain crucial problems at the interface between computation and game theory/economics/networks, while continuing past work employing computational concepts to elucidate evolution and, more recently, neuroscience. The PI will study the important problem of dynamic mechanism design in economics from the point of view of computational complexity and approximate implementation. He will also study mechanisms for managing congestion, with possible applications to air traffic control. The project will explore the computational and graph-theoretic properties of several novel and promising game-theoretic models of network creation. It will study from the complexity standpoint Nash equilibria with continuous strategies, and extensions of the Nash equilibrium concept beyond utility theory. The project will also explore new and timely modes of computation in which all inputs (ultimately, all computational components) are provided by selfish rational agents. In evolution, the PI will explore the connections between learning algorithms, games, and natural selection, and a different connection between Boolean satisfiability and the emergence of novelty. The PI also plans to develop a new genre of learning algorithms that are more faithful to the new insights we are gaining into the brain. Finally, from the standpoint of algorithms and complexity, the PI will look at several computational problems ranging from network variants of the set cover problem to linear programming and optimizing multivariate polynomials.