Difficult knapsack problems in theory and practice

Last registered on October 04, 2021
View Trial History

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

Country
Singapore
Region

Primary Investigator

Name
Joel Goh
Affiliation
National University of Singapore
Contact Primary Investigator

Other Primary Investigator(s)

Additional Trial Information

Status
In development
Start date
2021-09-29
End date
2023-01-01
Keywords
Behavior, Education
Additional Keywords
Computational Complexity
JEL code(s)
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 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)
Supporting Documents and Materials
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
Analysis Plan

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