The Computational Complexity of Rationalizing Behavior

Jose Apesteguia and Miguel Ballester

Journal of Mathematical Economics, 2010, vol. 46, issue 3, 356-363

Abstract: We study the computational 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 a collection of complete preorders that rationalizes behavior turns out to be intractable. We also 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.

Keywords: Rationalization; Computational; complexity; NP-complete; Arbitrary; choice; domains (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304-4068(10)00014-5
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:mateco:v:46:y:2010:i:3:p:356-363

Access Statistics for this article

Journal of Mathematical Economics is currently edited by Atsushi (A.) Kajii

More articles in Journal of Mathematical Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().