Decision-Making when Computational Complexity Drives Uncertainty

Peter Bossaerts

Cambridge Working Papers in Economics from Faculty of Economics, University of Cambridge

Abstract: 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.

Keywords: Computational Complexity; NP-Hard; Uncertainty; Ambiguity; Decision-Making; Rationality; Opportunism; Algorithms; Expected Utility; Neuroeconomics; Cognitive Foundations of Decision-Making (search for similar items in EconPapers)
Date: 2026-01-31
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.econ.cam.ac.uk/sites/default/files/pub ... pe-pdfs/cwpe2611.pdf

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cam:camdae:2611

Access Statistics for this paper

More papers in Cambridge Working Papers in Economics from Faculty of Economics, University of Cambridge
Bibliographic data for series maintained by Jake Dyer ().