Theoretical Computer Science and Economics

Introduction of Economics Session
Avi Wigderson, Herbert H. Maass Professor in the School of Mathematics
Institute for Advanced Study

Theoretical Computer Science and Economics
Tim Roughgarden, Stanford University

Theoretical computer science offers a number of tools to reason about economic problems in novel ways. For example, complexity theory sheds new light on the “bounded rationality” of decision-makers. Approximation guarantees, originally developed to analyze heuristics, can be usefully applied to Nash equilibria. Computationally efficient algorithms are an essential ingredient to modern, large-scale auction designs. Roughgarden surveys the key ideas behind these connections and their implications.

Tim Roughgarden is an Associate Professor of Computer Science and (by courtesy) Management Science and Engineering at Stanford University, where he holds the Chambers Faculty Scholar development chair. Roughgarden received his Ph.D. from Cornell University in 2002. His research interests lie on the interface of computer science and game theory, and he is currently investigating a wide range of game-theoretic issues in networks and auctions. For his research, he has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Shapley Lecturership of the Game Theory Society, a Sloan Fellowship, INFORM’s Optimization Prize for Young Researchers, the Mathematical Programming Society’s Tucker Prize, and the Gödel Prize. http://theory.stanford.edu/~tim/