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

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

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.