Advanced Search
MyIDEAS: Login to save this article or follow this journal

The computational complexity of rationalizing boundedly rational choice behavior

Contents:

Author Info

  • 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.

Download Info

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
File URL: http://www.sciencedirect.com/science/article/pii/S0304406811000504
Download Restriction: Full text for ScienceDirect subscribers only

As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.

Bibliographic Info

Article provided by Elsevier in its journal Journal of Mathematical Economics.

Volume (Year): 47 (2011)
Issue (Month): 4-5 ()
Pages: 425-433

as in new window
Handle: RePEc:eee:mateco:v:47:y:2011:i:4:p:425-433

Contact details of provider:
Web page: http://www.elsevier.com/locate/jmateco

Related research

Keywords: Boundedly rational choice; Rationalization by multiple rationales; Sequential rationalization; Rationalization by game trees; Status-quo bias; Computational complexity; NP-completeness;

References

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
as in new window
  1. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, Elsevier, vol. 63(2), pages 621-641, July.
  2. Apesteguia, Jose & Ballester, Miguel A., 2013. "Choice by sequential procedures," Games and Economic Behavior, Elsevier, Elsevier, vol. 77(1), pages 90-99.
  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. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, Elsevier, vol. 57(3), pages 292-303, May.
  5. Apesteguia, Jose & Ballester, Miguel A., 2010. "The Computational Complexity of Rationalizing Behavior," Journal of Mathematical Economics, Elsevier, Elsevier, vol. 46(3), pages 356-363, May.
  6. Masatlioglu, Yusufcan & Ok, Efe A., 2005. "Rational choice with status quo bias," Journal of Economic Theory, Elsevier, Elsevier, vol. 121(1), pages 1-29, March.
  7. Felix Brandt & Felix Fischer & Paul Harrenstein & Maximilian Mair, 2010. "A computational analysis of the tournament equilibrium set," Social Choice and Welfare, Springer, Springer, vol. 34(4), pages 597-609, April.
  8. Gil Kalai & Ariel Rubinstein & Ran Spiegler, 2002. "Rationalizing Choice Functions By Multiple Rationales," Econometrica, Econometric Society, Econometric Society, vol. 70(6), pages 2481-2488, November.
  9. Demuynck, Thomas & Lauwers, Luc, 2009. "Nash rationalization of collective choice over lotteries," Mathematical Social Sciences, Elsevier, Elsevier, vol. 57(1), pages 1-15, January.
  10. Xu, Yongsheng & Zhou, Lin, 2007. "Rationalizability of choice functions by game trees," Journal of Economic Theory, Elsevier, Elsevier, vol. 134(1), pages 548-556, May.
  11. Paola Manzini & Marco Mariotti, 2007. "Sequentially Rationalizable Choice," American Economic Review, American Economic Association, American Economic Association, vol. 97(5), pages 1824-1839, December.
  12. 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, Springer, vol. 31(1), pages 39-45.
  13. Seidl, C. & Traub, S., 1996. "Rational Choice and the Relevance of Irrelevant Alternatives," Discussion Paper, Tilburg University, Center for Economic Research 1996-91, Tilburg University, Center for Economic Research.
  14. Ariel Procaccia & Jeffrey Rosenschein & Aviv Zohar, 2008. "On the complexity of achieving proportional representation," Social Choice and Welfare, Springer, Springer, vol. 30(3), pages 353-362, April.
  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, Springer, vol. 12(1), pages 1-19, April.
  16. Ehlers, Lars & Sprumont, Yves, 2008. "Weakened WARP and top-cycle choice rules," Journal of Mathematical Economics, Elsevier, Elsevier, vol. 44(1), pages 87-94, January.
  17. Ray, Indrajit & Zhou, Lin, 2001. "Game Theory via Revealed Preferences," Games and Economic Behavior, Elsevier, Elsevier, vol. 37(2), pages 415-424, November.
  18. Suzumura, Kataro, 1976. "Remarks on the Theory of Collective Choice," Economica, London School of Economics and Political Science, London School of Economics and Political Science, vol. 43(172), pages 381-90, November.
  19. Loomes, Graham & Starmer, Chris & Sugden, Robert, 1991. "Observing Violations of Transitivity by Experimental Methods," Econometrica, Econometric Society, Econometric Society, vol. 59(2), pages 425-39, March.
  20. Itzhak Gilboa & Eitan Zemel, 1988. "Nash and Correlated Equilibria: Some Complexity Considerations," Discussion Papers, Northwestern University, Center for Mathematical Studies in Economics and Management Science 777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
  21. Loomes, Graham & Taylor, Caron, 1992. "Non-transitive Preferences over Gains and Losses," Economic Journal, Royal Economic Society, Royal Economic Society, vol. 102(411), pages 357-65, March.
  22. Sprumont, Yves, 2000. "On the Testable Implications of Collective Choice Theories," Journal of Economic Theory, Elsevier, Elsevier, vol. 93(2), pages 205-232, August.
  23. Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer, Springer, vol. 20(3), pages 523-528, 06.
  24. Brandt, Felix & Fischer, Felix, 2008. "Computing the minimal covering set," Mathematical Social Sciences, Elsevier, Elsevier, vol. 56(2), pages 254-268, September.
  25. Houy Nicolas, 2007. "Rationality and Order-Dependent Sequential Rationality," Theory and Decision, Springer, Springer, vol. 62(2), pages 119-134, March.
  26. Richard Baron & Jacques Durieu & Hans Haller & Philippe Solal, 2004. "Finding a Nash equilibrium in spatial games is an NP-complete problem," Economic Theory, Springer, Springer, vol. 23(2), pages 445-454, January.
  27. 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, Springer, vol. 30(1), pages 99-106.
  28. Samuelson, William & Zeckhauser, Richard, 1988. " Status Quo Bias in Decision Making," Journal of Risk and Uncertainty, Springer, Springer, vol. 1(1), pages 7-59, March.
  29. 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.
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 in new window

Cited by:
  1. Thomas DEMUYNCK, 2011. "The computational complexity of rationalizing Pareto optimal choice behavior," Center for Economic Studies - Discussion papers, Katholieke Universiteit Leuven, Centrum voor Economische Studiën ces11.13, Katholieke Universiteit Leuven, Centrum voor Economische Studiën.

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

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.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei).

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 references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link 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 profile, as there may be some citations waiting for confirmation.

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