ECON5001 · Microeconomic Theory
Matching Markets & Auctions
This is ECON5001's market-design finale, taught in Kesten's half: how to allocate when a price cannot, or should not, clear the market. The matching block studies two-sided markets with no money — its single test is stability (no blocking pair), and the Gale-Shapley deferred-acceptance algorithm always finds a stable matching, proposer-optimal and strategy-proof for the proposing side only. The auction block covers the four standard formats and their equivalences (English = second-price, Dutch = first-price), the second-price dominant strategy of bidding your true value, first-price bid shading, and the Revenue Equivalence Theorem. It is examined as algorithmic worked problems, so the marks are in running the rule and verifying the property — not reciting definitions.
What this chapter covers
- 011. Two-sided matching — the marriage model; both sides have preferences and money cannot clear the market; a partner is 'acceptable' if preferred to being single
- 022. Stability — a matching survives only if it is individually rational and has no blocking pair (a man and woman who both prefer each other to their assigned partners)
- 033. Gale-Shapley deferred acceptance — proposers propose, receivers tentatively hold the best offer and reject the rest; always terminates in a stable matching
- 044. Proposer-optimality — man-proposing DA is man-optimal and simultaneously woman-pessimal; who proposes decides who wins
- 055. Strategy-proofness & the roommate problem — DA is strategy-proof for proposers only (receivers can truncate); one-sided markets may have no stable matching
- 066. Four auction formats — first-price, second-price (Vickrey), English ascending, Dutch descending; equivalences English=2nd-price and Dutch=1st-price
- 077. Optimal bidding — bid your true value in second-price (dominant); shade to b = (n−1)/n · v in first-price (no dominant strategy)
- 088. Revenue Equivalence, design criteria & traps — equal expected revenue across formats; efficiency/fairness/incentives; winner's curse; third-price counterexample
Deferred acceptance and verifying stability
- +2Round 1: m1→w2, m2→w2, m3→w1. w2 has offers from m1 and m2 and ranks m2 above m1, so she holds m2 and rejects m1. w1 holds m3.
- +2Round 2: rejected m1 proposes to his next choice w1. w1 now compares m3 (held) with m1, ranks m1 first, so holds m1 and rejects m3.
- +2Round 3: rejected m3 proposes to w2. w2 compares m2 (held) with m3, ranks m3 first, so holds m3 and rejects m2. Round 4: rejected m2 proposes to w3, who is free and accepts. No further rejections, so the algorithm stops. Matching: (m1,w1), (m3,w2), (m2,w3).
- +2Stability check — look only at partners each man prefers to what he got. m1 (got w1) prefers w2, but w2 holds m3 whom she ranks above m1 — no block. m2 (got w3) prefers w2, but w2 prefers m3 — no block. m3 (got w2) prefers w1, but w1 prefers m1 — no block. No blocking pair exists ⇒ the matching is stable.
Key terms
- Two-sided matching
- A market with two disjoint sets of agents (men/women, students/schools, workers/firms) where both sides have preferences over the other side and money cannot be used to clear the market. The goal is to pair agents rather than to find a market-clearing price.
- Acceptable partner
- In the marriage model, a partner an agent prefers to remaining unmatched (single). A matching must be individually rational — nobody is paired with an unacceptable partner.
- Stable matching
- A matching that is individually rational and has no blocking pair. Because no agent can find a partner who would also abandon their own match, a stable matching is self-enforcing and does not unravel.
- Blocking pair
- A man and a woman, not matched to each other, who would BOTH strictly prefer being matched together to their current partners. A single blocking pair makes a matching unstable; verifying stability means showing none exists.
- Gale-Shapley deferred acceptance
- An algorithm in which one side proposes to its top remaining choice while the other side tentatively holds the best offer received so far and rejects the rest, repeating until no one is rejected. It always terminates in a stable matching, proving one exists in any two-sided market.
- Proposer-optimality / receiver-pessimality
- Man-proposing deferred acceptance gives every man his best partner among all stable matchings (man-optimal) and simultaneously gives every woman her worst stable partner (woman-pessimal). Switching who proposes reverses the advantage.
- Strategy-proofness
- A mechanism is strategy-proof if truthful reporting is a dominant strategy. Deferred acceptance is strategy-proof for the proposing side only; the receiving side can sometimes gain by truncating its list. Stability and full two-sided strategy-proofness cannot generally coexist.
- Second-price (Vickrey) auction
- A sealed-bid auction where the highest bidder wins but pays the second-highest bid. Bidding your true value is a dominant strategy, so the auction is efficient and strategy-proof; it is strategically equivalent to the English ascending auction.
- Revenue Equivalence Theorem
- With risk-neutral bidders, independent private values, symmetry and Nash play, all four standard auctions yield the same EXPECTED revenue (the expected second-highest value) and the highest-value bidder always wins. It equates averages across many draws, not revenue on any single realisation.
- Winner's curse
- In a common-value auction where bidders only estimate the object's value, the winner tends to be whoever most over-estimated it, so winning is bad news about your estimate. Rational bidders pre-empt it by shading bids further below their estimates.
Matching Markets & Auctions FAQ
What exactly makes a matching stable?
Two conditions. It must be individually rational — nobody is paired with a partner they would rather be single than have — and it must have no blocking pair, meaning there is no man and woman who would both prefer to abandon their assigned partners for each other. The blocking-pair test is the operative one in almost every exam question: 'everyone is matched' is NOT the same as stable, so you earn the verification mark by hunting for a blocking pair and showing none exists.
What does the Gale-Shapley algorithm guarantee?
That a stable matching always exists in a two-sided market, because the deferred-acceptance algorithm always terminates in one — the algorithm is itself the constructive proof. It also delivers the proposer-optimal stable matching: man-proposing deferred acceptance gives every man his best stable partner and, at the same time, every woman her worst. Note the one-sided roommate problem has no such guarantee — a stable matching may not exist.
Is it always best to report preferences truthfully?
Only for the proposing side. Deferred acceptance is strategy-proof for proposers — they can never do better than reporting their true ranking. The receiving side is not protected and can sometimes gain by truncating its list (declaring a genuine partner unacceptable to force a better outcome). Stability and full strategy-proofness for both sides cannot generally be achieved together, which is a favourite conceptual exam point.
How do I bid in each auction format?
In a second-price or English auction, bid your true value — it is a dominant strategy, so you never need to guess what rivals do. In a first-price or Dutch auction there is no dominant strategy: you shade below your value, and with n symmetric bidders and uniform values the equilibrium bid is (n−1)/n of your value. Lock in the equivalences: English = second-price and Dutch = first-price; swapping them is the classic mistake.
What does the Revenue Equivalence Theorem actually say?
Under risk-neutral bidders with independent private values, symmetry and Nash play, all four standard auctions raise the same EXPECTED revenue — equal to the expected second-highest value — and always award the object to the highest-value bidder. It is a statement about averages across many draws, not a promise that two formats raise identical revenue on any single auction. On one realisation a first-price auction can collect more or less than a second-price one, as worked examples show.
Does truthful bidding work in a third-price auction?
No — and this is a classic counterexample question. In a third-price auction the winner pays the third-highest bid, and bidding your true value is not a dominant strategy: bidders can do strictly better by over-bidding. The truth-telling result is special to the second-price (Vickrey) rule, so never assume Vickrey logic generalises to other pay-the-k-th-price formats.
Exam move
Treat this chapter as two algorithms plus the criteria you judge them by. For matching, drill deferred acceptance until the bookkeeping is automatic: write each round as propose → hold → reject, always comparing a new offer against whoever a receiver is already holding, and finish by verifying stability — scan only the partners each agent prefers to their match and confirm at least one side of every such pair is unwilling. Memorise that man-proposing is man-optimal and woman-pessimal, that strategy-proofness holds for proposers only, and that the one-sided roommate problem may have no stable matching. For auctions, lock in the two equivalences (English = second-price, Dutch = first-price) and the two reflexes (bid your value in second-price; shade to (n−1)/n·v in first-price), then practise computing the winner and the seller's revenue in each format. State the Revenue Equivalence Theorem precisely as an expected-revenue result, and keep three counterexamples ready: stability is about blocking pairs not full matching, the third-price auction breaks truthful bidding, and the winner's curse arises only with common values. The exam rewards running the rule cleanly under time pressure, so rehearse full worked problems rather than memorising prose.
