The computational complexity of rationalizing boundedly rational choice behavior
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.
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.:
- Itzhak Gilboa & Eitan Zemel, 1988.
"Nash and Correlated Equilibria: Some Complexity Considerations,"
777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
- Gil Kalai & Ariel Rubinstein & Ran Spiegler, 2002.
"Rationalizing Choice Functions By Multiple Rationales,"
Econometric Society, vol. 70(6), pages 2481-2488, November.
- Gil Kalai & Ariel Rubinstein & Ran Spiegler, 2001. "Rationalizing Choice Functions by Multiple Rationales," Discussion Paper Series dp278, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
- Gil Kalai & Ariel Rubenstein & Ran Spiegler, 2001. "Rationalizing Choice Functions by Multiple Rationales," Economics Working Papers 0010, Institute for Advanced Study, School of Social Science.
- Indrajit Ray & Lin Zhou, .
"Game Theory Via Revealed Preferences,"
00/15, Department of Economics, University of York.
- Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer, vol. 20(3), pages 523-528, 06.
- Houy Nicolas, 2007. "Rationality and Order-Dependent Sequential Rationality," Theory and Decision, Springer, vol. 62(2), pages 119-134, March.
- Francis C. Chu & Joseph Y. Halpern, 2000.
"On the NP-Completeness of Finding an Optimal Strategy in Games with Common Payoffs,"
Game Theory and Information
- 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, vol. 30(1), pages 99-106.
- Ehlers, Lars & Sprumont, Yves, 2008. "Weakened WARP and top-cycle choice rules," Journal of Mathematical Economics, Elsevier, vol. 44(1), pages 87-94, January.
- Loomes, Graham & Starmer, Chris & Sugden, Robert, 1991. "Observing Violations of Transitivity by Experimental Methods," Econometrica, Econometric Society, vol. 59(2), pages 425-39, March.
- Jose Apesteguia & Miguel�Angel Ballester, 2012.
"Choice By Sequential Procedures,"
615, Barcelona Graduate School of Economics.
- Jose Apesteguia & Miguel Ballester, 2009. "Choice by Sequential Procedures," NajEcon Working Paper Reviews 814577000000000404, www.najecon.org.
- Jose Apesteguia & Miguel A. Ballester, 2012. "Choice by sequential procedures," Economics Working Papers 1309, Department of Economics and Business, Universitat Pompeu Fabra.
- Demuynck, Thomas & Lauwers, Luc, 2009. "Nash rationalization of collective choice over lotteries," Mathematical Social Sciences, Elsevier, vol. 57(1), pages 1-15, January.
- Loomes, Graham & Taylor, Caron, 1992. "Non-transitive Preferences over Gains and Losses," Economic Journal, Royal Economic Society, vol. 102(411), pages 357-65, March.
- Samuelson, William & Zeckhauser, Richard, 1988. " Status Quo Bias in Decision Making," Journal of Risk and Uncertainty, Springer, vol. 1(1), pages 7-59, March.
- Felix Brandt & Felix Fischer & Paul Harrenstein & Maximilian Mair, 2010. "A computational analysis of the tournament equilibrium set," Social Choice and Welfare, Springer, vol. 34(4), pages 597-609, April.
- Masatlioglu, Yusufcan & Ok, Efe A., 2005. "Rational choice with status quo bias," Journal of Economic Theory, Elsevier, vol. 121(1), pages 1-29, March.
- Suzumura, Kataro, 1976. "Remarks on the Theory of Collective Choice," Economica, London School of Economics and Political Science, vol. 43(172), pages 381-90, November.
- Brandt, Felix & Fischer, Felix, 2008. "Computing the minimal covering set," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 254-268, September.
- Sprumont, Yves, 2000. "On the Testable Implications of Collective Choice Theories," Journal of Economic Theory, Elsevier, vol. 93(2), pages 205-232, August.
- Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
- 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, vol. 31(1), pages 39-45.
- Richard Baron & Jacques Durieu & Hans Haller & Philippe Solal, 2004. "Finding a Nash equilibrium in spatial games is an NP-complete problem," Economic Theory, Springer, vol. 23(2), pages 445-454, January.
- Apesteguia, Jose & Ballester, Miguel A., 2010. "The Computational Complexity of Rationalizing Behavior," Journal of Mathematical Economics, Elsevier, vol. 46(3), pages 356-363, May.
- Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
- Paola Manzini & Marco Mariotti, 2007. "Sequentially Rationalizable Choice," American Economic Review, American Economic Association, vol. 97(5), pages 1824-1839, December.
- Richard Baron & Jacques Durieu & Hans Haller & Philippe Solal & Savani Rahul, 2008. "Good neighbors are hard to find: computational complexity of network formation," Post-Print hal-00268851, HAL.
- 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, vol. 12(1), pages 1-19, April.
- Ariel Procaccia & Jeffrey Rosenschein & Aviv Zohar, 2008. "On the complexity of achieving proportional representation," Social Choice and Welfare, Springer, vol. 30(3), pages 353-362, April.
- Seidl, C. & Traub, S., 1996. "Rational Choice and the Relevance of Irrelevant Alternatives," Discussion Paper 1996-91, Tilburg University, Center for Economic Research.
- 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.
- 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.
- Xu, Yongsheng & Zhou, Lin, 2007. "Rationalizability of choice functions by game trees," Journal of Economic Theory, Elsevier, vol. 134(1), pages 548-556, May.
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 references are entirely missing, you can add them using this form.