The Computational Challenges of Means Selection Problems: Network Structure of Goal Systems Predicts Human Performance

Daniel Reichman, Falk Lieder, David D. Bourgin, Nimrod Talmon, Thomas L. Griffiths

Research output: Contribution to journalArticlepeer-review

Abstract

We study human performance in two classical NP-hard optimization problems: Set Cover and Maximum Coverage. We suggest that Set Cover and Max Coverage are related to means selection problems that arise in human problem-solving and in pursuing multiple goals: The relationship between goals and means is expressed as a bipartite graph where edges between means and goals indicate which means can be used to achieve which goals. While these problems are believed to be computationally intractable in general, they become more tractable when the structure of the network resembles a tree. Thus, our main prediction is that people should perform better with goal systems that are more tree-like. We report three behavioral experiments which confirm this prediction. Our results suggest that combinatorial parameters that are instrumental to algorithm design can also be useful for understanding when and why people struggle to choose between multiple means to achieve multiple goals.

Original languageEnglish (US)
Article numbere13330
JournalCognitive science
Volume47
Issue number8
DOIs
StatePublished - Aug 2023

All Science Journal Classification (ASJC) codes

  • Experimental and Cognitive Psychology
  • Artificial Intelligence
  • Cognitive Neuroscience

Keywords

  • Bounded rationality
  • Computational complexity
  • Goal systems
  • Graph theory

Fingerprint

Dive into the research topics of 'The Computational Challenges of Means Selection Problems: Network Structure of Goal Systems Predicts Human Performance'. Together they form a unique fingerprint.

Cite this