Game Theory
Auction Theory: Revenue Equivalence and Multi-Item Auctions
Why do eBay and a sealed-bid Christie's auction yield the seller the same average revenue? And how do you design an auction to extract the most - even by deliberately refusing to sell sometimes?
- **eBay vs Sotheby's:** first- and second-price auctions yield identical expected revenue under i.i.d. valuations - Vickrey's revenue equivalence theorem
- **FCC Spectrum Auction 2017:** a 84.7 billion dollar combinatorial auction - the largest in history, with bidders bidding on bundles of frequencies
- **Google AdWords:** the reserve price in the auction for ad slots implements Myerson's mechanism for revenue maximization
- **1990s privatizations:** poorly designed auctions without reserve prices led to assets being sold an order of magnitude below market value
Предварительные знания
- Bayes-Nash equilibrium: strategies under incomplete information
- Order statistics: E[theta_(n-1)] for revenue estimation
- Mechanism-design basics: IC and IR constraints
Revenue Equivalence Theorem
eBay and Sotheby's use fundamentally different auction formats, yet the 1961 revenue equivalence theorem (William Vickrey) proves: under symmetric valuations from a single distribution, first- and second-price auctions deliver the same expected revenue to the seller. eBay processed 1.7 billion transactions in 2023 leaning on exactly this result.
The revenue equivalence theorem applies under the condition that:
Key conditions: independent identically distributed valuations, the same winner, zero utility for the worst type.
Combinatorial Auctions
In 2017 the FCC (US Federal Communications Commission) ran a reverse-buyback radio-spectrum auction: 84.7 billion dollars in transactions, 70 MHz of spectrum redistributed. It was the largest combinatorial auction in history - bidders bid on combinations of lots rather than each lot individually.
Why is the winner determination problem in a combinatorial auction NP-hard?
The winner determination problem is the NP-hard generalization of the weighted set packing problem. In practice, ILP solvers (CPLEX, Gurobi) or heuristics are used.
Optimal Auction: Myerson's Theory
Myerson (1981, Nobel Prize 2007) solved the question: how do you design an auction that maximizes the seller's revenue? The answer: a reserve-price auction in which the seller sets a minimum sale price. The reserve price screens out low-valuation buyers, raising the average payment.
Optimal auction paradox: the seller deliberately refuses to sell sometimes (when all valuations fall below r*) to extract more revenue on average. This is inefficient from a social welfare standpoint but optimal for the seller.
Why does Myerson's theory introduce the virtual valuation psi(theta)?
The virtual valuation psi(theta) = theta - (1-F(theta))/f(theta) reflects that the seller must pay information rent (1-F)/f to high-valuation buyers so they do not mimic less valuable types.
Auctions in economics and computer science
Auction theory unites microeconomics, computational complexity, and algorithmic mechanism design.
- Algorithmic game theory — The winner determination problem in a combinatorial auction is an NP-hard optimization problem
- Mechanism design — Auctions are a special case of mechanisms: VCG generalizes Vickrey to multi-item settings
- Machine learning — Auto-bidding in advertising systems uses RL for strategic participation in Myerson auctions
Итоги
- Revenue equivalence theorem: all symmetric IC auctions with i.i.d. valuations yield the same E[R]
- First-price auction: strategy beta(theta) < theta; second-price (Vickrey) auction: dominant strategy beta(theta) = theta
- Combinatorial auctions: winner determination is NP-hard, solved by ILP solvers
- Myerson's optimal auction: sell to the buyer whose psi(theta) = theta - (1-F)/f is maximal and >= 0
- Reserve price r*: psi(r*) = 0; for U[0,1] this gives r* = 1/2