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

Cognitive Science 47 (8):e13330 (2023)
  Copy   BIBTEX

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.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 97,335

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Goal-based reasoning for argumentation.Douglas N. Walton - 2015 - New York, NY: Cambridge University Press.
A Goal-Oriented Theory of Science.David Jeremy Hymie Baumslag - 1997 - Dissertation, University of Calgary (Canada)
Peirce and the Continuum of Means and Ends.Chiasson Phyllis - 2001 - The Commens Encyclopedia: The Digital Encyclopedia of Peirce Studies.

Analytics

Added to PP
2023-08-29

Downloads
23 (#786,384)

6 months
14 (#320,010)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Tom Griffiths
Aarhus University
Daniel Reichman
Loyola University, Chicago

Citations of this work

No citations found.

Add more citations