IDEAS home Printed from https://ideas.repec.org/a/eee/matsoc/v101y2019icp54-64.html
   My bibliography  Save this article

Descriptive complexity and revealed preference theory

Author

Listed:
  • Galambos, Adam

Abstract

This paper formalizes revealed preference theory using the notion of Ramsey eliminability in logic, and shows how the language required to state a revealed preference axiom for some choice theory is closely connected with the computational tractability of testing that theory. The connection is made through results in descriptive complexity theory, a relatively new field in finite model theory. It is shown that checking whether observed choices of players in normal form games are Nash rationalizable is an NP-complete problem. This also means that there does not exist an analogue (in a precise sense) of the Strong Axiom of Revealed Preference for Nash equilibrium.

Suggested Citation

  • Galambos, Adam, 2019. "Descriptive complexity and revealed preference theory," Mathematical Social Sciences, Elsevier, vol. 101(C), pages 54-64.
    • Handle: RePEc:eee:matsoc:v:101:y:2019:i:c:p:54-64
    DOI: 10.1016/j.mathsocsci.2019.06.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0165489619300538
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.mathsocsci.2019.06.006?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Backhouse, Roger E., 2017. "Founder of Modern Economics: Paul A. Samuelson: Volume 1: Becoming Samuelson, 1915-1948," OUP Catalogue, Oxford University Press, number 9780190664091.
    2. Sprumont, Yves, 2000. "On the Testable Implications of Collective Choice Theories," Journal of Economic Theory, Elsevier, vol. 93(2), pages 205-232, August.
    3. Matzkin, Rosa L. & Richter, Marcel K., 1991. "Testing strictly concave rationality," Journal of Economic Theory, Elsevier, vol. 53(2), pages 287-303, April.
    4. Carvajal, Andres & Ray, Indrajit & Snyder, Susan, 2004. "Equilibrium behavior in markets and games: testable restrictions and identification," Journal of Mathematical Economics, Elsevier, vol. 40(1-2), pages 1-40, February.
    5. Varian, Hal R, 1982. "The Nonparametric Approach to Demand Analysis," Econometrica, Econometric Society, vol. 50(4), pages 945-973, July.
    6. Chambers,Christopher P. & Echenique,Federico, 2016. "Revealed Preference Theory," Cambridge Books, Cambridge University Press, number 9781107087804, September.
    7. Hands,D. Wade, 2001. "Reflection without Rules," Cambridge Books, Cambridge University Press, number 9780521797962.
    8. Gradwohl, Ronen & Shmaya, Eran, 2015. "Tractable Falsifiability," Economics and Philosophy, Cambridge University Press, vol. 31(2), pages 259-274, July.
    9. Chambers, Christopher P. & Echenique, Federico & Shmaya, Eran, 2017. "General revealed preference theory," Theoretical Economics, Econometric Society, vol. 12(2), May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Carvajal, Andres & Ray, Indrajit & Snyder, Susan, 2004. "Equilibrium behavior in markets and games: testable restrictions and identification," Journal of Mathematical Economics, Elsevier, vol. 40(1-2), pages 1-40, February.
    2. Federico Echenique, 2020. "New Developments in Revealed Preference Theory: Decisions Under Risk, Uncertainty, and Intertemporal Choice," Annual Review of Economics, Annual Reviews, vol. 12(1), pages 299-316, August.
    3. Carvajal, Andrés & González, Natalia, 2014. "On refutability of the Nash bargaining solution," Journal of Mathematical Economics, Elsevier, vol. 50(C), pages 177-186.
    4. Demuynck, Thomas & Hjertstrand, Per, 2019. "Samuelson's Approach to Revealed Preference Theory: Some Recent Advances," Working Paper Series 1274, Research Institute of Industrial Economics.
    5. Pawel Dziewulski, 2021. "A comprehensive revealed preference approach to approximate utility maximisation," Working Paper Series 0621, Department of Economics, University of Sussex Business School.
    6. Changkuk Im & John Rehbeck, 2021. "Non-rationalizable Individuals, Stochastic Rationalizability, and Sampling," Papers 2102.03436, arXiv.org, revised Oct 2021.
    7. Cherchye, Laurens & Demuynck, Thomas & De Rock, Bram, 2018. "Transitivity of preferences: when does it matter?," Theoretical Economics, Econometric Society, vol. 13(3), September.
    8. Pawel Dziewulski, 2016. "Eliciting the just-noticeable difference," Economics Series Working Papers 798, University of Oxford, Department of Economics.
    9. Cherchye, L.J.H. & Demuynck, T. & de Rock, B., 2009. "Degrees of Cooperation in Household Consumption Models : A Revealed Preference Analysis," Discussion Paper 2009-91, Tilburg University, Center for Economic Research.
    10. Thomas Demuynck, 2014. "The computational complexity of rationalizing Pareto optimal choice behavior," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(3), pages 529-549, March.
    11. Aluma Dembo & Shachar Kariv & Matthew Polisson & John Quah, 2021. "Ever since Allais," IFS Working Papers W21/15, Institute for Fiscal Studies.
    12. Cherchye, Laurens & Demuynck, Thomas & De Rock, Bram, 2014. "Revealed preference analysis for convex rationalizations on nonlinear budget sets," Journal of Economic Theory, Elsevier, vol. 152(C), pages 224-236.
    13. Federico Echenique & Taisuke Imai & Kota Saito, 2023. "Approximate Expected Utility Rationalization," Journal of the European Economic Association, European Economic Association, vol. 21(5), pages 1821-1864.
    14. Cherchye, Laurens & Demuynck, Thomas & De Rock, Bram, 2011. "Testable implications of general equilibrium models: An integer programming approach," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 564-575.
    15. Laurens Cherchye & Sam Cosaert & Thomas Demuynck & Bram De Rock, 2020. "Group Consumption with Caring Individuals," The Economic Journal, Royal Economic Society, vol. 130(627), pages 587-622.
    16. Ait-Sahalia, Yacine & Duarte, Jefferson, 2003. "Nonparametric option pricing under shape restrictions," Journal of Econometrics, Elsevier, vol. 116(1-2), pages 9-47.
    17. Fabrice Talla Nobibon & Laurens Cherchye & Bram De Rock & Jeroen Sabbe & Frits Spieksma, 2011. "Heuristics for Deciding Collectively Rational Consumption Behavior," Computational Economics, Springer;Society for Computational Economics, vol. 38(2), pages 173-204, August.
    18. Donald J. Brown & Rosa L. Matzkin, 2008. "Testable Restrictions on the Equilibrium Manifold," Lecture Notes in Economics and Mathematical Systems, in: Computational Aspects of General Equilibrium Theory, pages 11-25, Springer.
    19. Samiran Banerjee & James Murphy, 2009. "A simplified test for preference rationality of two-commodity choice," Experimental Economics, Springer;Economic Science Association, vol. 12(2), pages 252-252, June.
    20. Takashi Kunimoto & Roberto Serrano, 2020. "Rationalizable Incentives: Interim Implementation of Sets in Rationalizable Strategies," Working Papers 2020-15, Brown University, Department of Economics.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:matsoc:v:101:y:2019:i:c:p:54-64. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/505565 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.