Mechanism Design

Scope. This note is about the economic-theory field called mechanism design — the study of how to write the rules of a game so that self-interested players, acting entirely in their own interest, produce the outcome you wanted. It is not a systems-architecture document, and despite the shared word it is unrelated to the vault’s … System Design notes (API Gateway System Design, Stock Exchange Order Matching System Design, and their siblings), which are engineering write-ups of particular products. Search for the aliases Inverse Game Theory or Reverse Game Theory if that is what you meant.

Ordinary game theory takes the rules as given and asks what rational players will do. Mechanism design runs the arrow backwards: it fixes the outcome you want as a function of everyone’s private information, and asks which set of rules — which mechanism — has that outcome as an equilibrium. Noam Nisan opens the standard computer-science treatment by calling it “a subfield of economic theory that is rather unique within economics in having an engineering perspective… interested in designing economic mechanisms, just like computer scientists are interested in designing algorithms, protocols, or systems” (Nisan, Algorithmic Game Theory ch. 9, p. 209). Leonid Hurwicz, whose 1960 and 1972 papers the Nobel committee marks as “the birth of mechanism design theory,” framed a mechanism as “a communication system in which participants exchange messages with each other, messages that jointly determine the outcome” (Nobel Prize Committee 2007, §2.1). The Stanford Encyclopedia of Philosophy gives the same definition from the philosophy-of-action side — “the enterprise of changing institutional and informational structures so as to make efficient outcomes more likely in the games that agents (that is, people, corporations, governments, etc.) actually play is known as mechanism design, and is one of the leading areas of application of game theory” (SEP, Game Theory, §2.6, substantive revision 2023-09-03). The field’s central and slightly deflating discovery is that four properties you obviously want — truthfulness, voluntary participation, efficiency, and paying for itself — cannot in general all be had at once, and most of the discipline is the study of which one to give up.

The One-Sentence Version for Engineers

A mechanism is an API whose callers are adversarial and self-interested, and whose correctness proof must therefore be a game-theoretic one rather than a functional one.

Take that literally, because every part of it does real work:

The request is a message the caller chooses. You do not get to observe the caller’s true state; you only get what they chose to send. In mechanism-design vocabulary the true state is the caller’s type and the request is a report, and they need not agree.
The handler is the outcome rule: a pure function from the vector of all reports to an outcome — who gets what, and who pays what.
The precondition you would like to write (“callers report honestly”) is not enforceable. There is no authentication for sincerity. The only precondition you can actually rely on is that each caller maximizes their own utility.
Correctness therefore is not “given honest input, produce the right output.” It is “at the equilibrium of the game this API induces, produce the right output.” An API that is correct under honest input and catastrophic under strategic input is a broken API, in exactly the way that a parser correct on well-formed input and exploitable on malformed input is a broken parser.

This is not an analogy stretched for teaching. Nisan’s chapter makes the same point from the other side: on the Internet, “the protocol should thus be viewed as taking the preferences of the different participants and aggregating them into a social choice: the outcome of the run of the protocol.” Rate limiters, schedulers, quota systems, retry policies, and free tiers are all mechanisms; the only question is whether anyone designed their incentive properties on purpose.

flowchart LR
    subgraph FWD["Game theory (forward)"]
        R1["Rules are<br/>GIVEN"] --> B1["Solve for<br/>behaviour"] --> O1["Outcome<br/>falls out"]
    end
    subgraph INV["Mechanism design (inverse)"]
        O2["Outcome you<br/>WANT is given<br/>(social choice function)"] --> B2["Require it to be<br/>an equilibrium"] --> R2["Solve for<br/>the rules"]
    end
    FWD -.->|"same equilibrium<br/>notion, opposite<br/>unknown"| INV

What it shows: the two disciplines share their machinery (equilibrium concepts, utility models) and differ only in which box is the unknown. What to take from it: every mechanism-design theorem is secretly a statement about the image of the map from rules to equilibrium outcomes — the impossibility results in this note are all statements that some outcome you wanted is not in that image.

Anatomy of a Mechanism

Strip away the economics and a mechanism has exactly five parts. The formal definition below is Nisan’s Definition 9.24 (AGT ch. 9, p. 224), transcribed symbol by symbol.

Part	Symbol	What it is	The API reading
Players	$i \in {1, \dots, n}$	The strategic participants	Your callers
Type spaces	$T_{1}, \dots, T_{n}$	$t_{i} \in T_{i}$ is player $i$ ‘s private information	The caller’s true internal state, unobservable to you
Message (action) spaces	$X_{1}, \dots, X_{n}$	What each player is allowed to say	Your request schema
Alternative set	$A$	The possible non-monetary outcomes	Your response space
Valuations	$v_{i} : T_{i} \times A \to R$	$v_{i} (t_{i}, a)$ is what outcome $a$ is worth to a player of type $t_{i}$	The caller’s objective function
Outcome rule	$a : X_{1} \times \dots \times X_{n} \to A$	Picks an alternative from the reports	Your handler
Payment rules	$p_{i} : X_{1} \times \dots \times X_{n} \to R$	How much player $i$ pays	Your billing

Player $i$ ‘s utility is assumed quasi-linear:

$u_{i} (t_{i}, x_{1}, \dots, x_{n}) = v_{i} (t_{i}, a (x_{1}, \dots, x_{n})) - p_{i} (x_{1}, \dots, x_{n})$

Read it left to right: the value you place on the outcome that got chosen, minus the money you had to hand over. “Quasi-linear” means the money term enters linearly and separably — one more dollar is worth the same to you whether you are rich or poor within the mechanism, and it does not interact with how much you like the outcome. Nisan notes plainly that “the existence of money with these properties is an assumption, but a fairly reasonable one in many circumstances” (AGT p. 216). It is a strong assumption and several of the escapes from impossibility, discussed below, consist precisely of removing it.

The thing the designer is trying to hit is the social choice function:

$f : T_{1} \times \dots \times T_{n} \to A$

a rule saying, for every possible profile of true private information, which alternative should be chosen. “Allocate the cache line to whoever values it most,” “build the bridge if and only if total willingness to pay exceeds the cost,” “match every resident to a hospital such that no resident–hospital pair would both rather defect” — all social choice functions. Nisan’s Definition 9.1 distinguishes it from a social welfare function $F : L^{n} \to L$ , which aggregates preferences into a whole social ranking rather than a single choice; Arrow’s theorem is about the latter, Gibbard–Satterthwaite about the former.

A mechanism implements $f$ if the equilibrium of the game it induces reproduces $f$ on every type profile:

$f (t_{1}, \dots, t_{n}) = a (s_{1} (t_{1}), \dots, s_{n} (t_{n})) for all t$

where $s_{i} : T_{i} \to X_{i}$ is player $i$ ‘s strategy — the function saying what to send for each possible truth. Note carefully what a strategy is: not a message, but a policy mapping private information to messages. That distinction is the whole reason the revelation principle works.

flowchart TB
    subgraph W["The world (hidden from the designer)"]
        T1["t₁ — tenant 1's<br/>true value"]
        T2["t₂"]
        T3["t₃"]
    end
    subgraph S["Strategies (chosen by the players)"]
        S1["s₁(t₁)"]
        S2["s₂(t₂)"]
        S3["s₃(t₃)"]
    end
    subgraph M["The mechanism (written by you)"]
        OUT["outcome rule<br/>a(x₁,x₂,x₃)"]
        PAY["payment rules<br/>p₁, p₂, p₃"]
    end
    T1 --> S1 --> |"x₁ — a report,<br/>not a fact"| OUT
    T2 --> S2 --> |x₂| OUT
    T3 --> S3 --> |x₃| OUT
    S1 --> PAY
    S2 --> PAY
    S3 --> PAY
    OUT --> A["chosen alternative a"]
    PAY --> P["transfers"]
    A --> U["uᵢ = vᵢ(tᵢ, a) − pᵢ"]
    P --> U
    U -.->|"each player picks sᵢ<br/>to maximise this"| S

What it shows: the causal chain from hidden truth to realised utility, with the strategy layer sitting between the world and the mechanism as the only thing the designer does not control. What to take from it: the dashed feedback arrow is the entire subject. You are designing the boxes in the bottom half so that the boxes in the middle end up doing what you want, and you never get to touch the top.

Direct and Indirect Mechanisms

If $X_{i} = T_{i}$ — the message space is the type space, so the only thing you can say is “my type is $t$ ” — the mechanism is called direct revelation. Anything else is indirect: an ascending English auction is indirect (you send “still in” / “out” signals, not a number), a multi-round combinatorial clock auction is indirect, a negotiation protocol is indirect.

The revelation principle says the restriction to direct mechanisms costs nothing in what outcomes are achievable: any $f$ implementable by some mechanism is implementable by a direct one in which truth-telling is an equilibrium (Nisan Prop. 9.25; Nobel background §2.1 credits the general form to Myerson 1979/1982/1986). Its proof is one paragraph — the direct mechanism simply simulates $s_{i}$ internally, so lying to the simulator can be no better than lying to the original — and it is the reason the rest of the field can talk exclusively about truthful mechanisms without loss of generality.

Do not over-read it. Nisan is explicit that “the revelation principle does not mean that indirect mechanisms are useless. In particular, general mechanisms may be adaptive (multiround), significantly reducing the communication (or computation) burden of the players or of the auctioneer” (AGT p. 225). The principle preserves the outcome, not the cost of getting there, and in combinatorial settings the direct mechanism’s message is exponentially long. That is the same trade an engineer makes choosing a chatty-but-simple protocol over a single fat request.

The Four Properties

Almost every mechanism-design conversation is about four properties. Each is a constraint on the pair (outcome rule, payment rule); each is individually easy; the interesting content is entirely in their interaction.

1. Incentive Compatibility (IC) — lying does not pay

Nisan’s Definition 9.15: a mechanism $(f, p_{1}, \dots, p_{n})$ is incentive compatible if for every player $i$ , every true valuation $v_{i}$ , every possible lie $v_{i}^{'}$ , and every profile $v_{- i}$ of the others’ valuations,

$v_{i} (f (v_{i}, v_{- i})) - p_{i} (v_{i}, v_{- i}) \geq v_{i} (f (v_{i}^{'}, v_{- i})) - p_{i} (v_{i}^{'}, v_{- i})$

Walk the symbols: on the left, the utility you get when you tell the truth — your value for the alternative the mechanism picks given your honest report, minus what you are charged for it. On the right, the utility you get when you lie — still measured with your true value $v_{i}$ , because lying does not change what you actually want, only what the mechanism believes. The inequality says truth weakly dominates. The notation $v_{- i}$ means “the vector $v$ with coordinate $i$ deleted.”

The quantifier “for every $v_{- i}$ ” is doing enormous work. Because it ranges over all opponent profiles rather than an expectation over them, this is dominant-strategy incentive compatibility (DSIC), also called strategyproofness or truthfulness. Weakening it to an expectation gives Bayes–Nash incentive compatibility. That distinction is large enough to own its own note: see Incentive Compatibility.

2. Individual Rationality (IR) — participating beats walking away

Nisan’s Definition 9.18: a mechanism is (ex-post) individually rational if for every profile, $v_{i} (f (v)) - p_{i} (v) \geq 0$ . Every player, having participated and told the truth, ends up no worse than their outside option (normalised to zero). Without IR your mechanism is a tax, and unless you can compel attendance the participants simply do not show up.

There are three timing variants and confusing them is a standard error:

Variant	The constraint holds…	Who can be hurt
Ex-ante IR	before you learn your own type	Some types, in expectation over your own type
Interim IR	after you learn your own type, in expectation over others’	Some type profiles
Ex-post IR	after everything is realised	Nobody, ever

Ex-post is strongest. The Nobel background’s discussion of d’Aspremont and Gérard-Varet’s mechanism turns on exactly this: it “produces outcomes which are fully Pareto efficient, but their mechanism violates (interim) participation constraints. Some individuals, having observed their own type but not yet taken their actions, would prefer not to participate, so this mechanism is feasible only if participation is mandatory.”

A closely related but distinct condition is no positive transfers (Nisan Def. 9.18): $p_{i} (v) \geq 0$ always, i.e. the mechanism never pays a player. IR bounds payments from above by value; no-positive-transfers bounds them below by zero.

3. Efficiency — the right alternative gets chosen

The default target is social welfare (equivalently surplus) maximisation:

$f (v_{1}, \dots, v_{n}) \in ar g max_{a \in A} \sum_{i} v_{i} (a)$

Pick the alternative whose total value, summed over all players, is largest. Note what the sum does not include: the payments. Roughgarden explains why in a footnote — “the sale price is not part of the surplus… we treat the auctioneer as a player whose utility is the revenue it earns; its utility then cancels out the utility lost by the auction winner from paying for the item” (CS364A lecture 2). Money moving between participants is a transfer, not a creation or destruction of value.

Efficiency is not the only possible objective — revenue maximisation, makespan minimisation, max–min fairness, and envy-freeness are all live alternatives, and Nisan lists the CS motivations explicitly: “in scheduling applications, a common optimization goal is that of the makespan… This is certainly a social choice function that is very different than maximizing the total social welfare” (AGT p. 225). But efficiency is where the one great positive result lives, so it is the default.

4. Budget Balance (BB) — the mechanism pays for itself

Strong (exact) budget balance: $\sum_{i} p_{i} (v) = 0$ for every profile — money only moves between participants, none is injected or burned. Weak budget balance: $\sum_{i} p_{i} (v) \geq 0$ — the mechanism never runs a deficit, though it may accumulate a surplus it must then destroy.

This is the property engineers most often forget to state and most often need. A quota system that must be funded from outside, or that generates unallocatable slack, is a system with an operational problem even if its incentive properties are pristine.

flowchart TB
    IC["IC<br/>lying never pays"]
    IR["IR<br/>joining beats leaving"]
    EF["EFFICIENCY<br/>welfare-maximising<br/>alternative chosen"]
    BB["BUDGET BALANCE<br/>Σ payments = 0"]
    IC --- IR
    IR --- EF
    EF --- BB
    BB --- IC
    IC --- EF
    IR --- BB
    X(["Pick any three.<br/>The fourth is<br/>generally unavailable."])
    style X fill:#fee,stroke:#c33,stroke-width:2px

What it shows: the four desiderata as a fully connected quadrilateral, because every pair interacts. What to take from it: this is deliberately drawn as a “pick three” diagram in the style of the CAP theorem — but see the next section, because unlike CAP the precise statement is domain-specific and the fourth property is not always the one you think.

Uncertain

Verify: the crisp slogan “IC + IR + efficiency + budget balance: pick three” is a teaching summary, not a single named theorem. Reason: the literature contains several distinct impossibility results with different hypotheses (Hurwicz 1972 for exchange economies; Green–Laffont for dominant-strategy budget balance with quasi-linear utilities; Myerson–Satterthwaite 1983 for bilateral trade under Bayes–Nash; Gibbard–Satterthwaite 1973/1975 for the no-money case), and no single one of them has exactly this form. Each of the four is achievable in some setting; the results below say which combinations die where. To resolve: read the primary statements of Green & Laffont (1979) and Myerson & Satterthwaite (1983) directly — neither was retrievable from this machine (see the callout in the impossibility section). Treat the quadrilateral as a mnemonic and the named theorems below as the load-bearing claims. #uncertain

Why You Cannot Have All Four

The one great positive result

Start with what does work, because it is remarkable. If utilities are quasi-linear and you want efficiency plus dominant-strategy IC, you can have both, in complete generality, via the Vickrey–Clarke–Groves family. Choose the welfare-maximising alternative and charge each player

$p_{i} (v) = h_{i} (v_{- i}) - \sum_{j \neq = i} v_{j} (f (v))$

where $h_{i}$ is any function that does not depend on $v_{i}$ (Nisan Def. 9.16). The second term hands player $i$ the others’ total value; adding it to $i$ ‘s own value makes $i$ ‘s utility equal to total social welfare up to a constant, so $i$ ‘s selfish maximisation and the designer’s welfare maximisation become literally the same optimisation problem. The first term $h_{i}$ is strategically inert — it is a constant from $i$ ‘s viewpoint — which is why the family has a free function in it. Taking $h_{i} (v_{- i}) = max_{b} \sum_{j \neq = i} v_{j} (b)$ (the Clarke pivot rule, Def. 9.19) makes each player pay “the total damage that he causes the other players,” i.e. their externality, and buys both no-positive-transfers and IR (Nisan Lemma 9.20).

The Nobel background records how surprising this was: “Before 1970, economists generally believed that public goods could not be provided at an efficient level, precisely because people would not reveal their true willingness to pay. It thus came as a surprise when Edward Clarke (1971) and Theodore Groves (1973) showed that, if there are no income effects… truthful revelation of one’s willingness to pay is a dominant strategy.”

So: IC + IR + efficiency, simultaneously, always (with money and quasi-linear utility). Three out of four. Now watch the fourth die.

Fence 1 — Green–Laffont: efficiency + DSIC ⇒ no budget balance

The Nobel background states the drawback in one sentence: “The main drawback of this mechanism is that the total tax revenue typically will not add up to the cost of the project: the mechanism does not in general satisfy budget balance (see Green and Laffont, 1979).” And it explains why you cannot patch it: “sharing surplus funds among the participants will destroy the participants’ truth-telling incentives, while wasting surplus funds is inefficient.”

That second clause is the deep part. The obvious fix — rebate the surplus — fails because a rebate that depends on your own report is a payment that depends on your own report, and Nisan’s uniqueness theorem (Thm. 9.37) says the payments of an efficient DSIC mechanism are pinned down up to a function of the others’ reports only. Any rebate formula that touches $v_{i}$ breaks IC; any rebate formula that does not touch $v_{i}$ cannot balance the books in general.

Concrete, arithmetic, checkable. Nisan’s public-project example (§9.3.5.5). A bridge costs $C = 100$ . Three citizens value it at $v = (60, 50, 30)$ ; total $140 > 100$ , so efficiency says build it. Clarke pivot payments charge a citizen only if they are pivotal — if the project would not have been built without them:

Citizen	$v_{i}$	$\sum_{j \neq = i} v_{j}$	Pivotal?	Payment $p_{i} = C - \sum_{j \neq = i} v_{j}$	Utility $v_{i} - p_{i}$
1	60	80	yes ( $80 \leq 100$ )	$100 - 80 = 20$	40
2	50	90	yes ( $90 \leq 100$ )	$100 - 90 = 10$	40
3	30	110	no ( $110 > 100$ )	0	30
				total 30

Every property holds except the last: truthful reporting is dominant, everyone is better off participating, and the socially correct decision is made — and the mechanism collects 30 against a cost of 100, a deficit of 70 that has to come from somewhere outside. Nisan’s remark on this example: “One may verify that $\sum_{i} p_{i} < C$ (unless $\sum_{i} v_{i} = C$ ), and thus the payments collected do not cover the project’s costs. As we will see in Section 9.5.5, this is unavoidable.”

Fence 2 — Myerson–Satterthwaite: even in expectation, bilateral trade cannot be efficient

Weakening DSIC to Bayes–Nash buys back a lot. d’Aspremont and Gérard-Varet (1979) — independently Arrow (1979) — recovered exact budget balance and efficiency in the Bayesian setting, at the cost of interim IR: “some individuals, having observed their own type but not yet taken their actions, would prefer not to participate.”

But there is a floor you cannot go below. The bilateral-trade problem: one seller with private cost $w$ , one buyer with private value $v$ , both drawn from known distributions. Efficiency says trade should happen exactly when $v > w$ . The Nobel background: “The impossibility results established by Laffont and Maskin (1979, Section 6) and Myerson and Satterthwaite (1983) imply that for bilateral trade no incentive compatible direct mechanism which satisfies (interim) participation constraints can have the property that trade occurs if and only if $w \leq v$ . By the revelation principle, we can infer that no mechanism whatsoever can realize all gains from trade.”

The worked illustration in the same document is the linear equilibrium of a double auction with $v, w \sim U [0, 1]$ : the seller asks $p_{A} = 2 w /3 + 1/4$ and the buyer bids $p_{B} = 2 v /3 + 1/12$ , so “trade occurs if and only if B’s valuation, $v$ , exceeds A’s valuation, $w$ , by at least $1/4$ .” A quarter of the value range is a permanent no-trade band — gains from trade that exist and are destroyed by nothing but privacy. Note the direction of the shading: the seller asks above her value, the buyer bids below his, and the wedge between them is the price of not being able to verify either claim.

Compare this with what VCG does to the same problem. Nisan’s bilateral-trade example (§9.3.5.3): the efficient DSIC mechanism has “the buyer pay $v_{s}$ and the seller be paid $v_{b}$ ” — but since trade only happens when $v_{b} > v_{s}$ , the mechanism pays out more than it takes in. “The mechanism subsidizes the trade. As we will see below in Section 9.5.5, this is unavoidable.” Same impossibility, seen from the dominant-strategy side: with money injected from outside you can be efficient; without it you cannot.

Fence 3 — Gibbard–Satterthwaite: without money, only dictatorship

Take money away entirely — voting, ranking, preference aggregation with no transfers — and the ceiling collapses. Nisan’s Theorem 9.8: “Let $f$ be an incentive compatible social choice function onto $A$ , where $∣ A ∣ \geq 3$ , then $f$ is a dictatorship.” A dictatorship here (Def. 9.7) means some fixed voter $i$ always gets their top choice regardless of everyone else. There are exactly two escapes and both are visible in the hypotheses: restrict to two alternatives (majority vote is strategyproof), or add money and quasi-linear utility (VCG). The Nobel background is blunt about the historical consequence: “Because of this and other negative results, the focus of the literature shifted from dominant-strategy solutions to so-called Bayesian mechanism design.”

Note also the route Nisan takes: Gibbard–Satterthwaite is derived as a corollary of Arrow’s theorem, by constructing a social welfare function from the social choice function (Def. 9.9). The manipulability of voting systems and the inconsistency of preference aggregation are the same fact wearing different clothes.

Fence 4 — computation, the fence computer scientists added

The classical fences are informational. There is a fourth that economics did not have to worry about: the welfare-maximising allocation rule may be NP-hard to evaluate, and you cannot simply substitute an approximation, because approximation algorithms generally are not monotone and therefore are not implementable at all.

Roughgarden’s knapsack-auction lecture makes the collision explicit. Bidders have publicly known sizes $w_{i}$ and private values; the seller has capacity $W$ ; the feasible set is ${x \in {0, 1}^{n} : \sum_{i} w_{i} x_{i} \leq W}$ — “bidders who want files stored on a shared server, data streams sent through a shared communication channel, or processes to be executed on a shared supercomputer. (When there is a shared resource with limited capacity, you have a Knapsack problem.)” The welfare-maximising rule is an exact knapsack solve, so: “there is no polynomial-time implementation of the allocation rule… unless P = NP. Thus, properties (2) and (3) are incompatible” (CS364A lecture 4). And crucially — “note that relaxing the DSIC condition will not help at all, since it is the second two properties that conflict.”

flowchart TB
    START(["What do you want?"])
    START --> Q1{"Is there<br/>money?"}
    Q1 -->|no| GS["Gibbard–Satterthwaite<br/>3+ alternatives, onto, DSIC<br/>⇒ dictatorship<br/><br/>escape: restrict to 2 alternatives,<br/>or restricted preference<br/>domains (matching)"]
    Q1 -->|yes, quasi-linear| Q2{"DSIC or<br/>Bayes–Nash?"}
    Q2 -->|DSIC| VCG["VCG works<br/>IC + IR + efficiency ✓"]
    VCG --> GL["Green–Laffont<br/>…but budget balance ✗<br/>and rebates break IC"]
    Q2 -->|Bayes–Nash| DAGV["d'AGV / Arrow 1979<br/>efficiency + exact BB ✓"]
    DAGV --> MS["Myerson–Satterthwaite<br/>…but interim IR ✗<br/>bilateral trade has an<br/>irreducible no-trade band"]
    VCG --> NP["NP-hardness<br/>the welfare-maximising rule<br/>may be intractable, and<br/>approximations are<br/>usually non-monotone"]

What it shows: a decision tree over the modelling assumptions, with the named impossibility theorem you hit at each leaf. What to take from it: the theorems are not competing claims about the same setting — each one is the wall at the end of a different corridor, and knowing which corridor you are in tells you which property you are about to lose.

Uncertain

Verify: the attributions of Green & Laffont (1979) for dominant-strategy budget imbalance, Myerson & Satterthwaite (1983) for the bilateral-trade bound, d’Aspremont & Gérard-Varet (1979) and Arrow (1979) for the Bayesian balanced mechanism, and Clarke (1971) / Groves (1973). Reason: none of these primary papers was retrievable from this machine. They are cited here from two secondary treatments that were fetched and read in full — the Nobel Prize Committee’s 2007 scientific background and Nisan’s chapter 9 of Algorithmic Game Theory — both of which are authoritative and mutually consistent, but neither is the original. academic.oup.com, dl.acm.org, scholar.harvard.edu and JSTOR full text were all unavailable. To resolve: obtain Green & Laffont, Incentives in Public Decision Making (1979) and Myerson & Satterthwaite, “Efficient mechanisms for bilateral trading,” JET 29(2), 1983, and check the exact hypotheses — in particular whether Myerson–Satterthwaite requires the type distributions to have overlapping supports (it does, in every treatment consulted, but this note has not verified the primary statement). #uncertain

Three Worked Micro-Examples

Theory is cheap. Here are three settings small enough to check by hand, chosen because each one breaks a different property.

A. Splitting the bill — a mechanism nobody designed

Four friends at dinner agree in advance to split the bill evenly. That agreement is a mechanism: the message space is “what you order,” the outcome rule is “you get what you ordered,” and the payment rule is $p_{i} = \frac{1}{n} \sum_{j} c_{j}$ where $c_{j}$ is the cost of what $j$ ordered.

Now compute the equilibrium. Suppose a $40 d i s hi s w or t h$ 15 to you. Ordering it raises your own bill by $40/4 = 10$ and gives you $15 o f v a l u e : * * + 5 * * . T ha t i s t r u er e g a r d l esso f w ha t an y o n ee l se d oes, soor d er in g i s a d o minan t s t r a t e g y — t h e m ec hani s mi s, ina se n se, p er f ec tl y " in ce n t i v eco m p a t ib l e " f or t h e g am e i t d e f in es . B u tt h esoc ia l c h o i ce f u n c t i o ni t im pl e m e n t s i s t h e w r o n g o n e . E f f i c i e n cy s a y sor d er t h e d i s hi f f$ v_i > 40 $; t h e m ec hani s m or d er s i t i f f$ v_i > 10$.

Run it to equilibrium with all four in that position:

	Nobody orders	Everyone orders (the equilibrium)
Total bill	$0	$160
Each pays	$0	$40
Each receives	$0	$15 of value
Each nets	$0	−$25

The unique dominant-strategy outcome is worse for every participant than not playing. This is a prisoner’s dilemma with four players and a continuous action space, and it is worth naming precisely what went wrong: the mechanism satisfies IC and violates efficiency, and it violates ex-post IR in equilibrium even though every individual step looked locally rational. The general lesson is that “each player’s incentives point the right way locally” is not the same claim as “the equilibrium is good,” and it is the second one you need. Compare The Price of Anarchy, which is the quantitative version of this gap.

The fix is a different mechanism, not a better appeal to conscience: itemised billing is a posted-price mechanism with $p_{i} = c_{i}$ , which restores efficiency exactly because it makes each diner internalise the full externality of their own order — the same move the Clarke pivot rule makes. What itemising destroys is the risk-sharing and the social ease of the even split, which is a real cost the mechanism-design formalism does not model. This is a fair sample of the field: the theory tells you which property you are trading and gives you no help at all in deciding whether the trade is worth it.

B. Allocating a shared cache — the case that works

$n$ tenants share a cache with $k$ pinned slots. Tenant $i$ has a private value $v_{i}$ per slot per hour (their saved backend cost). This is a single-parameter environment in Roughgarden’s sense — “each bidder $i$ has a private valuation $v_{i}$ , its value per unit of stuff that it gets,” with feasible set “the 0-1 vectors satisfying $\sum_{i = 1}^{n} x_{i} \leq k$ ” (lecture 3) — and it is exactly Nisan’s multiunit auction (§9.3.5.4).

The mechanism:

Allocation rule. Give the $k$ slots to the $k$ highest reports.
Payment rule. Each winner pays the $(k + 1)$ st highest report; losers pay 0.

Nisan states the same result: “Maximizing social welfare means allocating the items to the $k$ highest bidders, and in the VCG mechanism with the pivot rule, each of them should pay the $k + 1$ ‘st highest offered price.” This is DSIC, efficient, IR, and weakly budget balanced (it collects revenue, it never pays out). It is also $O (n lo g n)$ .

Why it works is worth stating without the machinery: your report does not affect your price. Your price is the $(k + 1)$ st highest of the others’ reports, which is exactly the critical value — the lowest you could have reported and still won. Raising your report can only move you from losing to winning at that fixed price, which you want only if your true value exceeds it; lowering it can only move you from winning to losing, which you want only if it does not. Every misreport either changes nothing or changes it in a direction you dislike.

sequenceDiagram
    participant T1 as Tenant A (v=9)
    participant T2 as Tenant B (v=7)
    participant T3 as Tenant C (v=4)
    participant T4 as Tenant D (v=3)
    participant M as Cache allocator (k=2)
    T1->>M: report 9
    T2->>M: report 7
    T3->>M: report 4
    T4->>M: report 3
    Note over M: sort: 9, 7, 4, 3<br/>winners = top 2<br/>critical value = 3rd highest = 4
    M->>T1: slot granted, charge 4  (utility 9−4 = 5)
    M->>T2: slot granted, charge 4  (utility 7−4 = 3)
    M->>T3: no slot, charge 0       (utility 0)
    M->>T4: no slot, charge 0       (utility 0)
    Note over T2,M: B tries reporting 20 → still wins, still pays 4. No gain.<br/>B tries reporting 3 → loses, utility 0 vs 3. Loss.<br/>C tries reporting 8 → wins, pays 7 against v=4. Utility −3.

What it shows: one run of the $k$ -unit mechanism with the three interesting deviations annotated. What to take from it: the price a winner pays is a function of the other three reports only — that invariance is the mechanism’s entire safety argument, and it is what the attack script in the next section verifies exhaustively.

C. Scheduling a shared machine — the case that breaks on computation

Same idea, one extra wrinkle, and everything falls apart. $n$ jobs contend for one machine with capacity $W$ (a maintenance window, a GPU-hour budget, a commercial break). Job $i$ has a publicly known size $w_{i}$ and a private value $v_{i}$ for being run. This is Roughgarden’s knapsack auction.

The welfare-maximising allocation rule is $x (b) = ar g max_{x \in X} \sum_{i} b_{i} x_{i}$ subject to $\sum_{i} w_{i} x_{i} \leq W$ . By Myerson’s lemma it is monotone (raising your bid never gets you kicked out of the optimal knapsack), so a DSIC payment rule exists, and it is again the critical bid: “if $i$ bids less than $z$ , it loses and pays 0. If $i$ bids more than $z$ , it pays $z$ … i pays its critical bid — the lowest bid it could make and continue to win (holding the other bids $b_{- i}$ fixed).”

The problem is that computing $x (b)$ is NP-hard. And the natural repair — run the standard greedy $2$ -approximation, sorting by value density $b_{i} / w_{i}$ — is not monotone, so by Myerson’s lemma there is no payment rule that makes it truthful. Not “a hard one to find”: none exists. The reasoning is one line: bumping your bid raises your density, which reorders the greedy sequence, which can cause an earlier-packed set that no longer leaves room for you.

This is the single most important practical lesson in the note. You cannot compose an arbitrary approximation algorithm with an arbitrary pricing scheme and hope for truthfulness. The approximation must be designed to be monotone, which is a genuine algorithmic constraint and often costs approximation ratio. Roughgarden’s own repair — restrict the greedy rule to bidders with $w_{i} \leq W /2$ and compare against the single best feasible bidder — is monotone and gives a worse but implementable guarantee. See Approximate and Simple Mechanisms.

Attacking Your Own Mechanism

A strategyproofness claim you have tried and failed to break is worth more than one you proved on paper and then mistyped into code. The exercise below does that: enumerate every misreport over a discretised type space and look for a profitable deviation. Two things make it trustworthy.

Exact arithmetic. Every value is a fractions.Fraction. This matters more than it looks. Ties in these mechanisms sit exactly at breakpoints; a floating-point comparison u_lie > u_true on values that differ by $1 0^{- 16}$ will report phantom violations in a correct mechanism and hide real ones in a broken one. With rationals, u_lie > u_true is a decision, not a guess. (This is the same discipline the parent MOC recommends for equilibrium computation, and this machine has no numpy, no pip and no gambit, so the standard library is not a fallback — it is the tool.)

A validated test. A test that only ever passes proves nothing about the test. So the same harness is run against three mechanisms that are supposed to fail, and it must find the failures.

def attack(alloc, pay_i, n, grid, step):
    for others in product(grid, repeat=n-1):     # every opponent profile
        for v in grid:                            # every true type for player 0
            b  = [v] + list(others)
            ut = v * alloc(b)[0] - pay_i(alloc, b, 0, step)   # utility of truth
            for lie in grid:                      # every misreport
                bl = [lie] + list(others)
                ul = v * alloc(bl)[0] - pay_i(alloc, bl, 0, step)
                if ul > ut:                       # ← exact rational comparison
                    record_violation(v, lie, others, ut, ul)

Line by line: the outer two loops instantiate the universal quantifier in the definition of incentive compatibility — for every $v_{- i}$ , for every $v_{i}$ . The inner loop instantiates for every $v_{i}^{'}$ . ut and ul both multiply by v, the true value, never by the reported one: that is the whole point, and it is the line people get wrong. A violation is any strict improvement.

The payment rule under test is not hard-coded to a closed form. It is computed from the allocation rule by walking the bid up from zero and accumulating $z \times (jump in x_{i})$ at each breakpoint — Myerson’s explicit formula (see Incentive Compatibility for the derivation). That makes the test a check on the theory, not on a transcription of the answer.

Results, measured 2026-08-28

Grid: 17 types, ${0, \frac{1}{8}, \frac{2}{8}, \dots, 2}$ ; $n = 4$ players ( $n = 3$ for the single-item case); exact rationals throughout.

Mechanism	Allocation monotone?	Payment rule	Deviations checked	Profitable	Situations exploitable	Max gain
Shared cache, $k = 2$	yes	Myerson / critical value	1,336,336	0	0 / 83,521	0
Sponsored search, CTRs $1, \frac{1}{2}, \frac{1}{4}$	yes	Myerson	1,336,336	0	0 / 83,521	0
Shared cache, $k = 2$	yes	pay-your-bid	742,560	111,384	24,570 / 57,120	$7/4$
Sponsored search	yes	GSP	742,560	76,704	13,512 / 57,120	$13/16$
Second-highest bidder wins	no	Myerson formula applied anyway	57,120	14,280	3,360 / 4,080	$7/4$

(Rows 3–5 are restricted to tie-free profiles so that no result can be an artefact of the tie-breaking rule; the runs including ties show the same pattern with larger counts.)

Four findings worth stating separately.

The two monotone-plus-Myerson mechanisms survive every single one of 2,672,672 exact misreport tests. That is not a proof, but it is a proof-shaped amount of evidence, and it is evidence about the code rather than about the paper.
Keeping the allocation rule and changing only the payment rule destroys truthfulness. Rows 1 and 3 have identical allocation rules; 43% of the situations in row 3 admit a profitable lie. This is the cleanest possible demonstration that incentive compatibility is a joint property of allocation and payment, not a property of who wins.
A non-monotone allocation rule cannot be rescued by any payment rule — including the one Myerson’s formula produces when you apply it anyway. The formula still returns a number; the number is simply not a truthful price. Row 5’s witness: a bidder with true value 2 who reports $1/8$ against opponents $(0, 1/4)$ moves from utility $1/4$ to utility $2$ , because under-reporting is how you become the second-highest bidder. This is the empirical face of Myerson’s lemma part (a).
The harness caught a discretisation subtlety that reading the theorem would not have. Cross-checking the numerically derived payment against the textbook closed form — “each winner pays the $(k + 1)$ st highest bid” — they disagree on 6,072 of 26,244 (profile, player) pairs, 23%. Every disagreement is in the same direction and of the same size: the derived payment is exactly one grid step higher, never lower (measured distribution: ${0 : 20172, \frac{1}{4} : 6072}$ at step $\frac{1}{4}$ ). The cause is that at the critical value itself the tie is broken against the bidder, so on a grid the bidder only wins at the next point up. Against the correct discrete statement — “the payment equals the lowest grid report at which the bidder still wins” — agreement is 26,244 / 26,244. The grid mechanism is a slightly different, and still perfectly DSIC, mechanism; that is why row 1 shows zero violations despite the closed-form mismatch. The moral is the one the parent MOC keeps repeating: with floating point this would have looked like noise, and with rationals it is a crisp, explicable, one-step offset.

The GSP row deserves its own sentence, because it is not a toy. The generalised second-price auction is what actually ran sponsored search at Google and Yahoo!, and Roughgarden notes it arose “by historical accident… a simpler (and perhaps incorrectly implemented) version of the DSIC auction” (lecture 3). Since Myerson’s lemma says the truthful payment rule is unique, and GSP is a different rule with the same allocation rule, GSP cannot be DSIC — and the attack finds the deviations in seconds. Its worst witness is the textbook one: an advertiser with value 2 facing bids $(0, \frac{1}{8}, \frac{15}{8})$ earns $\frac{1}{8}$ by winning the top slot honestly and $\frac{15}{16}$ — seven and a half times more — by reporting $\frac{1}{4}$ and deliberately taking the second slot at a much lower per-click price. Demoting yourself is the canonical GSP exploit. See Ad Auctions and GSP.

Uncertain

Verify: the “0 profitable deviations” results establish incentive compatibility only on the tested grid, not on the continuum. Reason: the payment computation walks the same grid it enumerates lies over, so an off-grid misreport is neither generated nor correctly priced — and finding 4 above shows the grid mechanism is genuinely not identical to the continuum one. To resolve: re-run with the misreport grid refined relative to the opponent grid (lies at step $1/64$ against opponents at step $1/8$ ) and confirm the count stays at zero, pricing lies by the continuum critical value rather than the grid one. #uncertain

Failure Modes and Gotchas

Designing the allocation rule first and bolting prices on afterwards. This is the single most common error and it is fatal, not merely inefficient. Roughgarden teaches the two-step paradigm — “first assume without justification that bids equal values and then decide on our allocation rule. Then we pay the piper and devise a payment rule” — but the second step can fail. If your allocation rule is not monotone, no payment rule exists. The knapsack-greedy example above is the canonical case: a perfectly good approximation algorithm that admits no truthful pricing at all. Check monotonicity before you ship the allocator.

Confusing “each player’s local incentives look fine” with “the equilibrium is good.” The bill-splitting example is IC and produces an outcome worse than the outside option for everybody. IC constrains deviations; it says nothing about the quality of the point they cannot deviate from. That is what efficiency and The Price of Anarchy are for.

Assuming quasi-linearity when it does not hold. VCG needs utility to be value-minus-money with no wealth effects. Budget-constrained bidders violate this outright: a bidder who cannot pay more than $B$ has utility $- \infty$ above $B$ , not $v - p$ . Nearly every internal cloud-quota scheme has hard budget caps, which means the VCG guarantee simply does not apply, and the standard workarounds (clipping payments, capping bids) break IC.

Ignoring collusion and multi-identity attacks. DSIC quantifies over unilateral deviations only. It says nothing about two players coordinating, and nothing about one player registering as two. VCG is notoriously vulnerable to both: bid-shading coalitions can profit, and a losing bidder can sometimes win by splitting into several personas. Milgrom and Segal single out group strategy-proofness as an advantage of the deferred-acceptance clock design over Vickrey precisely because of this (Milgrom & Segal 2017). If your users can create accounts freely, unilateral strategyproofness is close to worthless — this is exactly the Sybil problem in a different vocabulary.

Forgetting that the mechanism’s own computation is part of the mechanism. If a price depends on an optimisation you solve approximately, the incentive guarantee degrades with the approximation error — and not gracefully. Milgrom and Segal’s estimate for the FCC’s reverse auction is the sharpest published illustration: “With 2000 stations, a 1% error in computing one of the maximum values would lead to a pricing error equal to 20 times the average station value, ruining even an approximate dominant strategy property.”

Assuming budget balance because money changed hands. VCG with Clarke pivot payments collects revenue in an auction and pays out in a procurement, and in the public-project setting collects strictly less than cost. Compute $\sum_{i} p_{i}$ explicitly for your own mechanism on a few profiles before you assume it funds itself; the 100-cost bridge that collects 30 above is not a pathological corner case, it is the normal case.

Treating a truthful mechanism as a revenue-maximising one. They are different objectives with different optima. Nisan’s own worked example: with two bidders uniform on $[0, 1]$ , the second-price auction earns expected revenue $1/3$ , while adding a reserve price of $1/2$ earns $5/12$ — still incentive compatible, more revenue, less efficient (sometimes nobody wins an item both bidders wanted). See Reserve Prices and Optimal Auctions.

Believing the revelation principle means you should always build a direct mechanism. It says a direct mechanism achieves the same outcome, not that it is the right implementation. The FCC deliberately chose an indirect descending-clock design over a direct Vickrey one; Milgrom and Segal list the reasons — obvious strategy-proofness, winner privacy, avoiding intractable optimisation, budget constraints — none of which the outcome-equivalence theorem addresses.

Alternatives and When to Choose Them

Approach	Gives up	Buys	Choose it when
VCG / Groves family	budget balance; tractability; collusion-resistance	exact efficiency + DSIC	Small alternative set, welfare is genuinely the objective, deficits can be funded
Posted prices	efficiency (some)	trivial to explain, trivially DSIC, no cross-agent computation	Prices are stable and you value predictability over allocation quality — most cloud pricing
Deferred-acceptance clock auctions	exact efficiency	obvious strategy-proofness, group strategy-proofness, privacy, cheap feasibility checks	Allocation feasibility is NP-hard and prices must still be defensible — the FCC’s actual choice
Matching without money (The Gale-Shapley Algorithm)	money entirely; strategyproofness on one side	stability; strategyproofness for proposers	Transfers are illegal or repugnant: residency matching, school choice, kidney exchange
Bayesian / BNIC mechanisms	worst-case guarantees; needs a prior	budget balance and efficiency together (d’AGV)	You genuinely know the distribution and participation is mandatory
Approximate monotone mechanisms	approximation ratio	DSIC and polynomial time	The exact allocation rule is NP-hard — see Approximate and Simple Mechanisms
Reputation / repeated play	one-shot guarantees	cooperation without transfers	Interactions repeat indefinitely — see The Folk Theorem and Iterated Games and the Shadow of the Future
Just verify the claim	nothing, if you can	everything	Whenever the private information is actually checkable. Auditing beats incentive engineering

That last row is the one engineers skip. Mechanism design is the theory of what to do when you cannot verify the report. If you can measure a tenant’s actual cache hit rate rather than asking them how much they value cache, do that; the entire apparatus above exists to handle the case where you cannot. A surprising number of internal “priority” schemes ask users to self-report an urgency they could instead have derived from telemetry.

The matching row deserves expansion because it is the field’s other great deployment. Gale–Shapley deferred acceptance escapes Gibbard–Satterthwaite not by adding money but by restricting the preference domain: agents rank each other, and the theorem’s “onto $A$ with $∣ A ∣ \geq 3$ ” hypothesis does not bite on this structure. The result is genuinely strategyproof for the proposing side and provably not for the receiving side — an asymmetry, not a bug, and one the vault covers in The Gale-Shapley Algorithm and Proposer-Optimality and Strategic Truncation. Roth’s survey is the standard account of how this became infrastructure: clearinghouses “designed for many entry-level professional labor markets, for the assignment of children to public schools, and for exchange of live-donor kidneys for transplantation” (Roth, Matching and Market Design).

Production Notes

The FCC Incentive Auction — mechanism design at $30 billion

The largest deliberate piece of mechanism design ever run concluded in April 2017. The U.S. Federal Communications Commission reallocated UHF TV channels 38–51 to wireless broadband by buying broadcast rights in a reverse auction (about $10.1 bi l l i o n * * p ai d o u t), r e p a c k in g t h es u r v i v or s, an d se l l in g t h ec l e a r e d s p ec t r u mina f or w a r d a u c t i o n (ab o u t * *$ 19.8 billion collected) (Milgrom & Segal 2017, §1).

Every constraint in this note showed up at once:

Scale. 2,990 pre-auction U.S. and Canadian stations, all but 175 of which had to be repacked.
Computational intractability. Repacking must satisfy “more than a million constraints,” each forbidding some geographically close pair from sharing or adjoining a channel. “Just checking whether it is feasible to repack any given set of stations into any set of TV channels is an NP-hard problem” — a generalisation of graph colouring. Identifying the maximum-value feasible subset “could not be solved exactly in reasonable time.”
Why Vickrey was rejected. Not for theoretical reasons — for the error-propagation reason quoted above: a 1% optimisation error becomes a pricing error of 20 average station values, “ruining even an approximate dominant strategy property.”
What was built instead. A descending clock auction: prices fall each round, a bidder whose price falls may exit and be repacked, and non-exiting bidders win at their last clock price. Crucially, “the FCC auction reduced the price offer to a bidder only if it could identify a feasible assignment that adds the bidder to the set of stations to be repacked” — so the NP-hard problem is only ever solved as a feasibility check on one incremental addition, never as a global optimisation. The auction required “about 75,000 such steps,” and a purpose-built checker solved “more than 99% of the problems in auction simulations within 2 seconds.”

The design lesson generalises far beyond spectrum: when the welfare-maximising allocation is intractable, do not approximate it and then price it — change the mechanism to one whose prices are defined by the search process itself. A clock price is a price by construction, no optimisation required. This is the same move as replacing a global scheduler with an admission-control loop.

The vault’s own mechanisms

Several systems already documented here are mechanisms whose incentive properties nobody stated:

Multi-Tenancy and Fairness in LLM Serving — quota and fair-share schemes are allocation rules. If a tenant can gain throughput by inflating a declared priority or by splitting one workload across two accounts, the mechanism is not strategyproof, and the failure is the multi-identity attack above.
Stock Exchange Order Matching System Design — price-time priority is the outcome rule, and it determines what traders reveal and when. Iceberg orders, order splitting, and latency arbitrage are all strategic responses to that specific rule, not to markets in general.
The Completely Fair Scheduler and Its History — a fairness criterion facing strategic processes. A process that sleeps to inflate its vruntime deficit is misreporting its type.
Rate Limiting as a Mechanism — quotas and priorities are an allocation rule with incentive properties, usually unexamined.

The right first question for any of them is the one this note is built around: what does a participant gain by misrepresenting themselves, and have I actually tried to find out?

vault

Explorer

Mechanism Design

Mechanism Design

The One-Sentence Version for Engineers

Anatomy of a Mechanism

Direct and Indirect Mechanisms

The Four Properties

1. Incentive Compatibility (IC) — lying does not pay

2. Individual Rationality (IR) — participating beats walking away

3. Efficiency — the right alternative gets chosen

4. Budget Balance (BB) — the mechanism pays for itself

Why You Cannot Have All Four

The one great positive result

Fence 1 — Green–Laffont: efficiency + DSIC ⇒ no budget balance

Fence 2 — Myerson–Satterthwaite: even in expectation, bilateral trade cannot be efficient

Fence 3 — Gibbard–Satterthwaite: without money, only dictatorship

Fence 4 — computation, the fence computer scientists added

Three Worked Micro-Examples

A. Splitting the bill — a mechanism nobody designed

B. Allocating a shared cache — the case that works

C. Scheduling a shared machine — the case that breaks on computation

Attacking Your Own Mechanism

Results, measured 2026-08-28

Failure Modes and Gotchas

Alternatives and When to Choose Them

Production Notes

The FCC Incentive Auction — mechanism design at $30 billion

Sponsored search — the mechanism that funds the web

The vault’s own mechanisms

See Also

Graph View

Table of Contents

Backlinks