Auctions and Mechanism Design

Mechanism design is the art of creating rules for games so that players acting selfishly produce outcomes that are good for everyone. Auctions are the canonical example: you want to allocate an item to whoever values it most, and you want bidders to reveal their true valuations. Different auction formats achieve different properties.

The idea

An auction is a mechanism: you set the rules (how to bid, who wins, what they pay) and players respond strategically. A well-designed mechanism makes truth-telling a dominant strategy, meaning bidders have no incentive to lie about their valuations regardless of what others do. This is called incentive compatibility.

In a first-price sealed-bid auction, everyone submits a bid in an envelope. The highest bid wins and pays what they bid. But bidders shade their bids below their true value, because paying less is always better if you win. This makes the outcome depend on how well bidders guess what others will do, not just their own values.

In a second-price sealed-bid auction (Vickrey auction), the highest bid wins but pays the second-highest bid. This makes bidding your true value a dominant strategy: if you bid higher, you might win when you should not have (paying more than your value). If you bid lower, you might lose when you should have won. Bidding truthfully always maximizes your expected utility.

Mechanism design extends beyond auctions to voting systems, matching markets (kidney exchange, school assignment), and protocol design in distributed systems. The goal is always the same: align individual incentives with collective welfare.

The maths

Let v₁, v₂, ..., vₙ be the private valuations of n bidders. In a second-price auction, bidder i bids bᵢ. The winner is w = argmax(bᵢ) and they pay p = max(bⱼ : j ≠ w). Bidder i's utility is uᵢ = (vᵢ - p) if i wins, else 0.

Consider bidder i with value vᵢ. Suppose all others bid truthfully (bⱼ = vⱼ for j ≠ i). Let m = max(vⱼ : j ≠ i) be the highest competing valuation. If vᵢ > m, bidder i wins by bidding anything above m and pays m, giving utility vᵢ - m. Bidding vᵢ achieves this. Bidding below m risks losing. Bidding above vᵢ does not help: you still pay m if you win, and if m > vᵢ you get negative utility.

If vᵢ < m, bidder i cannot win profitably. Bidding vᵢ loses, giving utility 0. Bidding above vᵢ might win, but you pay m > vᵢ, giving negative utility. So bidding truthfully is optimal regardless of what others do.

A mechanism is individually rational if participation is always weakly better than not participating. The Vickrey auction is individually rational: winners pay at most their value (non-negative utility), and losers get zero. It is also strategy-proof (truth-telling is dominant) and efficient (the item goes to whoever values it most).

The revenue equivalence theorem states that any auction format where the item always goes to the highest bidder and losers pay zero generates the same expected revenue in equilibrium, assuming bidders are risk-neutral and have independent private values. First-price and second-price auctions are revenue-equivalent, even though they seem different.

Try it

Your value: 50

Auction type:

Your rank

Your payoff

0.00

Vickrey auction: you bid 50, payoff 0.00

Simulate first-price and second-price auctions

The widget runs both auction formats side by side with the same set of bidders. In the first-price auction, bidders shade their bids strategically. In the second-price auction, bidders bid their true values. Notice that the winner is the same in both, but the payment differs. The second-price auction is simpler to reason about because truth-telling is always optimal.

Where I used it

Easy to get wrong

Pitfalls

Assuming truth-telling is always optimal. It is only optimal in incentive-compatible mechanisms like the Vickrey auction. In first-price auctions, bidders shade their bids, and the optimal bid depends on beliefs about others.
Forgetting individual rationality. A mechanism can be incentive-compatible but still fail if participants lose utility by participating. Vickrey satisfies both, but some mechanisms require subsidies to ensure participation.
Ignoring collusion. Vickrey is strategy-proof for individual bidders, but if two bidders collude, they can manipulate the outcome. Mechanism design often assumes no collusion, which is not always realistic.
Confusing dominant strategy with Nash equilibrium. A dominant strategy is optimal no matter what others do. A Nash equilibrium is a profile of strategies where no one wants to deviate given others' strategies. Dominant strategies are stronger and easier to achieve.

Sources

COMP30024 (2022). Auction theory and incentive design for multi-agent systems. Textbook sources: Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory (2007); Shoham & Leyton-Brown, Multiagent Systems (2009).