CaltechAUTHORS
  A Caltech Library Service

A Revealed Preference Approach to Computational Complexity in Economics

Echenique, Federico and Golovin, Daniel and Wierman, Adam (2010) A Revealed Preference Approach to Computational Complexity in Economics. Social Science Working Paper, 1333. California Institute of Technology , Pasadena, CA. http://resolver.caltech.edu/CaltechAUTHORS:20100928-150942227

[img]
Preview
PDF - Published Version
See Usage Policy.

256Kb
[img]
Preview
PDF (Author's preprint) - Accepted Version
See Usage Policy.

231Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20100928-150942227

Abstract

One of the main building blocks of economics is the theory of the consumer, which postulates that consumers are utility maximizing. However, from a computational perspective, this model is called into question because the task of utility maximization subject to a budget constraint is computationally hard in the worst-case under reasonable assumptions. In this paper, we study the empirical consequences of strengthening consumer choice theory to enforce that utilities are computationally easy to maximize. We prove the possibly surprising result that computational constraints have no empirical consequences whatsoever for consumer choice theory. That is, a data set is consistent with a utility maximizing consumer if and only if a data set is consistent with a utility maximizing consumer having a utility function that can be maximized in strongly polynomial time. Our result motivates a general approach for posing questions about the empirical content of computational constraints: the revealed preference approach to computational complexity. The approach complements the conventional worst-case view of computational complexity in important ways, and is methodologically close to mainstream economics.


Item Type:Report or Paper (Working Paper)
Related URLs:
URLURL TypeDescription
http://www.hss.caltech.edu/SSPapers/sswp1333.pdfPublisherUNSPECIFIED
Additional Information:If you are unable to obtain a copy on the web or library contact the Working Paper Coordinator (sswp@hss.caltech.edu) and we will send you a copy.
Group:Social Science Working Papers
Subject Keywords:Computational Complexity, Strong Axiom of Revealed Preference, Revealed Preference, Theory of the consumer
Classification Code:JEL classification numbers: D01,C63
Record Number:CaltechAUTHORS:20100928-150942227
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20100928-150942227
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20206
Collection:CaltechAUTHORS
Deposited By: Victoria Mason
Deposited On:29 Sep 2010 18:35
Last Modified:26 Dec 2012 12:28

Repository Staff Only: item control page