\(\DeclareMathOperator*{\argmin}{arg\,min}\) \(\DeclareMathOperator*{\argmax}{arg\,max}\)
While auctions have been around for millenia, they have developed a deep importance in economic theory within the last century. More recently, the last two decades have seen an enormous rise in the practical application of auction theory in the context of selling online advertisements.
There are a myriad of auction types, but in this post we focus on two of the simplest formats, which are also relatively easy to analyze. These are the first-price and second-price (or Vickrey) sealed-bid auctions. We first provide a mathematical framing of the problem, describe each type of auction, and analyze the best bidding strategy in each.
Consider an auction with $n$ bidders, each of whom has a private value for the item under auction. For bidder $i$, denote this value by $x_i \in \mathbb{R}_+$, which we can intuitively think of as the price that bidder $i$ believes the item to be worth on the market.
In this post, we focus on auctions in which each bidder submits just one bid, and this bid is not disclosed to the other bidders. This is called a “sealed-bid” auction. At auction time, each bidder will submit a bid $b_i \in \mathbb{R}_+,$ representing the price they’re willing to pay for the item at the auction. Note that the bidder $i$’s bid $b_i$ need not be equal to their true assessment of the item’s value $x_i$. Bidder $i$ knows their own true value $x_i,$ but does not observe the other bidders’ values $\{x_j\}_{j \neq i},$ nor the other bidders’ bids $\{b_j\}_{j \neq i}.$ However, each bidder does know the total number of bidders in the auction.
When all bids have been submitted, a winner is chosen (deterministically, in our case) from the $n$ bidders based on their submitted bids, and the price the winner pays is determined as a function of the bids. In this post, we focus on auctions where the highest bidder wins the auction, and two settings for which price they pay. In a “first-price” auction, the winner pays the amount that they bid (which is the maximum bid). In a “second-price” auction (also known as a Vickrey auction), the winner pays the amount of the second-highest bid. For each auction, we have a payoff function $\Pi(x, b)$ that describes the payoff for a bidder with value $x$ who makes bid $b.$
We describe these in more detail below and work through the bidders’ equilibrium strategies in both types of auctions.
In a first-price sealed-bid auction, the bidder with the highest bid wins the auction and pays their bidding price for the item. The payoff for bidder $i$ is
\[\Pi(x_i, b_i) = \begin{cases} x_i - b_i & \text{ if } b_i > \max_{j \neq i} b_j \\\ 0 & \text{ otherwise.} \end{cases}\]Let $Y_1 = \max_{i \neq j}$ be the highest value of $\{X_j\}_{j\neq i}.$ Bidder $i$ wins when $b_i > \beta(Y_1).$ Thus, the probability that bidder $i$ wins the auction is given by
\[\mathbb{P}[b_i > \beta(Y_1)] = \mathbb{P}[Y_1 < \beta^{-1}(b_i)] = G(Y_1),\]where $G(\cdot)$ is the CDF of $Y_1$. If better $i$ wins the auction, their payoff is given by $x_i - b_i$. This implies that their expected payoff is
\[\mathbb{E}[\Pi(x_i, b_i)] = G(\beta^{-1}(b_i)) (x_i - b_i).\]To find the best bid, we can maximize the expected payoff with respect to $b_i$. This yields
\[\frac{\partial}{\partial b_i} \mathbb{E}[\Pi(x_i, b_i)] = \frac{g(\beta^{-1}(b_i))}{\beta^\prime (\beta^{-1}(b_i))}(x_i - b_i) - G(\beta^{-1}(b_i)).\]By definition, at a symmetric equilibrium we have $b_i = \beta(x_i) \implies \beta^{-1}(x_i) = x_i.$ Plugging this in and equating the deriviative to zero leads to
\[\frac{g(x_i)}{\beta^\prime (x_i)}(x_i - \beta(x_i)) - G(x_i) = 0.\]Rearranging, we have
\[\beta^\prime (x_i) G(x_i) + g(x_i) \beta(x_i) = x_i g(x_i) \implies \frac{d}{dx} \left[ \beta(x_i) G(x_i) \right] = x_i g(x_i).\]Integrating both sides and using the initial condition $\beta(0) = 0$ leaves us with
\[\beta(x_i) G(x_i) = \int_0^{x_i} t g(t) dt.\]We finally arrive at the optimum:
\begin{equation} \beta^\star(x_i) = \frac{1}{G(x_i)} \int_0^{x_i} t g(t) dt = \mathbb{E}[Y_1 | Y_1 < x_i]. \label{eq:first_price_optimum} \tag{1} \end{equation}
We have just derived the optimal strategy for bidder $i.$ However, to show that this is a symmetric equilibrium, we must also show that every other bidder should also follow this strategy. To do so, we can suppose that a bidder doesn’t follow this strategy and show that the expected outcome is suboptimal.
In particular, suppose bidder $j$ deviates from this strategy and instead bids an amount $b_j \neq \beta^\star(x_j),$ where $\beta^\star(\cdot)$ is defined in Equation \eqref{eq:first_price_optimum}. Let $z_j = \beta^{\star^{-1}}(b_j)$ be the hypothetical value that would have yielded the bid $b_j$ via the optimal bidding strategy.
Let’s compute the expected payoff for bidder $j$ by deviating from the strategy $\beta^\star.$
\[\mathbb{E}[\Pi(x_j, b_j)] = \underbrace{G(z_j)}_{\text{Prob. of winning}} \underbrace{(x_j - b_j)}_{\text{Payoff}} = G(z_j) (x_j - \beta^\star(z_j)).\]Plugging in the strategy given by Equation \eqref{eq:first_price_optimum}, we have
\begin{align} \mathbb{E}[\Pi(x_j, b_j)] &= G(z_j) x_j - G(z_j) \mathbb{E}[Y_1 | Y_1 < z_j] \\ &= G(z_j) x_j - G(z_j) \frac{1}{G(z_j)} \int_0^{z_j} t g(t) dt \\ &= G(z_j) x_j - \int_0^{z_j} t g(t) dt. \end{align}
We can solve the integral with integration by parts, letting $u = z$ and $v = G(z).$ This yields
\begin{align} \mathbb{E}[\Pi_j] &= G(z_j) x_j - G(z_j) z_j + \int_0^{z_j} G(t) dt \\ &= G(z_j) (x_j - z_j) + \int_0^{z_j} G(t) dt. \end{align}
Using a similar line of calculations, we find that the expected profit from bidding $\beta^\star(x_j)$ is $\int_0^{x_j} G(t) dt.$ Using these quantities, we can compute the difference in expected profit between betting $\beta^\star(x_j)$ and $\beta^\star(z_j):$
\begin{align} &\mathbb{E}[\Pi_j(x_j, \beta^\star(x_j)] - \mathbb{E}[\Pi_j(x_j, \beta^\star(z_j)] \\ =& ~\int_0^{x_j} G(t) dt - \left( G(z_j) (x_j - z_j) + \int_0^{z_j} G(t) dt \right) \\ =& ~G(z_j) (z_j - x_j) - \int_{x_j}^{z_j} G(t) dt. \end{align}
In all cases, it holds that
\[G(z_j) (z_j - x_j) \geq \int_{x_j}^{z_j} G(t) dt,\]implying that this difference is always nonnegative. In other words, the expected profit from following $\beta^\star(x_j)$ is always at least as good as bidding any other amount. Thus, we can conclude that it is optimal for all $n$ bidders to follow this strategy, making it a symmetric equilibrium.
In a second-price auction (also known as a Vickrey auction), the symmetric equilibrium strategy is given by
\[\beta(x_i) = x_i.\]In other words, the best strategy for each bidder is to simply bid the amount that they value the item.
To see this, we can walk through what would happen if this were not the case. Suppose instead that bidder $i$ submits a bid less than their value, $b_i < x_i,$ and suppose the highest competing bid is given by $y_1 = \max_{j \neq i} b_j.$ We have three cases:
We can see that, although the outcomes of the first two cases are identical regardless of whether bidder $i$ bids $x_i$ or $b_i < x_i,$ the outcome of case 3 is made worse by bidding $b_i < x_i.$ This allows us to conclude that this is a symmetric equilibrium strategy for a second-price auction.
Suppose that the bidders’ values are uniformly distributed, $x_1, \dots, x_n \sim \text{Unif}(0, 1).$ Recall that the CDF and PDF of the uniform are given by
\[F(x) = x,~~~f(x) = 1.\]In this case, the CDF and PDF of the maximum of $x_1, \dots, x_n$ are given by
\[F(y) = y^n,~~~f(y) = n y^{n-1}.\]The animation below shows the PDF of $y$ for an increasing value of $n$. We can see that the density tightens around the right end of the support (at $1$) as $n$ increases.
Let’s now evaluate the symmetric equilibrium strategy for a first-price auction. Recall that the strategy is given by
\[\beta^{\star}(x) = \frac{1}{G(x)} \int_0^{x} t g(t) dt.\]Plugging in $G(x) = x^{n-1}$ and $g(t) = (n - 1) t^{n-2},$ we have
\begin{align} \beta^{\star}(x) &= \frac{1}{x^{n-1}} \int_0^{x} t (n - 1) t^{n-2} dt \\ &= \frac{n - 1}{x^{n-1}} \int_0^{x} t^{n-1} dt \\ &= \frac{n - 1}{x^{n-1}} \left[\frac{1}{n} t^n \right] \bigg\rvert_{t=0}^x \\ &= \frac{n - 1}{x^{n-1}} \left(\frac{1}{n} x^n - 0 \right) \\ &= \frac{n - 1}{n} x. \end{align}
In this case, the best bidding strategy in a first-price auction is to bid a constant fraction of the true value $x.$ As the animation below shows, $\beta^\star(x)$ approaches $x$ as $n \to \infty.$