The Computational Complexity of Rationalizing Behavior

Jose Apesteguia, Miguel A. Ballester

Research output: Contribution to journalArticleResearchpeer-review

14 Citations (Scopus)


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. © 2010 Elsevier B.V.
Original languageEnglish
Pages (from-to)356-363
JournalJournal of Mathematical Economics
Issue number3
Publication statusPublished - 1 May 2010


  • Arbitrary choice domains
  • Computational complexity
  • NP-complete
  • Rationalization


Dive into the research topics of 'The Computational Complexity of Rationalizing Behavior'. Together they form a unique fingerprint.

Cite this