Incentive Compatibility

A mechanism is incentive compatible when no participant can do better by misrepresenting their private information than by reporting it honestly. It is the central constraint of Mechanism Design and the reason that field is hard: you are optimising an objective subject to one inequality for every player, every true type, and every lie they might tell instead. Roger Myerson — who shared the 2007 Nobel for this material — opens his own introduction to the subject with the reason it binds: “when one person has unverifiable private information that is not available to the others, then he cannot be compelled to reveal that information honestly unless he is given the correct incentives” (Myerson 1985, “Bayesian equilibrium and incentive-compatibility: an introduction”). The property comes in two strengths that are routinely conflated and are not close to equivalent — dominant-strategy IC, where lying never pays no matter what anyone else does, and Bayes–Nash IC, where honesty is merely the best reply in expectation, assuming everyone else is honest too. And in the single-parameter case there is a complete and startlingly clean answer to which mechanisms can be truthful at all: an allocation rule is implementable if and only if it is monotone, and the payments are then forced up to a constant. That is Myerson’s Lemma, and it is derived in full below.

Naming

Three words in the literature mean the same thing and you will meet all three: incentive compatible, strategyproof (also written strategy-proof), and truthful. Nisan introduces them together — “the key definition in this area, incentive compatibility also called strategy-proofness or truthfulness” (Algorithmic Game Theory ch. 9, p. 218). The parent MOC’s gloss is the one to keep: “incentive compatible” means lying does not pay.

Two nearby terms mean something else and must not be substituted:

• Individually rational means participating beats walking away. A mechanism can be truthful and still make you regret showing up. Roughgarden’s DSIC bundles both — “truthful bidding should be a dominant strategy (and never leads to negative utility)” (CS364A lecture 3) — which is convenient but hides the fact that they are separate conditions.
• Efficient means the right alternative gets chosen. Giving the item away to a uniformly random bidder is perfectly DSIC and completely useless; Roughgarden makes exactly this point when motivating why DSIC alone is not the goal.

The Definition, Symbol by Symbol

Nisan’s Definition 9.15. A mechanism $(f,p_1,\dots ,p_n)$ — an outcome rule $f$ mapping reported valuations to an alternative, plus a payment rule $p_i$ for each player — is incentive compatible if for every player $i$, every profile $v_1\in V_1,\dots ,v_n\in V_n$, and every alternative report $v_i^{\prime }\in V_i$:

$\underset{\text{utility from telling the truth}}{\underbrace{v_i(f(v_i,v_{-i}))-p_i(v_i,v_{-i})}}\ge \underset{\text{utility from reporting }{v}_i^{\prime }\text{ instead}}{\underbrace{v_i(f(v_i^{\prime },v_{-i}))-p_i(v_i^{\prime },v_{-i})}}$

Every symbol matters:

• $v_i$ is player $i$‘s true valuation function — what outcomes are actually worth to them. It is private and unverifiable.
• $v_i^{\prime }$ is what they say. There is no constraint linking the two. The message space and the type space happen to coincide here because this is a direct revelation mechanism (Nisan Def. 9.14); by the revelation principle that is without loss of generality.
• $v_{-i}$ is the vector of everyone else’s reports with coordinate $i$ deleted.
• $f(v_i^{\prime },v_{-i})$ is the alternative the mechanism picks given the lie. The mechanism has no way to tell it was a lie.
• The outer $v_i(\cdot )$ on the right-hand side is the true valuation applied to the outcome the lie produced. This is the line everyone gets wrong when they code it up. Lying changes what you get; it does not change what you want.

Nisan’s own gloss: “player $i$ whose valuation is $v_i$ would prefer ‘telling the truth’ $v_i$ to the mechanism rather than any possible ‘lie’ $v_i^{\prime }$, since this gives him higher (in the weak sense) utility.”

Note the weak inequality. Incentive compatibility does not require that lying strictly hurts, only that it never strictly helps. In a second-price auction, overbidding while still winning changes nothing at all — you pay the same price either way — and the definition is satisfied by indifference. That indifference is also the crack through which non-truthful equilibria and collusion get in.

The quantifier is the whole story

Read the quantifier prefix carefully:

$\forall i\forall v_i\forall v_{-i}\forall v_i^{\prime }:u_i(v_i;v_i,v_{-i})\ge u_i(v_i;v_i^{\prime },v_{-i})$

The third quantifier — for every $v_{-i}$ — is what makes this dominant-strategy incentive compatibility. It ranges over all possible reports by the others, including irrational ones, adversarial ones, and ones drawn from a distribution you got wrong. Hartline’s Definition 2.2.1 states the same thing in strategy language: “a dominant strategy equilibrium (DSE) is a strategy profile $b$ such that for all $i$, $t_i$, and $b_{-i}$… agent $i$‘s utility is maximized by following strategy $b_i(t_i)$” (Mechanism Design and Approximation ch. 2).

Replace that universal quantifier with an expectation and you get the weaker, and far more common, Bayes–Nash version. That swap is the subject of the next section.

DSIC versus Bayes–Nash IC

The two definitions side by side

Dominant-strategy IC (DSIC). Truth is optimal against every profile of opponent reports:

$\forall v_{-i}:v_i(f(v_i,v_{-i}))-p_i(v_i,v_{-i})\ge v_i(f(v_i^{\prime },v_{-i}))-p_i(v_i^{\prime },v_{-i})$

Bayes–Nash IC (BNIC, also BIC). Types are drawn from a commonly known prior $D_{-i}$, everyone else plays the truthful strategy, and truth is optimal in expectation:

${\mathbb{E}}_{v_{-i}\sim D_{-i}}\left[v_i\right(f(v_i,v_{-i}))-p_i(v_i,v_{-i})]\ge {\mathbb{E}}_{v_{-i}\sim D_{-i}}\left[v_i\right(f(v_i^{\prime },v_{-i}))-p_i(v_i^{\prime },v_{-i})]$

Nisan’s Definition 9.43: a mechanism “is truthful in the Bayesian sense if (a) it is ‘direct revelation’… and (b) the truthful strategies $s_i(t_i)=t_i$ are a Bayesian–Nash equilibrium.” A Bayes–Nash equilibrium itself (Def. 9.41) requires that ”$s_i(t_i)$ is the best response that $i$ has to $s_{-i}(\cdot )$ when his type is $t_i$, in expectation over the types of the other players.”

Everything that changes is that one expectation, and everything that follows changes with it.

	DSIC	BNIC
Truth beats lying…	against every possible $v_{-i}$	on average over $v_{-i}\sim D_{-i}$
Requires a prior?	no	yes, and it must be common knowledge
Requires opponents to be rational?	no	yes — they must be playing the equilibrium strategy
Robust to a wrong prior?	vacuously yes	no — the strategy itself is a function of $D$
Robust to a wrong player count?	yes	no (demonstrated below)
Achievable with efficiency + budget balance?	no (Green–Laffont)	yes (d’Aspremont & Gérard-Varet 1979)
Achievable at all without money?	essentially never (Gibbard–Satterthwaite)	more often
Cost to the participant	none — bid your value	must model the distribution and the field
Predictive strength for the designer	very high	depends on equilibrium selection

There is a third notion sitting between them, and it is worth naming because it is the one many “worst-case” computer-science mechanisms actually satisfy. Ex-post Nash: $s_i(t_i)$ is a best response to $s_{-i}(t_{-i})$ for every $t_{-i}$ — no prior needed, but the others must be following their strategies. Nisan’s Prop. 9.23 shows the gap is almost illusory: restrict each player’s action space to the range actually used in the ex-post equilibrium, and the same profile becomes a dominant-strategy equilibrium. “While at first sight the notion of dominant strategy equilibrium seems much stronger than ex-post Nash, this is only due to actions that are never used.”

flowchart TB
    DS["Dominant strategy<br/>best reply to EVERY x₋ᵢ<br/><br/>no prior, no rationality<br/>assumption about others"]
    EP["Ex-post Nash<br/>best reply to s₋ᵢ(t₋ᵢ)<br/>for every t₋ᵢ<br/><br/>no prior; others must<br/>follow their strategies"]
    BN["Bayes–Nash<br/>best reply in expectation<br/>over t₋ᵢ ~ D₋ᵢ<br/><br/>needs a common prior<br/>AND rational others"]
    DS --> |"strictly stronger"| EP
    EP --> |"strictly stronger"| BN
    DS -.->|"Nisan Prop. 9.23:<br/>restrict actions to the<br/>range actually used and<br/>these two coincide"| EP
    BN --> W["Wilson doctrine:<br/>prefer the concept that<br/>assumes least about<br/>what agents know"]

What it shows: the three solution concepts as a strict hierarchy, with the two collapses and the design pressure annotated. What to take from it: moving down the chain buys you existence — mechanisms that DSIC forbids — and pays for it in assumptions you must actually be able to defend. Every step down is a claim you are making about your users’ knowledge on their behalf.

Why the weaker notion is usually what you get

Four independent reasons, in roughly increasing order of how often they bite.

1. DSIC does not exist for most objectives. Without money, Gibbard–Satterthwaite says that any onto, incentive-compatible social choice function over three or more alternatives is a dictatorship (Nisan Thm. 9.8). With money it exists for welfare maximisation via VCG, and — by Roberts’ theorem (Nisan Thm. 9.32) — on unrestricted valuation domains only for affine maximisers, $f(v)\in \arg {\max }_a(c_a+{\sum }_i{w}_i{v}_i(a))$. If your objective is makespan, or max–min fairness, or revenue, and your domain is unrestricted, there is no DSIC mechanism at all. The single-parameter case is the great exception, and the next section is about exactly why.

2. DSIC costs properties you also need. Efficiency plus DSIC forces a budget deficit (Green–Laffont); the Bayesian relaxation recovers exact balance. The Nobel committee’s summary is the crisp statement of the mechanism: “In the Bayesian model, agents are expected utility maximizers, and the IC constraints only have to hold in expectation. Accordingly, the IC constraints are easier to satisfy in the Bayesian model, and d’Aspremont and Gérard-Varet could obtain more positive results than is possible with dominant strategies” (Nobel 2007, §2.3).

3. The mechanisms actually deployed are BNIC at best. First-price auctions, the generalised second-price auction that runs sponsored search, uniform-price auctions for treasury securities, most procurement — none is DSIC. They are analysed by computing a Bayes–Nash equilibrium and hoping the participants find it.

4. Sometimes you inherit the mechanism. You are given a first-price auction and asked to bid well, not to redesign the market. Then BNIC is not a design choice, it is the only available analysis.

Measured: what the Bayesian equilibrium costs you

Here is the price of the weaker concept, made concrete. Nisan’s Lemma 9.45 states that in a first-price auction between two bidders with values uniform on $[0,1]$, “the strategies $x(a)=a/2$ and $y(b)=b/2$ are in Bayesian–Nash equilibrium.” His derivation: Alice’s expected utility from bid $x$ is $\mathrm{Pr}[\text{Alice wins}]\cdot (a-x)$; against $y=b/2$ with $b\sim U[0,1]$ that probability is $2x$ on $[0,\frac{1}{2}]$; maximise $2x(a-x)$ by setting the derivative $2a-4x$ to zero, giving $x=a/2$.

The general symmetric case is $b(v)=v\cdot \frac{n-1}{n}$. Rather than trust the algebra, best-respond numerically on a grid of 2,001 exact rational bids, assuming the $n-1$ opponents play the conjectured strategy — so $\mathrm{Pr}[\text{win with }x]=(x\cdot \frac{n}{n-1}{)}^{n-1}$:

$n$	Opponents play	Best reply for $v=\frac{1}{4}$	for $v=\frac{1}{2}$	for $v=\frac{3}{4}$	for $v=1$	Predicted $v\frac{n-1}{n}$
2	$v/2$	$0.1250$	$0.2500$	$0.3750$	$0.5000$	✓ exact
3	$2v/3$	$0.1665$	$0.3335$	$0.5000$	$0.6665$	✓ (grid resolution $5\times 10^{-4}$)
4	$3v/4$	$0.1875$	$0.3750$	$0.5625$	$0.7500$	✓ exact
5	$4v/5$	$0.2000$	$0.4000$	$0.6000$	$0.8000$	✓ exact

Two things fall straight out of that table, and they are the practical content of the DSIC/BNIC distinction:

• The optimal bid depends on $n$. A bidder with value $\frac{1}{2}$ should bid $0.25$ against one rival and $0.40$ against four. In a second-price auction the answer is $0.50$ in every row. Change the number of participants — which happens constantly in any real system — and every BNIC participant’s strategy is wrong until they re-derive it. The DSIC participant’s strategy is unchanged because it never referred to the field in the first place.
• Truthful bidding is strictly dominated in every row. The measured utility of bidding your true value is exactly $0$ everywhere: you win only when you gain nothing. A first-price auction is not “less truthful”; it is anti-truthful, and honesty is a guaranteed loss.

This is the strongest single argument for paying whatever DSIC costs when you can get it: a DSIC mechanism is one where the correct participant behaviour survives every change to the environment you did not tell them about.

Uncertain

Verify: the closed form $b(v)=v\frac{n-1}{n}$ for the symmetric first-price BNE with $n$ bidders and values i.i.d. uniform on $[0,1]$. Reason: the $n=2$ case is stated and proved in the primary source read here (Nisan, AGT Lemma 9.45); the general-$n$ formula was verified numerically by best-response search but its derivation was not read in a primary source during this task. The numerical check confirms only that the conjectured profile is a mutual best reply on a discrete grid, not that it is the unique equilibrium or that it extends to non-uniform distributions. To resolve: read a primary treatment of symmetric first-price equilibria — Levin’s Stanford lecture notes on auctions, or Krishna’s Auction Theory ch. 2. #uncertain

Myerson’s Lemma: Which Rules Can Be Truthful At All

This is the single most useful theorem in the note. It answers, completely and constructively, the question “I have an allocation rule I like — can I price it truthfully, and if so how?”

Setting: single-parameter environments

The theorem needs the private information to be one number. Roughgarden’s definition: “such an environment has some number $n$ of bidders. Each bidder $i$ has a private valuation $v_i$, its value per unit of stuff that it gets. Finally, there is a feasible set $X$. Each element of $X$ is an $n$-vector $(x_1,\dots ,x_n)$, where $x_i$ denotes the ‘amount of stuff’ given to bidder $i$” (CS364A lecture 3). Utility is quasi-linear: $u_i(b)=v_i\cdot x_i(b)-p_i(b)$.

Examples of feasible sets $X$, all from Roughgarden’s list:

Environment	$X$	$x_i$ means
Single item	0-1 vectors with ${\sum }_i{x}_i\le 1$	you won
$k$ identical goods, one each	0-1 vectors with ${\sum }_i{x}_i\le k$	you got one
Sponsored search	assignments of bidders to slots	the click-through rate ${\alpha }_j$ of your slot
Knapsack / shared machine	0-1 with ${\sum }_i{w}_i{x}_i\le W$	your job ran

Nisan reaches the same class from the valuation side (Def. 9.33): a single parameter domain is given by a publicly known set $W_i\subseteq A$ of “winning” alternatives and a scalar range, with $v_i(a)=t$ for $a\in W_i$ and $0$ otherwise. “The main point is that all winning alternatives are equivalent to each other for player $i$; and similarly all losing outcomes are equivalent to each other.”

The restriction is real. Combinatorial auctions, where a bidder values every subset of items differently, are multi-parameter and Myerson’s Lemma does not apply — that is why The VCG Mechanism and its computational troubles exist as a separate story.

The two definitions the theorem equates

Implementable (Roughgarden Def. 4.1): an allocation rule $x$ is implementable if there exists a payment rule $p$ such that $(x,p)$ is DSIC. “If our aim is to design a DSIC mechanism, we must confine ourselves to implementable allocation rules — they form our ‘design space.’”

Monotone (Def. 4.2): $x$ is monotone if for every bidder $i$ and every $b_{-i}$, the allocation $x_i(z,b_{-i})$ is nondecreasing in $z$. In one sentence: bidding higher can only get you more stuff.

The first definition is what you want and is essentially impossible to check directly — it quantifies over all payment rules. The second is a property of a single one-dimensional function and takes thirty seconds to verify. Myerson’s Lemma says they are the same set.

Theorem (Myerson’s Lemma). Fix a single-parameter environment. (a) An allocation rule $x$ is implementable if and only if it is monotone. (b) If $x$ is monotone, there is a unique payment rule making $(x,p)$ DSIC, given the normalisation that $b_i=0\Rightarrow p_i(b)=0$. (c) That payment rule has an explicit closed form.

Roughgarden on why (a) is the valuable half: “This equivalence is incredibly powerful: Definition 4.1 describes our design goal but is unwieldy to work with and verify, while Definition 4.2 is far more ‘operational.’”

The derivation

Fix a bidder $i$ and the other bids $b_{-i}$, and write $x(z)$ and $p(z)$ for $x_i(z,b_{-i})$ and $p_i(z,b_{-i})$ — one bidder’s allocation and payment as functions of their own report, everything else frozen. The whole proof lives in this one-dimensional slice.

Step 1 — write down DSIC twice. Take any two possible reports $y$ and $z$ in the bidder’s range (nothing below depends on their order until Step 3, where we will take $y<z$, and Step 4, where we will take $y>z$). The bidder might truly have value $z$ and could lie by saying $y$; DSIC forbids that being profitable:

z \cdot x(z) - p(z) \;\ge\; z \cdot x(y) - p(y) \tag{2}

The bidder might equally truly have value $y$ and lie by saying $z$; DSIC forbids that too:

y \cdot x(y) - p(y) \;\ge\; y \cdot x(z) - p(z) \tag{3}

Roughgarden calls this “a simple but clever swapping trick,” and it is the entire engine of the proof. We are using the constraint in both directions between the same pair of types, which pins the payment difference from both sides at once.

Step 2 — the payment difference sandwich. Rearrange each inequality so that the payment difference $p(y)-p(z)$ stands alone. From (2), move $p(y)$ left and $zx(z)$ right:

$p(y)-p(z)\ge zx(y)-zx(z)=z[x(y)-x(z)]$

From (3), the same move in the other direction:

$p(y)-p(z)\le yx(y)-yx(z)=y[x(y)-x(z)]$

Stack them and you have Roughgarden’s “payment difference sandwich”, valid for every ordered pair $(y,z)$:

z \cdot [x(y) - x(z)] \;\le\; p(y) - p(z) \;\le\; y \cdot [x(y) - x(z)] \tag{4}

Read it as: the change in payment between two reports is squeezed between the change in allocation, priced at the higher type and at the lower type.

Step 3 — monotonicity falls out immediately. Since $y<z$, the left bound exceeds the right bound unless $x(y)-x(z)\le 0$. If the rule were non-monotone somewhere — if $x(y)>x(z)$ for some $y<z$ — then (4) reads $z\cdot (\text{positive})\le p(y)-p(z)\le y\cdot (\text{positive})$ with $z>y$, which asks a number to be simultaneously at least $zc$ and at most $yc$ for $c>0$. No such number exists, so no payment rule exists. That is part (a)‘s “only if” direction, in one line. This is why Roughgarden interjects “the payment difference sandwich already implies one major component of Myerson’s Lemma — do you see why?”

Step 4 — take the limit. Now assume $x$ is monotone. Fix $z$ and let $y$ approach it from above, $y\downarrow z$ (Roughgarden: “in (4), fix $z$ and let $y$ tend to $z$ from above”). Two cases:

Piecewise constant $x$ (the usual case: 0-1 allocation rules, slot assignments). Away from a jump, both bounds go to zero, so $p$ is flat there. At a jump of magnitude $h$ located at $z$, both bounds tend to $z\cdot h$, so the payment must jump by exactly the same amount:

\text{jump in } p \text{ at } z \;=\; z \cdot (\text{jump in } x \text{ at } z) \tag{5}

Differentiable $x$. Divide (4) by $y-z$ and let $y\downarrow z$: $p^{\prime }(z)=z\cdot x^{\prime }(z)$.

Step 5 — integrate. With the normalisation $p(0)=0$, sum or integrate the constraint:

p_i(b_i, b_{-i}) \;=\; \sum_{j=1}^{\ell} z_j \cdot \bigl(\text{jump in } x_i(\cdot, b_{-i}) \text{ at } z_j\bigr) \tag{6}

where $z_1,\dots ,z_{\ell }$ are the breakpoints of $x_i(\cdot ,b_{-i})$ inside $[0,b_i]$; or in the smooth case

p_i(b_i, b_{-i}) \;=\; \int_0^{b_i} z \cdot \frac{d}{dz} x_i(z, b_{-i})\, dz \tag{7}

Steps 3–5 have derived the payment rule rather than guessed it, and along the way proved it is the only candidate — that is part (b). Roughgarden: “we reiterate that the payment formula in (6) is the only payment rule with a chance of extending the given piecewise constant allocation rule $x$ into a DSIC mechanism.”

Step 6 — check sufficiency. Uniqueness is not existence: we have shown that if a DSIC payment rule exists it must be (6), not that (6) works. Roughgarden closes the gap with a proof by picture, comparing three areas. Since the shading cannot be expressed in mermaid, here it is as an ASCII sketch — a deliberate fallback from the vault’s mermaid-first rule because the argument is about regions between curves, which no mermaid diagram type draws.

   TRUTHFUL (b = v)              OVERBID (b > v)             UNDERBID (b < v)
 x(z)                        x(z)                        x(z)
  1 |      ______             1 |      ______             1 |      ______
    |     |######             |     |######|              |     |###|
    |     |######             |     |######| ///          |     |###|
    |  ___|######             |  ___|######|///           |  ___|###|
  0 +--------------- z      0 +--------------- z        0 +--------------- z
         v=b                        v      b                    b    v

   utility = the area           utility = that same         utility = a strict
   UNDER the curve on           area MINUS the lined        SUBSET of the area
   [0, v]                       region above the curve      under the curve on
                                on [v, b]                   [0, v]
   ###  = area under x(z), which is exactly v·x(b) − p(b)
   ///  = area above x(z) on [v, b]: value you did not want at a price you paid

What it shows: the bidder’s realised utility as a signed area for the three possible reporting behaviours, with the truthful case as the reference. The insight: overbidding buys allocation in a range $[v,b]$ where the marginal price exceeds your value (the lined region is a strict loss), and underbidding forfeits allocation in $[b,v]$ where the marginal price is below your value (a strict forfeit). Truth is the unique report that collects all the surplus and none of the loss — and the picture makes it obvious that this holds for every $b_{-i}$, which is precisely the dominant-strategy quantifier. Fallback rationale: this is an area-comparison argument; mermaid has no diagram type that shades regions between a step function and a vertical line, so ASCII is used and should be upgraded to an embedded SVG in Attachments/ if this note is ever revisited.

Two forms of the same formula

Hartline states the Bayesian analogue with the integral on the other side (Theorem 2.5.1, part ii):

$p_i(v_i)=v_i{x}_i(v_i)-{\int }_0^{v_i}{x}_i(z)dz+p_i(0)$

This is Roughgarden’s (7) after integration by parts, and checking that is a two-line exercise worth doing once:

${\int }_0^{v}z{x}^{\prime }(z)dz=[zx(z){]}_0^v-{\int }_0^{v}x(z)dz=vx(v)-{\int }_0^{v}x(z)dz$

The second form is often the more useful one because it exhibits the bidder’s utility directly: $u_i(v_i)=v_i{x}_i(v_i)-p_i(v_i)={\int }_0^{v_i}{x}_i(z)dz$ (with $p_i(0)=0$), which is exactly the “area under the allocation curve” in the picture above. Roughgarden notes the same decomposition: “the social surplus contributed by this bidder ($v\cdot x(v)$) naturally splits into its utility (or ‘consumer surplus’), the area under the curve, and the seller revenue, the area above the curve.”

That identity is also, immediately, Revenue Equivalence: two mechanisms with the same allocation rule and the same payment at $v=0$ have the same payments everywhere.

flowchart TB
    A["Pick two reports<br/>0 ≤ y &lt; z"] --> B["Write DSIC twice:<br/>type z must not want to say y<br/>type y must not want to say z"]
    B --> C["Payment difference sandwich<br/>z·[x(y)−x(z)] ≤ p(y)−p(z) ≤ y·[x(y)−x(z)]"]
    C --> D{"Is x(y) &gt; x(z)<br/>for some y &lt; z?"}
    D -->|"yes — non-monotone"| E["Sandwich is unsatisfiable:<br/>needs a number ≥ zc and ≤ yc<br/>with z &gt; y, c &gt; 0<br/><br/>⇒ NO payment rule exists<br/>(part a, 'only if')"]
    D -->|"no — monotone"| F["Let y ↓ z<br/>jump in p = z × jump in x"]
    F --> G["Integrate from 0<br/>with p(0) = 0<br/><br/>⇒ formula is FORCED<br/>(part b: uniqueness)"]
    G --> H["Proof by picture:<br/>area comparison shows<br/>the formula actually works<br/>(part a, 'if' + part c)"]

What it shows: the logical skeleton of the derivation, with the branch that produces the impossibility half and the branch that produces the formula. What to take from it: uniqueness (part b) and existence (part a’s “if” direction) come from different steps — the algebra pins down the only candidate, and only the picture verifies that the candidate works. Skipping the second half is the standard way to convince yourself of a false theorem.

Worked example 1: the Vickrey auction, regenerated

Single item, allocation rule “highest bidder wins.” Fix $i$ and $b_{-i}$, and let $B={\max }_{j\ne i}{b}_j$. Then $x_i(z,b_{-i})$ is $0$ for $z<B$ and $1$ for $z>B$: a single jump of magnitude $1$ at $z=B$. Formula (6) has one breakpoint:

$p_i(b_i,b_{-i})=\{\begin{array}{ll}0& b_i<B\\ B\cdot 1=B& b_i>B\end{array}$

The winner pays the second-highest bid. Roughgarden: “Myerson’s Lemma regenerates the Vickrey auction as a special case.” For any 0-1 allocation rule the same argument gives the general statement: you pay your critical bid — “the lowest bid it could make and continue to win (holding the other bids $b_{-i}$ fixed)” (lecture 4). Nisan reaches the identical conclusion from the domain side (Thm. 9.36): a normalised mechanism on a single-parameter domain is incentive compatible iff $f$ is monotone in every $v_i$ and “every winning bid pays the critical value.”

Worked example 2: sponsored search, where the formula earns its keep

Now the case with no obvious answer. There are $k$ ad slots with click-through rates ${\alpha }_1\ge {\alpha }_2\ge \cdots \ge {\alpha }_k$; the allocation rule assigns the $j$th highest bidder to the $j$th best slot, so $x_i={\alpha }_j$ if $i$ lands in slot $j$. This is monotone — “raising your bid can only increase your position in the sorted order of bids, which can only net you a higher slot, which can only increase the click-through-rate” — so a unique DSIC payment rule exists. Find it by walking $z$ upward with the others fixed, re-indexed so $b_1\ge b_2\ge \cdots \ge b_n$:

• As $z$ rises past $b_{j+1}$, bidder $i$ overtakes bidder $j+1$ and moves from slot $j+1$ to slot $j$.
• The allocation therefore jumps by ${\alpha }_j-{\alpha }_{j+1}$ at the point $z=b_{j+1}$.

Feed those breakpoints into (6):

p_i(b) \;=\; \sum_{j=i}^{k} b_{j+1}\,(\alpha_j - \alpha_{j+1}), \qquad \alpha_{k+1} = 0 \tag{8}

and per click, dividing by ${\alpha }_i$:

p_i(b) \;=\; \sum_{j=i}^{k} b_{j+1}\,\frac{\alpha_j - \alpha_{j+1}}{\alpha_i} \tag{9}

Roughgarden’s reading of (9): “when its link is clicked, an advertiser pays a suitable convex combination of the lower bids.” The weights $\frac{{\alpha }_j-{\alpha }_{j+1}}{{\alpha }_i}$ are non-negative and sum to $1$ for the top bidder, so the price is genuinely an average of the bids below you — never your own.

Concretely, with $\alpha =(1,\frac{1}{2},\frac{1}{4})$ and bids $b=(2,\frac{15}{8},\frac{1}{8},0)$, the top bidder pays $\frac{15}{8}(1-\frac{1}{2})+\frac{1}{8}(\frac{1}{2}-\frac{1}{4})+0\cdot \frac{1}{4}=\frac{15}{16}+\frac{1}{32}=\frac{31}{32}$ in total, against $\frac{15}{8}$ under the generalised second-price rule that real ad systems use. GSP is a different rule with the same allocation rule, and by part (b) of the lemma exactly one of the two can be DSIC. It is not GSP. See Ad Auctions and GSP.

The Bayesian Twin of the Lemma

Everything above is the dominant-strategy story. The Bayes–Nash story has the same shape, which is the most useful structural fact in this note, and it is why the two notions feel similar even though their guarantees are not.

Move from ex-post quantities to interim ones — expectations conditioned on your own value, with the others’ drawn from the prior. Hartline’s notation (ch. 2, §2.4): $x_i(v_i)=\mathbb{E}[x_i(\mathbf{v})\mid v_i]$ is your interim allocation probability, $p_i(v_i)=\mathbb{E}[p_i(\mathbf{v})\mid v_i]$ your interim expected payment, $u_i(v_i)=v_i{x}_i(v_i)-p_i(v_i)$ your interim utility. Then:

Theorem (Hartline 2.5.1). When values are drawn from a continuous product distribution $F$, a single-dimensional game $(\tilde{x},\tilde{p})$ and strategy profile $b$ are in Bayes–Nash equilibrium only if for all $i$: (i) (monotonicity) $x_i(v_i)$ is monotone non-decreasing, and (ii) (payment identity) $p_i(v_i)=v_i{x}_i(v_i)-{\int }_0^{v_i}{x}_i(z)dz+p_i(0)$. If the strategy profile is onto, the converse also holds.

Monotonicity plus a payment identity, exactly as before — but now the monotone object is the interim allocation $x_i(v_i)$, a probability, rather than the ex-post $x_i(z,b_{-i})$ for every fixed $b_{-i}$. That is precisely the quantifier swap from the start of this note, appearing again at the level of the characterisation theorem.

Two consequences follow immediately.

Revenue equivalence. If two mechanisms induce the same interim allocation rule and agree on the payment of the lowest type, the payment identity forces them to agree everywhere. Nisan’s Theorem 9.46 says the same in his notation, and he flags the parallel explicitly: “the similarity to Theorem 9.37 should be noted: in both cases it is shown that the allocation rule determines the payments, up to a normalization. In the case of dominant strategy implementation, this is true for every fixed type of the other players, while in the case of Bayesian–Nash implementation, this is true in expectation.” His two-bidder check: second-price revenue is $\mathbb{E}[\min (a,b)]=\frac{1}{3}$ and first-price revenue is $\mathbb{E}[\max (a/2,b/2)]=\frac{1}{3}$ for $a,b\sim U[0,1]$. Same allocation rule (highest value wins), same revenue, wildly different bidding behaviour.

Truthfulness is not the source of the constraint. Notice that Hartline’s theorem is about any Bayes–Nash equilibrium of any single-dimensional game, truthful or not. The monotonicity and payment identity are properties of the equilibrium outcome, not of a truth-telling assumption. First-price auctions obey them just as much as second-price ones do. This is the revelation principle showing up as a structural fact rather than a proof technique.

Where the two theories genuinely diverge: the onto hypothesis in Hartline’s converse. A Bayes–Nash equilibrium’s guarantees rest on the whole profile being played; if a bidder plays a strategy that never emits some action, the interim quantities stop describing the game. The dominant-strategy version has no such hypothesis, because it never referred to anyone else’s strategy at all.

Measured: Is the Payment Rule Really Unique?

Part (b) of Myerson’s Lemma is a uniqueness claim, and uniqueness claims are the kind that feel true until you test them. Nisan’s Theorem 9.37 gives the exact leeway: an incentive compatible mechanism stays incentive compatible under $p_i^{\prime }(v)=p_i(v)+h_i(v_{-i})$, “and it turns out that this is the only leeway in the payment.” So the prediction is sharp and falsifiable:

• Add anything that depends only on the others’ reports → still DSIC.
• Add anything that depends on your own report, however small → broken.

The test perturbs the payment rule of a known-good mechanism (top-2-of-4 with Myerson payments, exact rationals, 9-point type grid) and re-runs the exhaustive misreport attack from Mechanism Design. 52,488 deviations per row.

Perturbation added to $p_i$	Depends on $b_i$?	Verdict	Profitable deviations	Max gain
nothing (baseline)	—	still DSIC	0 / 52,488	0
$+\frac{1}{2}$ (a flat fee)	no	still DSIC	0 / 52,488	0
$-\frac{3}{4}$ (a flat rebate)	no	still DSIC	0 / 52,488	0
$+\mathrm{mean}(b_{-i})$	no	still DSIC	0 / 52,488	0
$+\max (b_{-i})/5$	no	still DSIC	0 / 52,488	0
$+b_i/100$ (1% of own report)	yes	broken	17,592 / 52,488	$1/50$
$-b_i/100$ (1% own-report discount)	yes	broken	14,676 / 52,488	$1/50$
$+b_i/1000$ (0.1% of own report)	yes	broken	17,592 / 52,488	$1/500$
$+\frac{1}{4}$ if $b_i\ge \frac{3}{2}$ (“high bidder surcharge”)	yes	broken	6,561 / 52,488	$1/4$
$-\frac{1}{8}$ if $b_i\ge \frac{3}{2}$ (“loyalty discount”)	yes	broken	5,427 / 52,488	$1/8$

Restricting to tie-free profiles to rule out tie-breaking artefacts, the pattern is identical and the witnesses are cleaner: $p_i+b_i/1000$ leaves 4,536 of 15,120 deviations profitable (30% of situations exploitable), with a concrete witness — true value $2$, opponents $(0,\frac{1}{4},\frac{3}{4})$, reporting $\frac{1}{2}$ instead of $2$ raises utility from $\frac{437}{250}$ to $\frac{3499}{2000}$. Meanwhile $p_i+\mathrm{mean}(b_{-i})$ remains at 0 / 15,120.

Four things worth extracting.

1. The theorem’s boundary is exactly where it says it is. Not approximately, not mostly — the dividing line between the surviving perturbations and the fatal ones is precisely “does it read $b_i$.”
2. A 0.1% own-bid-dependent fee is fatal. This is the finding with real operational teeth. Any percentage fee levied on the bid rather than on the price destroys truthfulness. It does not degrade it gracefully; it creates a profitable deviation in 30% of situations. Percentage fees on the realised price are fine (that is a function of $b_{-i}$); percentage fees on the submitted bid are not.
3. Tiered pricing is a trap. The “high bidder surcharge” and “loyalty discount” rows are the shape of every volume-tier and priority-tier scheme ever added to an internal quota system. Both are functions of your own declaration, both break truthfulness, and the loyalty discount breaks it in the direction of over-claiming — a bidder with true value $0$ profits by declaring $\frac{3}{2}$.
4. Flat fees and rebates are free. The $-\frac{3}{4}$ row is worth noting separately: it destroys individual rationality for low types (they can end up paying nothing and receiving a subsidy, or in a fee variant, paying more than their value) without touching incentive compatibility at all. The two properties really are independent, and a change that violates one may leave the other untouched.

Uncertain

Verify: whether $h_i(v_{-i})$ perturbations are harmless in general or only on this connected, bounded grid. Reason: Nisan’s Theorem 9.37 assumes “the domains of preference $V_i$ are connected sets in the usual metric in the Euclidean space,” and he notes the assumption is essential — “if the valuations are restricted to be integral, then modifying $p_i$ by any small constants $ϵ<1/2$ will not modify incentive compatibility,” so on a discrete domain there is strictly more leeway than the theorem’s continuous statement allows. The measurements above are on a discrete grid and therefore test the easier direction. To resolve: repeat with a perturbation smaller than the grid step that does depend on $b_i$ (e.g. $+b_i/10^6$ on a step-$\frac{1}{4}$ grid) and check whether it survives, as the discrete-domain caveat predicts it might not, since the perturbation is still monotone in $b_i$. #uncertain

Failure Modes and Gotchas

Testing with floating point. Incentive-compatibility violations live exactly at the breakpoints of the allocation curve, which is precisely where two utilities are equal. A comparison u_lie > u_true on doubles will report phantom violations for a correct mechanism and, worse, miss real ones whose magnitude is near the rounding error. Every number in the measurements above is a fractions.Fraction, and this machine has no numpy, no pip, and no gambit — the standard library is not a fallback here, it is the right tool.

Multiplying by the reported value instead of the true one. The single most common bug in a strategyproofness test:

u_lie = lie * alloc(b_lie)[i] - pay(b_lie)[i]     # WRONG
u_lie = v   * alloc(b_lie)[i] - pay(b_lie)[i]     # right

The first line computes the utility of a bidder who actually had value lie, which is a different bidder. It makes every mechanism look truthful, because you have accidentally re-derived the tautology that reporting $v$ is optimal for someone whose value is $v$.

Checking only unilateral deviations and calling it strategyproof. DSIC quantifies over one player deviating. It says nothing about two players coordinating (group strategy-proofness) and nothing about one player registering twice (false-name-proofness). Milgrom and Segal list group strategy-proofness among the properties that made deferred-acceptance clock auctions preferable to Vickrey for the FCC (Milgrom & Segal 2017). In any system with free account creation, unilateral DSIC is close to worthless — this is the Sybil problem under a different name.

Assuming quasi-linearity survives a budget cap. Myerson’s Lemma and everything above assume $u_i=v_i{x}_i-p_i$ with no wealth effects. A bidder with a hard budget $B$ has utility $-\infty$ for $p_i>B$, which is not quasi-linear, and Roughgarden devotes a whole lecture to what breaks (lecture 9, “Beyond Quasi-Linearity”). Every internal cloud-quota scheme has budget caps. The guarantees do not transfer.

Treating a single-parameter result as a general one. Myerson’s Lemma is only about single-parameter environments. In multi-parameter domains the right condition is weak monotonicity (Nisan Def. 9.28: $f(v_i,v_{-i})=a\ne b=f(v_i^{\prime },v_{-i})$ implies $v_i^{\prime }(a)-v_i^{\prime }(b)\ge v_i(a)-v_i(b)$), which is necessary always and sufficient only on convex domains — “it is known that WMON is not a sufficient condition for incentive compatibility in general nonconvex (more precisely, nonsimply connected) domains.” Nisan flags the interesting middle as open: “the intermediate range where the $V_i$‘s are somewhat restricted, a range in which most computationally interesting problems lie, is still wide open.”

Assuming that “no profitable deviation found” means DSIC. It means DSIC on the tested grid, against the deviations enumerated. The grid in these experiments has 9 or 17 points; a real type space is continuous. Exhaustive enumeration is a sharp instrument for finding bugs and a blunt one for proving their absence.

Forgetting that indifference is not safety. The definition is a weak inequality, so a mechanism can be DSIC while leaving a bidder completely indifferent across a range of reports. Vickrey overbidding is the standard case: bid anything above the second price and nothing changes. Those indifferent regions are where collusive and non-truthful equilibria live, and where “unique dominant strategy” and “dominant strategy” come apart.

Approximating the allocation rule after fixing the prices. If you compute prices from an exact optimisation and then swap in an approximation, the incentive guarantee does not degrade proportionally. Milgrom and Segal’s estimate for the FCC reverse auction is the sharpest published number on this: “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.”

Alternatives and When to Choose Them

Incentive compatibility is not a binary you either have or lack. It is a ladder of strengths, and the engineering question is which rung you can afford.

Strength	The guarantee	Costs	Choose it when
Obvious strategy-proofness	Truth is dominant and the participant can see that it is, without contingent reasoning. Li’s (2017) definition, as quoted by Milgrom & Segal: a strategy is obviously dominant if at every information set where it differs from an alternative, its worst outcome is at least as good as the alternative’s best	Usually forces an indirect, multi-round format; more communication rounds	Participants are humans with no analytics team. The FCC’s stated reason for a clock auction: “the obviously strategy-proof DA clock auction would make it easy to decide to participate and bid”
Group strategy-proofness	No coalition gains by jointly misreporting	Rules out VCG. Milgrom & Segal’s counterexample: a Vickrey auction acquiring stations 1 and 3 pays $v_2-v_3$ and $v_2-v_1$, so “bidders 1 and 3 could cooperate to increase those by bidding less than their station values”	Collusion is cheap and detection is hard — small bidder pools, repeated interactions, shared ownership
DSIC	Truth is dominant	Often nonexistent (Gibbard–Satterthwaite, Roberts); forfeits budget balance with efficiency	The default target whenever it exists. Buy it if you can
Ex-post Nash	Truth is a best reply for every realised type profile, given others follow their strategies	Needs others to be rational, not just present	Nearly free relative to DSIC — Nisan Prop. 9.23 shows the gap is only unused actions
BNIC	Truth is a best reply in expectation under a common prior	Needs the prior to be right and commonly known; strategies move with $n$	You genuinely know the distribution, or you inherited the mechanism
$\epsilon$-IC / approximate IC	Lying gains at most $\epsilon$	No hard guarantee; $\epsilon$ can compound across repeated play	Large markets where individual influence vanishes; when exact IC is provably unattainable
None, plus monitoring	Detect and punish rather than prevent	Ongoing operational cost; adversarial arms race	The private information is verifiable. Then audit it and skip this entire theory

That last row is the one to reach for first in a systems context. Incentive compatibility is the theory of unverifiable claims. If you can measure the thing rather than ask about it — actual cache hit rate rather than declared priority, observed job runtime rather than requested slot, historical traffic rather than a forecast — verification strictly dominates incentive engineering, because it removes the constraint instead of designing around it.

flowchart TB
    Q0{"Can you verify<br/>the private<br/>information?"}
    Q0 -->|yes| VER["Measure it.<br/>The IC constraint<br/>does not apply."]
    Q0 -->|no| Q1{"Is the environment<br/>single-parameter?"}
    Q1 -->|yes| MYE["Myerson's Lemma applies.<br/>Check monotonicity of x.<br/>Monotone ⇒ price at the<br/>critical value and you are done.<br/>Non-monotone ⇒ redesign x;<br/>no pricing can save it."]
    Q1 -->|no, multi-parameter| Q2{"Is welfare<br/>the objective?"}
    Q2 -->|yes| VCG["VCG / Groves.<br/>Accept the budget deficit,<br/>the collusion exposure,<br/>and the exact optimisation."]
    Q2 -->|no| Q3{"Unrestricted<br/>valuation domain?"}
    Q3 -->|yes| ROB["Roberts' theorem:<br/>only affine maximisers are DSIC.<br/>Your objective is out of reach."]
    Q3 -->|no| WMON["Weak monotonicity is necessary;<br/>sufficient only on convex domains.<br/>Nisan: this middle range is<br/>'still wide open'."]

What it shows: the actual decision procedure for “can I make this truthful,” ordered by how much it costs to find out. What to take from it: the monotonicity check in the second box is cheap and decisive, and it is the step most designs skip — they build the allocator, discover the pricing does not work, and conclude the pricing was the problem.

Production Notes

Deferred-acceptance clock auctions: choosing a weaker mechanism on purpose

The FCC’s 2017 Incentive Auction reallocated UHF spectrum through a reverse auction costing about $10.1billion\ast \ast andaforwardauctionraisingabout\ast \ast$19.8 billion (Milgrom & Segal 2017). Vickrey — the textbook DSIC answer — was rejected, and the reasoning is the best real-world illustration of everything in this note.

The obstacle was that repacking the roughly 2,815 surviving stations satisfies “more than a million constraints,” and checking feasibility of any given repack is NP-hard. Vickrey prices require near-exact optimisation, and the error amplification is brutal: “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.”

What was built instead is a descending clock auction: prices fall, a bidder whose price falls may exit, non-exiting bidders win at their last clock price. Its incentive properties are a deliberate trade:

• It is obviously strategy-proof, not merely DSIC. A broadcaster does not need to reason about the mechanism at all — the rule is “exit when the price drops below your value,” and its worst case dominates any alternative’s best case.
• It is weakly group strategy-proof, which Vickrey is not — the paper gives the explicit two-bidder collusion against Vickrey quoted in the table above.
• It preserves winners’ privacy: a winner’s value is never revealed, because they never had to state it.
• It gives up exact efficiency, and in simulations “leads to nearly efficient outcomes at a lower cost than a Vickrey auction while using a fraction of the computational effort.”

The pattern generalises: when the exact mechanism is computationally out of reach, the answer is not a worse approximation of it but a different mechanism whose incentive guarantee does not depend on solving the hard problem.

Sponsored search: shipping a non-truthful mechanism on purpose

Sponsored search “generate[d] roughly 98% of Google’s revenue” around 2006 and still “tens of billions of dollars of revenue every year” (Roughgarden lecture 2). The deployed rule, GSP, is provably not DSIC — Myerson’s Lemma part (b) settles it in one line, because GSP has the same allocation rule as the DSIC mechanism and a different payment rule, and only one payment rule can be truthful. The exhaustive attack in Mechanism Design finds profitable deviations in 24% of tie-free situations, with the canonical exploit being deliberate self-demotion: an advertiser with value $2$ facing bids $(0,\frac{1}{8},\frac{15}{8})$ earns $\frac{1}{8}$ by honestly taking the top slot and $\frac{15}{16}$ by bidding $\frac{1}{4}$ and taking the second.

It ships anyway because the participants are automated bidders in a market that clears millions of times per day, so equilibrium-finding is cheap and continuous. Truthfulness is a usability property, and its value is proportional to how expensive strategising is for your participants. Against bots, it is worth much less than against humans; the FCC’s broadcasters were humans.

Matching: strategyproof on one side only

Deferred acceptance is the vault’s live example of the concept. It escapes Gibbard–Satterthwaite not with money but by restricting the preference domain to rankings, and the resulting mechanism is strategyproof for the proposing side and provably not for the receiving side. That asymmetry is not an implementation defect; it is a theorem, and it determines who benefits from a real deployment — which is why the question “who proposes?” is the first one to ask about any matching market. See Proposer-Optimality and Strategic Truncation and Hospital-Residents and the NRMP.

Where the vault’s own systems sit

• Multi-Tenancy and Fairness in LLM Serving — a declared-priority scheme is a direct revelation mechanism whose allocation rule you can check for monotonicity in about a minute. If the allocation is monotone in the declared priority and the price is the critical priority, it is truthful; if the price is a function of the declared priority (a tier), the measurements above say it is not.
• Rate Limiting as a Mechanism — quota requests are reports. Ask whether requesting more can ever get you less, and whether the charge depends on what you asked for or on what everyone else asked for.
• Stock Exchange Order Matching System Design — price-time priority is a monotone allocation rule with a pay-your-bid payment rule, which the measurements above put in the same category as the first-price auction: shading is rational and universal, which is exactly what real order books show.
• The Completely Fair Scheduler and Its History — a process that sleeps to accumulate vruntime deficit is misreporting its type to a mechanism nobody designed to resist it.

See Also

• Mechanism Design — the parent concept: the anatomy of a mechanism, the four properties, and the impossibility results that constrain them
• The Revelation Principle — why it suffices to study mechanisms in which truth is an equilibrium
• The VCG Mechanism — the general multi-parameter DSIC construction for welfare maximisation
• Why VCG Is Rare in Practice — collusion, revenue deficiency, and computational cost, with the FCC as the case study
• Impossibility Results — Gibbard–Satterthwaite, Roberts, Green–Laffont, Myerson–Satterthwaite
• The Vickrey Auction — the single-item case that Myerson’s Lemma regenerates in two lines
• First-Price and Second-Price Auctions and Revenue Equivalence — where the BNIC/DSIC distinction is most visible
• Ad Auctions and GSP — the deployed, provably non-truthful mechanism
• Approximate and Simple Mechanisms — monotone approximation algorithms, and why an arbitrary approximation is not implementable
• Bayesian Games and Types — the Harsanyi type machinery underlying BNIC
• Nash Equilibrium and Dominant Strategies and Iterated Elimination — the underlying solution concepts; DSIC is dominance applied to a designed game
• The Gale-Shapley Algorithm and Stable Matching — strategyproofness without money, one side only
• Games and Strategic Systems in C MOC — parent map; this note is the second rung of P7