ICES: Small: A Revealed Preference Approach to Computational Complexity in Economics

California Institute Of Technology, Pasadena CA

Investigators

Abstract

One of the foundational tasks for the emerging interaction between computer science and economics is to incorporate "computation" into classic economic theories. As results have emerged, it has become clear that many of the standard economic models involve solving, in the worst-case, computationally hard problems. These results are often viewed as harsh critiques of the economic models, since it seems unreasonable to model agents as solving computationally hard problems. However, economists have, in general, resisted such critiques. The core of the current proposal is that this resistance stems not from a refusal to consider computational restrictions, but instead from a different perspective on the models themselves -- an "empirical" perspective as opposed to an "algorithmic" perspective. Specifically, an algorithmic view of the model assumes the model is fixed and literal and then proceeds to ask about the demands placed on the agents by the model. In contrast, an empirical view of the model does not presume agents actually follow the model, only that the model provides a way to explain the observed behavior, i.e., the data. A model still loses credibility if the agents must solve computationally hard problems; however, standard worst-case complexity is no longer the relevant concept. This proposal seeks to formalize and study this empirical view of how to incorporate computation into economic models. This new view is strongly motivated by the revealed preference literature in economics, which seeks to understand how generally a model is applicable. Our proposed empirical view of computational complexity adds to revealed preference theory the constraint that the instance revealed does not require agents to solve any computationally hard problems. Thus, the question becomes: Do computational constraints have empirical consequences for economic models? We propose to address this question across a range of classic economic models, including consumer choice theory, Walrasian (general) equilibrium theory, Nash equilibrium theory, and the theory of stable matchings. This proposal sets an ambitious goal, and it is one that presents true opportunities for interdisciplinary dialogue. Such a dialogue presents an opportunity to rethink traditional economic models with an eye toward computation, which will shed a new light on the predictive power of the foundational theories of economics. In addition to the research components of this work, the PIs have a history of, and will continue to, facilitate the increasing interaction of computer science and economics through a variety of educational activities including (i) teaching new interdisciplinary courses at the undergraduate and graduate levels, (ii) advising interdisciplinary research at the undergraduate, graduate, and postdoctoral levels, and (iii) organizing annual joint workshops with other universities in southern California and with industry partners.