|
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 (features) in a task where
objects are to be compared lexicographically. We investigate the complexity
of the problem of approximating optimal cue permutations for lexicographic
strategies. We show that no efficient algorithm can approximate the optimum
to within any constant factor, if $P\neq NP$. We further consider a greedy
approach for building lexicographic strategies and derive tight bounds for
the performance ratio of a new and simple algorithm. This algorithm is
proven to perform better than take-the-best.
|
