Decision Theory

Auction Theory

First-price, second-price, English, Dutch. Revenue equivalence, optimal reserve prices, Myerson's theorem, and connections to ad auctions, spectrum allocation, and ML compute markets.

AdvancedTier 2Stable~45 min

Prerequisites

Game Theory Nash Equilibrium Common Probability Distributions

Quiz (3)

Why This Matters

Auctions allocate billions of dollars daily. Online advertising runs on real-time auction systems (Google's ad auctions process billions of queries per day). Government spectrum auctions have raised hundreds of billions of dollars. Cloud compute pricing increasingly uses auction-like mechanisms.

The theory behind auctions connects game theory, mechanism design, and optimization. The central insight is the revenue equivalence theorem: under standard assumptions, the auction format does not matter. First-price, second-price, English, Dutch: all yield the same expected revenue. Once you relax the assumptions, the differences become precise and predictable.

For ML practitioners, auction theory is relevant whenever you design or interact with pricing mechanisms for compute, data, or model access. It is also a clean example of Bayesian game theory and mechanism design.

Auction Formats

Definition

First-Price Sealed-Bid Auction

Each bidder submits a sealed bid. The highest bidder wins and pays their bid. Bidders face a tradeoff: bidding higher increases the probability of winning but decreases the surplus from winning. Rational bidders shade their bids below their true valuations.

Definition

Second-Price Sealed-Bid (Vickrey) Auction

Each bidder submits a sealed bid. The highest bidder wins and pays the second-highest bid. Named after William Vickrey, who showed this format has a dominant strategy: bid your true valuation.

Definition

English (Ascending) Auction

The price starts low and rises. Bidders drop out when the price exceeds their willingness to pay. The last bidder standing wins and pays the price at which the second-to-last bidder dropped out. Strategically equivalent to a second-price sealed-bid auction under independent private values.

Definition

Dutch (Descending) Auction

The price starts high and drops. The first bidder to accept the current price wins and pays that price. Strategically equivalent to a first-price sealed-bid auction: accepting at price $b$ is the same as submitting bid $b$ .

The Independent Private Values Model

Definition

Independent Private Values (IPV)

The independent private values model assumes:

Each bidder $i$ has a private valuation $v_i$ for the item.
Valuations are independently drawn from a common distribution $F$ with density $f$ on $[0, \bar{v}]$ .
Each bidder knows their own $v_i$ but not the others' valuations.
Bidders are risk-neutral expected utility maximizers.

A bidder's payoff from winning at price $p$ is $v_i - p$ . The payoff from losing is 0.

Truthful Bidding in Second-Price Auctions

Theorem

Truthful Bidding in Vickrey Auctions

Statement

In a second-price sealed-bid auction, bidding $b_i = v_i$ (your true valuation) is a weakly dominant strategy. That is, regardless of what other bidders do, you can never do better than bidding truthfully, and you can sometimes do strictly worse by bidding differently.

Intuition

Your bid determines whether you win, not what you pay. If you win, you pay the second-highest bid, which is independent of your own bid. Overbidding ( $b_i > v_i$ ) risks winning at a price above your valuation (negative surplus). Underbidding ( $b_i < v_i$ ) risks losing when you could have won at a profitable price. Bidding exactly $v_i$ wins exactly when winning is profitable.

Proof Sketch

Fix the second-highest bid at $p$ . If $v_i > p$ : bidding $v_i$ wins and yields surplus $v_i - p > 0$ . Any bid $b_i > p$ also wins with the same surplus. Any bid $b_i < p$ loses, yielding 0. So $b_i = v_i$ is at least as good as any other bid. If $v_i < p$ : bidding $v_i$ loses (surplus 0). Any bid $b_i > p$ wins but yields negative surplus $v_i - p < 0$ . So $b_i = v_i$ is strictly better than overbidding. If $v_i = p$ : all bids yield 0 surplus. In every case, $b_i = v_i$ is weakly optimal.

Why It Matters

Truthfulness is rare in mechanism design. The Gibbard-Satterthwaite theorem says no non-dictatorial social choice function is strategy-proof without payments. Vickrey auctions achieve truthfulness precisely because the payment is decoupled from the bid: you pay someone else's bid, not your own. This principle generalizes to VCG (Vickrey-Clarke-Groves) mechanisms.

Failure Mode

Truthfulness is dominant strategy only for single-item auctions with private values. In multi-item auctions, VCG truthfulness holds but can lead to low revenue. In common-value settings (where the item has a single true value unknown to all bidders), truthful bidding in a Vickrey auction does not prevent the winner's curse. Risk-averse bidders may also deviate from truthful bidding.

Equilibrium Bidding in First-Price Auctions

In a first-price auction, you pay your bid. Bidding your true valuation guarantees zero surplus. Rational bidders shade their bids below $v_i$ .

Proposition

Symmetric Equilibrium in First-Price Auctions

Statement

In a symmetric Bayesian Nash equilibrium of the first-price auction with $n$ i.i.d. bidders with CDF $F$ , the equilibrium bid function is:

$\beta(v) = v - \frac{\int_0^v F(t)^{n-1} \, dt}{F(v)^{n-1}}$

For the uniform distribution $F(v) = v/\bar{v}$ on $[0, \bar{v}]$ , this simplifies to:

$\beta(v) = \frac{n-1}{n} v$

Each bidder shades their bid by a factor of $1/n$ . With more bidders, competition increases and bids approach true valuations.

Intuition

The bidder trades off two effects: raising the bid increases the probability of winning ( $F(\beta^{-1}(b))^{n-1}$ ) but decreases the surplus ( $v - b$ ). The optimal bid balances these. With uniform valuations and $n$ bidders, the expected highest competing valuation is $(n-1)v/n$ (the expected value of the maximum of $n-1$ uniform draws conditional on your value being the highest). So the optimal bid equals this expected competing maximum.

Proof Sketch

Bidder $i$ with valuation $v$ chooses $b$ to maximize expected payoff $(v - b) \cdot P(\text{win})$ . In a symmetric equilibrium with bid function $\beta$ , a bid of $b = \beta(z)$ wins if all other bidders have valuations below $z$ , so $P(\text{win}) = F(z)^{n-1}$ . The objective is $(v - \beta(z)) F(z)^{n-1}$ . Take the first-order condition with respect to $z$ and set $z = v$ (the equilibrium condition). This gives the ODE $\beta'(v) F(v)^{n-1} + (n-1) \beta(v) F(v)^{n-2} f(v) = (n-1) v F(v)^{n-2} f(v)$ , which is equivalent to $\frac{d}{dv}[\beta(v) F(v)^{n-1}] = (n-1) v F(v)^{n-2} f(v)$ . Integrate with boundary condition $\beta(0) = 0$ .

Why It Matters

This result makes the strategic tradeoff in first-price auctions explicit and quantitative. The bid-shading formula is used in practice for bidding in procurement auctions, ad auctions, and any competitive bidding environment.

Failure Mode

The formula assumes risk-neutral bidders. Risk-averse bidders shade less (they bid closer to $v$ to reduce the risk of losing). With asymmetric value distributions, the symmetric equilibrium does not exist and computing asymmetric equilibria is much harder. In practice, bidders also face budget constraints, which change the analysis.

Revenue Equivalence

Theorem

Revenue Equivalence Theorem

Statement

Any two auction mechanisms that (i) allocate the item to the bidder with the highest valuation in equilibrium and (ii) give zero expected surplus to the bidder with the lowest possible valuation yield the same expected revenue to the seller.

Formally, the expected payment by a bidder with valuation $v$ is:

$m(v) = v \cdot F(v)^{n-1} - \int_0^v F(t)^{n-1} \, dt$

This is the same in first-price, second-price, English, and Dutch auctions.

Intuition

The bidder's expected surplus is determined entirely by the allocation rule (who wins) and the boundary condition (lowest type pays zero). The payment is the residual: total value minus surplus. Since the allocation is the same (highest value wins) and the boundary condition is the same, the payments must be identical. The auction format changes how the payment is structured (pay your bid vs. pay second bid) but not the expected amount.

Proof Sketch

Let $U(v) = v \cdot Q(v) - m(v)$ be the expected surplus of a bidder with valuation $v$ , where $Q(v) = F(v)^{n-1}$ is the probability of winning. By the envelope theorem (or incentive compatibility), $U'(v) = Q(v)$ . Integrating from 0: $U(v) = U(0) + \int_0^v Q(t) \, dt$ . With $U(0) = 0$ (boundary condition) and $Q(v) = F(v)^{n-1}$ (efficient allocation), we get $m(v) = v Q(v) - U(v) = v F(v)^{n-1} - \int_0^v F(t)^{n-1} \, dt$ . This depends only on $F$ , $n$ , and $v$ , not on the auction format.

Why It Matters

Revenue equivalence tells the seller: do not waste time choosing between standard auction formats. They all yield the same revenue under the IPV assumptions. To increase revenue, you need to change the assumptions: add a reserve price, attract more bidders, exploit risk aversion, or use information asymmetries. This result focuses mechanism design effort on the right levers.

Failure Mode

Revenue equivalence fails when:

Bidders are risk-averse: First-price auctions yield higher revenue (bidders shade less to avoid losing).
Valuations are correlated: English auctions can yield more than sealed-bid formats because the dropout pattern reveals information.
Reserve prices differ: Adding a reserve price (minimum bid) breaks the boundary condition and can increase expected revenue.
Entry is endogenous: Different formats attract different numbers of bidders.
Bidders are asymmetric: Revenue equivalence requires symmetric distributions.

Myerson's Optimal Auction

Definition

Virtual Valuation

The virtual valuation of a bidder with valuation $v$ drawn from CDF $F$ is:

$\phi(v) = v - \frac{1 - F(v)}{f(v)}$

The virtual valuation adjusts the true valuation downward to account for the informational rent the seller must pay. It is the analog of marginal revenue in monopoly pricing. The distribution $F$ is regular if $\phi(v)$ is strictly increasing in $v$ .

Myerson (1981) showed that the revenue-maximizing auction allocates the item to the bidder with the highest virtual valuation, provided it is non-negative. This amounts to a second-price auction with a reserve price.

For the uniform distribution on $[0, 1]$ , $\phi(v) = 2v - 1$ . Setting $\phi(v) = 0$ gives $v = 1/2$ . The optimal reserve price is $1/2$ : reject all bids below $1/2$ . This sacrifices some probability of sale but extracts more surplus from high-value bidders.

The Winner's Curse

Definition

Common Value Auction

In a common-value auction, the item has a single true value $V$ unknown to all bidders. Each bidder $i$ observes a private signal $s_i$ correlated with $V$ (e.g., $s_i = V + \epsilon_i$ ). The winner is the bidder with the most optimistic signal, which means the winner's signal is biased upward on average.

Watch Out

Winning is bad news

In a common-value auction, the fact that you won means your signal was the most optimistic. Conditional on winning, your expected valuation is lower than your unconditional estimate. Naive bidders who ignore this selection effect will, on average, overpay. This is the winner's curse. Rational bidders must condition their bid on the event of winning: $E[V | s_i, \text{I win}] < E[V | s_i]$ . Oil lease auctions, corporate takeovers, and spectrum auctions all exhibit the winner's curse.

Applications

Online ad auctions. Google's ad system uses a variant of the Generalized Second-Price (GSP) auction, where advertisers bid for positions on a search results page. GSP is not truthful (unlike VCG), but it has a Nash equilibrium that approximates VCG outcomes. Revenue equivalence tells us the format matters less than the number of competing advertisers and the reserve price.

Spectrum auctions. Governments sell wireless spectrum licenses using simultaneous multiple-round auctions (a variant of English auctions for multiple items). The combinatorial complexity of bidding for packages of licenses is enormous, and the winner's curse is severe because spectrum valuations have a common component.

ML compute markets. Cloud providers increasingly use spot pricing (a form of auction) for GPU compute. Users bid for compute capacity, and the market-clearing price fluctuates. Understanding auction theory helps ML practitioners optimize their compute costs: bid your true valuation for interruptible workloads, as the spot market approximates a Vickrey mechanism.

Common Confusions

Watch Out

Second-price does not mean you always pay less

In a second-price auction, you pay the second-highest bid, which is lower than the highest bid. But in a first-price auction, the highest bidder shades their bid, so they also pay less than their true valuation. Revenue equivalence says the expected payments are identical. The realized payment differs across formats, but the expected payment does not (under IPV assumptions).

Watch Out

Revenue equivalence is about expectations, not realizations

For any specific realization of bidder valuations, different auction formats produce different revenues. Revenue equivalence holds in expectation over the distribution of valuations. The variance of revenue can differ across formats. First-price auctions typically have lower revenue variance than second-price auctions.

Watch Out

VCG is not always practical

The Vickrey-Clarke-Groves mechanism generalizes second-price auctions to multi-item settings and achieves truthfulness. But VCG has practical problems: revenue can be very low (or zero), it requires an accurate model of bidder valuations, it is computationally hard for combinatorial auctions (NP-hard winner determination), and it is susceptible to collusion. Real-world multi-item auctions rarely use VCG.

Exercises

ExerciseCore

Problem

In a second-price auction with 3 bidders whose valuations are $v_1 = 80$ , $v_2 = 50$ , $v_3 = 30$ , what does each bidder bid in the dominant strategy equilibrium? Who wins and what do they pay?

ExerciseCore

Problem

In a first-price auction with $n = 4$ bidders whose valuations are i.i.d. uniform on $[0, 100]$ , what is the equilibrium bid function? If a bidder's valuation is $v = 80$ , what do they bid?

ExerciseAdvanced

Problem

Verify revenue equivalence for $n = 2$ bidders with valuations i.i.d. uniform on $[0, 1]$ . Compute the expected revenue in (a) a second-price auction and (b) a first-price auction, and show they are equal.

ExerciseAdvanced

Problem

Compute the optimal reserve price in Myerson's framework for a single bidder with valuation $v \sim \text{Uniform}[0, 1]$ . What is the expected revenue with and without the reserve price?

ExerciseResearch

Problem

Google's ad auction uses a Generalized Second-Price (GSP) mechanism where $k$ ad slots have click-through rates $\alpha_1 > \alpha_2 > \cdots > \alpha_k$ and each advertiser $i$ has value-per-click $v_i$ . In GSP, the advertiser in slot $j$ pays the bid of the advertiser in slot $j+1$ per click. Show that truthful bidding ( $b_i = v_i$ ) is not a Nash equilibrium in GSP. Describe the "locally envy-free" equilibrium concept and explain why Google uses GSP instead of the truthful VCG mechanism.

References

Canonical:

Milgrom, Putting Auction Theory to Work (2004), Chapters 1-5
Krishna, Auction Theory (2nd ed., 2010), Chapters 2-5, 13

Foundational papers:

Vickrey, "Counterspeculation, Auctions, and Competitive Sealed Tenders," Journal of Finance 16(1), 1961
Myerson, "Optimal Auction Design," Mathematics of Operations Research 6(1), 1981

Applications:

Edelman, Ostrovsky, and Schwarz, "Internet Advertising and the Generalized Second-Price Auction," AER 97(1), 2007
Cramton, Shoham, and Steinberg (eds.), Combinatorial Auctions (2006), Chapters 1-3

Next Topics

Directions from auction theory:

Mechanism design: the general theory of designing games to achieve desired outcomes, of which auction design is the leading application

Last reviewed: April 2026

Prerequisites

Foundations this topic depends on.

Game Theory FoundationsLayer 2
Common Probability DistributionsLayer 0A
Sets, Functions, and RelationsLayer 0A
Basic Logic and Proof TechniquesLayer 0A
Convex Optimization BasicsLayer 1
Differentiation in RnLayer 0A
Matrix Operations and PropertiesLayer 0A
Nash EquilibriumLayer 2

Next Topics

Mechanism DesignContinue →