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

AF：媒介：网络、市场、进化和大脑的算法探索

• 批准号: 1408635
• 负责人: Christos Papadimitriou
• 金额: $ 77.06万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-04-01 至 2018-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1408635&HistoricalAwards=false
• 关键词: AF; Medium; Algorithmic; Explorations; Networks

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.

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