EAGER: Bounding Rationality by Computational Complexity

EAGER：计算复杂性限制理性

• 批准号: 1255900
• 负责人: Lance Fortnow
• 金额: $ 15.2万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1255900&HistoricalAwards=false
• 关键词: EAGER; Bounding; Rationality; Computational; Complexity

People make choices, trying to choose the best of many options, for example, choosing items at a grocery store based on their cost, value and their budget. Sometimes to choose the truly best option requires solving hard computational problems. Economic theory has mostly ignored these computational issues, or has used very simple cost models of computation. The field of computational complexity has developed sophisticated models for handling computational costs and this project will apply the models and tools from computational complexity to economic situations. The project will apply these tools to answer a variety of questions such as- How do we give an economic justification for a cryptographic protocol?- How do we model complex interactive games such as chess?- How do people choose from a large range of possibilities (such as choosing a restaurant in a large city)?- Is there an economic difference between true randomness and pseudorandom number generators?With the vast number of options and data that one has from the ever-growing Internet, the limited computational power of humans and even our computers cannot hope to give a complete analysis of the best choices. This research will generate a large number of tools that will help us understand the limits of our decision-making ability as well as guide the techniques we need to make choices in our ever-more-complex society.

人们做出选择，试图从许多选项中选择最好的，例如，根据成本，价值和预算在杂货店选择物品。有时候，选择真正的最佳方案需要解决困难的计算问题。经济理论大多忽略了这些计算问题，或者使用非常简单的计算成本模型。计算复杂性领域已经开发出处理计算成本的复杂模型，本项目将把计算复杂性的模型和工具应用于经济情况。该项目将应用这些工具来回答各种问题，例如-我们如何为加密协议提供经济理由？我们如何为复杂的交互式游戏（如国际象棋）建模？人们如何从大量的可能性中进行选择（例如在大城市选择餐馆）？真随机数发生器和伪随机数发生器之间是否存在经济差异？随着人们从不断增长的互联网中获得大量的选择和数据，人类甚至我们的计算机有限的计算能力无法对最佳选择进行完整的分析。这项研究将产生大量的工具，帮助我们了解我们决策能力的局限性，并指导我们在日益复杂的社会中做出选择所需的技术。