Knapsack Auctions

How to cite

Khezr, Peyman; Mohan, Vijay. 2023. "Knapsack Auctions." AEA RCT Registry. AEARCTR-0011146. https://doi.org/10.1257/rct.11146-1.1

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

Peyman Khezr* , Vijay Mohan

* Primary investigator

Registry ID
AEARCTR-0011146
DOI
https://doi.org/10.1257/rct.11146-1.1
First registered
Last updated
Status
In development
Trial dates
2023-03-30 – 2023-08-31
Countries
Private
JEL codes
D4
Registry record
http://www.socialscienceregistry.org/trials/11146

Abstract

A well-known problem in the scientific community is the 'Knapsack Problem', which essentially deals with how to fit objects of varying dimensions, and worth different values, into a space with a limited capacity (the knapsack). In general, this problem has been encountered in a number of applications ranging from filling cargo in an airplane, to selling advertisement slots on the internet or on television. Recently, there has been an expanding volume of research in the application of the Knapsack Problem in the context of blockchains; specifically, this research seeks to examine how transactions of varying data sizes can efficiently be allocated into a block with limited data capacity.

Our project focuses on developing 'Knapsack Auctions': a mechanism to allocate transactions to blocks that factors in asymmetric information between participants in a blockchain. This project has both a theoretical and an experimental component. While the theory provides broad guidelines on how to construct a Knapsack Auction, it has gaps relating to the behavioral responses of agents. To fill this gap, we conduct experiments on three different versions of the Knapsack Auction: the discriminatory-price auction, the generalized second-price (GSP) auction and the uniform-price auction. There are three central issues the experiments seek to address: first, which of the 3 auction versions yields the highest revenue for the seller; second, whether the uniform price auction outcomes conform to theoretical prediction of truthful bidding ; and third, the extent to which the discriminatory and GSP auctions result in under-bidding.

Intervention

The study involves lab experiments to evaluate 3 different candidates for a Knapsack Auction.

Experimental design

The experiment will seek to compare three alternative candidates for Knapsack Auctions: the discriminatory-price (DP) auction; the generalized second-price (GSP) auction; and, the uniform-price (UP) auction. Each variation is a treatment. Each iteration of an auction treatment involves 7 participants, and there are 10 iterations per treatment; each iteration will have different participants. There are 20 rounds of bidding planned for each iteration of the treatment.

In order to conduct these experiments, participants will be provided a units of experimental currency. The will also be assigned hypothetical objects with randomly assigned sizes. The participants will be instructed to submit bids (of the experimental currency) so that their object can be selected to fit into a knapsack of limited capacity. Each participant will be assigned a random value of the benefit (measured in units of the experimental currency) received if the object is indeed selected to fill the knapsack. Their cost will be in experimental currency units and will depend on the nature of the auction, as described below:
(a) In a DP auction, the cost to a participant will be his or her bid.
(b) In a GSP auction, the participant will pay the amount of the next lower bid.
(c) in a UP auction, all participants will pay a uniform amount equal to the highest losing bid.

A participant's payoff from the auction is the benefit minus the cost, again measured in units of the experimental currency. The goal of the participants will be to maximize their payoffs.

The outcomes we wish to test are:
(1) Which of the 3 auction versions yields the highest revenue for the seller
(2) Whether the uniform price auction outcomes conform to theoretical prediction of truthful bidding
(3) The extent to which the discriminatory and GSP auctions result in under-bidding
(4) How each of the versions perform in terms of efficiently allocating the knapsack space to potential bidders

Design details

Randomization method
Participants are randomly assigned to each treatment. Moreover, each participant will be randomly assigned values and sizes for objects to fit into the knapsack in every round that will be generated by a random number generator.
Randomization unit
There are 3 treatments and 10 iterations per treatment. Each individual is randomly selected into a treatment, and then randomly assigned to an iteration.
Clusters
There are 3 variations (treatments) of the Knapsack Auction. Each treatment will have 10 iterations, each with a distinct set of participants. So there will be 30 distinct iterations of the auction.
Observations
Each iteration will have 7 participants. No participant can take part in more than one iteration. The total number of unique participants required is 210 participants. Each participant will take part in 20 rounds of bidding in their assigned iteration, so there will be (a maximum of) 4200 bids across all rounds of the auction. Also given that there are 10 iterations for each version of the the knapsack auction, we collect 10 independent observations for each version.
Arms
The bids will placed across 600 rounds of auction bidding, with 200 rounds for each treatment.
Primary outcomes
(a) The revenue obtained from each variant of the Knapsack Auction (b) Whether participants engage in truthful bidding or not (c) Efficiency of each variant

Cited by

No citation data available for this registration yet.

Keywords