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 language | English |
---|---|
Pages (from-to) | 356-363 |
Journal | Journal of Mathematical Economics |
Volume | 46 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 May 2010 |
Keywords
- Arbitrary choice domains
- Computational complexity
- NP-complete
- Rationalization