EUVIMEDEUVIMED entdecken
Crossref

Human Performance at Solving 0-1 Knapsack Problems: Results from a Large-Scale Field Experiment

Sumit Agarwal, Joel Goh, Wenlan Qian, Xin Zou

Management Science · 17.11.2026

DOI: 10.1287/mnsc.2023.00747 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Management Science, online erschienen am 17.11.2026. Verfasst von Sumit Agarwal und 3 weiteren Autor:innen. Die Arbeit nennt 37 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The 0-1 knapsack problem is a fundamental problem of discrete choice that permeates many diverse fields and applications, but relatively little is known about what instances human solvers find more difficult than others. This paper reports the results of the first large-scale randomized controlled field experiment investigating this question, conducted in partnership with a global mobile gaming platform. A total of 100,000 different knapsack instances were predesigned for this study and randomly assigned to each player attempt at the knapsack problem. For our base-case analysis, there were 17,950,838 distinct player accounts who made a total of 150,284,195 submitted solution attempts. Contrary to expectations, players performed better on problems that were rated as more difficult by two traditional measures of knapsack difficulty (the Pearson correlation between value and weight vectors and Sahni complexity), but performed worse on problem instances that featured large optimality gaps from a suite of heuristic solution algorithms. These suggest that optimality gaps can serve as promising measures of human-perceived knapsack difficulty and potentially could be used to measure human-perceived problem difficulty for other types of discrete choice problems. We found evidence that players improved their performance with repeated attempts at the knapsack task overall, but less-experienced players of the mobile game improved more quickly than more-experienced players. Through the construction of a new measure of human-perceived difficulty rating for each knapsack instance, we found evidence that players who were assigned to instances with a higher difficulty rating in the past tended to perform better on future attempts. This paper was accepted by Manel Baucells, behavioral economics and decision analysis. Funding: S. Agarwal’s research is supported by the Ministry of Education, Singapore, under its Social Science and Humanities Research Thematic [Grant SSRC2024-SSHRTG-022] and the National Natural Science Foundation of China [Grant 72495154]. J. Goh’s research is supported by a Startup [Grant R-314-000-110-133] and a 2021 Humanities and Social Sciences Faculty Research Fellowship from the National University of Singapore. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.00747 .

Zitieren

APA

Agarwal, S., Goh, J., Qian, W., & Zou, X. (2026). Human Performance at Solving 0-1 Knapsack Problems: Results from a Large-Scale Field Experiment. Management Science. https://doi.org/10.1287/mnsc.2023.00747

Vancouver

Agarwal S, Goh J, Qian W, Zou X. Human Performance at Solving 0-1 Knapsack Problems: Results from a Large-Scale Field Experiment. Management Science. 2026. doi:10.1287/mnsc.2023.00747

BibTeX
@article{Agarwal2026,
  author = {Agarwal, Sumit and Goh, Joel and Qian, Wenlan and Zou, Xin},
  title = {Human Performance at Solving 0-1 Knapsack Problems: Results from a Large-Scale Field Experiment},
  journal = {Management Science},
  year = {2026},
  doi = {10.1287/mnsc.2023.00747}
}
Kostenlos starten →