Game Theory
Auction Theory
In 1994, the FCC used an auction to sell radio spectrum for the first time. Result: $617 million instead of the expected $100 million. In 2020, Paul Milgrom and Robert Wilson received the Nobel Prize for designing these auctions. Every time an ad appears on Google or Instagram, a second-price auction is running. Auction theory grew from academic mathematics into an engineering discipline moving trillions of dollars.
- **Google Ads (GSP):** every ad click is the result of a lightning-fast Vickrey auction across multiple positions. $237B in annual Google revenue rests on a game-theoretic mechanism
- **FCC Spectrum Auctions:** selling 4G/5G spectrum for $100B+. The first package was auctioned in 1994 using Milgrom's design-part of what earned him the 2020 Nobel
- **NFT and crypto auctions:** Ethereum uses EIP-1559-a fee auction mechanism designed with IC, Revenue Equivalence, and dynamic base fee considerations
Предварительные знания
First-Price Auctions
In a first-price sealed-bid auction, all participants submit sealed bids. The highest bidder wins and pays their bid. It seems simple: bid the item's true private value. But that's wrong. If a bidder bids the true value v, the surplus is zero (paying exactly what was received). The rational move is to shade the bid: bid below v and capture a profit on winning.
With n symmetric bidders and values v ~ U[0,1] independently: Optimal strategy: b*(v) = v · (n-1)/n Each bidder shades by 1/n. More competitors means less shading. As n → ∞: b* → v (truthful bidding becomes nearly optimal).
Why is shading optimal? It's a trade-off: a lower bid reduces the probability of winning but increases the surplus on winning. In equilibrium, both effects balance out. Intuitively: if everyone bid truthfully, I could bid v - ε and still win whenever I'm the highest-value bidder.
Auctions in practice: from fish markets to spectrum
The earliest documented auctions date to ancient Rome-selling war trophies. First-price sealed-bid auctions are used in government procurement (who offers the contract at the lowest price), bankruptcy real estate sales, and oil concessions. The theoretical foundations were laid by William Vickrey (Nobel 1996) and Paul Milgrom.
Truthful bidding (bid = true value) is the safest strategy in any auction
Truthful bidding is optimal only in SECOND-price auctions (Vickrey). In first-price auctions, it is strictly suboptimal-shading is required.
The auction format fundamentally changes the optimal strategy. That's why auction theory matters-the wrong strategy literally costs money.
Why does a rational bidder shade below their true value in a first-price auction?
Second-Price Auction (Vickrey)
In 1961, William Vickrey proposed a counterintuitive variant: the winner pays not their own bid but the second-highest. Seems strange-why would a seller accept less? The payoff: truthful bidding (bid = true value) is now a dominant strategy. No strategic calculation needed-just bid the item's true private value.
Let p = second bid (not under the agent's control). Consider an agent with value v: • If b > p: win, surplus = v - p → Shade to b' ∈ (p, b]: same win, same surplus → Shade to b' < p: lose, surplus = 0 < v-p (worse if v > p) • If b < p: lose → Inflate to b' > p: win, surplus = v - p < 0 (worse if v < p) Result: b = v weakly dominates any other strategy.
The Vickrey auction is the direct embodiment of VCG for a single item. Each agent's transfer equals the second bid-the Clarke tax: how much 'harm' the winner inflicted on the other participant by taking the item. The dominant strategy makes the auction simple for participants to understand and robust to complex strategic calculations.
The Vickrey auction always gives the seller less revenue than the first-price auction
By the Revenue Equivalence Theorem, both formats give the same expected revenue under standard conditions.
While bidders pay less in Vickrey (second price < their bid), they bid truthfully-without shading. In first-price they shade but pay their bid. Mathematically the revenue is equal.
Why is truthful bidding a dominant strategy in a Vickrey (second-price) auction?
The Revenue Equivalence Theorem
Here's the paradox: first-price bidders shade; second-price bidders don't. It seems the seller does better with first-price. But that's wrong. The Vickrey-Myerson Revenue Equivalence Theorem states: with symmetric, independent, private values, all 'standard' auctions give the same expected revenue.
Under conditions: n symmetric bidders, independent private values v ~ F(v), any two auction mechanisms satisfying: 1. Same winner (highest value) 2. Same expected payoff for the lowest type ...yield the same expected revenue to the seller. Corollary: first-price, second-price, English, and Dutch auctions are all equivalent!
| Condition | Revenue Equivalence | Example |
|---|---|---|
| Symmetric independent types | Holds | 4 companies bidding on spectrum |
| Asymmetric types | Fails | Strong vs. weak bidder |
| Affiliated values | Fails | Oil rights (common value) |
| Risk-averse bidders | Fails | First-price > second-price in revenue |
Revenue Equivalence is a powerful theoretical result, but it breaks down in real conditions: affiliated values (one player winning reveals information about others' values), asymmetric bidders, risk aversion. That's why real auction design is more than just choosing 'first vs. second price'-it's a complex engineering problem.
The second-price auction always brings less revenue to the seller than the first-price
Under Revenue Equivalence conditions, both formats give the same expected revenue. Bidders compensate through their strategies.
In first-price, bidders shade exactly enough for revenue to match second-price. Strategic behavior equalizes the difference in formats.
The Revenue Equivalence Theorem states that different auction formats yield the same expected revenue when:
Optimal Auctions and Real Applications
Revenue Equivalence says standard auctions are equal in revenue. But none of them maximizes the seller's revenue! Myerson showed: the optimal auction uses a reserve price r* and 'virtual values'-and generates strictly more revenue than the Vickrey auction without a reserve. The seller deliberately creates inefficiency to extract more rent.
Algorithm: 1. Compute virtual values ψᵢ(vᵢ) = vᵢ - (1-Fᵢ(vᵢ))/fᵢ(vᵢ) 2. Allocate to the bidder with max ψᵢ > 0 (if such a bidder exists) 3. Set payment = minimum bid at which the agent still wins For U[0,1], n=1: r* = 0.5, expected revenue = 0.25 (vs. 0 without reserve).
| Auction format | Used in | Key property |
|---|---|---|
| English (ascending) | Sotheby's, eBay | Efficient, lots of information revealed |
| Dutch (descending) | Flowers, fish | Fast, aggressive |
| First-price (sealed-bid) | Government procurement, oil | Strategic shading |
| Second-price (Vickrey) | Google Ads (basis of GSP) | IC, simple strategy |
| Myerson with reserve | Spectrum auctions | Maximum revenue |
Google uses GSP (Generalized Second Price) for advertising. This extends the second-price idea to multiple positions (top of page, bottom, etc.). It's not strictly IC, but in equilibrium produces similar payoffs to VCG. Key: each advertiser pays the minimum bid needed to maintain their position-the analog of a second price.
The optimal auction always sells to whoever values the item most
The optimal auction can deliberately NOT sell, or sell to someone who is not the highest-value bidder-when the highest bidder's virtual value is negative.
Maximum revenue and maximum efficiency are different goals. The optimal auction sacrifices efficiency for more revenue through informational rent.
Why does Myerson's optimal auction set a reserve price?
Key ideas
- **First-price auction:** strategic bid shading b* = v·(n-1)/n in Bayes-Nash equilibrium
- **Vickrey auction (second-price):** truthful bidding is dominant; VCG for a single item
- **Revenue Equivalence:** under standard conditions, all auction formats give the same expected revenue
- **Myerson's optimal auction:** reserve price r* and virtual values-maximum seller revenue
Related topics
Auction theory is the applied peak of mechanism design:
- Mechanism Design — Auctions are a special case of mechanisms; IC and Revelation Principle apply directly
- Extensive Form Games — The English auction is a sequential game; analyzed via backward induction
- Game Theory in Tech: pricing, markets — GSP, surge pricing, marketplace auctions-auction theory in products
Вопросы для размышления
- eBay uses an ascending auction with a proxy bidding feature. How does this interact with the Vickrey auction? Is 'enter the maximum' a dominant strategy on eBay?
- In Google's ad auctions, Quality Score affects both position and price. How does this change the theoretical properties of the auction-IC, Revenue Equivalence?
- NFT auctions often use a 'highest price wins' format. What sniping problems (last-second bidding) does this create? How could the design be improved?