Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Assignment 3: Auctions

Deadline for submission to BRUTE is 12.12.2023

AdSense has moved from second-price to a first-price sealed bid auction. Your objective will be to develop a program that computes the optimal bids for purchasing website advertising space under the new rules.

When ad space is to be auctioned, N people are selected to participate. Every participant submits a sealed bit. The highest bid wins the space.

You know your own value for the space and how many people will participate in the auction. While you do not know the values of the other bidders, you have the historical records of prices from before the switch to first-price rules. You will need to reconstruct the distribution from the historical data. Assume that everyone bids rationally and that the private values are independent and symmetrically distributed according to a normal distribution.

Input and Output

The expected usage is python main.py < auction.txt > bid.txt.

The input has the following format:

private_value bidder_count
past_selling_price[0]
past_selling_price[1]
past_selling_price[2]
...

The output should be the estimated optimal bid represented as a single decimal number.

Requirements and Scoring

  • Upload all files as a single archive.
  • The main file must reside in the root of the archive (not in a sub-directory).
  • Your program must accept input from stdin and output to stdout.

Make sure You are not writing debugging output to stdout.

You will be awarded points based on the utility you achieve relative to the reference implementation on randomly generated auctions. The assignment will be graded based on the last score achieved, not the best.

Template and Hints

You can use this template to get started.

First, estimate the population distribution of private values from the past winning bids. You can use the scipy.stats.fit function by inheriting from scipy.stats.rv_continuous and implementing a custom distribution class for the kth order statistic of a normal distribution (the kth smallest from a random sample of size n).

The optimal strategy is to bid the amount you would expect to pay if you were the winner of a second-price auction. To do this, sample from the estimated distribution truncated by your private value, then compute the mean of the second highest bids (Yours being the highest).

  • You need to implement at least the _pdf function to use scipy.stats.fit,
  • Provide reasonable parameter bounds or an initial guess to the fitting function,
  • The _cdf function may be useful if you wish to generate testing data with rvs,
  • To sample from a truncated normal distribution, use the rvs function of scipy.stats.truncnorm,
  • The scipy.stats module already implements the pdf and cdf functions of the normal distribution,
  • The expected length of your solution is around 100 lines.
courses/cgt/assignment3.txt · Last modified: 2023/12/04 23:41 by votroto1