{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# SOLD!\n",
"\n",
"\n",
"#### Authors:\n",
"v1.0 (2016 Spring) Kabir Chandrasekher, Tony Duan, David Marn, Ashvin Nair, Kangwook Lee, and Kannan Ramchandran\n",
"\n",
"v1.1 (2017 Spring) Tavor Baharav, Kabir Chandrasekhar, Sinho Chewi, Andrew Liu, Kamil Nar, David Wang, and Kannan Ramchandran\n",
"\n",
"v1.2 (2017 Fall) Sinho Chewi, Avishek Ghosh, Chen Meng, Abhay Parekh, and Jean Walrand\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
" | \n",
"\n",
" |

\n",
"Be it frequency bandwidth or ads that we \"see\" everyday (thanks Adblock Plus!), we're constantly asking ourselves how to distribute goods in a \"fair\" manner. Optimal allocation of rival goods is a hot question in both theoretical EE research (see research articles by Sahai [[1]](#References) and Harrison [[2]](#References)) and in society as a philosophical conundrum (see books by Nozick [[3]](#References) or Rawles [[4]](#References)).\n",
"\n",
"## Introduction\n",
"\n",
"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. \n",
"\n",
"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$. \n",
"\n",
"\n",
"\n",
"We will attempt to answer some basic questions about auctions. We are interested in:\n",
"\n",
"- Seller revenue, i.e. how much does the seller make?
\n",
"- Buyer profit - what, if any, is the difference between the winning bid and the buyer's value of an item?
\n",
"- Difference between mechanisms - what difference does the type of auction have on the buyer? What about the seller? How do reserves affect them?
\n",
"

\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Assumptions\n",
"We assume that this is a fair and reasonable auction. See [auction details](#Definitions) for a more precise definition, but in general, these assumptions simply mean that the auction operates as you would expect."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Q1) First Price Auction (FPA)\n",
"In this auction, each buyer makes one bid (\"offer\") to the seller. The seller sells the item to the highest bidder for that amount. \n",
"\n",
"Example of an ad auction:\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"Advertiser | Bid | Ad shown? | Price paid |
---|

Abra | \\$5 | Yes | \\$5 |

Bulbasaur | \\$3 | No | \\$0 |

Charmander | \\$2 | No | \\$0 |

\n",
"In this example, the seller revenue is \\$5.\n",
"\n",
"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$. \n",
"\n",
"Try to maximize your profit (or expected utility, as referred in the homework), using the bidding function you derived in your homework!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Auction Simulator\n",
"We will begin by building a simulator for our auctions."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def simulate_fpa(num_players, beta_fn, distribution, num_trials=1000):\n",
" \"\"\"\n",
" num_players (int): The number of bidders in the auction.\n",
" beta_fn (function): The bidding function (takes in as input the valuation of\n",
" a bidder and returns how much the bidder bids).\n",
" distribution (str): The distribution from which the valuations are drawn.\n",
" This can be either \"uniform\" or \"exponential\". See Q1(a) and Q1(b).\n",
" num_trials (int): The number of trials for which the simulation will run.\n",
"\n",
" Returns: profit_timeseries (np.ndarray)\n",
" An array containing the cumulative profit after each round. This will\n",
" be plotted in Q1(a) and Q1(b).\n",
" \"\"\"\n",
" # Your beautiful simulation code goes here\n",
" pass"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Q1 (a) FPA Uniform\n",
"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 (calculate this by hand) change if we have $n-1$ other bidders (plot with $n = 10$ (9 other bidders))? Explain the differences between these graphs."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# your bidding function, plot of profit over 1000 rounds, and expected profit,\n",
"# for n = 2 (1 other bidder)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# your bidding function, plot of profit over 1000 rounds, and expected profit,\n",
"# for n = 10 (9 other bidders)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# explanation for difference between graphs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Q1 (b) FPA Exponential\n",
"Now assume that everyone (including you) draws their values from the exponential distribution with parameter $\\lambda = 2$. Assuming everyone else is still bidding their valuation, how good of a bidding function can you empirically create for bidding against 9 other people ($n = 10$), who all bid their valuations? Note that it is not necessary to find a closed-form solution. Just play around with different bidding functions and try to find the best one you can! Additionally, feel free to reuse code from previous parts."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# modified simulator for exponential\n",
"# your bidding function and plot of profit over 1000 rounds for n = 5"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Q2) Second Price Auction (SPA)\n",
"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).\n",
"\n",
"Here is an example of a second price ad auction. Only one person gets to show the ad: \n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"Advertiser | Bid | Ad shown? | Price paid |
---|

Abra | \\$5 | Yes | \\$3 |

Bulbasaur | \\$3 | No | \\$0 |

Charmander | \\$2 | No | \\$0 |

\n",
"In this example, the seller revenue is \\$3.\n",
"\n",
"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.\n",
"\n",
"Modify your simulator to work for the second-price auction case, or feel free to copy and alter you first price simulator."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Q2 (a) SPA Profit\n",
"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$ bidders total ($n-1$ other bidders)? Evaluate the latter for $n = 10$ (9 other bidders)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# your bidding function, plot of profit over 1000 rounds, and expected profit,\n",
"# for n = 2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# your bidding function, plot of profit over 1000 rounds, and expected profit,\n",
"# for n = 10"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Q2 (b) Seller Revenue\n",
"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."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# FPA and SPA revenue plots"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Q3) First Price Auction with a Reserve\n",
"\n",
"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.\n",
"\n",
"Here is an example of a first price auction with a reserve of $4: \n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"Advertiser | Bid | Ad shown? | Price paid |
---|

Abra | \\$5 | Yes | \\$5 |

Bulbasaur | \\$3 | No | \\$0 |

Charmander | \\$2 | No | \\$0 |

\n",
"In this example, the seller revenue is \\$5.\n",
"\n",
"\n",
"Whereas, here is an example of that same auction with a reserve of $6:\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"Advertiser | Bid | Ad shown? | Price paid |
---|

Abra | \\$5 | No | \\$0 |

Bulbasaur | \\$3 | No | \\$0 |

Charmander | \\$2 | No | \\$0 |

\n",
"In this example, the seller revenue is \\$0.\n",
"\n",
"\n",
"Using a similar framework to before, we are now going to try to optimize the reserve to maximize the seller's profit."
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"### Q3 (a) Varying Reserve\n",
"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?\n",
"\n",
"Below, please write an explanation of your strategy in markdown (no code needed)."
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"#### Q3 (a) $\\mathcal{Y}\\text{our beautiful explanation here}$:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Q3 (b) Fixed Reserve\n",
"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 = 5$ 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."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# Your optimized reserve and expected revenue"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Competition (Optional)\n",
"\n",
"Now that we've got your attention, we'd like to announce our first lab competition! The top 3 teams (form teams of 3-4 people) will be given extra credit.\n",
"\n",
"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.\n",
"\n",
"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.\n",
"\n",
"Good Luck!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## References\n",
"[1] Sahai, A., Mishra, M., Tandra, R., Woyach, K., 2009. Cognitive radios for spectrum sharing. IEEE Signal\n",
"Processing Magazine , 140–146.

\n",
"[2] A. Sahai, K. Woyach, K. Harrison, H. Palaiyanur, and R. Tandra, “Towards a “theory of spectrum zoning”,” Allerton, Oct. 2009.

\n",
"[3] Nozick, Robert. Anarchy, State, and Utopia. New York: Basic, 1974. Print.

\n",
"[4] Rawls, J. A. (1971) A Theory of Justice. Cambridge, MA: Harvard University Press.

\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Definitions\n",
"For this model to work, we should start with a list of assumptions:\n",
"\n",
"- Infinite wealth: Each buyer can afford to pay their valuation of the item;
\n",
"- Anonymity: The only thing that matters is the buyer's bid, not the identity of the buyer (more formally, if buyer $i$ offers $x_i$ and wins against buyer $j$ who offers $x_j$, then buyer $j$ would win if she would offer $x_i + \\epsilon$);
\n",
"- Privacy: Buyer $i$ only knows the value $x_i$ and does not know any bids or valuations $\\beta_j \\text{ or } x_j \\ \\forall j\\neq i$;
\n",
"- All auctions are sealed-bid auctions: Every buyer submits the bid simultaneously.
\n",
"

\n",
"[Back to Assumptions](#Assumptions)"
]
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.1"
}
},
"nbformat": 4,
"nbformat_minor": 0
}