This paper bridges the gap between cognitive psychology and computational complexity by providing a rigorous mathematical analysis of "fast and frugal" heuristics. These are simple rules of thumb humans use to make decisions. The authors reveal the inherent mathematical difficulty of finding the most accurate version of these rules, while proposing a novel algorithmic alternative.
Executive Summary
The authors prove that finding the optimal cue ordering for lexicographic decision-making is NP-hard and cannot even be approximated within a constant factor. However, they introduce a new greedy algorithm that provides a guaranteed performance bound and provably outperforms the classic "Take-the-Best" (TTB) heuristic in finding optimal decision paths.
The Problem: Modeling Human Decision-Making
In the 1990s, psychologists like Gerd Gigerenzer proposed that humans aren't "rational" in the traditional economic sense of calculating every probability. Instead, we rely on fast and frugal heuristics like Take-the-Best (TTB).
TTB works by evaluating "cues" (features) one by one in a specific order, stopping as soon as one cue discriminates between two options. For example, when deciding which of two cities is larger, one might ask: "Does City A have a soccer team while City B does not?" If yes, City A is chosen.
While TTB is psychologically plausible and surprisingly accurate, two major questions remained unresolved:
- Computational Complexity: How hard is it to find the best possible ordering of cues to minimize decision errors?
- Optimality: Is the standard TTB method of ranking cues—by their individual success rate—actually the optimal way to sequence them?
Methods
The authors formalize the decision task as the Minimum Incorrect Lexicographic Strategy problem. They employ two primary methods to dissect it:
- Complexity Analysis: They use a reduction from the Minimum Hitting Set problem (a classic NP-hard problem) to prove that finding an optimal cue permutation is computationally intractable.
- Algorithm Design: They introduce Algorithm 1: Greedy Cue Permutation. Unlike standard TTB, which ranks cues based on their "ecological validity" (success rate across all possible pairs), this greedy approach uses "conditional validity." It selects the best cue for the current set of pairs, removes the pairs that the cue successfully distinguishes, and then re-evaluates the remaining cues only for the undecided pairs.
Datasets
The paper primarily references the German Cities Task (Gigerenzer and Goldstein, 1996). This dataset involves comparing German cities with populations over 100,000 based on nine binary cues (e.g., presence of a state capital, a soccer team, or specific license plate types).
The authors also use synthetic, lexicographically ordered pairs to demonstrate specific edge cases where TTB fails but their greedy algorithm succeeds.
Key Insights and Ideas
- The "Hardness" of Simplicity: Even though a lexicographic strategy is one of the simplest decision rules imaginable, finding the best version of that rule is a "hard" problem. Specifically, if $P \neq NP$, no efficient algorithm can guarantee a solution that is within a constant factor of the optimal error rate.
- TTB's Blind Spot: TTB ranks cues based on their performance in isolation. This is a mistake because it ignores redundancy. If two cues are highly successful but distinguish the exact same pairs, TTB might rank them 1st and 2nd, wasting the second cue's potential.
- The Power of Conditional Validity: By picking cues that specifically address the pairs not yet decided by previous cues, the greedy algorithm ensures that every cue added to the sequence provides maximum "marginal" utility.
- A New Benchmark for Bounded Rationality: The paper suggests that the greedy method is a more robust model for accuracy than TTB, posing a challenge to cognitive psychologists to see if humans actually use this more sophisticated "conditional" logic.
Key Results
- Non-Approximability: The authors prove that the problem of minimizing incorrect inferences cannot be approximated to within any constant factor in polynomial time (unless $P=NP$).
- Greedy Performance Ratio: They prove that their Greedy Cue Permutation algorithm approximates the optimum within a factor of $n$ (where $n$ is the number of cues).
- Superiority over TTB: The authors demonstrate that the greedy algorithm is guaranteed to find a perfect cue ordering (zero errors) if one exists. TTB, conversely, can fail to find a perfect ordering even when one is available.
Limitations and Future Work
- Worst-Case vs. Average-Case: The $n$-approximation bound is a theoretical worst-case. In practice, the greedy algorithm likely performs much closer to the optimum, but this paper doesn't deeply explore average-case performance on real-world datasets beyond the city task.
- Psychological Plausibility: While the greedy algorithm is more accurate, it is also more computationally demanding for a human brain than the simple TTB. Future work could investigate whether humans actually use conditional validity or if the "cost" of that calculation is too high for biological systems.
- Binary Constraints: The study focuses on binary cues. Extending this analysis to continuous or multi-valued attributes remains an open area for research.
Summary updated