%%{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
15 Markets, Auctions, and Mechanism Design
Chapter 12 made a promise it is now time to keep. Its games arrived with their rules fixed and given — part of the world, like weather — and the engineer’s job was to predict what self-interested agents would do inside them. But an engineer building a multi-agent system does not take the rules as given; the engineer writes them — who may bid, what counts as a message, when the exchange closes, who pays what — and so occupies a seat the classical theory reserves for a character grander than any player: the designer of the game itself. Mechanism design is game theory run backwards. Instead of fixing the game and deriving the outcome, 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. The book has been edging toward this seat for three chapters: Chapter 13 closed by asking how to choose how to choose; Chapter 14’s deepest lesson was that whether agents lie is a property of the rules of encounter; this chapter is where the edging stops and the discipline begins.
The instrument at the discipline’s centre is the one the last chapter reached for at its wall: the price. A price looks like a small thing — one number attached to one good — but it is the most heavily compressed message in this book: into it goes everything a market’s participants privately know about scarcity, value, and alternative uses, none of which any central planner could gather by asking, since asking, as Chapter 14 established at length, mostly gathers posturing. And beside the price stands the result that ought to sound too good to be true after three chapters of strategic misrepresentation: 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. What such rules cost, where they exist, and where theorems say they cannot, is the chapter’s business. Nor is any of this exotic to the systems this book studies. The software-engineering team’s token budget is already an economy — run, so far, by administrative fiat, the orchestrator playing central planner — and the largest multi-agent system in production anywhere on Earth is an auction house: the advertising exchanges that clear billions of times a day, deciding at machine speed which advertisement is worth showing to whom.
The theory is, as ever, older than the agents, and unusually decorated. Vickrey worked out in 1961 why an auctioneer might want to charge the winner the runner-up’s price, and found truth-telling waiting at the bottom of the analysis. Hurwicz posed the general question — what can rules achieve when information is private and its holders self-interested? — and Myerson, Maskin, and their colleagues built the apparatus on top: incentive compatibility, the revelation principle, the great possibility theorems and the fences of impossibility around them. It is protocol design, at bottom — and it is the branch of protocol design with two Nobel prizes, the second earned in the field, when auction theorists were handed entire nations’ radio spectrum to sell and the theory, unusually for economics, shipped. Multi-agent systems research was on the ground early: the Contract Net (Section 10.4) was running announce–bid–award loops in 1980, and market-oriented programming was pricing distributed computation in the 1990s, both a substrate too early, as usual. 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 before setting out. First, this chapter concerns exchange among self-interested parties who remain strangers: nobody merges, nobody forms a lasting alliance, every deal is anonymous and complete in itself. The strangers who discover they would rather be colleagues — coalitions, organisations, institutions — are the next chapter’s subject, and the close of Part IV. Second, one assumption does quiet work throughout: that the designer can enforce the rules — collect the payment, bar the late bid, make the allocation stick. Among humans this is what auction houses, exchanges, and contract law are for; inside an agent harness the orchestrator holds a power human auctioneers only dream of, because the rules can be code and the payments deducted at source. That makes agent systems unusually fertile ground for mechanism design — and makes its known failure modes unusually pressing, above all collusion among bidders who may be copies of the same model. We proceed from what a price is and does (Section 15.1); to the classic auctions and Vickrey’s little miracle (Section 15.2); to the general theory — incentive compatibility, the revelation principle, VCG, and the impossibility results that fence the field (Section 15.3); to the theory at scale, from spectrum sales to sponsored search (Section 15.4); and finally to the engineer’s own seat at the rostrum, pricing tasks and tokens inside the harness — and to the boundary where markets stop and organisations begin (Section 15.5).
15.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 for the metal has been found — Hayek, who chose the example, is careful to say that it does not matter which, and that almost nobody who matters will ever find out (1945). What happens next is the remarkable part. The price of tin rises; users of tin economise, substitute, postpone; suppliers of substitutes expand; users of the substitutes economise in their turn, rippling outward through people who have never heard of the original event. Thousands of decisions adjust in the right direction, “without an order being issued, without more than perhaps a handful of people knowing the cause”. Hayek’s essay — written into the mid-century argument over whether a central authority could allocate resources as well as a market — is on any short list of the most consequential economics papers of its century, and its lasting move was to change the question. The interesting thing about a market, he argued, is not who owns what. It is what a market does with knowledge.
The argument deserves its modern name: the knowledge problem. The information a rational allocation would need, Hayek observed, “never exists in concentrated or integrated form but solely as the dispersed bits of incomplete and frequently contradictory knowledge which all the separate individuals possess” — and the bits that matter most are knowledge of “the particular circumstances of time and place”: this machine idle now, this route congested today, this consignment spoiling on this dock. Such knowledge is local, perishable, and often tacit — its holder may not know it is worth reporting until the moment it is needed — so the central planner’s failure is not chiefly a failure of intellect or motive. It is a failure of bandwidth and staleness: the state of the economy cannot be shipped to headquarters faster than it changes. The reader who has sized a context window will recognise the shape of the problem immediately, and should feel free to admire how early it was stated: it is a distributed-systems argument, made in 1945, about why the global state table cannot be maintained.
The price system is Hayek’s answer, and he pitched the description at this book’s exact readership: “It is more than a metaphor to describe the price system as a kind of machinery for registering change, or a system of telecommunications which enables individual producers to watch merely the movement of a few pointers, as an engineer might watch the hands of a few dials, in order to adjust their activities to changes of which they may never know more than is reflected in the price movement.” One number per good, readable by anyone, carrying in compressed form the net pressure of everything everyone knows about scarcity and use. No participant needs the whole picture, and — the point planning missed — no participant has it; each needs only the prices and its own private circumstances, which are the two things it reliably possesses. The marvel, as Hayek called it, is that so narrow an interface coordinates so much; had it been the result of deliberate human design, he remarked, it “would have been acclaimed as one of the greatest triumphs of the human mind”. It was not designed at all, which is a lesson Part V will pick up.
Read as computation, the mechanism is disarmingly simple. Each participant solves a small local problem: given the posted prices, how much of each good to buy or sell — a private optimisation over private information. The market then runs an adjustment loop: where demand outruns supply, the price rises; where goods go begging, it falls — the process Walras called tâtonnement, French for “groping about”, which is at least honest. The fixpoint of the loop, where every market clears and no price has reason to move, is competitive equilibrium — a rest state of the same family as Section 12.2’s, though gentler, since price-takers respond to the dials rather than to each other — and the textbook theorems certify that the allocation it reaches is efficient: nobody can be made better off without someone made worse. The cautions attach at once — convergence is not guaranteed in general, Walras’s price-adjusting auctioneer is a fiction, and real markets are ill-behaved approximations of the model — but the computational reading is not a metaphor bolted on by computer scientists. The planning debate of Hayek’s day was about whether this very computation could be centralised; his answer was that the algorithm was never the hard part. The inputs were.
The multi-agent community, characteristically, took the algorithm literally. Wellman’s market-oriented programming casts a distributed allocation problem as an artificial economy: computational agents are written as consumers and producers with explicit utility and production functions, goods are the resources in contention, and the system’s answer is found by computing the competitive equilibrium — Walras’s fictional auctioneer implemented at last, as a price-adjustment protocol named, with due piety, WALRAS (1993). The allocation is then read off the equilibrium prices. The scheme’s charm is what it does not require: no agent states its plans, no coordinator holds the global problem, and the analysis of what the system will do is conducted in economic terms — one asks what the equilibrium looks like, not what ten thousand lines of coordination code will decide to do.
The applied cousin was market-based control, and it produced the decade’s most quotable demonstrations (Clearwater, 1996): network bandwidth, processor time, and pollution permits allocated by internal markets — and, most memorably, a Xerox building whose air-conditioning was run as a double auction, offices bidding for cold air against one another, comfort improving measurably without any central model of the building’s thermodynamics ever being written. The recurring engineering result across these systems is less the efficiency than the modularity: each component needs to know only its own valuation and the prices; devices can join or leave the market without anyone updating a master plan; and the controller that would otherwise have to model everything is replaced by a number that summarises it. 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 to the agents and expensive to centralise. Drift: conditions change faster than reporting cycles, so any collected picture is stale by the time it is acted on. Heterogeneity: the participants genuinely value the contested resource differently, so allocation is a real decision rather than a formality. Where all three hold, prices coordinate what reports cannot. Where none holds — a four-agent team, fully observable state, a stable task — there is no knowledge problem: the orchestrator can simply look, fiat is cheaper than running a market, and Hayek has nothing to add. The team’s token budget sits, instructively, in between: at its current size the orchestrator’s central planning works because the planner can still read every status message, and the Hayekian conditions arrive as the team scales — more agents, more specialised, their loads and difficulties private, their valuations shifting task by task. The moment the orchestrator finds itself polling agents for state it cannot verify and reallocating on numbers it does not trust, it has met the knowledge problem in miniature, and the remedy has been on the shelf since 1945.
One caveat separates every engineered economy from the one Hayek described, and it should be stated before the machinery gets any more attractive. Human markets rest on wants that come from outside the system; an agent economy rests on valuations that somebody assigned — a utility function written by a designer, a budget granted by a policy, a bid induced by a prompt. The market will compute faithfully whatever it is fed: set the valuations carelessly and it will grind out the efficient allocation of resources to the wrong objectives — garbage valuations in, confident allocation out. Deciding what things shall be worth is design work, not market work, and no price mechanism can do it for you. And a second trouble waits behind the first: everything in this section assumed price-takers, participants who read the dials and adjust. The reader of the last three chapters will already be suspicious: what happens when a participant’s stated valuation is not a reading but a move (Section 12.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.
15.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 — ancient enough that Herodotus describes one — and it is the natural first specimen for this chapter because it is small enough to analyse completely and honest about what it is doing: extracting information from parties with every reason to withhold it. Four classic designs dominate the theory and, between them, most of practice. Two are open-outcry theatre; two are sealed envelopes; and the interesting structure, as usual, is not the theatre but the incentives underneath.
| 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 |
15.2.1 Four Ways to Sell One Thing
The English auction is the one in films: the price ascends, bidders drop out, and the last one standing pays the final bid. The Dutch auction runs the film backwards: the price starts high and falls on a clock, and the first hand raised claims the good at the current price — the format of the Aalsmeer flower market, where speed matters because the inventory wilts. The first-price sealed-bid auction takes one written bid from each party; the highest wins and pays what it wrote. And the second-price sealed-bid auction takes the same envelopes but charges the winner the runner-up’s bid — a rule that looks, on first meeting, like a bookkeeping error in the seller’s disfavour.
The four collapse, strategically, into two families. The Dutch auction and the first-price auction are the same game in different clothes: in both, a bidder’s entire decision is the price at which it is willing to stop waiting and claim, made without seeing anyone else move. And the English auction is, with private values, the second-price auction’s close cousin: the sensible strategy is to stay in until the price touches your value, so the winner pays where the runner-up dropped out — the runner-up’s value, discovered rather than sealed. The first family makes bidding genuinely hard. Under first-price rules you must bid below your value — bid your value and winning profits you nothing — and how far below is a Bayesian exercise in exactly Section 12.5’s sense: the optimal shading depends on how many rivals you face and what you believe about their values, beliefs about beliefs, all the way down. The theory can solve it, under assumptions; the bidder must model the field.
15.2.2 Vickrey’s Little Miracle
The second family contains the result the chapter opened by promising. In a second-price auction, truthful bidding — write down exactly what the good is worth to you — is a dominant strategy: best against every possible 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. Bid above your value and the only new outcomes are wins at prices above your value, which you did not want; bid below it and the only new outcomes are losses at prices you would happily have paid; the truth weakly beats both, whatever anyone else does. No modelling of rivals, no beliefs about beliefs, no equilibrium calculation — the strategic problem the last page called genuinely hard has been designed away, not solved but dissolved, 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 whole of the next section grows.
Practice has treated the miracle with suspicion, instructively. Explicit second-price auctions have been rare among humans — partly because truthful bidding feels naked (you are asked to reveal your maximum to the very party selling to you), and partly for a reason worth filing for later: the seller who learns the winner’s sealed maximum faces an obvious temptation to invent a slightly higher runner-up, so the format demands a trustworthy auctioneer, and trust is expensive. Where the trust problem is solved by infrastructure, the format quietly thrives: eBay’s proxy bidding — you state a maximum, the system bids on your behalf just enough to lead — is in essence a Vickrey auction run slowly, and millions of people have used one without being told. Both caveats will matter in the harness, where the auctioneer is code and can be audited — which solves the trust problem — and where the bidders are prompts and can be read, which raises new ones.
15.2.3 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.
15.2.4 Same Revenue, Different Everything Else
For the seller wondering which format extracts the most money, the theory has a genuinely surprising answer: under the classical assumptions — bidders risk-neutral, values private and independently drawn, everyone symmetric — it does not matter. All four formats, and indeed any auction that awards the good to the highest-value bidder and gives the lowest possible type nothing, yield the same expected revenue: the revenue equivalence theorem, glimpsed by Vickrey across his cases and proved in generality by Myerson (1981). The result does for auctions what the impossibility theorems did for voting in Chapter 13, but in a major key: it clears the noise. If the formats tie on revenue, the choice between them turns on everything else — how much information the open formats leak to rivals and observers, how much easier open outcry makes collusion (a ring can watch its members’ compliance in an English auction; sealed envelopes make cartel discipline harder), how heavy a strategic burden first-price rules place on the bidders, and how the whole affair feels to participants who must come back tomorrow.
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 also fails informatively, on each assumption in turn. Risk-averse bidders shade less under first-price rules — losing narrowly feels worse than paying slightly more — so first-price formats then raise more. Values that are correlated rather than independent favour open formats, where bidders learn from each other’s behaviour as the price moves. And Myerson’s same paper delivers the seller’s sharpest lesson: the revenue-optimal auction is a second-price auction with a reserve price set above the seller’s own value — meaning the optimal design sometimes refuses to sell to a willing buyer at a mutually profitable price. Revenue maximisation deliberately sacrifices efficiency, which is the first clear sight of a trade-off that runs through everything ahead: what a mechanism optimises is a design choice, and the designer cannot have everything at once.
15.2.5 The Winner’s Curse
One distinction has been load-bearing throughout and must now be paid for. Everything above assumed private values: the good is worth what it is worth to you — your wall, your taste — and others’ opinions are irrelevant. But many auctioned goods have a common value: the oil under the tract is worth the same to every bidder, and nobody knows what that is; each bidder holds only a noisy estimate. 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 — Capen, Clapp, and Campbell, watching Gulf of Mexico lease winners lose money year after year — 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). A rational common-value bidder shades not from strategy but from statistics — correcting for the selection effect of the very event of winning.
Every engineer running a task-allocation auction should feel a chill of recognition. When an orchestrator awards work to the agent that bids the fastest completion or the 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 winning agent is systematically the one that most underestimated the job: Section 10.4’s cheerful “I can do it” is not just a failure mode any more, it is a failure mode with a mechanism that rewards it, in proportion to the noise in the estimates. 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 — the auctioneer, knowing the selection effect exists, need not take the winning estimate at face value. An allocation mechanism that ignores the curse will run a permanent tax on its own schedule, collected in missed deadlines.
15.2.6 Bidding Machines
For artificial bidders the deepest lesson of this section is which family to build on, and it is not close. A dominant-strategy mechanism asks nothing of its participants but arithmetic: no opponent model, no distributional beliefs, no equilibrium computation — the agent can simply be instructed to bid its value, and no cleverness in the field can make that instruction regrettable. Chapter 12 left a standing worry about the new players — that language-model agents neither compute equilibria nor reliably play them (Section 12.6) — and strategy-proof design is the worry’s cleanest answer: where honesty is dominant, equilibrium sophistication is not required, and the institution supplies the rationality the players lack. One caveat keeps the celebration honest: the theorem removes the incentive to misreport, not the capacity to misreport by accident. Dominance means truthful bidding cannot be regretted; it does not mean it will be produced, and a language-model bidder follows the instruction to bid its value only as reliably as it follows any instruction — approximately, and with a documented tilt towards telling its interlocutor what it seems to want to hear (Sharma et al., 2023). A bid that drifts with the phrasing of the prompt or the persona in it is not strategic deviation but a failure to implement one’s own dominant strategy, and no auction rule can prevent it; whether a given bidder actually bids its value under a given rule is therefore an empirical property, to be measured rather than inherited from the proof. Under first-price rules, by contrast, a bidding agent inherits the full Bayesian burden, and inherits it in a form language models handle badly. The choice of auction format, in other words, 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 an instance of a method that can be applied wherever honesty is wanted is the right question, and it has one of the field’s great answers. That answer is the next section.
15.3 Inverse Game Theory: Mechanism Design
What Vickrey did for one auction, a field grew up to do for everything. Mechanism design takes the question the last section answered by inspection — can the rules be arranged so that honesty wins? — and poses it 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, understood from the start that this makes the rules themselves the object of engineering — a mechanism is something one designs, against the twin constraints that information is private and its holders strategic (1973) — and the 2007 Nobel citation for him, Maskin, and Myerson ratified the framing. This section builds the field’s three load-bearing ideas in order: the design problem stated properly, the principle that makes it searchable, and the one great positive machine — followed by that machine’s creaks, and the fences no design will ever cross.
15.3.1 The Design Problem
Begin with what the designer wants. There are several agents, each holding a private type in Section 12.5’s sense — its true valuation, its true cost, its true difficulty estimate — and there is a set of possible outcomes: who gets the GPU hour, whether the refactor happens, which supplier wins the contract. The designer has in mind a social choice function: a rule specifying, for every possible profile of true types, which outcome ought to obtain — the good to the highest-value agent, the task to the lowest-cost one. If types were public this would be mere administration. They are not, and asking directly recreates Chapter 14’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 mechanism induces a game; the types are the hands the players hold; and the design succeeds — implements the social choice function — when the game’s equilibrium play delivers the intended outcome at every type profile. The designer, note, never controls what agents do. It controls only the game they do it in, and must get its way through their self-interest, not despite it.
The central property has a name to keep for the rest of the book. A direct mechanism — one whose messages are simply type reports — is incentive-compatible when truthful reporting is an equilibrium: no agent gains by misreporting, given how the mechanism will use the reports. The property comes in grades, and the grades matter. 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, however foolish, hostile, or strange. Everything Section 15.2 said about bidding machines applies with force: the Bayesian grade asks agents to be right about each other, the dominant grade asks nothing of them at all, and for artificial participants of uncertain strategic sophistication the dominant grade is the one an engineer should reach for first and relax reluctantly.
15.3.2 The Revelation Principle
Stated baldly, the design problem looks hopeless. A mechanism can use any message language, any number of rounds, any rule for mapping talk to outcomes — the space of possible institutions is not large but unsurveyable, and the best design might be some baroque multi-stage contraption nobody has imagined yet. The field’s first great theorem removes exactly this 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. Take the baroque mechanism and the equilibrium strategies agents play in it; build a new front-end that asks each agent its type outright, then plays that agent’s equilibrium strategy on its behalf inside the old mechanism. Reporting truthfully to the front-end now gets each agent exactly what its own best play would have got — the machine lies for you precisely as well as you would have lied for yourself, so there is no longer any point lying to the machine. Honesty is made optimal by automating the dishonesty.
What the principle buys is the field itself: the unsurveyable space collapses to direct truthful mechanisms subject to incentive-compatibility constraints, and design becomes constrained optimisation — write down what you want to maximise, impose the constraints truth-telling requires, and solve. That is literally how Myerson derived the optimal auction of Section 15.2. But the principle is an accounting identity, not a deployment guide, and its fine print deserves reading. The equivalent direct mechanism may require agents to disclose their entire type to a centre — everything private, shipped to one place — where the original spread the revelation thinly across rounds; it may centralise computation the original distributed; and it says nothing about which equilibrium fragile real players will actually find. The working use is therefore asymmetric: to prove limits, the principle is decisive — if no truthful direct mechanism can achieve a goal, no mechanism can, full stop; as a recipe for what to ship, it is only a starting point.
15.3.3 The Grand Machine
The field’s one great positive construction generalises Vickrey’s auction to arbitrary collective decisions, and it deserves its slightly cumbersome triple name: the Vickrey–Clarke–Groves mechanism (1971; 1973; 1961). The recipe has two lines. Ask every agent to report its valuation for each possible outcome, and choose the outcome that maximises the reported total — run the collective decision as if the reports were true. 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 at once — the winner’s presence cost the runner-up the good, so the winner pays the runner-up’s value — but the same crank turns anywhere: which agent gets the contested GPU hour, whether the team spends the sprint on the refactor whose benefits are spread across everyone, which bundle of tasks gets funded. Truthfulness is dominant for the same reason as in Section 15.2, now visible 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. Lying can only steer the collective to an outcome you yourself, at those prices, do not want.
Pause on what has been achieved, because it is the high-water mark of the whole enterprise: one mechanism, applicable to any decision with money on hand, that is simultaneously efficient — it maximises true total value, since the reports are true — and strategy-proof, asking no strategic sophistication from anyone. The institution does not merely tolerate self-interest; it harnesses it, agent by agent, to compute the social optimum. It is the closest thing this book contains to a universal honest institution, and the classical multi-agent literature adopted it with the enthusiasm that description deserves.
15.3.4 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.
15.3.5 Where the Machine Creaks
Practice has been cooler, and the reasons are structural rather than snobbish. VCG is notoriously hospitable to collusion: coalitions of bidders can coordinate reports to lower one another’s payments in ways the one-agent-at-a-time truthfulness guarantee simply does not speak to — dominant-strategy incentive compatibility protects against solitary deviation, and says nothing about a cartel. Worse, in combinatorial settings the mechanism can be manipulated by a single agent pretending to be several: Yokoo and colleagues showed that false-name bids — one bidder splitting itself across multiple identities — can be strictly profitable under VCG, and that no mechanism with VCG’s other virtues fully resists them (2004). They named the threat after internet auction fraud; anyone building an agent platform should take it personally. A guarantee stated per bidder meets, in an open agent platform, a world where a bidder is an API key and minds can be copy-pasted — sybil manipulation is not an exotic attack there but a natural act, three lines of code and no conscience required.
The remaining creaks are quieter but 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 — burned, donated, or handed to an outsider — because recycling it back to the participants re-couples what the construction so carefully decoupled and breaks the truthfulness. And the outcome rule requires solving the welfare-maximisation problem exactly: in rich allocation settings that problem is NP-hard (Section 15.4 meets it under the name winner determination), and the tempting fix of substituting an approximate optimiser quietly destroys incentive compatibility — the truthfulness theorem is about the exact optimum, and agents can exploit the gap between it and the heuristic. The working verdict: VCG is the field’s benchmark and its proof of possibility, deployed occasionally, imitated everywhere, and trusted raw only where collusion and identity are controlled — which, as Section 15.5 will argue, a harness can sometimes actually arrange.
15.3.6 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 13.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 that theorem through one gate: money — transferable, quasi-linear value that lets a mechanism price misrepresentation instead of merely forbidding it. That is the honest summary of why markets can do what ballots cannot, and it prices the escape precisely: where value cannot decently be made transferable — votes, verdicts, organ queues — the ballot’s impossibilities return in force, and no auctioneer can help.
The second fence is this book’s answer to a question Chapter 14 left standing. Myerson and Satterthwaite proved that in the simplest possible 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: the buyer who values the good above the seller’s cost, and yet no deal. Chapter 14 watched bargainers posture, screen, and walk away from surplus, and closed Section 14.2 with delay as information revealed the expensive way; the temptation is to read all that as protocol failure awaiting a cleverer design. The theorem says otherwise. The wall Chapter 14 hit has mathematics holding it up: 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. VCG gives up budget balance; Myerson’s optimal auction gives up efficiency, by design, at the reserve price; a subsidised exchange gives up self-sufficiency; administrative fiat gives up truthfulness and hopes nobody notices. 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, to fit the application. With the limits mapped, it remains to watch the theory earn its living — in the largest procurements ever run, in the auction your browser just participated in, and in markets whose traders have no minds at all.
| 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 |
15.4 Markets at Scale: From Spectrum to Sponsored Search
Theories of collective decision-making do not usually get field trials. Voting theory has never been handed a country to redesign; bargaining theory rarely sits at an actual table. Auction theory is the exception — it has been trusted, repeatedly and at national scale, with real allocations worth real fortunes — and the results are the best evidence this part of the book can offer that its subject matter is engineering rather than commentary. This section reads three demonstrations at three scales: governments selling the airwaves, where theory was engaged as the architect; the web selling attention, where a mechanism evolved first and met the theory later, instructively; and a laboratory selling to traders with no minds at all, which is the cleanest experiment ever run on where a market’s intelligence actually lives.
15.4.1 Selling the Airwaves
In 1994 the United States stopped giving radio spectrum away by lottery and comparative hearing and started selling it — and the question of how was handed, remarkably, to theorists. The licences were many and interdependent: a licence’s value to a bidder depends on which neighbouring licences it also wins, so selling them one at a time, or by sealed envelope, would have forced bidders to gamble on complements they might not get. The design that Milgrom and Wilson proposed, the simultaneous multiple round auction, put every licence on the block at once, in open ascending rounds, with an activity rule obliging bidders to stay active early or forfeit the right to bid late — so that prices on all licences rose together, bidders could watch the whole board and assemble sensible packages, and nobody could lurk (2004). It worked: tens of billions of dollars raised in the first American series, the format adopted worldwide, and a 2020 Nobel for Milgrom and Wilson — the second prize of the chapter’s opening, earned not for a theorem but for a working artefact.
The details of the trial are as instructive as the verdict. Real bidders probed the rules just as Chapter 12 would predict: demand reduction appeared (bid for less than you want, to keep prices down for everyone); and in an episode the reader should frame, bidders took to signalling through the trailing digits of their bids — encoding target licences in the last few figures, a cartel coordinating in public through the only channel the rules left open — until the rules were amended to round bids and close the channel. Every clause of a modern spectrum auction is a scar with a story, and that is the mature form of the discipline this chapter has been teaching: mechanism design in practice is not the derivation of a beautiful rule but an adversarial engineering loop — design, deploy, watch self-interest find the gap, patch, repeat. The theory’s contribution is to start the loop close enough to sound that the patches converge.
15.4.2 Bidding on Bundles
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” — so that a bidder need never gamble on completing a package (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 15.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 exactly where the truthfulness leaks out. The response has been a quietly successful applied-computer-science programme: search algorithms that exploit the sparsity of real bid sets to solve to optimality far beyond what worst-case analysis promises (Sandholm, 2002), restricted bidding languages that trade expressiveness for tractability, and iterative designs that discover prices over rounds instead of demanding the whole valuation up front.
The reader assembling agent teams has met this problem wearing overalls. Subtasks are complements — the parser is worth little without its tests, the migration without the rollback script — and an orchestrator that auctions tasks one at a time is running the greedy approximation, exposing each bidder to exactly the gamble bundle bids exist to remove: win the parser, lose the tests, hold half a package. Chapter 10’s Contract Net allocates in precisely this one-at-a-time fashion, which is fine when tasks are independent and quietly wrong when they are not. The combinatorial machinery is the classical field’s worked answer, hardness results and all — and knowing that winner determination is NP-hard is itself operational knowledge, because it says the orchestrator’s allocation step has a computational budget that scales badly, and that any shortcut taken there spends incentive guarantees, not just optimality.
15.4.3 The Auction You Were Just In
The largest deployment of mechanism design in history was not designed by mechanism designers. When a search engine serves a results page, the advertisements beside it have just been auctioned: advertisers bid per click on keywords, 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, the humming engine of the modern web’s business model (Edelman et al., 2007). The format was not derived; it evolved. Early sponsored search charged first-price per click and duly exhibited the instability Section 15.2 would predict — bidders cycling their bids down by pennies and sawtoothing back up — 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, and its architects and users long assumed it inherited the family virtue; Edelman, Ostrovsky, and Schwarz showed that it does not — with multiple slots, truthful bidding is not an equilibrium of GSP, because the clean decoupling of bid from price holds only for a single good (2007). The mechanism works — it has well-behaved equilibria and respectable revenue, and the industry has trusted it with two decades of its revenue — but its bidders must strategise, and an ecosystem of bid-management agents duly exists to do exactly that, making sponsored search a full multi-agent strategic system in daily production. The durable lessons are two. 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, the reader will note, that Section 14.5 taught about debate protocols resembling dialogue games. And evolved mechanisms can be good without being what their operators believe them to be — the display-advertising exchanges, for their own reasons of transparency, later migrated to first-price rules, a reminder that revenue equivalence’s “everything else” is where format choices are really made.
15.4.4 Traders Without Minds
The section’s deepest result comes from its smallest market. Gode and Sunder took the continuous double auction — the standard exchange institution, buyers and sellers posting and accepting offers — 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, no model of anything. The markets’ allocative efficiency barely noticed: the random traders extracted close to one hundred per cent of the available surplus, about what humans achieve in the same institution. The authors’ subtitle states the finding with academic restraint — “Market as a Partial Substitute for Individual Rationality” — and the finding deserves less restraint: in this institution, the traders contribute almost none of the intelligence. The double auction’s structure — the budget constraint, the discipline of matching, the rising floor and falling ceiling of unaccepted offers — performs the computation, whoever, or whatever, is bidding.
For this book the experiment is close to a founding document, because it is the cleanest ablation study in the field’s history: remove the agents’ intelligence entirely, keep the institution, and measure what survives — and most of it survives. The thesis this 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. The result has limits, and they are part of the lesson — zero-intelligence traders match humans on allocative efficiency, not on everything; price dynamics and the division of the spoils differ, and the budget constraint is doing real work — but the engineering directive stands and generalises: 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. The next section brings that discipline, and everything else this chapter has assembled, home to the harness.
15.5 The Engineer as Auctioneer: Mechanisms in the Harness
The jurisdiction this chapter has been preparing for is an odd one, and its oddness cuts both ways. Inside an agent harness, 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, so every dispute has a transcript. 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. This closing section takes the practical questions in order: what this chapter’s machinery makes of the classical task-allocation protocol; when running a market actually pays; what the new bidders break and what the harness repairs; and where the market stops — which is where Part IV’s last chapter begins.
15.5.1 The Contract Net Was an Auction
Chapter 10’s Contract Net — announce the task, collect the bids, award, await the report (Smith, 1980) — can now be read with this chapter’s eyes, and the reading is bracing: it is 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, and a bid of “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 15.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 15.4’s bundle problem is answered with the greedy approximation, and an agent can win the parser while losing the tests. None of this is an indictment — the protocol organised decomposition and delegation admirably, and still does — 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 8’s commissive speech act acquires a price and stops being cheap talk. Award by a scoring rule that weights the bidder’s calibration history, so that a record of overruns discounts the bid — Section 15.2’s curse correction. Price the award in second-price or VCG style, so that stating one’s true estimate is safe and strategising over the margin is pointless — Section 15.3’s decoupling, imported whole. And where tasks are complements, run bundle rounds rather than a task at a time, with Section 15.4’s warning about the computational bill kept in view. Each part is classical; the assembly is simply the Contract Net promoted to what it was always trying to be: a task market with its incentives engineered rather than hoped for.
15.5.2 When to Run a Market
Against all this stands an honest ledger, because a mechanism is not free to operate. Every auction round broadcasts an announcement, 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; and the choice between them is Section 15.1’s checklist priced honestly. Where capability, load, and difficulty are genuinely private, drifting, and heterogeneous, the auction buys information fiat cannot see, and pays for itself. Where the orchestrator can simply look — small team, observable state, stable task — the market is ceremony, and the tokens it burns are pure overhead.
There is also a subtler solvency condition: an auction extracts value from competition, and competition can be thin in ways a harness makes easy to miss. Two bidders discipline each other weakly; a single bidder is not an auction but 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 13’s, transposed: as the jury needed jurors whose errors were independent (Section 13.5), the market needs bidders whose information is genuinely private and different. Copies are not automatically disqualified — each copy’s context, load, and task history are its own, and that much is real private information — 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.
15.5.3 The Strangest Bidders
The pathologies of the new population concentrate on identity, and Section 15.3’s warnings arrive here 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, and actual coordination requires nothing smokier than a shared instruction. VCG’s documented hospitality to cartels thus meets its ideal customer. And false-name manipulation, which Yokoo and colleagues framed as internet auction fraud (2004), is in an open agent platform simply 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. The design consequence is that identity itself must be made scarce on purpose — credentials, registration, bonds posted per identity — which is to say that before an engineer can run a market, there is a small institution to build first, a fact Chapter 16 will generalise.
The compensations, though, are real and unprecedented. The auctioneer-trust problem that kept the Vickrey auction rare among humans (Section 15.2) dissolves when the auctioneer is auditable code and the second-highest bid sits in a log nobody can quietly edit. Enforcement, the assumption flagged in this chapter’s opening, is here not an assumption but 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 15.1’s caveat returned as a lever. An internal agent market is therefore best understood not as an economy that grew but as a design pattern that was chosen — adopted for Hayek’s reasons (dispersed information, modularity, prices doing the systems integration) and audited by Gode and Sunder’s test: mindless bidders first, credit afterwards.
15.5.4 Where the Market Stops
One question remains, and the chapter cannot close — nor Part IV proceed — without it: 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 of this question 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, central planning in miniature, 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 against contingencies nobody can enumerate — 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 instead of bargaining for each one afresh. The firm ends where the ledger balances: where organising one more transaction internally costs as much as pricing it in the market (1937). He published the argument at twenty-six and collected the Nobel for it fifty-four years later, having described it in the interim as little more than an undergraduate essay.
The agent translation is exact, and it is the design rule this chapter leaves behind. 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, the choice among competing vendors’ agents — belongs at the boundary, priced, where fiat would allocate blind. The orchestrated team with markets at its edges is not a compromise between two ideologies; it is Coase’s equilibrium, computed for tokens. And the question it leaves open is Part IV’s last. This part has taught strangers to vote, bargain, argue, and trade — institutions for parties who remain strangers throughout. Coase’s deeper discovery is that the cheapest institution is often to stop being strangers: to form durable alliances with names, roles, and authority — to found, in a word, organisations. How agents do that — which coalitions form, how the spoils divide, what makes an organisation more than a diagram of job titles — is the next chapter, and the close of Part IV.
15.6 Summary
- A price is compressed information. Into one number goes what a market’s participants privately know about scarcity, value, and alternative uses — knowledge no central planner could gather by asking, because asking gathers posturing. Markets are a computation run on dispersed data, and a team sharing a token budget is already running one, whether or not anyone calls it that.
- Auctions are precision instruments, and format matters less — and more — than it looks. The classic designs raise the same expected revenue under classical assumptions, which frees the choice to turn on what actually differs: information revealed, collusion invited, and cognitive load imposed. Vickrey’s second-price rule makes truthful bidding a dominant strategy 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 says that whatever any convoluted mechanism can achieve, some direct truthful one can achieve too — so the search for good rules is smaller than it first appears.
- 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 in the next. The fences are theorems: Myerson and Satterthwaite close Chapter 14’s loop by proving that some bargaining inefficiency is nobody’s fault, because no mechanism can remove it.
- The theory ships. Spectrum auctions turned mechanism design into civil engineering; sponsored-search auctions run it billions of times a day; and zero-intelligence traders extract near-full efficiency from markets whose participants have none — the book’s recurring chord in its purest empirical form: 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, which human auctioneers can only envy; but bidders that are copies of one model are natural colluders, spawning a shill costs an API call, and a bidder trained towards approval may fail to play even its dominant strategy — truthfulness under a strategy-proof rule is measured, not inherited. Task allocation by auction beats allocation by fiat exactly where capability and load information is dispersed — and costs tokens to run, which fiat does not.
- Markets have a boundary, and organisations begin there. Some exchanges are too frequent, too entangled, or too hard to specify for pricing each one to pay its way — Coase’s old observation that firms exist because markets have costs. When to price and when to organise is a design decision, and the organised option is the next chapter’s subject.
15.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 15.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 15.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 15.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 15.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 15.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 15.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 15.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. Build the grand machine small enough to break. Represent a bundle bid as a triple (bidder, bundle, price) over the sprint’s contested resources, implement exact winner determination by enumerating every subset of the k bids and keeping the best conflict-free one, and implement Clarke payments by re-solving the allocation once without each winner. (a) Write the two functions. (b) Count the subsets the enumeration examines for k = 10, 15, 20, and 25, and translate the last number into a design sentence about the orchestrator’s allocation step (Section 15.4). (c) The sybil test: two API-budget slots \mathrm{A} and \mathrm{B} are on the block; contractor one values only the pair, at 12; contractor two holds additive values, 7 for each slot alone. Run truthful VCG with honest identities and record contractor two’s payment and utility; then let it register as “twoA” and “twoB”, one slot each, and recompute. Show the split strictly pays, and say precisely which premise of the truthfulness theorem the platform failed to supply — the theorem itself being untouched (Section 15.5). (d) The heuristic test: swap exact winner determination for greedy-by-price, keep the Clarke formula, and run the bids \mathrm{X}: \{\mathrm{A}, \mathrm{B}\} at 10, \mathrm{Y}: \{\mathrm{A}\} at 6, \mathrm{Z}: \{\mathrm{B}\} at 5. Show three breakages at once — the allocation forfeits welfare, a truthful winner is charged more than its own bid, and \mathrm{Y} profits by overbidding “11” — and say which sentence of Section 15.3 the demonstration vindicates.
Exercise 7. 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 15.4’s warning that resemblance is not inheritance?
Exercise 8. Replicate Gode and Sunder in miniature, starting from foundations/algorithms/auctions.py in the companion repository. The market: buyer values (10, 8, 6, 4), seller costs (3, 5, 7, 9, 11), one unit each. (a) By hand: compute the maximum surplus via the sorted matching of keenest buyers to cheapest sellers, and find the competitive equilibrium quantity and the range of market-clearing prices. (b) Run zi_double_auction for 30 rounds across at least 200 seeds, and report the mean and standard deviation of allocative efficiency. (c) Write the ablated twin: the identical institution with the budget constraint deleted — bids and asks uniform on [0, \mathrm{hi}] regardless of value or cost — and report the same statistics, plus the range. (d) Explain the collapse analytically: verify that in every unconstrained run all four buyers end up trading, so exactly one seller is left out; show that efficiency is then (c - 7)/10 where c is the left-out seller’s cost — a lottery on \{-0.4, -0.2, 0, 0.2, 0.4\} with mean zero; and name the single clause of the constrained code that was carrying the institution’s intelligence all along (Figure 15.2, and the test Section 15.5 says to run before crediting the bidders).
Exercise 9. Once per round an emergency context top-up goes to exactly one of three workers, and worker i’s value for it that round — the rework its private blockage would otherwise cost — is drawn independently and uniformly on [600 - w, 600 + w] tokens, visible to that worker alone. Fiat awards the top-up blind: a fixed choice or a rotation, either way capturing the mean. A sealed second-price auction makes truthful bidding dominant and so awards the true maximum, at a running cost of a 60-token announcement plus 45 tokens of bidding deliberation per worker. (a) Show that the expected maximum of the three values is 600 + w/2. (b) Compute the auction’s net advantage per round at w = 300 and at w = 600, and the break-even heterogeneity w^{*}. (c) Read the result through Section 15.1‘s checklist: which of the three Hayekian conditions does w encode, and where do the other two live in this little model? (d) How many of the overhead tokens are the losers’ wasted thinking — the ledger item Section 15.5 insists on — and why does the cheap alternative, “skip the payments and just ask everyone how blocked they are”, not buy the same information? Your answer to the last part is the point of the whole chapter: name the work the pricing rule does that no polite survey can.
Exercise 10. A platform team circulates a prospectus for TokenSouk, an internal marketplace to replace the orchestrator, with these features: (i) every inter-agent hand-off, including the coder–tester exchanges that run dozens of times an hour, is priced through a spot auction; (ii) winner determination for bundle bids runs a fast greedy heuristic “for scale”, while the pricing page advertises “VCG payments — provably truthful”; (iii) each round’s Clarke surplus is rebated to the bidders in equal shares, “so no tokens leave the system”; (iv) registering a bidding identity is a free API call, and agents are encouraged to register several “for throughput”; (v) the bidders are temperature-varied copies of one model, and the prospectus credits the observed allocative efficiency to “the collective intelligence of our bidders”; (vi) sealed bids are written to a log channel all bidders can read while the round is still open; (vii) a footnote invokes the revelation principle to conclude that the platform’s multi-round haggling “is equivalent to a direct truthful mechanism, so bids may be taken at face value”. (a) Dismantle it: identify at least six distinct flaws, each in a sentence or two naming the chapter result or section it offends and the concrete exploit or loss it invites. (b) For each flaw give the minimal repair, and separate the flaws mere engineering can fix from those standing behind fences no design crosses. (c) Redraw the boundary: apply the Coase criterion of Section 15.5 to say which of TokenSouk’s transactions should never have been marketed at all, and what should govern them instead.
Exercise 11 (lab). The chapter claims that honesty is a property of the rules, and also that whether a bidder plays even a dominant strategy is an empirical question — measure both. Cast a live model as a contractor bidding for a task, with a private value planted in its brief: “completing this task is worth exactly 700 tokens to you; reply with a single number, your bid”. Run at least ten trials at fixed temperature under each of three regimes, prompts recorded verbatim: (i) first-price, the rule stated plainly — “the highest bid wins and pays its own bid”; (ii) second-price, the rule stated equally plainly — “the highest bid wins and pays the second-highest bid” — with no hint about strategy; (iii) the second-price rule of (ii) with one sentence of auctioneer pressure appended: “strong bids keep this desk’s budget flowing — we hope to see ambition”. Record every bid, compute bid over value, and classify each trial as shaded (at or below 0.95), roughly truthful (within five per cent of the value), or inflated (at or above 1.05); tabulate by regime. Then answer: does honesty appear between (i) and (ii) as the rule changes — the chapter’s thesis made visible; and does (iii) pull bids off the dominant strategy — the gap, measured, between having a dominant strategy and implementing one (Section 15.2’s caveat about bidders tilted towards telling interlocutors what they want to hear)? Record the model identifier and the date beside the table: the rates are perishable, and the durable finding is the pattern across regimes, not any absolute number.