7 min read
On this page

Auction Theory

Single-Item Auctions

Auction Types Overview

Standard Auction Formats

English (ascending) auction: Price rises until one bidder remains. Dominant strategy: bid up to true value. Winner pays just above second-highest value. Equivalent to second-price sealed-bid under independent private values (IPV).

Dutch (descending) auction: Price drops until a bidder claims the item. Strategically equivalent to first-price sealed-bid: bidders must decide a price to claim without observing others' decisions.

First-price sealed-bid: Bidders submit sealed bids simultaneously. Highest bidder wins, pays their bid. Bidders shade below their true value; equilibrium bid function depends on the distribution of values and number of bidders.

Vickrey (second-price sealed-bid): Highest bidder wins, pays the second-highest bid. Truthful bidding is a weakly dominant strategy (Vickrey, 1961). Proof: if you win, your payment is independent of your bid; if truthful bidding would lose, any higher bid either still loses or wins at a price above your value.

Independent Private Values (IPV) Model

Each bidder i has a private value v_i drawn independently from distribution F_i. Bidder i knows v_i but not v_j for j != i.

Symmetric first-price equilibrium: With n symmetric bidders, values drawn from F on [0, v_bar]:

b(v) = v - integral_0^v F(z)^{n-1} dz / F(v)^{n-1}

This is the expected value of the highest of n-1 competing values, conditional on all being below v. Bidders shade their bids; shading decreases as competition increases.

Common Value and Affiliated Models

Common value: The item has an objective value unknown to all bidders; each observes a private signal. Classic example: oil rights auction.

Winner's curse: The winner tends to have the most optimistic signal, leading to overpayment relative to the true value. Rational bidders must shade bids to account for the information content of winning.

Affiliated values (Milgrom-Weber): General model where bidders' values and signals are affiliated (positively correlated). Revenue ranking under affiliation: English >= second-price >= first-price. The English auction reveals information during bidding, reducing the winner's curse and allowing more aggressive bidding.

Linkage principle: Any mechanism that links the payment to information affiliated with the winner's value increases revenue. Explains the revenue advantage of open auctions and the benefit of revealing the seller's information.

Revenue Equivalence

Theorem

Under IPV with symmetric risk-neutral bidders, any auction mechanism where (1) the bidder with the highest value wins and (2) a bidder with value zero pays zero yields the same expected revenue.

Proof: By the payment identity (Myerson), expected payment is pinned down by the allocation rule and the boundary condition. Since the allocation rule is identical (highest value wins), expected payments are identical.

When Revenue Equivalence Fails

| Condition | Effect | |---|---| | Risk-averse bidders | First-price > second-price (less shading due to risk aversion) | | Asymmetric bidders | Different formats have different revenue | | Correlated/affiliated values | English > second-price > first-price (linkage principle) | | Budget constraints | Revenue equivalence breaks down | | Interdependent values | Auction format matters |

Optimal Auctions (Myerson)

Myerson's Characterization

For revenue maximization with a single item, n independent bidders, regular distributions:

  1. Define virtual valuation: phi_i(v_i) = v_i - (1 - F_i(v_i)) / f_i(v_i)
  2. Allocate to argmax_i phi_i(v_i) if max_i phi_i(v_i) >= 0; otherwise no sale
  3. Charge each bidder their critical value

Ironing: If virtual valuations are not monotone (irregular distributions), iron by pooling intervals to restore monotonicity. The ironed virtual valuation is constant on pooled intervals.

Symmetric case: Optimal auction is second-price with reserve r* where phi(r*) = 0, i.e., r* = v - (1 - F(r*))/f(r*) = 0. For uniform [0,1]: r* = 1/2.

Bulow-Klemperer Theorem

An optimal auction with n bidders generates less revenue than a standard (no-reserve) Vickrey auction with n+1 bidders (assuming regular distributions). Implication: attracting one more bidder is worth more than optimizing the auction format. Competition matters more than mechanism sophistication.

Combinatorial Auctions

Setting

Multiple heterogeneous items; bidders have values over bundles (subsets). Bidder i has valuation v_i: 2^M -> R over subsets of items M.

Complementarities: v({A,B}) > v({A}) + v({B}) (e.g., spectrum licenses in adjacent frequencies) Substitutes: v({A,B}) < v({A}) + v({B}) (e.g., two paintings for the same wall)

Computational Challenges

  • Winner determination: Finding the welfare-maximizing allocation is NP-hard (weighted set packing). ILP formulations solvable by CPLEX/Gurobi for practical instances with branch-and-cut.
  • Bidding language: Exponentially many bundles (2^m). Languages: OR bids (additive), XOR bids (exclusive), OR-of-XOR, bidding languages based on dummy items. Compact representation is essential.
  • Communication complexity: Exponential communication required in worst case to determine the efficient allocation (Nisan-Segal).

VCG in Combinatorial Auctions

VCG is DSIC and efficient but has severe practical issues:

  • Winner determination is NP-hard; VCG with approximate welfare maximization is not truthful
  • Low revenue: can yield zero revenue even with high competition
  • Non-monotonicity: adding a bidder can decrease revenue
  • Vulnerability to shill bidding

Practical Combinatorial Auction Mechanisms

Combinatorial Clock Auction (CCA): Used for spectrum auctions worldwide.

  1. Clock phase: Ascending clock prices for categories; bidders express demand at current prices
  2. Supplementary phase: Sealed bids on specific packages
  3. Winner determination: Optimize over all bids
  4. Core-selecting payment rule: VCG-nearest core payments (bidders pay at least enough that no coalition can block the outcome)

Ascending proxy auction (Ausubel-Milgrom): Proxy agents bid on behalf of bidders up to reported values. Converges to VCG outcome under substitutes valuations.

Setting

k ad positions with click-through rates alpha_1 > alpha_2 > ... > alpha_k. Advertiser i has value v_i per click. Revenue model: pay-per-click.

Generalized Second Price (GSP)

Used by Google, Bing:

  • Rank advertisers by bid (possibly adjusted by quality score)
  • Position j is charged the bid of position j+1
  • GSP is NOT truthful (unlike Vickrey); the equilibrium bids differ from true values

Symmetric Nash equilibrium of GSP: The "locally envy-free" equilibrium produces the same allocation and payments as VCG (Edelman-Ostrovsky-Schwarz, Varian). But multiple equilibria exist.

Truthful mechanism: each advertiser in position j pays the minimum bid to maintain their position, computed from lower-ranked advertisers' bids weighted by CTR differences.

VCG payment for position j: t_j = sum_{l=j+1}^{k} (alpha_{l-1} - alpha_l) * b_{l+1} + ... (telescoping sum involving bids below position j weighted by CTR differences).

GSP revenue >= VCG revenue in the worst locally envy-free equilibrium (Varian, 2007). This partly explains why search engines preferred GSP over VCG.

Modern Ad Auctions

  • Quality score: Google's ad rank = bid * quality score (relevance, CTR prediction, landing page quality). Changes the effective competition.
  • Auto-bidding: Advertisers specify target CPA/ROAS; the platform bids on their behalf. Changes the strategic landscape; value maximization replaces utility maximization.
  • Reserve prices: Machine-learned optimal reserves per query.
  • First-price auctions: Display ad exchanges have shifted from GSP/second-price to first-price auctions; bidders must use bid shading algorithms.

Spectrum Auctions

Simultaneous Multiple Round Auction (SMRA)

FCC design (Milgrom-Wilson): Multiple licenses auctioned simultaneously with ascending bids over multiple rounds. Activity rules require bidders to maintain bidding activity. Exposure problem: bidders seeking complementary licenses risk winning a subset at high prices.

Incentive Auction (FCC 2016-2017)

Two-sided: reverse auction repurchases broadcast TV licenses, forward auction sells cleared spectrum to mobile carriers. Computationally complex feasibility checking (interference constraints). Raised $19.8 billion.

Challenges in Auction Design

  • Budget constraints: Optimal mechanisms under budgets differ substantially from Myerson; requires careful mechanism design (Che-Gale)
  • Collusion: Bidder agreements to suppress prices; mechanism design can mitigate through information revelation policies
  • Entry: Auction design affects participation incentives; too-aggressive revenue extraction deters entry

Multi-Dimensional Mechanism Design

When agents have multi-dimensional types (values for multiple goods), optimal mechanism design becomes dramatically harder. Even for a single buyer with two-dimensional type, the optimal mechanism may be non-trivial (randomized, region-based pricing). Manelli-Vincent and Daskalakis-Deckelbaum-Tzamos show that optimal multi-item auctions can involve randomization and bundling, unlike the clean characterization in single-item settings.