How Well Can Humans Approximate Optimality In Computationally Hard Problems?

Many decisions people face are complex, even intractable. It is often suggested that decision-makers use heuristics to overcome complexity, and that the resulting behavior closely approximates optimality. The second claim deserves scrutiny because the theory of computation has concluded that solutions to certain classes of problems cannot reasonably be approximated. Still, the theory applies to algorithms of abstract computers -- as opposed to humans -- and classes are formed based on worst-case analysis. Here we report results of an experiment in which participants were asked to solve a number of tasks that differed in the degree of approximation complexity. We find that performance is as predicted by the theory. We elucidate how classification based only on worst cases can predict average human performance. Our findings demonstrate that properties of the task at hand explain performance without having to understand which heuristics are used, or which computational constraints humans face.