====== Assignment 4: Auctions ======
AdSense has moved from second-price to a first-price sealed bid auction. Your objective will be to develop a program that computes 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 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 =====

  * 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. 


===== Template and Hints =====
You can use {{ :courses:cgt:auctions_2023_template.zip | this template }} to get started and {{ :courses:cgt:auctions_2024_simple_example_generator.py | 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 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 | }}

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).

  * 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,
  * 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.

*/