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

ICES：小：经济学中计算复杂性的显示偏好方法

• 批准号: 1101470
• 负责人: Adam Wierman
• 金额: $ 40万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-05-01 至 2014-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1101470&HistoricalAwards=false
• 关键词: ICES; Small; Revealed; Preference; Approach

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.

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