IDEAS home Printed from https://ideas.repec.org/a/eee/mateco/v47y2011i4p425-433.html
   My bibliography  Save this article

The computational complexity of rationalizing boundedly rational choice behavior

Author

Listed:
  • Demuynck, Thomas

Abstract

We determine the computational complexity of various choice models that use multiple rationales to explain observed choice behavior. First, we demonstrate that the notion of rationalizability by K rationales, introduced by Kalai et al. (2002), is NP-complete for K greater than or equal to two. Then, we show that the question of sequential rationalizability by K rationales, introduced by Manzini and Mariotti (2007), is NP-complete for K greater than or equal to three. Finally, we focus on the computational complexity of two models that refine this model of sequential choice behavior. We establish that the model of choice by game trees, from Xu and Zhou (2007), is NP-complete while the status-quo bias model, from Masatlioglu and Ok (2005), can be verified in polynomial time.

Suggested Citation

  • Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    • Handle: RePEc:eee:mateco:v:47:y:2011:i:4:p:425-433
    DOI: 10.1016/j.jmateco.2011.05.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304406811000504
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jmateco.2011.05.001?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 look for a different version below or search for a different version of it.

    Other versions of this item:

    References listed on IDEAS

    as
    1. Ariel Procaccia & Jeffrey Rosenschein & Aviv Zohar, 2008. "On the complexity of achieving proportional representation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 30(3), pages 353-362, April.
    2. Ray, Indrajit & Zhou, Lin, 2001. "Game Theory via Revealed Preferences," Games and Economic Behavior, Elsevier, vol. 37(2), pages 415-424, November.
    3. Eike B. Kroll & Bodo Vogt, 2008. "The Relevance of Irrelevant Alternatives: An experimental investigation of risky choices," FEMM Working Papers 08028, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    4. Xu, Yongsheng & Zhou, Lin, 2007. "Rationalizability of choice functions by game trees," Journal of Economic Theory, Elsevier, vol. 134(1), pages 548-556, May.
    5. Gil Kalai & Ariel Rubinstein & Ran Spiegler, 2002. "Rationalizing Choice Functions By Multiple Rationales," Econometrica, Econometric Society, vol. 70(6), pages 2481-2488, November.
    6. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
    7. Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
    8. Masatlioglu, Yusufcan & Ok, Efe A., 2005. "Rational choice with status quo bias," Journal of Economic Theory, Elsevier, vol. 121(1), pages 1-29, March.
    9. Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    10. Francis Chu & Joseph Halpern, 2001. "On the NP-completeness of finding an optimal strategy in games with common payoffs," International Journal of Game Theory, Springer;Game Theory Society, vol. 30(1), pages 99-106.
    11. Sprumont, Yves, 2000. "On the Testable Implications of Collective Choice Theories," Journal of Economic Theory, Elsevier, vol. 93(2), pages 205-232, August.
    12. Richard Baron & Jacques Durieu & Hans Haller & Philippe Solal, 2004. "Finding a Nash equilibrium in spatial games is an NP-complete problem," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 23(2), pages 445-454, January.
    13. 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.
    14. Chiappori, Pierre-Andre, 1988. "Nash-Bargained Households Decisions: A Comment," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 29(4), pages 791-796, November.
    15. Richard Baron & Jacques Durieu & Hans Haller & Rahul Savani & Philippe Solal, 2008. "Good neighbors are hard to find: computational complexity of network formation," Review of Economic Design, Springer;Society for Economic Design, vol. 12(1), pages 1-19, April.
    16. Apesteguia, Jose & Ballester, Miguel A., 2013. "Choice by sequential procedures," Games and Economic Behavior, Elsevier, vol. 77(1), pages 90-99.
    17. Laurens Cherchye & Bram De Rock & Frederic Vermeulen, 2007. "The Collective Model of Household Consumption: A Nonparametric Characterization," Econometrica, Econometric Society, vol. 75(2), pages 553-574, March.
    18. Apesteguia, Jose & Ballester, Miguel A., 2010. "The Computational Complexity of Rationalizing Behavior," Journal of Mathematical Economics, Elsevier, vol. 46(3), pages 356-363, May.
    19. Bossert, Walter & Suzumura, Kotaro, 2010. "Consistency, Choice, and Rationality," Economics Books, Harvard University Press, number 9780674052994, Spring.
    20. Samuelson, William & Zeckhauser, Richard, 1988. "Status Quo Bias in Decision Making," Journal of Risk and Uncertainty, Springer, vol. 1(1), pages 7-59, March.
    21. Loomes, Graham & Starmer, Chris & Sugden, Robert, 1991. "Observing Violations of Transitivity by Experimental Methods," Econometrica, Econometric Society, vol. 59(2), pages 425-439, March.
    22. Houy Nicolas, 2007. "Rationality and Order-Dependent Sequential Rationality," Theory and Decision, Springer, vol. 62(2), pages 119-134, March.
    23. Daniel Kahneman & Jack L. Knetsch & Richard H. Thaler, 1991. "Anomalies: The Endowment Effect, Loss Aversion, and Status Quo Bias," Journal of Economic Perspectives, American Economic Association, vol. 5(1), pages 193-206, Winter.
    24. Sprumont, Yves, 2001. "Paretian Quasi-orders: The Regular Two-Agent Case," Journal of Economic Theory, Elsevier, vol. 101(2), pages 437-456, December.
    25. Seidl, C. & Traub, S., 1996. "Rational Choice and the Relevance of Irrelevant Alternatives," Discussion Paper 1996-91, Tilburg University, Center for Economic Research.
    26. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    27. Chiappori, Pierre-Andre, 1992. "Collective Labor Supply and Welfare," Journal of Political Economy, University of Chicago Press, vol. 100(3), pages 437-467, June.
    28. Varian, Hal R, 1982. "The Nonparametric Approach to Demand Analysis," Econometrica, Econometric Society, vol. 50(4), pages 945-973, July.
    29. Apps, Patricia F. & Rees, Ray, 1988. "Taxation and the household," Journal of Public Economics, Elsevier, vol. 35(3), pages 355-369, April.
    30. Loomes, Graham & Taylor, Caron, 1992. "Non-transitive Preferences over Gains and Losses," Economic Journal, Royal Economic Society, vol. 102(411), pages 357-365, March.
    31. Ehlers, Lars & Sprumont, Yves, 2008. "Weakened WARP and top-cycle choice rules," Journal of Mathematical Economics, Elsevier, vol. 44(1), pages 87-94, January.
    32. Paola Manzini & Marco Mariotti, 2007. "Sequentially Rationalizable Choice," American Economic Review, American Economic Association, vol. 97(5), pages 1824-1839, December.
    33. Talla Nobibon, Fabrice & Spieksma, Frits C.R., 2010. "On the complexity of testing the Collective Axiom of Revealed Preference," Mathematical Social Sciences, Elsevier, vol. 60(2), pages 123-136, September.
    34. Shanfeng Zhu & Xiaotie Deng & Maocheng Cai & Qizhi Fang, 2002. "On computational complexity of membership test in flow games and linear production games," International Journal of Game Theory, Springer;Game Theory Society, vol. 31(1), pages 39-45.
    35. Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 20(3), pages 523-528, June.
    36. Demuynck, Thomas & Lauwers, Luc, 2009. "Nash rationalization of collective choice over lotteries," Mathematical Social Sciences, Elsevier, vol. 57(1), pages 1-15, January.
    37. Felix Brandt & Felix Fischer & Paul Harrenstein & Maximilian Mair, 2010. "A computational analysis of the tournament equilibrium set," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 34(4), pages 597-609, April.
    38. García-Sanz, María D. & Alcantud, José Carlos R., 2010. "Rational choice by two sequential criteria," MPRA Paper 21487, University Library of Munich, Germany.
    39. repec:bla:econom:v:43:y:1976:i:172:p:381-90 is not listed on IDEAS
    40. Brandt, Felix & Fischer, Felix, 2008. "Computing the minimal covering set," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 254-268, September.
    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. Igor Kopylov, 2022. "Minimal rationalizations," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 73(4), pages 859-879, June.
    2. 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.
    3. Smeulders, Bart & Cherchye, Laurens & De Rock, Bram & Spieksma, Frits C.R. & Talla Nobibon, Fabrice, 2015. "Complexity results for the weak axiom of revealed preference for collective consumption models," Journal of Mathematical Economics, Elsevier, vol. 58(C), pages 82-91.
    4. Alcantud, José Carlos R. & Cantone, Domenico & Giarlotta, Alfio & Watson, Stephen, 2023. "Rationalization of indecisive choice behavior by pluralist ballots," Journal of Mathematical Economics, Elsevier, vol. 109(C).
    5. Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    6. García-Sanz, María D. & Alcantud, José Carlos R., 2015. "Sequential rationalization of multivalued choice," Mathematical Social Sciences, Elsevier, vol. 74(C), pages 29-33.
    7. Sam Cosaert, 2019. "What Types are There?," Computational Economics, Springer;Society for Computational Economics, vol. 53(2), pages 533-554, February.
    8. Jos'e Carlos R. Alcantud & Domenico Cantone & Alfio Giarlotta & Stephen Watson, 2022. "Rationalization of indecisive choice behavior by majoritarian ballots," Papers 2210.16885, arXiv.org.

    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. 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.
    2. Fabrice Talla Nobibon & Laurens Cherchye & Yves Crama & Thomas Demuynck & Bram De Rock & Frits C. R. Spieksma, 2016. "Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms," Operations Research, INFORMS, vol. 64(6), pages 1197-1216, December.
    3. Apesteguia, Jose & Ballester, Miguel A., 2013. "Choice by sequential procedures," Games and Economic Behavior, Elsevier, vol. 77(1), pages 90-99.
    4. García-Sanz, María D. & Alcantud, José Carlos R., 2015. "Sequential rationalization of multivalued choice," Mathematical Social Sciences, Elsevier, vol. 74(C), pages 29-33.
    5. 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.
    6. Gian Caspari & Manshu Khanna, 2021. "Non-Standard Choice in Matching Markets," Papers 2111.06815, arXiv.org, revised Aug 2024.
    7. Ray, Indrajit & Snyder, Susan, 2013. "Observable implications of Nash and subgame-perfect behavior in extensive games," Journal of Mathematical Economics, Elsevier, vol. 49(6), pages 471-477.
    8. Ray, Indrajit & Snyder, Susan, 2013. "Observable implications of Nash and subgame-perfect behavior in extensive games," Journal of Mathematical Economics, Elsevier, vol. 49(6), pages 471-477.
    9. Walter Bossert & Yves Sprumont, 2009. "Non‐Deteriorating Choice," Economica, London School of Economics and Political Science, vol. 76(302), pages 337-363, April.
    10. 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.
    11. Griffith, Rachel & O'Connell, Martin & Smith, Kate & Cherchye, Laurens & De Rock, Bram & Vermeulen, Frederic, 2017. "A new year, a new you? Heterogeneity and self-control in food purchases," CEPR Discussion Papers 12499, C.E.P.R. Discussion Papers.
    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. Smeulders, Bart & Cherchye, Laurens & De Rock, Bram & Spieksma, Frits C.R. & Talla Nobibon, Fabrice, 2015. "Complexity results for the weak axiom of revealed preference for collective consumption models," Journal of Mathematical Economics, Elsevier, vol. 58(C), pages 82-91.
    14. Özgür Kıbrıs & Yusufcan Masatlioglu & Elchin Suleymanov, 2023. "A theory of reference point formation," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 75(1), pages 137-166, January.
    15. Cherepanov, Vadim & Feddersen, Timothy & ,, 2013. "Rationalization," Theoretical Economics, Econometric Society, vol. 8(3), September.
    16. Riella, Gil & Teper, Roee, 2014. "Probabilistic dominance and status quo bias," Games and Economic Behavior, Elsevier, vol. 87(C), pages 288-304.
    17. Hassan Nosratabadi, 2017. "Referential Revealed Preference Theory," Departmental Working Papers 201707, Rutgers University, Department of Economics.
    18. Jos'e Carlos R. Alcantud & Domenico Cantone & Alfio Giarlotta & Stephen Watson, 2022. "Rationalization of indecisive choice behavior by majoritarian ballots," Papers 2210.16885, arXiv.org.
    19. Nishimura, Hiroki & Ok, Efe A., 2014. "Non-existence of continuous choice functions," Journal of Economic Theory, Elsevier, vol. 153(C), pages 376-391.
    20. Mandler, Michael, 2015. "Rational agents are the quickest," Journal of Economic Theory, Elsevier, vol. 155(C), pages 206-233.

    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:mateco:v:47:y:2011:i:4:p:425-433. 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/jmateco .

    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.