Decision-Making when Computational Complexity Drives Uncertainty

This review summarizes research over the last two decades on human attitudes towards computationally "hard" problems. The focus is on the nature of uncertainty that computational complexity generates because humans do not have the cognitive capacity or the resources (time) to fully resolve the problems they are dealing with. Although decision theorists have traditionally labeled this type of uncertainty as ambiguity, behavior under computational complexity shows that humans neither deal with it as prescribed in rational decision theory nor simply avoid it as in traditional accounts of ambiguity aversion. Instead, behavior (effort applied and performance reached) exhibits distinct features that can be rationalized using the theory of computational complexity, originally developed for electronic computers. Although the theory cannot decisively tell us which problems are most difficult, it does provide classifications that allow one to predict human performance and effort. The theory also identifies which instances of a problem are more difficult, and human performance and effort appear to align with this identification. Evidence is discussed that humans do not appear to allocate cognitive effort ex ante when faced with a "hard" choice. Absence of correlation between early neural signals and ex ante metrics of instance difficulty corroborate this finding. Finally, the heterogeneity in ways humans approach "hard" problems suggests that, collectively, much can be gained from incentive mechanisms that promote communication. Particular market designs appear to be extremely effective in helping participants make "hard" choices.