An empirical take on computation in economics
March 16, 2011
ABSTRACT: Recent results in complexity theory suggest that various economic theories require agents to solve intractable problems. However, such results assume the agents are optimizing explicit utility functions, whereas the economic theories merely assume the agents’ behavior is "rational" where rational behavior is defined via some optimization problem (e.g., constrained maximization of some utility function). Might merely generating rational behavior be computationally easier than solving the corresponding optimization problem? Perhaps surprisingly, we show that this is indeed the case for what is perhaps the most basic economic theory, the theory of the consumer. Our results suggest a new approach to understanding the proper role of computational constraints in economics which complements previous work, and is more in keeping with traditional economic thought.

Joint work with Federico Echenique and Adam Wierman.

Daniel Golovin is a postdoctoral fellow in Caltech's Center for the Mathematics of Information. His current research mainly focuses on online and approximation algorithms for machine learning and optimization, with an eye towards creating principled solutions that work well in practice. Prior to joining Caltech, he obtained a PhD from Carnegie Mellon University in 2008, and spent an additional year there at the Center for Computational Thinking. He did his undergraduate work at Cornell University.