Assignment 4: Auctions

You own a hotel at Charles Square and wish to run online advertising with AdSense. Certain search terms such as “Luxury Hotel Charles Square” are more profitable than for example “Cheap accommodation Prague,” and attract a different but consistent number of bidders. Very specific searches, such as your exact hotel name will have a high click-through-rate, but may be pointless to pay for if you are the only buyer.

Until recently, AdSense used second-price sealed-bid auction rules, and bidding your private value was the optimal strategy. Unfortunately, AdSense has moved to a first-price auction, making your task more difficult. Your objective will be to develop a program that computes optimal bids under the new rules based on an expected revenue and the expected number of bidders. 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 of private values for a given search term from the historical data.

Assume that private values are independent and symmetrically distributed according to a normal distribution. Assume that the number of bidders is unchanged between the historical records, and the current situation.

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.

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

Part of your points will be awarded 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.

You can use this template to get started and this simple example generator for testing.

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 order statistics.

The cumulative distribution function of the $k$'th order statistic (the $k$'th smallest from a random sample of size $n$) of a normal distribution is given by $$ F_{k:n}(x) = \sum_{j=k}^n\binom{n}{j}(F(x))^j(1-F(x))^{n-j} $$ while its probability density function is $$ f_{k:n}(x) = \frac{n!}{(k-1)!(n-k)!}(F(x))^{k-1}(1-F(x))^{n-k}f(x) $$ where $F(x)$ and $f(x)$ are the CDF and the PDF of the normal distribution.

In a first-price auction, it is a symmetric equilibrium strategy to bid E[Y|Y≤v], where v is the private value and Y is a random variable, whose value equals the highest private value of other bidders. To compute this value, sample from the estimated distribution truncated by your private value, then compute the mean of the second highest bids (Yours being the highest), or use the formula from the solved exercise list.

• Generate examples with known parameters and test if fitting recovers them correctly,
• 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,
• Use the scipy.stats.fit function and not the method rv_continuous.fit,
• 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.
• BRUTE AE runs Python 3.13 with SciPy 1.15.