====== 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:

<code>
private_value bidder_count
past_selling_price[0]
past_selling_price[1]
past_selling_price[2]
...
</code>

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 {{ :courses:cgt:auctions_2023_template.zip | 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 //k//th order statistic of a normal distribution (the //k//th smallest from a random sample of size //n//). 

{{ :courses:cgt:auctions_2023_hint_norm_sos_pdf_cdf.png?673 | }}

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.