%%{init: {"theme": "base", "themeVariables": {"primaryColor": "#E8ECFF", "primaryBorderColor": "#4054B2", "primaryTextColor": "#16171B", "lineColor": "#3B4351", "edgeLabelBackground": "#FAF7F0", "clusterBkg": "#EFE9DC", "clusterBorder": "#766F65"}}}%%
flowchart TB
D["Dutch<br/>descending clock"]
F["First-price<br/>sealed-bid"]
E["English<br/>ascending outcry"]
V["Second-price<br/>sealed-bid (Vickrey)"]
FP["First-price family:<br/>bid below value,<br/>shade against the field"]
SP["Second-price family:<br/>honesty is the right bid"]
DOM["Truthful bidding dominant:<br/>no model of rivals needed"]
D --> FP
F --> FP
FP ~~~ E
FP ~~~ V
E -->|"stay in to<br/>your value"| SP
V -->|"bid your<br/>value"| SP
V -->|"sealed form only"| DOM
classDef good fill:#DCEFE2,stroke:#1B6B5A,color:#16171B
class V good
12 Markets, Auctions, and Mechanism Design
Chapter 9 made a promise it is now time to keep. Its games arrived with their rules fixed, and the job was to predict play inside them. But an engineer building a multi-agent system writes the rules — who may bid, what counts as a message, when the exchange closes, who pays what. Mechanism design is game theory run backwards: fix the outcome you want — the task to the ablest agent, the budget to its highest-valued use, the truth told — and derive the game whose equilibrium, played by self-interested agents, delivers it. Chapter 10 closed by asking how to choose how to choose; Chapter 11 found that whether agents lie is a property of the rules of encounter; this chapter is where the discipline begins.
Its central instrument is the one the last chapter reached for at its wall: the price — the most heavily compressed message in this book, carrying everything a market’s participants privately know about scarcity, value, and alternative uses, none of which a planner could gather by asking, since asking, as Chapter 11 established, mostly gathers posturing. And beside the price stands the result that ought to sound too good to be true: there exist rules of exchange under which the best move — dominant, not merely hopeful — is to reveal what one actually values. Honesty not preached but priced in. Nor is any of it exotic: the team’s token budget is already an economy, run so far by fiat, and the largest multi-agent system in production on Earth is an auction house — the advertising exchanges clearing billions of times a day. The theory is older than the agents and unusually decorated — a shelf of Nobel prizes deep. When today’s frameworks allocate compute among competing agents by intuition and a queue, the preface’s warning falls due: they are re-deriving auction theory by folklore, at folklore prices.
Two boundary stones. First, this chapter concerns exchange among parties who remain strangers; those who discover they would rather be colleagues — coalitions, organisations, institutions — are the next chapter’s subject. Second, one assumption does quiet work throughout: the designer can enforce the rules. An orchestrator can write the rules as code and deduct payments at source — unusually fertile ground for mechanism design, and unusually pressing ground for its failure modes, above all collusion among bidders who may be copies of the same model.
12.1 What a Price Knows: Markets as Computation
Somewhere in the world, something has happened to tin. A mine has flooded, or a new use has been found — Hayek, who chose the example, says it does not matter which (1945). The price rises and thousands of decisions adjust in the right direction, rippling outward through people who never hear of the original event, “without an order being issued, without more than perhaps a handful of people knowing the cause”. The interesting thing about a market, Hayek argued, is not who owns what but what it does with knowledge: the information a rational allocation would need “never exists in concentrated or integrated form”, only as dispersed bits of knowledge of “the particular circumstances of time and place” — local, perishable, often tacit — so the planner’s failure is one of bandwidth and staleness, not intellect. This is the knowledge problem: a distributed-systems argument, made in 1945, about why the global state table cannot be maintained.
The price system is Hayek’s answer — “a system of telecommunications”, he wrote, whose users watch a few pointers “as an engineer might watch the hands of a few dials”: one number per good, readable by anyone. Read as computation, the mechanism is disarmingly simple: each participant solves a small local optimisation at the posted prices, and the market runs an adjustment loop — demand outruns supply, the price rises; goods go begging, it falls — Walras’s tâtonnement, French for “groping about”. The fixpoint is competitive equilibrium — a gentler rest state than Section 9.2’s, since price-takers respond to the dials rather than to each other — and the textbook theorems certify the allocation efficient. Convergence is not guaranteed and real markets are ill-behaved approximations, but the reading is no metaphor: the planning debate was about whether this very computation could be centralised, and Hayek’s answer was that the algorithm was never the hard part. The inputs were. And the machinery was not designed at all, a lesson Part V will pick up.
The multi-agent community, characteristically, took the algorithm literally. Wellman’s market-oriented programming casts a distributed allocation problem as an artificial economy, the answer read off the computed equilibrium — Walras’s fictional auctioneer implemented at last as a protocol named, with due piety, WALRAS (1993); no agent states its plans, and no coordinator holds the global problem. The applied cousin, market-based control, produced quotable demonstrations (Clearwater, 1996) — most memorably a Xerox building whose air-conditioning ran as a double auction, offices bidding for cold air, comfort improving without any central model of the building’s thermodynamics ever being written. The recurring result is less efficiency than modularity: components need only their own valuations and the prices, and devices join or leave without anyone updating a master plan. The price is doing the systems integration.
When does this beat the orchestrator’s fiat? The conditions fall straight out of Hayek’s argument, and they make a serviceable checklist. Dispersal: the state that matters — capability, load, local difficulty — is private and expensive to centralise. Drift: conditions change faster than reporting cycles, so any collected picture is stale. Heterogeneity: the participants genuinely value the contested resource differently. Where all three hold, prices coordinate what reports cannot; where none holds — a four-agent team, observable state, a stable task — the orchestrator can simply look, and fiat is cheaper. The team’s token budget sits, instructively, in between: central planning works while the planner can still read every status message, and the Hayekian conditions arrive as the team scales. An orchestrator polling agents for state it cannot verify has met the knowledge problem in miniature; the remedy has been on the shelf since 1945.
One caveat separates every engineered economy from Hayek’s. Human markets rest on wants from outside the system; an agent economy rests on valuations somebody assigned — a utility function written by a designer, a budget granted by a policy, a bid induced by a prompt. The market computes faithfully whatever it is fed — garbage valuations in, confident allocation out — and deciding what things shall be worth is design work, not market work. Everything here also assumed price-takers: what happens when a stated valuation is not a reading but a move (Section 9.5)? That is where the market stops being a passive computation and needs rules; and the simplest complete set of rules for putting one scarce good into the hands that value it most is an auction.
12.2 Going, Going, Gone: The Classic Auctions
An auction is a mechanism with one job: put a single scarce thing into the hands that value it most, at a price discovered rather than guessed, when every valuation is private and every stated one is a move. It is among the oldest formal institutions humanity runs — Herodotus describes one — and small enough to analyse completely. Four classic designs dominate the theory and, between them, most of practice (Table 12.1).
| Format | How it runs | Winner pays | Strategic family | Honesty dominant? |
|---|---|---|---|---|
| English | Open outcry; the price ascends; the last bidder standing wins | The final bid — the runner-up’s value, where it dropped out | Second-price (close cousin, private values) | Yes, weakly |
| Dutch | Descending clock; the first to claim wins | Its claim price | First-price (the same game) | No |
| First-price sealed-bid | One sealed bid each; the highest wins | Its own bid | First-price | No |
| Second-price sealed-bid (Vickrey) | One sealed bid each; the highest wins | The runner-up’s bid | Second-price | Yes |
The ascending English auction and the descending-clock Dutch auction are open-outcry theatre; the first-price and second-price sealed-bid auctions are envelopes, the latter charging the winner the runner-up’s bid — a rule that looks like a bookkeeping error in the seller’s disfavour. The four collapse, strategically, into two families (Figure 12.1): Dutch and first-price are the same game — one claim price, chosen blind — and the English auction is, with private values, the second-price auction’s close cousin: stay in until the price touches your value, and the winner pays where the runner-up dropped out. The first family makes bidding genuinely hard: bid your value and winning profits you nothing, so you must shade below, and how far is a Bayesian exercise in exactly Section 9.5’s sense — beliefs about beliefs, all the way down. The bidder must model the field.
The second family contains the promised result. In a second-price auction, truthful bidding — write down exactly what the good is worth to you — is a dominant strategy: best against every field of rivals, sophisticated or mad (Vickrey, 1961). The reason is a decoupling so clean it fits in a sentence: your bid determines only whether you win, never what you pay — the price is set by someone else’s envelope, so overbidding buys only wins you did not want and underbidding only losses you wanted to win. The strategic problem the last page called genuinely hard has been designed away by moving one rule. That is the Vickrey auction, and the sentence “change the pricing rule and honesty becomes dominant” is the seed from which the next section grows.
Practice has treated the miracle with suspicion: truthful bidding feels naked, and the seller who learns the winner’s sealed maximum is tempted to invent a slightly higher runner-up — the format demands a trustworthy auctioneer, and trust is expensive. Where infrastructure supplies the trust it quietly thrives — eBay’s proxy bidding is a Vickrey auction run slowly. Both caveats return in the harness, where the auctioneer is auditable code — which solves the trust problem — and the bidders are prompts that can be read, which raises new ones.
12.2.1 The Miracle, Formally*
The rule and its proof fit comfortably on one page, and the proof rewards watching because it never once needs a guess about what any rival will do. Each of n bidders privately values the good at v_i \ge 0 and seals a bid b_i; the second-price rule gives the good to the highest bidder, \operatorname*{arg\,max}_i b_i, at the highest price among the others’ envelopes. To see why truth dominates, fix a bidder i and compress everything its rivals do into the one number that matters,
m \;=\; \max_{j \ne i} b_j,
the highest rival bid. Bidder i’s own bid now settles exactly one question: bid above m and win at price m, for a payoff of v_i - m; bid below m and lose, for a payoff of nothing (exact ties are immaterial, and may be broken however the auctioneer pleases). Two cases exhaust the possibilities that matter (at the knife-edge v_i = m every available payoff is zero, so nothing is at stake). If v_i > m, winning is worth having, and the truthful bid b_i = v_i lies above m and secures it; nothing does better, since every winning bid collects the same v_i - m and every losing bid collects zero. If v_i < m, winning would mean paying m for a thing worth v_i, and the truthful bid duly loses, collecting the zero that is now the best on offer. In both cases truth attains the maximum payoff available against that field — and m was arbitrary, so b_i = v_i weakly dominates every alternative bid against every field. No distribution was assumed, no beliefs consulted, no equilibrium computed: that is what a dominant strategy is. What the rule earns the seller is the next subsection’s question.
12.2.2 Same Revenue, Different Everything Else
For the seller wondering which format extracts the most money, the answer is genuinely surprising: it does not matter. Any auction that awards the good to the highest-value bidder and gives the lowest possible type nothing yields the same expected revenue: the revenue equivalence theorem, glimpsed by Vickrey and proved in generality by Myerson (1981). If the formats tie on revenue, the choice turns on everything else — information leaked, collusion invited, strategic burden imposed.
That informal gloss can be tightened into the theorem’s exact terms. Suppose each of the n bidders is risk-neutral, and each draws its private value independently from the same continuous distribution — values private, draws independent, bidders symmetric. Then any two auction mechanisms whose equilibria (i) always award the good to the bidder with the highest value and (ii) leave a bidder of the lowest possible type with an expected payoff of zero yield the seller identical expected revenue, whatever their clocks, envelopes, rounds, or theatre: nothing else about a format survives the taking of expectations.
Equivalence fails informatively on each assumption: risk-averse bidders make first-price formats raise more; correlated values favour open formats. And Myerson’s same paper delivers the seller’s sharpest lesson: for well-behaved value distributions, the revenue-optimal auction is a second-price auction with a reserve price set above the seller’s own value — the optimal design sometimes refuses to sell to a willing buyer at a mutually profitable price. Revenue maximisation deliberately sacrifices efficiency: what a mechanism optimises is a design choice, and the designer cannot have everything at once.
12.2.3 The Winner’s Curse
Everything above assumed private values — the good is worth what it is worth to you — and the assumption must now be paid for. But many auctioned goods have a common value — the oil under the tract is worth the same to every bidder, and each holds only a noisy estimate — and here the auction’s selection logic turns sinister. The winner is whoever holds the highest estimate, and the highest of many noisy estimates of the same quantity is, on average, an overestimate. Winning is bad news: it tells you that you were the optimist. The petroleum engineers who documented the effect on Gulf of Mexico oil leases named it the winner’s curse and drew the paradoxical-sounding remedy: bid as though your estimate is the highest in the room, because if you win, it was (1971). The rational common-value bidder shades not from strategy but from statistics.
Every engineer running a task-allocation auction should feel a chill of recognition. When an orchestrator awards work to the agent bidding the fastest completion or highest confidence, the bids are noisy estimates of a common quantity — the task’s true difficulty — and the auction selects the most optimistic error: the winner is systematically the agent that most underestimated the job, Section 7.4’s cheerful “I can do it” rewarded in proportion to the noise. The corrections are the curse’s own: penalise overrun so that bids carry consequences, weight bids by calibration history so that chronic optimists pay for their record, and shade awards away from the extreme bid.
12.2.4 Bidding Machines
For artificial bidders the lesson is which family to build on, and it is not close. A dominant-strategy mechanism asks nothing of its participants but arithmetic — the agent can simply be instructed to bid its value. Chapter 9 left a standing worry that language-model agents neither compute equilibria nor reliably play them (Section 9.6); strategy-proof design is the worry’s cleanest answer: where honesty is dominant, the institution supplies the rationality the players lack. The caveat: the theorem removes the incentive to misreport, not the capacity to misreport by accident. A language-model bidder follows the instruction to bid its value only as reliably as it follows any instruction — approximately, with a documented tilt towards telling its interlocutor what it seems to want to hear (Sharma et al., 2023) — so whether a given bidder actually bids its value under a given rule is an empirical property, to be measured rather than inherited from the proof. The choice of auction format decides where the strategic difficulty lives — in the agents or in the rules — and the engineer, uniquely, gets to choose. Whether Vickrey’s rule is an isolated trick or a general method is the next section’s question.
12.3 Inverse Game Theory: Mechanism Design
What Vickrey did for one auction, a field grew up to do for everything. Mechanism design poses the last section’s question at full generality: for any collective decision among self-interested parties with private information, what can any set of rules achieve, and what can no set of rules achieve, ever? Hurwicz, who founded the enterprise, made the rules themselves the object of engineering (1973); the 2007 Nobel citation for him, Maskin, and Myerson ratified the framing.
Several agents each hold a private type in Section 9.5’s sense — a true valuation, cost, or difficulty estimate — and the designer has in mind a social choice function: a rule specifying, for every profile of true types, which outcome ought to obtain — who gets the GPU hour, whether the refactor happens. Types are private, and asking directly recreates Chapter 11’s posturing, so the designer must work through a mechanism: a specification of what messages agents may send and how the outcome (and any payments) will be computed from them. The design succeeds — implements the social choice function — when the induced game’s equilibrium play delivers the intended outcome at every type profile. The designer never controls what agents do, only the game they do it in; it must get its way through their self-interest, not despite it.
The central property has a name to keep. A direct mechanism — one whose messages are simply type reports — is incentive-compatible when truthful reporting is an equilibrium. The property comes in grades: Bayesian incentive compatibility makes truth optimal on average, given beliefs about the other agents and the assumption that they too are truthful; dominant-strategy incentive compatibility — strategy-proofness — makes truth optimal whatever the others do. The Bayesian grade asks agents to be right about each other, the dominant grade asks nothing of them at all; for artificial participants of uncertain sophistication, reach for the dominant grade first and relax it reluctantly.
The design problem looks hopeless — any message language, any rounds, any mapping from talk to outcomes: an unsurveyable space. The field’s first great theorem removes the terror. The revelation principle says: whatever any mechanism, however elaborate, achieves in equilibrium, some direct incentive-compatible mechanism achieves too. The proof is one construction: build a front-end that asks each agent its type outright, then plays that agent’s equilibrium strategy on its behalf inside the old mechanism. The machine lies for you precisely as well as you would have lied for yourself, so there is no longer any point lying to it: honesty made optimal by automating the dishonesty.
What the principle buys is the field itself: the unsurveyable space collapses to direct truthful mechanisms, and design becomes constrained optimisation — literally how Myerson derived Section 12.2’s optimal auction. But the principle is an accounting identity, not a deployment guide: the equivalent direct mechanism may centralise what the original distributed, and it says nothing about which equilibrium fragile real players will find. Its working use is asymmetric: decisive for proving limits — if no truthful direct mechanism can achieve a goal, no mechanism can, full stop — and only a starting point for what to ship.
The field’s one great positive construction generalises Vickrey’s auction to arbitrary collective decisions: the Vickrey–Clarke–Groves mechanism (1971; 1973; 1961). The recipe has two lines: choose the outcome that maximises the total of every agent’s reported valuations, then charge each agent the externality its presence imposed — the difference between what everyone else would have got had it stayed home and what everyone else actually got. The Vickrey auction falls out (the winner’s presence cost the runner-up the good), and the same crank turns anywhere: the contested GPU hour, the sprint spent on the refactor. Truthfulness is dominant for the same reason as in Section 12.2, now in general form: your payment is constructed from other agents’ reports, so your own report steers only which outcome is chosen — and since you are charged the others’ loss, your private objective and the social objective have been made the same function. It is the high-water mark of the enterprise: one mechanism, applicable to any decision with money on hand, simultaneously efficient and strategy-proof — self-interest harnessed to compute the social optimum.
12.3.1 The Machine, Formally*
The machine’s two lines can be written exactly, and the truthfulness argument is short enough to watch working. Let X be the set of possible outcomes, and let each agent i report a valuation function \hat v_i(\cdot) over outcomes — the hat marking a report, which may or may not be the true v_i(\cdot). The mechanism chooses the outcome that maximises reported welfare,
x^{*} \;=\; \operatorname*{arg\,max}_{x \in X} \; \sum_{i} \hat v_i(x),
and charges each agent its Clarke pivot payment,
p_i \;=\; \max_{x \in X} \sum_{j \ne i} \hat v_j(x) \;-\; \sum_{j \ne i} \hat v_j(x^{*}),
which is the prose’s externality, priced: what the others could have had without i, minus what they actually get. Now inspect agent i’s utility. It values the chosen outcome at v_i(x^{*}) and pays p_i, so its utility equals
v_i(x^{*}) \;+\; \sum_{j \ne i} \hat v_j(x^{*}) \;-\; \max_{x \in X} \sum_{j \ne i} \hat v_j(x),
whose final term is computed from the others’ reports alone — a constant, as far as i’s report is concerned. What i can influence is only the rest: the social welfare of the chosen outcome, measured with i’s true valuation and the others’ reports. Agent i therefore wants the mechanism to pick the x maximising v_i(x) + \sum_{j \ne i} \hat v_j(x); the mechanism picks the x maximising \hat v_i(x) + \sum_{j \ne i} \hat v_j(x); and reporting \hat v_i = v_i makes those two problems the same problem. Utility has been made equal to welfare plus a constant beyond the agent’s reach, so pursuing the one is pursuing the other, whatever anyone else reports — truth is dominant, and the argument, like Vickrey’s, consulted no beliefs and no equilibrium. What the machine gives up in exchange is the next subsection’s business.
12.3.2 Where the Machine Creaks
Practice has been cooler, for structural reasons. VCG is notoriously hospitable to collusion: dominant-strategy incentive compatibility protects against solitary deviation, and says nothing about a cartel coordinating reports to lower one another’s payments. Worse, the mechanism can be manipulated by a single agent pretending to be several: Yokoo and colleagues showed that false-name bids can be strictly profitable under VCG, and that no mechanism with VCG’s other virtues fully resists them (2004). Anyone building an agent platform should take the threat personally: where a bidder is an API key and minds can be copy-pasted, sybil manipulation is not an exotic attack but a natural act — three lines of code and no conscience required.
The remaining creaks bite the same way. The pivot payments do not in general sum to zero: VCG is not budget-balanced, and the surplus it collects must leave the system, because recycling it back to the participants re-couples what the construction so carefully decoupled. And the outcome rule requires solving the welfare-maximisation problem exactly: in rich allocation settings that problem is NP-hard (Section 12.4 meets it under the name winner determination), and substituting an approximate optimiser quietly destroys incentive compatibility. The verdict: VCG is the field’s benchmark and proof of possibility, imitated everywhere, trusted raw only where collusion and identity are controlled — which, as Section 12.5 will argue, a harness can sometimes actually arrange.
12.3.3 The Fences
What mechanism design cannot do is fenced by theorems, and the first fence the reader has already visited. Gibbard and Satterthwaite proved (Section 10.3) that with unrestricted preferences and no money, the only strategy-proof rule choosing among three or more outcomes is dictatorship. Everything this chapter has built escapes through one gate: money — transferable value that lets a mechanism price misrepresentation instead of merely forbidding it. That is why markets can do what ballots cannot; where value cannot decently be made transferable — votes, verdicts, organ queues — the impossibilities return, and no auctioneer can help.
The second fence answers a question Chapter 11 left standing. Myerson and Satterthwaite proved that in the simplest trade — one buyer, one seller, values private on both sides — no mechanism whatsoever is simultaneously efficient, incentive-compatible, voluntary, and free of outside subsidy (1983). Some mutually beneficial trades must, in expectation, fail. Chapter 11 closed Section 11.2 with bargainers posturing and walking away from surplus; the temptation is to read that as protocol failure awaiting a cleverer design. The theorem says otherwise: under two-sided private information, some posturing loss is not a bug in the bargaining but a property of the situation, unremovable by any rules at all.
Each of those four conditions carries an exact grade, and the theorem repays restating with the grades attached. Take the smallest market imaginable: one seller holding a good it privately values at v_s, one buyer privately valuing it at v_b, both parties risk-neutral, the two values drawn independently, each from a continuous distribution, and the supports overlapping, so that either party may be the one who values the good more. Then no mechanism whatever is simultaneously ex-post efficient (trade occurs exactly when v_b > v_s), Bayesian incentive-compatible (truthful reporting optimal given beliefs, assuming the other party reports truthfully), interim individually rational (each party, knowing its own value, expects to do no worse by participating than by walking away), and budget-balanced (payments net to zero, with no outside subsidy). The four conditions are exactly as many as can be refused: drop incentive compatibility and the question dissolves, since with honesty assumed the first-best is mere administration; drop any one of the other three and the remaining conditions become achievable; demand all four and the design space is empty.
The moral generalises into the field’s standing budget constraint: efficiency, truthfulness, voluntary participation, and budget balance cannot all be had at once, and every real mechanism is a choice of which to sacrifice — Table 12.2 names the price each of this chapter’s mechanisms pays. The gift the theory hands the engineer is not a perfect mechanism — there is none — but the knowledge that the sacrifice is forced: no amount of midnight debugging will find the design the theorem forbids, and the time is better spent choosing the sacrifice deliberately, in the open.
| Desideratum | What it demands | A mechanism that gives it up |
|---|---|---|
| Efficiency (ex-post) | The allocation happens exactly when it should — in a trade, when v_b > v_s | Myerson’s revenue-optimal auction — a reserve price set above the seller’s own value |
| Incentive compatibility (truthfulness) | Honest reporting is optimal — here Bayesian: truthful given one’s beliefs, assuming the others report honestly | Administrative fiat — gives up truthfulness and hopes nobody notices |
| Individual rationality (voluntary participation) | Each party, knowing its own value, expects to do no worse by taking part than by walking away | None this chapter names — each mechanism here keeps participation voluntary |
| Budget balance | Payments net to zero, with no outside subsidy | VCG; a subsidised exchange — which gives up self-sufficiency |
12.4 Markets at Scale: From Spectrum to Sponsored Search
Theories of collective decision-making do not usually get field trials; auction theory has been trusted, at national scale, with allocations worth fortunes — the best evidence this part can offer that its subject is engineering rather than commentary. In 1994 the United States stopped giving radio spectrum away by lottery and started selling it — and the question of how was handed, remarkably, to theorists. The licences were interdependent — a licence’s value depends on which neighbours the bidder also wins — so selling them one at a time would have forced bidders to gamble on complements they might not get. Milgrom and Wilson’s simultaneous multiple round auction put every licence on the block at once, in open ascending rounds, an activity rule obliging bidders to stay active early or forfeit the right to bid late (2004). It worked: tens of billions raised, the format adopted worldwide, a Nobel earned not for a theorem but for a working artefact. The details are as instructive as the verdict. Real bidders probed the rules just as Chapter 9 would predict: demand reduction appeared, and bidders took to signalling through the trailing digits of their bids — a cartel coordinating in public through the only channel the rules left open — until the rules were amended to round bids. Every clause of a modern spectrum auction is a scar with a story: mechanism design in practice is an adversarial engineering loop — design, deploy, watch self-interest find the gap, patch, repeat — and the theory’s contribution is to start the loop close enough to sound that the patches converge.
When goods are complements, the honest thing is to let bidders say so: a combinatorial auction accepts bids on bundles — “these three licences together, or nothing” (Cramton et al., 2006). The price of that honesty is computational, and it is steep. Choosing the revenue-maximising set of compatible bundle bids — the winner determination problem — is NP-hard, Section 12.3’s warning arriving on schedule: this is the welfare-maximisation that VCG demands be solved exactly, and the gap between exact and approximate is where the truthfulness leaks out. The response: search that exploits the sparsity of real bid sets (Sandholm, 2002), restricted bidding languages, iterative price discovery over rounds. The reader assembling agent teams has met the problem on site: subtasks are complements — the parser is worth little without its tests — and an orchestrator that auctions tasks one at a time is running the greedy approximation. Chapter 7’s Contract Net allocates in precisely this fashion, fine when tasks are independent and quietly wrong when they are not; and knowing the problem is NP-hard is itself operational knowledge, because any shortcut taken in the allocation step spends incentive guarantees, not just optimality.
12.4.1 The Auction You Were Just In
The largest deployment of mechanism design in history was not designed by mechanism designers. The advertisements beside a search results page have just been auctioned: advertisers bid per click, slots go to the high bidders in rank order, and each winner pays roughly the bid of the advertiser below it — the generalised second-price auction, run billions of times a day (Edelman et al., 2007). The format was not derived; it evolved: early sponsored search charged first-price per click, duly exhibited the instability Section 12.2 would predict, and the pay-next-bid rule emerged as the industry’s stabilising patch, later christened with a name that advertised its Vickrey ancestry.
The christening is the cautionary tale. GSP looks like the Vickrey auction generalised to several slots; Edelman, Ostrovsky, and Schwarz showed that it is not — with multiple slots, truthful bidding is not an equilibrium, because the clean decoupling of bid from price holds only for a single good (2007). The mechanism works — well-behaved equilibria, respectable revenue, the welfare its strategising surrenders provably capped at just over a fifth of the optimum, a price-of-anarchy bound of Section 9.2’s kind (Caragiannis et al., 2015) — but its bidders must strategise, and an ecosystem of bid-management agents duly exists. The durable lesson: resemblance is not inheritance. A mechanism’s guarantees live in its proof, and the proof’s hypotheses, not the mechanism’s pedigree, decide whether they transfer — the same lesson Section 11.5 taught about debate protocols resembling dialogue games.
12.4.2 Traders Without Minds
Gode and Sunder took the continuous double auction — the standard exchange institution — and replaced every human trader with a zero-intelligence program: a bidder that submits random offers, subject to a single budget constraint forbidding it to buy above its assigned value or sell below its assigned cost (1993). No learning, no strategy, no memory. The markets’ allocative efficiency barely noticed: the random traders extracted close to 100% of the available surplus, about what humans achieve in the same institution (Figure 12.2). The subtitle states the finding with academic restraint — “Market as a Partial Substitute for Individual Rationality” — and it deserves less: in this institution, the traders contribute almost none of the intelligence.
For this book the experiment is close to a founding document: the field’s cleanest ablation study — remove the agents’ intelligence, keep the institution, measure what survives; most of it survives. The thesis the book has been humming since Chapter 1, that system-level competence lives as much in the arrangement as in the participants, here stops being a slogan and becomes a number. Zero-intelligence traders match humans only on allocative efficiency — not price dynamics, not the division of the spoils — but the directive stands: before crediting your agents’ cleverness for a system’s performance, run the Gode–Sunder test. Replace them with something mindless, keep the mechanism, and see how much was the mechanism all along.
12.5 The Engineer as Auctioneer: Mechanisms in the Harness
The harness is an odd jurisdiction. Inside it, the mechanism designer’s eternal headaches simply vanish: the rules are code, so they cannot be bent; payments are deducted at source, so nobody reneges; every bid is logged. Human auction designers spend careers approximating these conditions with law, reputation, and armed bailiffs; the orchestrator gets them free. In exchange, it faces the strangest bidder population ever assembled — participants that can be copied, spawned, prompted, and read — and a resource, tokens, that bidding itself consumes.
Chapter 7’s Contract Net — announce, bid, award, await the report (Smith, 1980) — reads, with this chapter’s eyes, as a procurement auction, built fifteen years before auction theory reached the field, with every incentive question left open. The bids are free text in the first-price family, so nothing makes them truthful — “I can complete this in ten minutes with high confidence” is chosen for its effect on the award, not its accuracy. The award goes to the most attractive claim, so Section 12.2’s winner’s curse operates at full strength: the protocol systematically selects the bidder that most underestimates the task. And the tasks go one at a time, so Section 12.4’s bundle problem is answered with the greedy approximation. The protocol organised decomposition and delegation admirably, but it was designed as a conversation, and the moment the bidders acquired interests it began operating as a market, unpriced and unguarded. The upgrade path is this chapter applied line by line: make the bid a structured, binding commitment — an estimate with a penalty for overrun, so that Chapter 5’s commissive speech act acquires a price and stops being cheap talk; award by a scoring rule that weights the bidder’s calibration history — Section 12.2’s curse correction; price the award in second-price or VCG style, so that stating one’s true estimate is safe — Section 12.3’s decoupling, imported whole; and where tasks are complements, run bundle rounds, with Section 12.4’s warning about the computational bill in view. Each part is classical; the assembly is the Contract Net promoted to what it was always trying to be: a task market with its incentives engineered rather than hoped for.
12.5.1 When to Run a Market
Against all this stands an honest ledger. Every auction round sets several agents deliberating over bids and then discards all but one of those deliberations — the running cost of a market is mostly the losers’ wasted thinking, and in a token economy the bidding burns the very resource being allocated. Fiat is cheap and blind; a market is informative and expensive; the choice between them is Section 12.1’s checklist priced honestly. Where the checklist holds, the auction pays for itself; where the orchestrator can simply look, the market is ceremony, and the tokens it burns are pure overhead.
The checklist has a two-decade field record on real hardware: robotics. Gerkey and Matarić’s MURDOCH auctioned tasks robot to robot (2002); the TraderBots lineage was surveyed, wins and failure modes attached, by Dias and colleagues (2006); the consensus-based bundle algorithm decentralises the auctioneer itself, vehicles on a lossy radio link converging on a conflict-free allocation with nobody holding the hammer (Choi et al., 2009). A robot’s battery, position, and travel costs are genuinely private, drifting, and its own — exactly the dispersed information prices exist to carry — and the auction earned its overhead on the warehouse floor long before anyone proposed one over a token budget.
A subtler solvency condition: an auction extracts value from competition, and competition can be thin — a single bidder is a hostage negotiation, and a field of bidders that are all copies of one model raises the question of what information the market is aggregating at all. The requirement is Chapter 10’s, transposed: as the jury needed jurors whose errors were independent (Section 10.5), the market needs bidders whose information is genuinely private and different. Each copy’s context, load, and task history are its own, so copies are not disqualified; but a market where the only variation is the sampling temperature is the photocopied electorate at the auction house, paying auction prices for poll-quality information.
12.5.2 The Strangest Bidders
The new population’s pathologies concentrate on identity, and Section 12.3’s warnings arrive with their safeties off. Copies of one model are natural colluders — not conspiratorially but structurally, since shared weights produce correlated strategies without a word exchanged — so VCG’s documented hospitality to cartels meets its ideal customer. And false-name manipulation, which Yokoo and colleagues framed as fraud (2004), is in an open agent platform the default physics: spawning another bidder is an API call, so any mechanism whose guarantees are stated per bidder is making an assumption the environment does not supply. Identity itself must be made scarce on purpose — credentials, registration, bonds posted per identity — which is to say that before running a market an engineer must build a small institution, a fact Chapter 13 will generalise.
The compensations are real and unprecedented. The auctioneer-trust problem that kept the Vickrey auction rare among humans (Section 12.2) dissolves when the auctioneer is auditable code and the second-highest bid sits in a log nobody can quietly edit. Enforcement, the chapter-opening assumption, is here a property: the payment clears before the bidder’s next token is sampled. And the designer holds both sides of a ledger no human mechanism designer ever touched, writing the rules and assigning the valuations — Section 12.1’s caveat returned as a lever. An internal agent market is not an economy that grew but a design pattern that was chosen — adopted for Hayek’s reasons, audited by Gode and Sunder’s test: mindless bidders first, credit afterwards.
12.5.3 Where the Market Stops
One question remains: if prices are this good, why does the team exist at all? Why not dissolve the orchestrator into an exchange and auction every function call? Coase asked the mirror image about human firms in 1937: if the market is the marvel Hayek said it was, why is the economy full of firms — islands of administrative fiat floating in the price system’s sea? His answer founded a field: using the price mechanism costs something — there are transaction costs. Prices must be discovered, exchanges negotiated, contracts written — and where exchanges are frequent, entangled, and hard to specify, it is cheaper to bring them inside a boundary and coordinate them by authority, standing roles, and routine. The firm ends where the ledger balances: where organising one more transaction internally costs as much as pricing it in the market (1937).
The agent translation is exact, and it is the chapter’s parting design rule. Coordination that is frequent, entangled, and hard to specify — the coder and tester trading partial artefacts twenty times an hour — belongs inside the boundary, run by Part III’s machinery of plans, roles, and joint commitments, where a market would price each handoff at ruinous overhead. Allocation that is occasional, separable, contested, and valuable — the scarce GPU hour, the external API budget — belongs at the boundary, priced, where fiat would allocate blind. The orchestrated team with markets at its edges is Coase’s equilibrium, computed for tokens. Part IV has taught strangers to vote, bargain, argue, and trade; Coase’s deeper discovery is that the cheapest institution is often to stop being strangers — to form durable alliances with names, roles, and authority: organisations. Which coalitions form, how the spoils divide, what makes an organisation more than a diagram of job titles — that is the next chapter, and the close of Part IV.
12.6 Summary
- A price is compressed information. Into one number goes what participants privately know about scarcity, value, and alternative uses — knowledge no planner could gather by asking; a team sharing a token budget is already running this computation.
- Auctions are precision instruments. The classic designs tie on expected revenue under classical assumptions, so the choice turns on everything else; Vickrey’s second-price rule makes truthful bidding dominant by divorcing what you pay from what you said.
- Mechanism design is game theory run backwards. Fix the outcome, derive the game: incentive compatibility is a property of the rules, not a virtue of the players, and the revelation principle shrinks the search to direct truthful mechanisms.
- VCG is the grand machine, and it creaks under load. Charging each winner the externality it imposes buys efficiency and truthfulness in one stroke — and invites collusion, false-name bidding, and hard computation; Myerson–Satterthwaite proves some bargaining inefficiency is nobody’s fault.
- The theory ships. Spectrum auctions turned mechanism design into civil engineering; sponsored search runs it billions of times a day; zero-intelligence traders extract near-full efficiency from markets whose participants have none — the institution, not the agent, carries the intelligence.
- In the harness the engineer holds the enforcement advantage and faces stranger bidders. Rules can be code and payments deducted at source; but copies of one model are natural colluders, a shill costs an API call, and truthfulness under a strategy-proof rule is measured, not inherited. Some exchanges are too frequent or entangled to price — Coase’s firms exist because markets have costs — and there the next chapter begins.
12.7 Exercises
Exercise 1. The orchestrator auctions the sprint’s one contested GPU-hour among the coder, the reviewer, and the tester by sealed bid, and bids are in whole tokens; the coder privately values the hour at v_c = 800 tokens of rework avoided, and the rival envelopes turn out to hold “500” from the reviewer and “650” from the tester, so the highest rival bid is m = 650 (a winning bid must exceed m; exact ties are immaterial). (a) Under the second-price rule, tabulate the coder’s payoff for every bid in \{500, 600, 650, 700, 800, 900, 1000\}, and confirm the shape the proof in Section 12.2 promises: every winning bid collects the same v_c - m, every losing bid collects zero, and the truthful bid sits among the maximisers. (b) Repeat with v_c = 600: show every winning bid now collects the same loss, that truth loses and collects the best available payoff of zero, and say which of the proof’s two cases each table is. (c) Score the same field under the first-price rule: show the truthful bid of 800 wins and collects nothing, find the best whole-token bid against this known field and its payoff, and explain what changes about the bidder’s problem — not the arithmetic but its inputs — the moment the field is no longer known. (d) The Bayesian version of (c): two bidders, values drawn independently and uniformly on [0, 1]; supposing the rival bids half its value, show that a bidder with value v who bids b \le 1/2 wins with probability 2b and so expects (v - b) \cdot 2b, derive the best response, and conclude that bidding half one’s value is an equilibrium, with expected payoff v^2/2. Close with one sentence: which strategic family Table 12.1 recommends for artificial bidders, and what precisely your workings in (a)–(b) versus (d) are evidence for.
Exercise 2. Stay with two bidders whose values are independent and uniform on [0, 1], and take the seller’s chair. (a) Show that the second-price auction’s expected revenue is \mathbb{E}[\min(v_1, v_2)] = 1/3. (b) Using the equilibrium of Exercise 1(d), show the first-price auction’s expected revenue is also 1/3 — revenue equivalence, verified by hand for this pair (Section 12.2). (c) Myerson’s lesson made arithmetic: add a reserve price r to the second-price auction — no sale if both values fall below r, a lone bidder above r pays r, two above pay second-price as usual — show the seller’s expected revenue is E(r) = 2r^2(1 - r) + (1 - r)^2 \bigl(r + (1 - r)/3\bigr), differentiate, and find the optimal reserve and its revenue, noting that the seller values the good at nothing. (d) Price the reserve: compute the probability the good goes unsold although a willing buyer stands ready, the fall in expected welfare, and the fall in expected buyer surplus, and reconcile the ledger — how much of what the buyers lose reaches the seller, and how much simply evaporates? Name the desideratum of Table 12.2 the optimal auction is spending, and what it buys.
Exercise 3. The orchestrator announces a gnarly bug-fix and awards it to whichever of n candidate coders returns the lowest difficulty estimate; the task’s true cost is D = 10{,}000 tokens, and each candidate’s estimate is D + \epsilon_i with the errors independent and uniform on [-a, a] for a = 3{,}000 — so every individual estimate is unbiased. (a) Show that the expected minimum of the n error draws is -a(n-1)/(n+1), and compute the winning estimate’s expected value for n = 2, 4, and 8. (b) Compute the expected overrun — true cost measured against the winning estimate — as a percentage of the winning estimate for each n, and resolve the paradox in one sentence: every estimator is unbiased, yet the better-staffed the field, the worse the winner’s number. (c) Derive the statistical correction: by how much should the orchestrator inflate the winning estimate before scheduling against it, why is the corrected figure unbiased in expectation, and what must be known for the correction to be computable? (d) Section 12.2 names three engineering corrections — overrun penalties, calibration-weighted awards, and shading awards away from the extreme bid. Which of the three is (c), and what do the other two supply that (c) cannot when the noise width is unknown, or differs from bidder to bidder?
Exercise 4. The sprint has slack for exactly one collective project — the refactor \mathrm{R}, the flaky-test hunt \mathrm{F}, or the documentation rebuild \mathrm{D} — and the orchestrator decides by VCG (Section 12.3), collecting valuation reports in tokens: the coder reports (\mathrm{R}, \mathrm{F}, \mathrm{D}) = (500, 200, 0), the reviewer (100, 350, 150), the tester (250, 150, 300). (a) Compute the reported welfare of each outcome, the chosen x^{*}, and each agent’s Clarke payment; identify the pivotal agent, and say what a zero payment means about the other two. (b) Verify the proof’s central identity on the coder: its utility equals the welfare of the chosen outcome minus a constant beyond its reach — exhibit both numbers. (c) The reviewer would rather have \mathrm{F}: find the smallest exaggeration of its \mathrm{F} report that flips the outcome, compute its resulting payment and utility, and compare with honesty; then state the general moral in the chapter’s terms — what did the lie steer the collective towards, and at what price to the liar? (d) Sum the three payments. Where must the surplus go, and why does the tidy-minded proposal of rebating it to the three agents in equal shares break the very property the mechanism was chosen for?
Exercise 5. The orchestrator needs a bespoke component from an external specialist agent: the buyer’s value v_b and the seller’s cost v_s are private, independent, and uniform on [0, 1] in normalised budget units, and they trade split-the-difference — each reports a number, and trade happens at the midpoint of the reports whenever the buyer’s report is at least the seller’s. In this mechanism’s linear equilibrium the buyer reports 2v_b/3 + 1/12 and the seller 2v_s/3 + 1/4. (a) Show that trade occurs exactly when v_b \ge v_s + 1/4. (b) Show the first-best expected surplus is \mathbb{E}\bigl[\max(v_b - v_s, 0)\bigr] = 1/6, using the fact that the difference d = v_b - v_s has the triangular density 1 - |d| on [-1, 1]. (c) Compute the equilibrium’s expected surplus and the share of first-best it captures. (d) Compute the probability that a mutually beneficial trade fails outright — unconditionally, and conditional on a gain from trade existing. (e) Take as given that no incentive-compatible, individually rational, budget-balanced mechanism captures more expected surplus in this setting than this one does, and read your numbers against Table 12.2: which desideratum has been sacrificed, what exactly is the residual gap the price of, and why is a cleverer protocol not the remedy?
Exercise 6. A results page has two advertisement slots delivering 200 and 180 clicks, and three bidders value a click at 10, 4, and 2. (a) Under truthful bidding, compute the GSP assignment, each winner’s payment, and each winner’s utility. (b) Show truthful bidding is not an equilibrium of GSP: exhibit a deviation for the top bidder — a bid between its rivals’ — and compute the gain. (c) Compute the VCG payments on the same instance, verify by cases that the top bidder now gains from no deviation, and note which slot’s payment the two mechanisms agree on. (d) In at most two sentences: which step of Vickrey’s single-good decoupling fails once there are two slots, and how does the episode illustrate Section 12.4’s warning that resemblance is not inheritance?
Further exercises for this chapter continue in the web edition’s exercise bank.
