|
Fast and frugal heuristics are well studied models of bounded
rationality. Psychological research has proposed the take-the-best heuristic
as a successful strategy in decision making with limited resources.
Take-the-best searches for a sufficiently good ordering of cues (or features)
in a task where objects are to be compared lexicographically. We investigate
the computational complexity of finding optimal cue permutations for
lexicographic strategies and prove that the problem is NP-complete. It
follows that no efficient (that is, polynomial-time) algorithm computes
optimal solutions, unless $P=NP$. We further analyze the complexity of
approximating optimal cue permutations for lexicographic strategies. We show
that there is no efficient algorithm that approximates the optimum to within
any constant factor, unless $P=NP$.
The results have implications for the complexity of learning lexicographic
strategies from examples. They show that learning them in polynomial time
within the model of agnostic probably approximately correct (PAC) learning is
impossible, unless $RP=NP$. We further consider greedy approaches for
building lexicographic strategies and determine upper and lower bounds for
the performance ratio of simple algorithms. Moreover, we present a greedy
algorithm that performs provably better than take-the-best. Tight bounds on
the sample complexity for learning lexicographic strategies are also given in
this article.
|
