The Computational Complexity of Rationalizing Behavior

Jose Apesteguia, Miguel A. Ballester

Research output: Contribution to journalArticleResearchpeer-review

14 Citations (Scopus)

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

Keywords

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

Fingerprint

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

Cite this