Difficult knapsack problems in theory and practice

Last registered on October 04, 2021


Trial Information

General Information

Difficult knapsack problems in theory and practice
Initial registration date
September 29, 2021

Initial registration date is when the trial was registered.

It corresponds to when the registration was submitted to the Registry to be reviewed for publication.

First published
October 04, 2021, 2:00 PM EDT

First published corresponds to when the trial was first made public on the Registry after being reviewed.



Primary Investigator

National University of Singapore

Other Primary Investigator(s)

Additional Trial Information

In development
Start date
End date
Secondary IDs
Prior work
This trial does not extend or rely on any prior RCTs.
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.
External Link(s)

Registration Citation

Goh, Joel. 2021. "Difficult knapsack problems in theory and practice." AEA RCT Registry. October 04. https://doi.org/10.1257/rct.8307-1.0
Sponsors & Partners

There is information in this trial unavailable to the public. Use the button below to request access.

Request Information
Experimental Details


Knapsack tasks of varying complexity levels.
Intervention Start Date
Intervention End Date

Primary Outcomes

Primary Outcomes (end points)
The average optimality gap between participants' submitted solutions and the actual optimal solution, and the proportion of solutions that were optimal.
Primary Outcomes (explanation)

Secondary Outcomes

Secondary Outcomes (end points)
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.
Secondary Outcomes (explanation)

Experimental Design

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).
Experimental Design Details
This will be done in partnership with a mobile gaming company and listed as an in-game mini-game "event" for players to participate. The mobile game has an estimated playerbase of 80 million players across the world. Based on the participation rates for past events, we expect about 10 million players to participate in the event.
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.
Was the treatment clustered?

Experiment Characteristics

Sample size: planned number of clusters
50 million gameplay instances
Sample size: planned number of observations
50 million gameplay instances
Sample size (or number of clusters) by treatment arms
100,000 different knapsack problems
Minimum detectable effect size for main outcomes (accounting for sample design and clustering)

Institutional Review Boards (IRBs)

IRB Name
Faculty Ethics Review Committee, NUS Business School
IRB Approval Date
IRB Approval Number


Post Trial Information

Study Withdrawal

There is information in this trial unavailable to the public. Use the button below to request access.

Request Information


Is the intervention completed?
Data Collection Complete
Data Publication

Data Publication

Is public data available?

Program Files

Program Files
Reports, Papers & Other Materials

Relevant Paper(s)

Reports & Other Materials