Decision-Making When Computational Complexity Drives Uncertainty

Abstract

This review summarizes research over the past two decades on human attitudes toward 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. Although decision theorists have traditionally labeled this type of uncertainty “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. The absence of correlation between early neural signals and ex ante metrics of instance difficulty corroborates 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.