Difficult knapsack problems in theory and practice

How to cite

Goh, Joel. 2021. "Difficult knapsack problems in theory and practice." AEA RCT Registry. AEARCTR-0008307. https://doi.org/10.1257/rct.8307-1.0

Download: BibTeX · RIS — for reference managers without a browser translator. Zotero and most others pick up this page's citation metadata directly.

Joel Goh*

* Primary investigator

Registry ID
AEARCTR-0008307
DOI
https://doi.org/10.1257/rct.8307-1.0
First registered
Last updated
Status
In development
Trial dates
2021-09-29 – 2023-01-01
Countries
Private
Registry record
http://www.socialscienceregistry.org/trials/8307

Abstract

In this field study, we assess how people perform on knapsack problems with different levels of theoretical difficulties. Participants will be randomly assigned knapsack problems with varying levels of difficulty. We intend to assess whether problems that are theoretically "more difficult" produce worse solutions in participants and vice versa, as well as whether participants gain proficiency with the knapsack task as over more iterations of the problem. Finally, we plan to study if there are correlations between known characteristics of participants and their performance on the knapsack problem.

Intervention

Knapsack tasks of varying complexity levels.

Experimental design

This study is a field study using a randomized controlled design, where participants are randomly assigned knapsack problems with of varying levels of difficulty. The knapsack problem is coded in an electronic format as a mini-game, and there are a number of different study sites (servers) on which this game is hosted. Participants can play different instantiations of this problem (different item weights and values) either over 7 days or 14 days (depending on the server that hosts the game).

Design details

Randomization method
Randomization done by a computer server.
Randomization unit
Individual and instance; each individual has the option to play the mini-game over either 7 or 14 days. At each "instance" of the gameplay, the individual is randomly assigned (without replacement) a pre-generated instance of a knapsack problem.
Clusters
50 million gameplay instances
Observations
50 million gameplay instances
Arms
100,000 different knapsack problems
Primary outcomes
The average optimality gap between participants' submitted solutions and the actual optimal solution, and the proportion of solutions that were optimal.
Secondary outcomes
Whether there was evidence of "learning" -- do participants' quality of solutions improve as they repeatedly interact with the task; whether other observable characteristics of participants correlate with the quality of solution or the rate at which they learn.

Cited by

No citation data available for this registration yet.

Keywords