How do humans solve the knapsack problem?

OVERVIEW

The knapsack problem is the problem of selecting from a set of items with different values weights, the set of items with the highest total value, subject to a weight constraint. The problem is discrete constrained optimisation problem. It is ubiquitous in every-day life and of significant theoretical interest.

Using behavioural experiments, we asked participants to solve a set of instances of the knapsack problem that differed in the computational resources (number of computations, memory) required to solve them. We found that while participants, on average, exerted more effort on instances that required more computational resources, their ability to solve those instances decreased.

Most models of decision-making, including rational choice theory and bounded rationality theory, postulate that choices are the outcome of an optimisation problem such as the knapsack problem. Our work casts doubt on those theories, suggesting that in many situations decision-makers do not have the necessary the necessary computational resources to solve the optimisation problems they face.

KEY RESEARCH QUESTIONS

What is the effect of instance complexity on (mental) effort and decision quality?
How do decision-makers adapt their strategies to changing levels of instance complexity?

Recent Publications

Research Program

Complexity