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, January.
    7. Hands,D. Wade, 2001. "Reflection without Rules," Cambridge Books, Cambridge University Press, number 9780521797962, November.
    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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Carvajal, Andrés, 2024. "Recent advances on testability in economic equilibrium models," Journal of Mathematical Economics, Elsevier, vol. 114(C).

    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, Andrés, 2024. "Recent advances on testability in economic equilibrium models," Journal of Mathematical Economics, Elsevier, vol. 114(C).
    2. 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.
    3. 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.
    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. 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.
    6. Pawel Dziewulski, 2021. "A comprehensive revealed preference approach to approximate utility maximisation," Working Paper Series 0621, Department of Economics, University of Sussex Business School.
    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. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. Carvajal, Andres & Quah, John K.-H., 2009. "A Nonparametric Analysis of the Cournot Model," The Warwick Economics Research Paper Series (TWERPS) 922, University of Warwick, Department of Economics.
    16. Cherchye, L.J.H. & Demuynck, T. & de Rock, B., 2009. "Degrees of Cooperation in Household Consumption Models : A Revealed Preference Analysis," Other publications TiSEM 097597d5-7724-4d31-b044-e, Tilburg University, School of Economics and Management.
    17. H. Spencer Banzhaf & Yaqin Liu & Martin Smith & Frank Asche, 2019. "Non-Parametric Tests of the Tragedy of the Commons," NBER Working Papers 26398, National Bureau of Economic Research, Inc.
    18. ,, 2010. "Rationalizable voting," Theoretical Economics, Econometric Society, vol. 5(1), January.
    19. Aguiar, Victor H. & Hjertstrand, Per & Serrano, Roberto, 2020. "A Rationalization of the Weak Axiom of Revealed Preference," Working Paper Series 1321, Research Institute of Industrial Economics.
    20. Cherchye, Laurens & Demuynck, Thomas & De Rock, Bram & Freer, Mikhail, 2022. "Revealed preference analysis of expected utility maximization under prize-probability trade-offs," Journal of Mathematical Economics, Elsevier, vol. 99(C).

    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.