IDEAS home Printed from https://ideas.repec.org/p/upf/upfgen/1048.html
   My bibliography  Save this paper

On the complexity of rationalizing behavior

Author

Abstract

We study the complexity of rationalizing choice behavior. We do so by analyzing two polar cases, and a number of intermediate ones. In our most structured case, that is where choice behavior is defined in universal choice domains and satisfies the "weak axiom of revealed preference," finding the complete preorder rationalizing choice behavior is a simple matter. In the polar case, where no restriction whatsoever is imposed, either on choice behavior or on choice domain, finding the complete preorders that rationalize behavior turns out to be intractable. We show that the task of finding the rationalizing complete preorders is equivalent to a graph problem. This allows the search for existing algorithms in the graph theory literature, for the rationalization of choice.

Suggested Citation

  • Jose Apesteguia & Miguel A. Ballester, 2007. "On the complexity of rationalizing behavior," Economics Working Papers 1048, Department of Economics and Business, Universitat Pompeu Fabra.
    • Handle: RePEc:upf:upfgen:1048
    as

    Download full text from publisher

    File URL: https://econ-papers.upf.edu/papers/1048.pdf
    File Function: Whole Paper
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Yuval Salant, 2003. "Limited Computational Resources Favor Rationality," NajEcon Working Paper Reviews 666156000000000082, www.najecon.org.
    2. Xu, Yongsheng & Zhou, Lin, 2007. "Rationalizability of choice functions by game trees," Journal of Economic Theory, Elsevier, vol. 134(1), pages 548-556, May.
    3. Gil Kalai & Ariel Rubinstein & Ran Spiegler, 2002. "Rationalizing Choice Functions By Multiple Rationales," Econometrica, Econometric Society, vol. 70(6), pages 2481-2488, November.
    4. Yuval Salant, 2003. "Limited Computational Resources Favor Rationality," Discussion Paper Series dp320, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    5. Rubinstein,Ariel, 2000. "Economics and Language," Cambridge Books, Cambridge University Press, number 9780521789905.
    6. Ballester, Coralio, 2004. "NP-completeness in hedonic games," Games and Economic Behavior, Elsevier, vol. 49(1), pages 1-30, October.
    7. Enriqueta Aragones & Itzhak Gilboa & Andrew Postlewaite & David Schmeidler, 2012. "Fact-Free Learning," World Scientific Book Chapters, in: Case-Based Predictions An Axiomatic Approach to Prediction, Classification and Statistical Learning, chapter 8, pages 185-210, World Scientific Publishing Co. Pte. Ltd..
    8. Amartya K. Sen, 1971. "Choice Functions and Revealed Preference," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 38(3), pages 307-317.
    9. Paola Manzini & Marco Mariotti, 2007. "Sequentially Rationalizable Choice," American Economic Review, American Economic Association, vol. 97(5), pages 1824-1839, December.
    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. Tyson, Christopher J., 2008. "Cognitive constraints, contraction consistency, and the satisficing criterion," Journal of Economic Theory, Elsevier, vol. 138(1), pages 51-70, January.
    2. Tyson, Christopher J., 2008. "Cognitive constraints, contraction consistency, and the satisficing criterion," Journal of Economic Theory, Elsevier, vol. 138(1), pages 51-70, January.

    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. Apesteguia, Jose & Ballester, Miguel A., 2010. "The Computational Complexity of Rationalizing Behavior," Journal of Mathematical Economics, Elsevier, vol. 46(3), pages 356-363, May.
    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. Domenico Cantone & Alfio Giarlotta & Stephen Watson, 2021. "Choice resolutions," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 56(4), pages 713-753, May.
    4. Attila Ambrus & Kareen Rozen, 2015. "Rationalising Choice with Multi‐self Models," Economic Journal, Royal Economic Society, vol. 125(585), pages 1136-1156, June.
    5. Sophie Bade, 2016. "Pareto-optimal matching allocation mechanisms for boundedly rational agents," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 501-510, October.
    6. Alfio Giarlotta & Angelo Petralia & Stephen Watson, 2022. "Semantics meets attractiveness: Choice by salience," Papers 2204.08798, arXiv.org, revised Aug 2022.
    7. Michele Lombardi, 2008. "Uncovered set choice rules," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 31(2), pages 271-279, August.
    8. Apesteguia, Jose & Ballester, Miguel A., 2013. "Choice by sequential procedures," Games and Economic Behavior, Elsevier, vol. 77(1), pages 90-99.
    9. Heller, Yuval, 2012. "Justifiable choice," Games and Economic Behavior, Elsevier, vol. 76(2), pages 375-390.
    10. Chambers, Christopher P. & Hayashi, Takashi, 2012. "Choice and individual welfare," Journal of Economic Theory, Elsevier, vol. 147(5), pages 1818-1849.
    11. T. Hayashi & R. Jain & V. Korpela & M. Lombardi, 2023. "Behavioral strong implementation," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(4), pages 1257-1287, November.
    12. Jose Apesteguia & Miguel A. Ballester, 2008. "A characterization of sequential rationalizability," Economics Working Papers 1089, Department of Economics and Business, Universitat Pompeu Fabra.
    13. Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    14. Stewart, Rush T., 2020. "Weak pseudo-rationalizability," Mathematical Social Sciences, Elsevier, vol. 104(C), pages 23-28.
    15. 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.
    16. 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.
    17. 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.
    18. Attila Ambrus & Kareen Rozen, 2008. "Revealed Conflicting Preferences," Levine's Working Paper Archive 122247000000002161, David K. Levine.
    19. 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.
    20. Gian Caspari & Manshu Khanna, 2021. "Non-Standard Choice in Matching Markets," Papers 2111.06815, arXiv.org.

    More about this item

    Keywords

    Rationalization; Computational complexity; NP-complete; Arbitrary Choice Domains;
    All these keywords.

    JEL classification:

    • D00 - Microeconomics - - General - - - General

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:upf:upfgen:1048. 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: the person in charge (email available below). General contact details of provider: http://www.econ.upf.edu/ .

    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.