EAGER: Bounding Rationality by Computational Complexity

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

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.