A revealed preference approach to computational complexity in economics
Recent results in complexity theory suggest that various economic theories require agents to solve computationally intractable problems. However, such results assume the agents are optimizing explicit utility functions, whereas the economic theories merely assume the agents behave rationally, where rational behavior is defined via some optimization problem. Might making rational choices be easier than solving the corresponding optimization problem? For at least one major economic theory, the theory of the consumer (which simply postulates that consumers are utility maximizing), we find this is indeed the case. In other words, we prove the possibly surprising result that computational constraints have no empirical consequences for consumer choice theory. Our result motivates a general approach for posing questions about the empirical content of computational constraints: the revealed preference approach to computational complexity. This approach complements the conventional worst-case view of computational complexity in important ways, and is methodologically close to mainstream economics.
© 2011 ACM. The authors wish to thank Vincent Conitzer for helpful discussions and the anonymous reviewers for their valuable feedback. This work was supported in part by the Center for the Mathematics of Information at Caltech and by the NSF through grants SES-0751980 and CNS-0846025. Formerly SSWP 1333.