Difficult knapsack problems in theory and practice

Last registered on October 04, 2021

Pre-Trial

Trial Information

General Information

Title
Difficult knapsack problems in theory and practice
RCT ID
AEARCTR-0008307
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.

Locations

Region

Primary Investigator

Affiliation
National University of Singapore

Other Primary Investigator(s)

Additional Trial Information

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

Registration Citation

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

Interventions

Intervention(s)
Knapsack tasks of varying complexity levels.
Intervention (Hidden)
We randomly generated 100,000 instances of the knapsack problem with different levels of complexity. Complexity was measured by the Sahni score, which measures how well a greedy algorithm would perform on the task, as well as through the correlation between the item weights and values (higher correlations close to 1 correspond to more difficult problems).
Intervention Start Date
2021-09-29
Intervention End Date
2021-10-11

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?
No

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)
IRB

Institutional Review Boards (IRBs)

IRB Name
Faculty Ethics Review Committee, NUS Business School
IRB Approval Date
2021-07-01
IRB Approval Number
BIZ-AO-21-0623

Post-Trial

Post Trial Information

Study Withdrawal

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

Request Information

Intervention

Is the intervention completed?
No
Data Collection Complete
Data Publication

Data Publication

Is public data available?
No

Program Files

Program Files
Reports, Papers & Other Materials

Relevant Paper(s)

Reports & Other Materials