Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-27T21:49:55.397Z Has data issue: false hasContentIssue false
  • English
  • Français

TRACTABLE FALSIFIABILITY

Published online by Cambridge University Press:  07 May 2015

Ronen Gradwohl  and
Eran Shmaya
Ronen Gradwohl
Affiliation:
Kellogg School of Management, Northwestern University, 2001 Sheridan Road, Evanston, IL 60208, USA. Email: [email protected]. URL: http://www.kellogg.northwestern.edu/faculty/Gradwohl/index.html.
Eran Shmaya
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 6997801, Israel and Kellogg School of Management, Northwestern University, 2001 Sheridan Road, Evanston, IL 60208, USA. Email: [email protected]. URL: http://www.kellogg.northwestern.edu/faculty/directory/shmaya_eran.aspx.
Get access Rights & Permissions [Opens in a new window]

Abstract:

We propose to strengthen Popper’s notion of falsifiability by adding the requirement that when an observation is inconsistent with a theory, there must be a ‘short proof’ of this inconsistency. We model the concept of a short proof using tools from computational complexity, and provide some examples of economic theories that are falsifiable in the usual sense but not with this additional requirement. We consider several variants of the definition of ‘short proof’ and several assumptions about the difficulty of computation, and study their different implications on the falsifiability of theories.

Keywords

Falsifiabilitycomputational complexity
Type
Articles
Information
Economics & Philosophy , Volume 31 , Issue 2 , July 2015 , pp. 259 - 274
Check for updates
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Apesteguia, J. and Ballester, M.. 2010. The computational complexity of rationalizing behavior. Journal of Mathematical Economics 46: 356–363.CrossRefGoogle Scholar
Babai, L. 1985. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computing (STOC '85), Providence, RI, 421–429. New York, NY: Association for Computing Machinery.CrossRefGoogle Scholar
Bernstein, E. and Vazirani, U.. 1997. Quantum complexity theory. SIAM Journal on Computing 26: 1411–1473.CrossRefGoogle Scholar
Chambers, C., Echenique, F. and Shmaya, E.. 2011. General revealed preference theory. Caltech SS Working Paper 1332.Google Scholar
Chambers, C., Echenique, F. and Shmaya, E.. 2014. The axiomatic structure of empirical content. American Economic Review 104: 2303–2319.CrossRefGoogle Scholar
Demuynck, T. 2011. The computational complexity of boundedly rational choice behavior. Journal of Mathematical Economics 47: 425–433.CrossRefGoogle Scholar
Demuynck, T. 2014. The computational complexity of rationalizing Pareto optimal choice behavior. Social Choice and Welfare 42: 529–549.CrossRefGoogle Scholar
Duhem, P. 1954. The Aim and Structure of Physical Theory. Princeton, NJ: Princeton University Press.CrossRefGoogle Scholar
Echenique, F., Golovin, D. and Wierman, A.. 2011. A revealed preference approach to computational complexity in economics. In Proceedings of the 12th ACM Conference on Electronic Conference (EC '11), San Jose, CA, 101–110. New York, NY: Association for Computing Machinery.CrossRefGoogle Scholar
Fortnow, L. and Vohra, R. V.. 2009. The complexity of forecast testing. Econometrica 77: 93–105.Google Scholar
Goldreich, O. 2008. Computational Complexity: A Conceptual Perspective. New York, NY: Cambridge University Press.CrossRefGoogle Scholar
Goldwasser, S., Micali, S. and Rako, C.. 1989. The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18: 186–208.CrossRefGoogle Scholar
Hu, T. and Shmaya, E.. 2012. Expressible inspections. Theoretical Economics 8: 263–280.CrossRefGoogle Scholar
Impagliazzo, R. 1995. A personal view of average-case complexity. In Proceedings of the Tenth Annual IEEE Structure in Complexity Theory Conference, Minneapolis, MN, 134–147. Los Alamitos, CA: IEEE Computer Science.Google Scholar
Kalai, G., Rubinstein, A. and Spiegler, R.. 2002. Rationalizing choice functions by multiple rationales. Econometrica 70: 2481–2488.CrossRefGoogle Scholar
Kalyanaraman, S. and Umans, C.. 2008. The complexity of rationalizing matchings. Algorithms and Computation: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 2008, Proceedings, Lecture Notes in Computer Science 5369, ed. S.-H. Hong, H. Nagamochi and T. Fukunaga, 171–182. Berlin: Springer.CrossRefGoogle Scholar
Kalyanaraman, S. and Umans, C.. 2009. The complexity of rationalizing network formation. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), Atlanta, GA, 485–494. Los Alamitos, CA: IEEE Computer Science.CrossRefGoogle Scholar
Levin, L. A. 1986. Average case complete problems. SIAM Journal on Computing 15: 285–286.CrossRefGoogle Scholar
Olszewski, W. and Sandroni, A.. 2011. Falsiability. American Economic Review 101: 788–818.CrossRefGoogle Scholar
Shamir, A. 1992. IP = PSPACE. Journal of the ACM 39: 869–877.CrossRefGoogle Scholar