ABSTRACT

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.

Please report errors in award information by writing to: awardsearch@nsf.gov.