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

背包问题 连续背包问题 启发式 数学优化 度量(数据仓库) 数学 变更制定问题 领域(数学) 计算机科学 广义指派问题 多项式时间逼近格式 任务(项目管理) 价值(数学) 博弈论 最优化问题
作者
Sumit D. Agarwal,Joel Goh,Wenlan Qian,Xin Zou
出处
期刊:Management Science [Institute for Operations Research and the Management Sciences]
标识
DOI:10.1287/mnsc.2023.00747
摘要

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 .
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
刚刚
wanci的应助被熊猫海采纳,获得10
刚刚
老张发布了新的文献求助10
1秒前
在水一方的应助被细心觅风采纳,获得10
1秒前
大模型的应助被要死的研究者采纳,获得10
1秒前
斯文败类的应助被duhp采纳,获得10
2秒前
风吹麦浪的应助被陈哈哈采纳,获得10
2秒前
2秒前
DCleanMeow完成签到,获得积分10
3秒前
3秒前
搜集达人的应助被温婉采纳,获得10
3秒前
3秒前
Blackmamba完成签到,获得积分10
4秒前
nenshen完成签到,获得积分10
4秒前
Xiang123完成签到,获得积分10
4秒前
4秒前
lml发布了新的文献求助10
5秒前
成就自行车关注了科研通微信公众号
5秒前
金融完成签到,获得积分10
6秒前
Dong完成签到,获得积分10
6秒前
阳光男孩完成签到,获得积分10
6秒前
zzz完成签到,获得积分10
6秒前
王晴晴完成签到,获得积分10
7秒前
酷波er的应助被聪聪哥哥采纳,获得10
7秒前
lijiaoshou完成签到,获得积分10
7秒前
7秒前
沉默的怀绿完成签到,获得积分10
7秒前
abc37发布了新的文献求助10
7秒前
无奈的萍完成签到,获得积分10
7秒前
xixi发布了新的文献求助10
8秒前
天然完成签到,获得积分10
8秒前
8秒前
霸王丹完成签到,获得积分10
9秒前
斯文败类的应助被dddd采纳,获得10
9秒前
丘比特的应助被霁月采纳,获得10
9秒前
和树发布了新的文献求助10
10秒前
zww发布了新的文献求助10
10秒前
molihuakai的应助被霁月采纳,获得10
10秒前
molihuakai的应助被霁月采纳,获得10
10秒前
无辜小鸭子完成签到,获得积分10
10秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
八旗制度の研究 600
Boundaries and Bodhisattvas 500
高分子基功能界面水蒸发材料与应用研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8182743
求助须知:如何正确求助?哪些是违规求助? 9572114
关于积分的说明 21822835
捐赠科研通 7779324
什么是DOI,文献DOI怎么找? 3433718
关于科研通互助平台的介绍 2557891
邀请新用户注册赠送积分活动 2479803