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

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

• 批准号: 1819935
• 负责人: Christos Papadimitriou
• 金额: $ 20.57万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-12-01 至 2019-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1819935&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将努力将学习算法与神经科学的新见解调和。该项目包括对计算与游戏理论/经济学/网络之间界面上某些关键问题的研究，同时继续使用过去的计算概念来阐明进化以及最近的Neuroscience。 PI将从计算复杂性和近似实施的角度研究经济学中动态机制设计的重要问题。他还将研究管理拥塞的机制，并可能用于空中交通管制。 该项目将探讨几种新颖和有前途的网络创建游戏理论模型的计算和图理论属性。 它将从复杂性的角度来研究NASH平衡，并具有连续的策略，以及纳什均衡概念超出实用性理论的扩展。 该项目还将探索新的和及时的计算模式，其中所有输入（最终，所有计算组件）均由自私理性代理提供。在进化中，PI将探索学习算法，游戏和自然选择之间的联系，以及布尔可满意性与新颖性的出现之间的不同联系。 PI还计划开发一种学习算法的新类型，这些算法更忠实于我们正在获得大脑的新见解。 最后，从算法和复杂性的角度来看，PI将研究一些计算问题，从设定覆盖问题的网络变体到线性编程到线性编程和优化多元多项式。