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

计算机科学与经济学之间新兴的相互作用的基础任务之一是将“计算”纳入经典的经济理论。随着结果的出现，很明显，在最坏的情况下，许多标准的经济模型都涉及解决难以计算的问题。这些结果通常被视为对经济模型的严厉批评，因为将代理人建模为解决计算难题似乎是不合理的。然而，经济学家总体上抵制这种批评。当前提案的核心是，这种阻力不是来自拒绝考虑计算限制，而是来自模型本身的不同视角——与“算法”视角相反的“经验”视角。具体来说，模型的算法视图假设模型是固定的和文字的，然后继续询问模型对代理的要求。相比之下，模型的经验观点并不假设代理实际上遵循模型，只是模型提供了一种解释观察到的行为（即数据）的方法。如果代理必须解决计算困难的问题，模型仍然会失去可信度；然而，标准的最坏情况复杂度不再是相关的概念。本提案旨在形式化和研究如何将计算纳入经济模型的经验观点。这种新观点受到经济学中揭示的偏好文献的强烈推动，这些文献试图理解一个模型的普遍适用性。我们提出的计算复杂性的经验观点增加了揭示偏好理论的约束，即揭示的实例不需要代理解决任何计算困难的问题。因此，问题就变成了：计算约束对经济模型有经验后果吗？我们建议通过一系列经典经济模型来解决这个问题，包括消费者选择理论、瓦尔拉斯（一般）均衡理论、纳什均衡理论和稳定匹配理论。该提案设定了一个雄心勃勃的目标，它为跨学科对话提供了真正的机会。这样的对话提供了一个机会，让我们从计算的角度重新思考传统的经济模型，这将为经济学基础理论的预测能力提供新的视角。除了这项工作的研究组成部分外，pi已经并将继续通过各种教育活动促进计算机科学和经济学日益增加的互动，包括(i)在本科和研究生阶段教授新的跨学科课程，（ii）在本科、研究生和博士后阶段为跨学科研究提供建议，（三）与南加州其他大学和行业合作伙伴组织年度联合研讨会。

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.