{
"cells": [
{
"cell_type": "markdown",
"id": "d80be0ac",
"metadata": {},
"source": [
"# First-Price and Second-Price Auctions\n",
"\n",
"This lecture is designed to set the stage for a subsequent lecture about [Multiple Good Allocation Mechanisms](https://python.quantecon.org/house_auction.html)\n",
"\n",
"In that lecture, a planner or auctioneer simultaneously allocates several goods to set of people.\n",
"\n",
"In the present lecture, a single good is allocated to one person within a set of people.\n",
"\n",
"Here we’ll learn about and simulate two classic auctions :\n",
"\n",
"- a First-Price Sealed-Bid Auction (FPSB) \n",
"- a Second-Price Sealed-Bid Auction (SPSB) created by William Vickrey [[Vickrey, 1961](https://python.quantecon.org/zreferences.html#id26)] \n",
"\n",
"\n",
"We’ll also learn about and apply a\n",
"\n",
"- Revenue Equivalent Theorem \n",
"\n",
"\n",
"We recommend watching this video about second price auctions by Anders Munk-Nielsen:\n",
"\n",
"and\n",
"\n",
"Anders Munk-Nielsen put his code [on GitHub](https://github.com/GamEconCph/Lectures-2021/tree/main/Bayesian%20Games).\n",
"\n",
"Much of our Python code below is based on his."
]
},
{
"cell_type": "markdown",
"id": "301734b2",
"metadata": {},
"source": [
"## First-Price Sealed-Bid Auction (FPSB)\n",
"\n",
"**Protocols:**\n",
"\n",
"- A single good is auctioned. \n",
"- Prospective buyers simultaneously submit sealed bids. \n",
"- Each bidder knows only his/her own bid. \n",
"- The good is allocated to the person who submits the highest bid. \n",
"- The winning bidder pays price she has bid. \n",
"\n",
"\n",
"**Detailed Setting:**\n",
"\n",
"There are $ n>2 $ prospective buyers named $ i = 1, 2, \\ldots, n $.\n",
"\n",
"Buyer $ i $ attaches value $ v_i $ to the good being sold.\n",
"\n",
"Buyer $ i $ wants to maximize the expected value of her **surplus** defined as $ v_i - p $, where\n",
"$ p $ is the price that she pays, conditional on her winning the auction.\n",
"\n",
"Evidently,\n",
"\n",
"- If $ i $ bids exactly $ v_i $, she pays what she thinks it is worth and gathers no surplus value. \n",
"- Buyer $ i $ will never want to bid more than $ v_i $. \n",
"- If buyer $ i $ bids $ b < v_i $ and wins the auction, then she gathers surplus value $ b - v_i > 0 $. \n",
"- If buyer $ i $ bids $ b < v_i $ and someone else bids more than $ b $, buyer $ i $ loses the auction and gets no surplus value. \n",
"- To proceed, buyer $ i $ wants to know the probability that she wins the auction as a function of her bid $ v_i $ \n",
" - this requires that she know a probability distribution of bids $ v_j $ made by prospective buyers $ j \\neq i $ \n",
"- Given her idea about that probability distribution, buyer $ i $ wants to set a bid that maximizes the mathematical expectation of her surplus value. \n",
"\n",
"\n",
"Bids are sealed, so no bidder knows bids submitted by other prospective buyers.\n",
"\n",
"This means that bidders are in effect participating in a game in which players do not know **payoffs** of other players.\n",
"\n",
"This is a **Bayesian game**, a Nash equilibrium of which is called a **Bayesian Nash equilibrium**.\n",
"\n",
"To complete the specification of the situation, we’ll assume that prospective buyers’ valuations are independently and identically distributed according to a probability distribution that is known by all bidders.\n",
"\n",
"Bidder optimally chooses to bid less than $ v_i $."
]
},
{
"cell_type": "markdown",
"id": "47323f8a",
"metadata": {},
"source": [
"### Characterization of FPSB Auction\n",
"\n",
"A FPSB auction has a unique symmetric Bayesian Nash Equilibrium.\n",
"\n",
"The optimal bid of buyer $ i $ is\n",
"\n",
"\n",
"<a id='equation-eq-optbid1'></a>\n",
"$$\n",
"\\mathbf{E}[y_{i} | y_{i} < v_{i}] \\tag{75.1}\n",
"$$\n",
"\n",
"where $ v_{i} $ is the valuation of bidder $ i $ and $ y_{i} $ is the maximum valuation of all other bidders:\n",
"\n",
"\n",
"<a id='equation-eq-optbid2'></a>\n",
"$$\n",
"y_{i} = \\max_{j \\neq i} v_{j} \\tag{75.2}\n",
"$$\n",
"\n",
"A proof for this assertion is available at the [Wikepedia page](https://en.wikipedia.org/wiki/Vickrey_auction) about Vickrey auctions"
]
},
{
"cell_type": "markdown",
"id": "927fc7bc",
"metadata": {},
"source": [
"## Second-Price Sealed-Bid Auction (SPSB)\n",
"\n",
"**Protocols:** In a second-price sealed-bid (SPSB) auction, the winner pays the second-highest bid."
]
},
{
"cell_type": "markdown",
"id": "bd45ead9",
"metadata": {},
"source": [
"## Characterization of SPSB Auction\n",
"\n",
"In a SPSB auction bidders optimally choose to bid their values.\n",
"\n",
"Formally, a dominant strategy profile in a SPSB auction with a single, indivisible item has each bidder bidding its value.\n",
"\n",
"A proof is provided at [the Wikepedia\n",
"page](https://en.wikipedia.org/wiki/Vickrey_auction) about Vickrey auctions"
]
},
{
"cell_type": "markdown",
"id": "a90e2f22",
"metadata": {},
"source": [
"## Uniform Distribution of Private Values\n",
"\n",
"We assume valuation $ v_{i} $ of bidder $ i $ is distributed $ v_{i} \\stackrel{\\text{i.i.d.}}{\\sim} U(0,1) $.\n",
"\n",
"Under this assumption, we can analytically compute probability distributions of prices bid in both FPSB and SPSB.\n",
"\n",
"We’ll simulate outcomes and, by using a law of large numbers, verify that the simulated outcomes agree with analytical ones.\n",
"\n",
"We can use our simulation to illustrate a **Revenue Equivalence Theorem** that asserts that on average first-price and second-price sealed bid auctions provide a seller the same revenue.\n",
"\n",
"To read about the revenue equivalence theorem, see [this Wikepedia page](https://en.wikipedia.org/wiki/Revenue_equivalence)"
]
},
{
"cell_type": "markdown",
"id": "8008b0da",
"metadata": {},
"source": [
"## Setup\n",
"\n",
"There are $ n $ bidders.\n",
"\n",
"Each bidder knows that there are $ n-1 $ other bidders."
]
},
{
"cell_type": "markdown",
"id": "7625219a",
"metadata": {},
"source": [
"## First price sealed bid auction\n",
"\n",
"An optimal bid for bidder $ i $ in a **FPSB** is described by equations [(75.1)](#equation-eq-optbid1) and [(75.2)](#equation-eq-optbid2).\n",
"\n",
"When bids are i.i.d. draws from a uniform distribution, the CDF of $ y_{i} $ is\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\tilde{F}_{n-1}(y) = \\mathbf{P}(y_{i} \\leq y) &= \\mathbf{P}(\\max_{j \\neq i} v_{j} \\leq y) \\\\\n",
"&= \\prod_{j \\neq i} \\mathbf{P}(v_{j} \\leq y) \\\\\n",
"&= y^{n-1}\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"and the PDF of $ y_i $ is $ \\tilde{f}_{n-1}(y) = (n-1)y^{n-2} $.\n",
"\n",
"Then bidder $ i $’s optimal bid in a **FPSB** auction is:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\mathbf{E}(y_{i} | y_{i} < v_{i}) &= \\frac{\\int_{0}^{v_{i}} y_{i}\\tilde{f}_{n-1}(y_{i})dy_{i}}{\\int_{0}^{v_{i}} \\tilde{f}_{n-1}(y_{i})dy_{i}} \\\\\n",
"&= \\frac{\\int_{0}^{v_{i}}(n-1)y_{i}^{n-1}dy_{i}}{\\int_{0}^{v_{i}}(n-1)y_{i}^{n-2}dy_{i}} \\\\\n",
"&= \\frac{n-1}{n}y_{i}\\bigg{|}_{0}^{v_{i}} \\\\\n",
"&= \\frac{n-1}{n}v_{i}\n",
"\\end{aligned}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "8bd2b14a",
"metadata": {},
"source": [
"## Second Price Sealed Bid Auction\n",
"\n",
"In a **SPSB**, it is optimal for bidder $ i $ to bid $ v_i $."
]
},
{
"cell_type": "markdown",
"id": "30af9697",
"metadata": {},
"source": [
"## Python Code"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "80db086a",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"import seaborn as sns\n",
"import scipy.stats as stats\n",
"import scipy.interpolate as interp\n",
"\n",
"# for plots\n",
"plt.rcParams.update({\"text.usetex\": True, 'font.size': 14})\n",
"colors = plt. rcParams['axes.prop_cycle'].by_key()['color']\n",
"\n",
"# ensure the notebook generate the same randomess\n",
"np.random.seed(1337)"
]
},
{
"cell_type": "markdown",
"id": "c819257f",
"metadata": {},
"source": [
"We repeat an auction with 5 bidders for 100,000 times.\n",
"\n",
"The valuations of each bidder is distributed $ U(0,1) $."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "29c055ac",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"N = 5\n",
"R = 100_000\n",
"\n",
"v = np.random.uniform(0,1,(N,R))\n",
"\n",
"# BNE in first-price sealed bid\n",
"\n",
"b_star = lambda vi,N :((N-1)/N) * vi\n",
"b = b_star(v,N)"
]
},
{
"cell_type": "markdown",
"id": "5a4be89c",
"metadata": {},
"source": [
"We compute and sort bid price distributions that emerge under both FPSB and SPSB."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "65022664",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"idx = np.argsort(v, axis=0) # Biders' values are sorted in ascending order in each auction.\n",
"# We record the order because we want to apply it to bid price and their id.\n",
"\n",
"v = np.take_along_axis(v, idx, axis=0) # same as np.sort(v, axis=0), except now we retain the idx\n",
"b = np.take_along_axis(b, idx, axis=0)\n",
"\n",
"ii = np.repeat(np.arange(1,N+1)[:,None], R, axis=1) # the id for the bidders is created.\n",
"ii = np.take_along_axis(ii, idx, axis=0) # the id is sorted according to bid price as well.\n",
"\n",
"winning_player = ii[-1,:] # In FPSB and SPSB, winners are those with highest values.\n",
"\n",
"winner_pays_fpsb = b[-1,:] # highest bid\n",
"winner_pays_spsb = v[-2,:] # 2nd-highest valuation"
]
},
{
"cell_type": "markdown",
"id": "7b5a385f",
"metadata": {},
"source": [
"Let’s now plot the *winning* bids $ b_{(n)} $ (i.e. the payment) against valuations, $ v_{(n)} $ for both FPSB and SPSB.\n",
"\n",
"Note that\n",
"\n",
"- FPSB: There is a unique bid corresponding to each valuation \n",
"- SPSB: Because it equals the valuation of a second-highest bidder, what a winner pays varies even holding fixed the winner’s valuation. So here there is a frequency distribution of payments for each valuation. "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "36e61d3d",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# We intend to compute average payments of different groups of bidders\n",
"\n",
"binned = stats.binned_statistic(v[-1,:], v[-2,:], statistic='mean', bins=20)\n",
"xx = binned.bin_edges\n",
"xx = [(xx[ii]+xx[ii+1])/2 for ii in range(len(xx)-1)]\n",
"yy = binned.statistic\n",
"\n",
"fig, ax = plt.subplots(figsize=(6, 4))\n",
"\n",
"ax.plot(xx, yy, label='SPSB average payment')\n",
"ax.plot(v[-1,:], b[-1,:], '--', alpha = 0.8, label = 'FPSB analytic')\n",
"ax.plot(v[-1,:], v[-2,:], 'o', alpha = 0.05, markersize = 0.1, label = 'SPSB: actual bids')\n",
"\n",
"ax.legend(loc='best')\n",
"ax.set_xlabel('Valuation, $v_i$')\n",
"ax.set_ylabel('Bid, $b_i$')\n",
"sns.despine()"
]
},
{
"cell_type": "markdown",
"id": "965e8016",
"metadata": {},
"source": [
"## Revenue Equivalence Theorem\n",
"\n",
"We now compare FPSB and a SPSB auctions from the point of view of the revenues that a seller can expect to acquire.\n",
"\n",
"**Expected Revenue FPSB:**\n",
"\n",
"The winner with valuation $ y $ pays $ \\frac{n-1}{n}*y $, where n is the number of bidders.\n",
"\n",
"Above we computed that the CDF is $ F_{n}(y) = y^{n} $ and the PDF is $ f_{n} = ny^{n-1} $.\n",
"\n",
"Consequently, expected revenue is\n",
"\n",
"$$\n",
"\\mathbf{R} = \\int_{0}^{1}\\frac{n-1}{n}v_{i}\\times n v_{i}^{n-1}dv_{i} = \\frac{n-1}{n+1}\n",
"$$\n",
"\n",
"**Expected Revenue SPSB:**\n",
"\n",
"The expected revenue equals n $ \\times $ expected payment of a bidder.\n",
"\n",
"Computing this we get\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\mathbf{TR} &= n\\mathbf{E_{v_i}}\\left[\\mathbf{E_{y_i}}[y_{i}|y_{i} < v_{i}]\\mathbf{P}(y_{i} < v_{i}) + 0\\times\\mathbf{P}(y_{i} > v_{i})\\right] \\\\\n",
"&= n\\mathbf{E_{v_i}}\\left[\\mathbf{E_{y_i}}[y_{i}|y_{i} < v_{i}]\\tilde{F}_{n-1}(v_{i})\\right] \\\\\n",
"&= n\\mathbf{E_{v_i}}[\\frac{n-1}{n} \\times v_{i} \\times v_{i}^{n-1}] \\\\\n",
"&= (n-1)\\mathbf{E_{v_i}}[v_{i}^{n}] \\\\\n",
"&= \\frac{n-1}{n+1}\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Thus, while probability distributions of winning bids typically differ across the two types of auction, we deduce that expected payments are identical in FPSB and SPSB."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "52064653",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots(figsize=(6, 4))\n",
"\n",
"for payment,label in zip([winner_pays_fpsb, winner_pays_spsb], ['FPSB', 'SPSB']):\n",
" print('The average payment of %s: %.4f. Std.: %.4f. Median: %.4f'% (label,payment.mean(),payment.std(),np.median(payment)))\n",
" ax.hist(payment, density=True, alpha=0.6, label=label, bins=100)\n",
"\n",
"ax.axvline(winner_pays_fpsb.mean(), ls='--', c='g', label='Mean')\n",
"ax.axvline(winner_pays_spsb.mean(), ls='--', c='r', label='Mean')\n",
"\n",
"ax.legend(loc='best')\n",
"ax.set_xlabel('Bid')\n",
"ax.set_ylabel('Density')\n",
"sns.despine()"
]
},
{
"cell_type": "markdown",
"id": "51ce032a",
"metadata": {},
"source": [
"**Summary of FPSB and SPSB results with uniform distribution on $ [0,1] $**\n",
"\n",
"|Auction: Sealed-Bid|First-Price|Second-Price|\n",
"|:-------------------------------:|:-------------------------------:|:-------------------------------:|\n",
"|Winner|Agent with highest bid|Agent with highest bid|\n",
"|Winner pays|Winner’s bid|Second-highest bid|\n",
"|Loser pays|0|0|\n",
"|Dominant strategy|No dominant strategy|Bidding truthfully is dominant strategy|\n",
"|Bayesian Nash equilibrium|Bidder $ i $ bids $ \\frac{n-1}{n}v_{i} $|Bidder $ i $ truthfully bids $ v_{i} $|\n",
"|Auctioneer’s revenue|$ \\frac {n-1}{n+1} $|$ \\frac {n-1}{n+1} $|\n",
"**Detour: Computing a Bayesian Nash Equibrium for FPSB**\n",
"\n",
"The Revenue Equivalence Theorem lets us an optimal bidding strategy for a FPSB auction from outcomes of a SPSB auction.\n",
"\n",
"Let $ b(v_{i}) $ be the optimal bid in a FPSB auction.\n",
"\n",
"The revenue equivalence theorem tells us that a bidder agent with value $ v_{i} $ on average receives the same **payment** in the two types of auction.\n",
"\n",
"Consequently,\n",
"\n",
"$$\n",
"b(v_{i})\\mathbf{P}(y_{i} < v_{i}) + 0 * \\mathbf{P}(y_{i} \\ge v_{i}) = \\mathbf{E}_{y_{i}}[y_{i} | y_{i} < v_{i}]\\mathbf{P}(y_{i} < v_{i}) + 0 * \\mathbf{P}(y_{i} \\ge v_{i})\n",
"$$\n",
"\n",
"It follows that an optimal bidding strategy in a FPSB auction is $ b(v_{i}) = \\mathbf{E}_{y_{i}}[y_{i} | y_{i} < v_{i}] $."
]
},
{
"cell_type": "markdown",
"id": "45ade7f9",
"metadata": {},
"source": [
"## Calculation of Bid Price in FPSB\n",
"\n",
"In equations [(75.1)](#equation-eq-optbid1) and [(75.1)](#equation-eq-optbid1), we displayed formulas for\n",
"optimal bids in a symmetric Bayesian Nash Equilibrium of a FPSB auction.\n",
"\n",
"$$\n",
"\\mathbf{E}[y_{i} | y_{i} < v_{i}]\n",
"$$\n",
"\n",
"where\n",
"\n",
"- $ v_{i} = $ value of bidder $ i $ \n",
"- $ y_{i} = $: maximum value of all bidders except $ i $, i.e., $ y_{i} = \\max_{j \\neq i} v_{j} $ \n",
"\n",
"\n",
"Above, we computed an optimal bid price in a FPSB auction analytically for a case in which private values are uniformly distributed.\n",
"\n",
"For most probability distributions of private values, analytical solutions aren’t easy to compute.\n",
"\n",
"Instead, we can compute bid prices in FPSB auctions numerically as functions of the distribution of private values."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f1701132",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def evaluate_largest(v_hat, array, order=1):\n",
" \"\"\"\n",
" A method to estimate the largest (or certain-order largest) value of the other biders,\n",
" conditional on player 1 wins the auction.\n",
"\n",
" Parameters:\n",
" ----------\n",
" v_hat : float, the value of player 1. The biggest value in the auction that player 1 wins.\n",
"\n",
" array: 2 dimensional array of bidders' values in shape of (N,R),\n",
" where N: number of players, R: number of auctions\n",
"\n",
" order: int. The order of largest number among bidders who lose.\n",
" e.g. the order for largest number beside winner is 1.\n",
" the order for second-largest number beside winner is 2.\n",
"\n",
" \"\"\"\n",
" N,R = array.shape\n",
" array_residual=array[1:,:].copy() # drop the first row because we assume first row is the winner's bid\n",
"\n",
" index=(array_residual<v_hat).all(axis=0)\n",
" array_conditional=array_residual[:,index].copy()\n",
"\n",
" array_conditional=np.sort(array_conditional, axis=0)\n",
" return array_conditional[-order,:].mean()"
]
},
{
"cell_type": "markdown",
"id": "8bf94211",
"metadata": {},
"source": [
"We can check the accuracy of our `evaluate_largest` method by comparing it with an analytical solution.\n",
"\n",
"We find that despite small discrepancy, the evaluate_largest method functions well.\n",
"\n",
"Furthermore, if we take a very large number of auctions, say 1 million, the discrepancy disappears."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "02203965",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"v_grid = np.linspace(0.3,1,8)\n",
"bid_analytical = b_star(v_grid,N)\n",
"bid_simulated = [evaluate_largest(ii, v) for ii in v_grid]\n",
"\n",
"fig, ax = plt.subplots(figsize=(6, 4))\n",
"\n",
"ax.plot(v_grid, bid_analytical, '-', color='k', label='Analytical')\n",
"ax.plot(v_grid, bid_simulated, '--', color='r', label='Simulated')\n",
"\n",
"ax.legend(loc='best')\n",
"ax.set_xlabel('Valuation, $v_i$')\n",
"ax.set_ylabel('Bid, $b_i$')\n",
"ax.set_title('Solution for FPSB')\n",
"sns.despine()"
]
},
{
"cell_type": "markdown",
"id": "ba8b47fd",
"metadata": {},
"source": [
"## $ \\chi^2 $ Distribution\n",
"\n",
"Let’s try an example in which the distribution of private values is a $ \\chi^2 $ distribution.\n",
"\n",
"We’ll start by taking a look at a $ \\chi^2 $ distribution with the help of the following Python code:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6969fb9e",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"np.random.seed(1337)\n",
"v = np.random.chisquare(df=2, size=(N*R,))\n",
"\n",
"plt.hist(v, bins=50, edgecolor='w')\n",
"plt.xlabel('Values: $v$')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "d783bbe2",
"metadata": {},
"source": [
"Now we’ll get Python to construct a bid price function"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "30432c4b",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"np.random.seed(1337)\n",
"v = np.random.chisquare(df=2, size=(N,R))\n",
"\n",
"\n",
"# we compute the quantile of v as our grid\n",
"pct_quantile = np.linspace(0, 100, 101)[1:-1]\n",
"v_grid = np.percentile(v.flatten(), q=pct_quantile)\n",
"\n",
"EV=[evaluate_largest(ii, v) for ii in v_grid]\n",
"# nan values are returned for some low quantiles due to lack of observations"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "79e873cf",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# we insert 0 into our grid and bid price function as a complement\n",
"EV=np.insert(EV,0,0)\n",
"v_grid=np.insert(v_grid,0,0)\n",
"\n",
"b_star_num = interp.interp1d(v_grid, EV, fill_value=\"extrapolate\")"
]
},
{
"cell_type": "markdown",
"id": "e13ab930",
"metadata": {},
"source": [
"We check our bid price function by computing and visualizing the result."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "18a632a8",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"pct_quantile_fine = np.linspace(0, 100, 1001)[1:-1]\n",
"v_grid_fine = np.percentile(v.flatten(), q=pct_quantile_fine)\n",
"\n",
"fig, ax = plt.subplots(figsize=(6, 4))\n",
"\n",
"ax.plot(v_grid, EV, 'or', label='Simulation on Grid')\n",
"ax.plot(v_grid_fine, b_star_num(v_grid_fine) , '-', label='Interpolation Solution')\n",
"\n",
"ax.legend(loc='best')\n",
"ax.set_xlabel('Valuation, $v_i$')\n",
"ax.set_ylabel('Optimal Bid in FPSB')\n",
"sns.despine()"
]
},
{
"cell_type": "markdown",
"id": "8da68bfb",
"metadata": {},
"source": [
"Now we can use Python to compute the probability distribution of the price paid by the winning bidder"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7502e3a8",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"b=b_star_num(v)\n",
"\n",
"idx = np.argsort(v, axis=0)\n",
"v = np.take_along_axis(v, idx, axis=0) # same as np.sort(v, axis=0), except now we retain the idx\n",
"b = np.take_along_axis(b, idx, axis=0)\n",
"\n",
"ii = np.repeat(np.arange(1,N+1)[:,None], R, axis=1)\n",
"ii = np.take_along_axis(ii, idx, axis=0)\n",
"\n",
"winning_player = ii[-1,:]\n",
"\n",
"winner_pays_fpsb = b[-1,:] # highest bid\n",
"winner_pays_spsb = v[-2,:] # 2nd-highest valuation"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e876543e",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots(figsize=(6, 4))\n",
"\n",
"for payment,label in zip([winner_pays_fpsb, winner_pays_spsb], ['FPSB', 'SPSB']):\n",
" print('The average payment of %s: %.4f. Std.: %.4f. Median: %.4f'% (label,payment.mean(),payment.std(),np.median(payment)))\n",
" ax.hist(payment, density=True, alpha=0.6, label=label, bins=100)\n",
"\n",
"ax.axvline(winner_pays_fpsb.mean(), ls='--', c='g', label='Mean')\n",
"ax.axvline(winner_pays_spsb.mean(), ls='--', c='r', label='Mean')\n",
"\n",
"ax.legend(loc='best')\n",
"ax.set_xlabel('Bid')\n",
"ax.set_ylabel('Density')\n",
"sns.despine()"
]
},
{
"cell_type": "markdown",
"id": "92e33473",
"metadata": {},
"source": [
"## 5 Code Summary\n",
"\n",
"We assemble the functions that we have used into a Python class"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f8110779",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"class bid_price_solution:\n",
"\n",
" def __init__(self, array):\n",
" \"\"\"\n",
" A class that can plot the value distribution of bidders,\n",
" compute the optimal bid price for bidders in FPSB\n",
" and plot the distribution of winner's payment in both FPSB and SPSB\n",
"\n",
" Parameters:\n",
" ----------\n",
"\n",
" array: 2 dimensional array of bidders' values in shape of (N,R),\n",
" where N: number of players, R: number of auctions\n",
"\n",
" \"\"\"\n",
" self.value_mat=array.copy()\n",
"\n",
" return None\n",
"\n",
" def plot_value_distribution(self):\n",
" plt.hist(self.value_mat.flatten(), bins=50, edgecolor='w')\n",
" plt.xlabel('Values: $v$')\n",
" plt.show()\n",
"\n",
" return None\n",
"\n",
" def evaluate_largest(self, v_hat, order=1):\n",
" N,R = self.value_mat.shape\n",
" array_residual = self.value_mat[1:,:].copy()\n",
" # drop the first row because we assume first row is the winner's bid\n",
"\n",
" index=(array_residual<v_hat).all(axis=0)\n",
" array_conditional=array_residual[:,index].copy()\n",
"\n",
" array_conditional=np.sort(array_conditional, axis=0)\n",
"\n",
" return array_conditional[-order,:].mean()\n",
"\n",
" def compute_optimal_bid_FPSB(self):\n",
" # we compute the quantile of v as our grid\n",
" pct_quantile = np.linspace(0, 100, 101)[1:-1]\n",
" v_grid = np.percentile(self.value_mat.flatten(), q=pct_quantile)\n",
"\n",
" EV=[self.evaluate_largest(ii) for ii in v_grid]\n",
" # nan values are returned for some low quantiles due to lack of observations\n",
"\n",
" # we insert 0 into our grid and bid price function as a complement\n",
" EV=np.insert(EV,0,0)\n",
" v_grid=np.insert(v_grid,0,0)\n",
"\n",
" self.b_star_num = interp.interp1d(v_grid, EV, fill_value=\"extrapolate\")\n",
"\n",
" pct_quantile_fine = np.linspace(0, 100, 1001)[1:-1]\n",
" v_grid_fine = np.percentile(self.value_mat.flatten(), q=pct_quantile_fine)\n",
"\n",
" fig, ax = plt.subplots(figsize=(6, 4))\n",
"\n",
" ax.plot(v_grid, EV, 'or', label='Simulation on Grid')\n",
" ax.plot(v_grid_fine, self.b_star_num(v_grid_fine) , '-', label='Interpolation Solution')\n",
"\n",
" ax.legend(loc='best')\n",
" ax.set_xlabel('Valuation, $v_i$')\n",
" ax.set_ylabel('Optimal Bid in FPSB')\n",
" sns.despine()\n",
"\n",
" return None\n",
"\n",
" def plot_winner_payment_distribution(self):\n",
" self.b = self.b_star_num(self.value_mat)\n",
"\n",
" idx = np.argsort(self.value_mat, axis=0)\n",
" self.v = np.take_along_axis(self.value_mat, idx, axis=0) # same as np.sort(v, axis=0), except now we retain the idx\n",
" self.b = np.take_along_axis(self.b, idx, axis=0)\n",
"\n",
" self.ii = np.repeat(np.arange(1,N+1)[:,None], R, axis=1)\n",
" self.ii = np.take_along_axis(self.ii, idx, axis=0)\n",
"\n",
" winning_player = self.ii[-1,:]\n",
"\n",
" winner_pays_fpsb = self.b[-1,:] # highest bid\n",
" winner_pays_spsb = self.v[-2,:] # 2nd-highest valuation\n",
"\n",
" fig, ax = plt.subplots(figsize=(6, 4))\n",
"\n",
" for payment,label in zip([winner_pays_fpsb, winner_pays_spsb], ['FPSB', 'SPSB']):\n",
" print('The average payment of %s: %.4f. Std.: %.4f. Median: %.4f'% (label,payment.mean(),payment.std(),np.median(payment)))\n",
" ax.hist(payment, density=True, alpha=0.6, label=label, bins=100)\n",
"\n",
" ax.axvline(winner_pays_fpsb.mean(), ls='--', c='g', label='Mean')\n",
" ax.axvline(winner_pays_spsb.mean(), ls='--', c='r', label='Mean')\n",
"\n",
" ax.legend(loc='best')\n",
" ax.set_xlabel('Bid')\n",
" ax.set_ylabel('Density')\n",
" sns.despine()\n",
"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5b233a2a",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"np.random.seed(1337)\n",
"v = np.random.chisquare(df=2, size=(N,R))\n",
"\n",
"chi_squ_case = bid_price_solution(v)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4a769742",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"chi_squ_case.plot_value_distribution()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d9468e04",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"chi_squ_case.compute_optimal_bid_FPSB()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "66d98455",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"chi_squ_case.plot_winner_payment_distribution()"
]
},
{
"cell_type": "markdown",
"id": "b2e7ec5f",
"metadata": {},
"source": [
"## References\n",
"\n",
"1. Wikipedia for FPSB: [https://en.wikipedia.org/wiki/First-price_sealed-bid_auction](https://en.wikipedia.org/wiki/First-price_sealed-bid_auction) \n",
"1. Wikipedia for SPSB: [https://en.wikipedia.org/wiki/Vickrey_auction](https://en.wikipedia.org/wiki/Vickrey_auction) \n",
"1. Chandra Chekuri’s lecture note for algorithmic game theory: [http://chekuri.cs.illinois.edu/teaching/spring2008/Lectures/scribed/Notes20.pdf](http://chekuri.cs.illinois.edu/teaching/spring2008/Lectures/scribed/Notes20.pdf) \n",
"1. Tim Salmon. ECO 4400 Supplemental Handout: All About Auctions: [https://s2.smu.edu/tsalmon/auctions.pdf](https://s2.smu.edu/tsalmon/auctions.pdf) \n",
"1. Auction Theory- Revenue Equivalence Theorem: [https://michaellevet.wordpress.com/2015/07/06/auction-theory-revenue-equivalence-theorem/](https://michaellevet.wordpress.com/2015/07/06/auction-theory-revenue-equivalence-theorem/) \n",
"1. Order Statistics: [https://online.stat.psu.edu/stat415/book/export/html/834](https://online.stat.psu.edu/stat415/book/export/html/834) "
]
}
],
"metadata": {
"date": 1750302298.4512863,
"filename": "two_auctions.md",
"kernelspec": {
"display_name": "Python",
"language": "python3",
"name": "python3"
},
"title": "First-Price and Second-Price Auctions"
},
"nbformat": 4,
"nbformat_minor": 5
}