v1.0 (2016 Spring) Kabir Chandrasekher, Tony Duan, David Marn, Ashvin Nair, Kangwook Lee, Kannan Ramchandran
v1.1 (2017 Spring) Tavor Baharav, Kabir Chandrasekhar, Sinho Chewi, Andrew Liu, Kamil Nar, David Wang, and Kannan Ramchandran
If we want to use math and probability to gain some insight into this dilemma, we must first set up a theoretical model of an auction - which is basically a mechanism.
An auction has a seller, who is trying to sell one item. Multiple buyers (synonymous with "bidder") - there are $n$ of them - are interested in purchasing this item, but the item can only be sold to one buyer. Each buyer associates a value to an item (how much is this item worth to them). These values usually differ and may or may not be independent of one another. Call buyer $i$'s value of an item $x_i$. Each buyer then bids $\beta_i (x_i)$, a function of $x_i$. This is person $i$'s bidding function. The seller then sells the item to one of the buyers according to some mechanism $M$.
We will attempt to answer some basic questions about auctions. We are interested in:
We assume that this is a fair and reasonable auction. See auction details for a more precise definition, but in general, these assumptions simply mean that the auction operates as you would expect.
In this auction, each buyer makes one bid ("offer") to the seller. The seller sells the item to the highest bidder for that amount.
Example of an ad auction:
Advertiser | Bid | Ad shown? | Price paid |
---|---|---|---|
Abra | \$5 | Yes | \$5 |
Bulbasaur | \$3 | No | \$0 |
Charmander | \$2 | No | \$0 |
Suppose that we know that all buyers draw their values uniformly at random from the $(0,1)$ interval. Given that you are person $i$, valuing the item at $x_i$, how much should you bid? Suppose that everyone else is extremely risk averse, meaning that their function is $\beta_j(x_j) = x_j, \forall j \neq i$.
Try to maximize your profit (or expected utility, as referred in the homework), using the bidding function you derived in your homework!
We will begin by building a simulator for our auctions
#Your beautiful simulation code goes here
Now, run a simulation for 1000 rounds with two buyers, and your optimized bidding function. Plot your cumulative profit as it evolves over time. How much can you earn on average? How do your bidding function, cumulative profit, and expected profit change if we have $n$ other bidders (plot with n = 10)? Explain the differences between these graphs.
# your bidding function, plot of profit over 1000 rounds, and expected profit, for n=2
# your bidding function, plot of profit over 1000 rounds, and expected profit, for n=2
# Explanation for difference between graphs
Now assume that everyone draws their values from the exponential distribution with parameter $\lambda = 2$. How good of a bidding function can you empirically create for bidding against $n$ other people? Note that it is not necessary to find a closed form solution. Additionally, feel free to reuse code from previous parts.
# modified simulator for exponential
# your bidding function, plot of profit over 1000 rounds, and expected profit, for n=2
In this auction, each buyer again makes one secret bid. The bidder with the highest bid wins, but they only pay the second highest value. Google uses a modified version of this auction in practice ( see https://support.google.com/adsense/answer/160525?hl=en ).
Here is an example of a second price ad auction. Only one person gets to show the ad:
Advertiser | Bid | Ad shown? | Price paid |
---|---|---|---|
Abra | \$5 | Yes | \$3 |
Bulbasaur | \$3 | No | \$0 |
Charmander | \$2 | No | \$0 |
Operating under the same assumptions as in the first price option case, we assume all buyers draw their values uniformly at random from the $(0,1)$ interval. Given that you are person $i$, valuing the item at $x_i$, how much should you bid? Suppose that everyone else is extremely risk averse, meaning that their function is $\beta_j(x_j) = x_j, \forall j \neq i$. We will show that this is a good valuation function in the homework (Q7d).
Modify your simulator to work for the second-price auction case, or feel free to copy and alter you first price simulator.
Plot your cumulative profit for two buyers as it evolves over time. How much can you earn on average? How do your bidding function, cumulative profit, and expected profit change if we have $n$ other bidders?
# your bidding function, plot of profit over 1000 rounds, and expected profit, for n=2
# your bidding function, plot of profit over 1000 rounds, and expected profit, for n=10
Now, let's try and see how things look from the other side. Given that all $n$ buyers draw their values uniformly at random from the (0,1) interval, should the seller choose to hold a First Price Auction, or a Second Price Auction, given that people use optimal bidding functions as you solved for above and in the homework? Show your answer by plotting the revenue from both auctions.
# FPA and SPA revenue plots
In this scenario, you are again operating as the $\textbf{seller}$. You want to maximize your revenue selling $k$ identical items over $a$ auctions, $a\geq k$, and thus set a reserve price for each auction. This means that unless the maximum bid in a given auction is above the reserve price you set, the transaction is not completed, and no money or goods exchange hands. If the highest bid is above the reserve price, then the transaction occurs as per usual, with the winner paying what he bid in exchange for the item.
Here is an example of a first price auction with a reserve of $4:
Advertiser | Bid | Ad shown? | Price paid |
---|---|---|---|
Abra | \$5 | Yes | \$5 |
Bulbasaur | \$3 | No | \$0 |
Charmander | \$2 | No | \$0 |
Whereas, here is an example of that same auction with a reserve of $6:
Advertiser | Bid | Ad shown? | Price paid |
---|---|---|---|
Abra | \$5 | No | \$0 |
Bulbasaur | \$3 | No | \$0 |
Charmander | \$2 | No | \$0 |
Using a similar framework to before, we are now going to try to optimize the reserve to maximize the seller's profit.
Suppose that you have 1 iPhone that you can try to sell at 100 different auctions, with one auction occuring each day, where at each auction n bidders bid independently according to a fixed bidding function and a fixed but unknown distribution. If you can change the reserve for each auction, what should your reserve strategy as the seller be?
Below, please write an explanation of your strategy in markdown (no code needed)
Now suppose that you have 10 iPhones that you can take to 100 different auctions, with one auction occuring each day, where at each auction n bidders draw their values uniformly at random from the exponential distribution with parameter 2, with $\beta_j(x_j) = x_j, \forall j$. Empirically try and optimize one fixed reserve value to use over all the auctions to maximize your expected total revenue.
# Your optimized reserve and expected revenue
Now that we've got your attention, we'd like to announce our first lab competition! The top 3 teams (form teams of 2-3 people) will be given extra credit.
The details of the competition are as follows: you are a seller trying to maximize your expected revenue selling $k$ identical items over $a$ different auctions, where $n$ bidders draw their values uniformly at random from the interval (0,1), with $\beta_j(x_j) = x_j, \forall j$. Your job as the seller is to set a single fixed reserve price $r$ to be used over all $a$ auctions, to maximize your revenue. You will submit your solution in a separate python file, results.py, which will contain the method calculateReserve(a,k,n), where $a$ = # of auctions, $k$ = # of items, and $n$ = # of bidders. You may include any additional helper functions and standard imports you want. We will allow your algorithm to run for 30 seconds for each (a,k,n) input, awarding you 0 revenue for that input tuple if you run over the time limit. We will be running your code with Python 2, if we are unable to run it, you will not be entered into the competition.
Please include a comment at the top of your results.py file with the names of the members of your team. Only submit this file once per team.
Good Luck!
[1] Sahai, A., Mishra, M., Tandra, R., Woyach, K., 2009. Cognitive radios for spectrum sharing. IEEE Signal
Processing Magazine , 140–146.
[2] A. Sahai, K. Woyach, K. Harrison, H. Palaiyanur, and R. Tandra, “Towards a “theory of spectrum zoning”,” Allerton, Oct. 2009.
[3] Nozick, Robert. Anarchy, State, and Utopia. New York: Basic, 1974. Print.
[4] Rawls, J. A. (1971) A Theory of Justice. Cambridge, MA: Harvard University Press.
For this model to work, we should start with a list of assumptions: