5D Library › Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering · 中文
Chapter 1 The Revelation Principle, Incentive Compatibility and Commitment
What a mechanism is
Mechanism design treats a rule as a machine. Each participant has a type known only to himself (his value for an object, his cost of a task, his preference over a public project); he submits a message , and the machine applies a publicly announced outcome function (who gets what, who pays how much). The designer has in mind a social choice function , “the outcome I would want if I knew everyone’s type”. The question is whether can be designed so that when participants choose messages in their own interest, the equilibrium outcome is exactly . If so, the mechanism implements .
All the auctions in this book assume private values (each person’s value depends only on his own type) and quasi-linear utility: a participant who receives outcome and pays gets . These two assumptions fix the scope of most results below. Book 27 introduced the “reverse game theory” viewpoint through cake-cutting, auctions and public goods; here we go straight to the theorems. Systematic textbook treatments include Börgers’s introduction to mechanism design, the auction-theory monographs of Krishna and of Milgrom, and the Algorithmic Game Theory volume (Börgers 2015; Krishna 2010; Milgrom 2004; Nisan et al. 2007).
Two versions of the revelation principle
A direct mechanism is one whose message space is the type space: each person reports a type and the machine computes the outcome from the reports. If truthful reporting is an equilibrium of it, the direct mechanism is incentive compatible.
Theorem (dominant-strategy version). If the mechanism has a dominant-strategy equilibrium with for all , then the direct mechanism itself is dominant-strategy incentive compatible: truthful reporting is a dominant strategy for everyone.
Proof. Let ’s true type be ; he reports and the others report arbitrary . In the direct mechanism he receives . Since is optimal in the original mechanism against any messages of the others, in particular against ,
the left side is the utility of reporting truthfully and the right side the utility of reporting . Done.
Theorem (Bayesian version). If types are drawn from a common prior and has a Bayes–Nash equilibrium with , then the direct mechanism is Bayesian incentive compatible: when the others report truthfully, each person’s expected utility is highest when he reports truthfully.
Proof. As above, replacing “against any messages of the others” by “in expectation over the conditional distribution of the others’ types”: given , maximises expected utility, so no other message does better. Done.
Both proofs amount to “let the machine play your equilibrium strategy for you”: the direct mechanism merely composes the original mechanism with the participants’ equilibrium strategies. The dominant-strategy version was given by Gibbard in 1973 in the setting of voting (Gibbard 1973); the Bayesian version was formulated independently by Myerson (1979), Dasgupta, Hammond and Maskin (1979), Harris and Townsend (1981) and others (Myerson 1979; Dasgupta et al. 1979; Harris and Townsend 1981). In his Nobel lecture Myerson summarised its significance: in searching for the best rule one may, without loss of generality, consider only truthful direct mechanisms (Myerson 2008).
Note
The two kinds of incentive compatibility. Dominant-strategy incentive compatibility requires neither knowledge of the distribution of others’ types nor belief that others tell the truth; Bayesian incentive compatibility only requires that truth be best on average when others are truthful and one knows only the distribution. The latter is much weaker: in any particular round, someone who knows the others’ reports can often gain. The program below illustrates this with the first-price auction of Book 27.
The program takes a first-price auction with two bidders whose values are independent and uniform on . Book 27 derived the equilibrium bid . Composing it with the auction gives a direct mechanism: report ; the highest report wins and pays . A type who reports has expected utility , maximised at , so the mechanism is Bayesian incentive compatible; but a bidder with value 0.8 who knows that the rival reports 0.3 need only report a little above 0.3. The second part of the program concerns commitment and is discussed in the next section.
Calculation
# Chapter 1. (A) The Bayesian revelation principle, checked on a grid: take the
# first-price auction with two bidders, values i.i.d. U[0,1], whose Bayes-Nash
# equilibrium is b(v) = v/2 (Book 27). The "direct" mechanism composes the strategy with
# the auction: report r, highest report wins and pays r/2. Truth is optimal in
# expectation (Bayesian IC) but NOT a dominant strategy: against a known rival report,
# shading pays. (B) Commitment: one buyer, v ~ U[0,1], T selling periods, discount d.
# With commitment the seller posts p = 1/2 once (revenue 1/4, Myerson / Riley-Zeckhauser).
# Without commitment she re-prices after each refusal and the buyer anticipates it (the
# Coase problem). Backward induction: with remaining types [0, k], continuation revenue
# is c_t k^2 and the price a_t k; type kappa is indifferent between buying now and next
# period: kappa - p = d (kappa - a_{t+1} kappa).
G = [i / 1000 for i in range(1001)]
def bayes_utility(v, r): # P(win) = P(rival value < r) = r; pay r/2 if win
return r * (v - r / 2)
def expost_utility(v, r, rival_report):
return (v - r / 2) if r > rival_report else 0.0
def no_commitment(d, T):
a, c = 0.5, 0.25 # last period: price k/2, revenue k^2/4
for _ in range(T - 1):
m = 1 - d + d * a # p = m * kappa keeps type kappa indifferent
s = m / (2 * m - 2 * d * c) # optimal new cutoff kappa = s k
a, c = m * s, m * s * (1 - s) + d * c * s * s
return c, a # revenue from k = 1, first-period price
if __name__ == "__main__":
worst = max(abs(max(G, key=lambda r: bayes_utility(v, r)) - v) for v in G[::10])
print(f"(A) Bayesian IC: largest gap, best report vs true value = {worst:.3f}")
v, rival = 0.80, 0.30
best = max(G, key=lambda r: expost_utility(v, r, rival))
print(f" ex post, value {v}, rival report {rival}: truth earns"
f" {expost_utility(v, v, rival):.3f}; report {best:.3f} earns"
f" {expost_utility(v, best, rival):.3f}")
k2 = max(G, key=lambda k: k * (1 - 0.9 / 2) * (1 - k) + 0.9 * (k / 2) ** 2)
print(f"(B) two periods, d = 0.9: grid cutoff {k2:.3f}; closed form (2-d)/(4-3d)"
f" = {(2 - 0.9) / (4 - 3 * 0.9):.4f}")
print(" revenue without commitment (commitment: 0.2500 for every d and T)")
print(" periods T: 1 2 5 20 100 1000")
for d in (0.5, 0.9, 0.99):
row = [no_commitment(d, T) for T in (1, 2, 5, 20, 100, 1000)]
print(f" d = {d:<5}" + "".join(f"{c:8.4f}" for c, _ in row))
c, a = no_commitment(0.99, 1000)
print(f" d = 0.99, T = 1000: first price {a:.4f}, revenue {c / 0.25:.1%}"
" of the commitment value")
# (A) Bayesian IC: largest gap, best report vs true value = 0.000
# ex post, value 0.8, rival report 0.3: truth earns 0.400; report 0.301 earns 0.650
# (B) two periods, d = 0.9: grid cutoff 0.846; closed form (2-d)/(4-3d) = 0.8462
# revenue without commitment (commitment: 0.2500 for every d and T)
# periods T: 1 2 5 20 100 1000
# d = 0.5 0.2500 0.2250 0.2084 0.2071 0.2071 0.2071
# d = 0.9 0.2500 0.2327 0.1926 0.1269 0.1201 0.1201
# d = 0.99 0.2500 0.2476 0.2405 0.2084 0.1028 0.0455
# d = 0.99, T = 1000: first price 0.0909, revenue 18.2% of the commitment valueThe first line confirms that on a grid from 0 to 1 with step 0.001, every type’s best report equals its true type (gap 0.000). The second shows that the mechanism is not dominant-strategy incentive compatible: knowing that the rival reports 0.3, truth earns 0.400 and reporting 0.301 earns 0.650. The Bayesian revelation principle turns the first-price auction into a mechanism in which truth is “best on average”, but it cannot turn it into one in which truth is “best whatever happens”; that requires changing the payment rule itself, that is, the second-price rule.
What the revelation principle does not say
The revelation principle is an equivalence result, and its force comes from its assumptions. There are at least five things it does not guarantee.
First, uniqueness of equilibrium. It guarantees only that truth-telling is an equilibrium, not that there is no other equilibrium that is bad for the designer. Requiring every equilibrium to yield is the problem of full implementation; Maskin proved that a social choice rule implementable in Nash equilibrium under complete information must satisfy a monotonicity condition (since called Maskin monotonicity) (Maskin 1999). The collusion among losers in VCG discussed in Book 27 is one form of multiple equilibria.
Second, commitment. “The machine plays your strategy for you” presupposes that the designer will not change the rules after seeing the reports. If she can renegotiate or revise them, participants foresee it and the principle has to be restated: Bester and Strausz proved that with a single agent and imperfect commitment one can still restrict attention to direct mechanisms whose message space is the type space, but one can no longer assume that the agent reports truthfully (Bester and Strausz 2001). The clearest example is the Coase problem (Coase 1972). A seller faces one buyer with value . If she can commit, her best course is to post the price 1/2 once and never cut it, for expected revenue 1/4 (with commitment the optimal selling mechanism is a posted price; see Riley and Zeckhauser (Riley and Zeckhauser 1983)). But if she can cut the price after a refusal, the buyer will wait, and she can only sell along a sequence of falling prices.
The second part of the program solves the linear equilibrium with periods and discount factor by backward induction: with remaining types the continuation revenue is and the price , and the marginal type is indifferent between buying now and waiting one period: . With two periods and the grid search finds the cutoff 0.846, agreeing with the closed form . The table shows that with revenue falls from 0.2500 with one period to 0.2327 with two and 0.1926 with five, tending to 0.1201 with many; with and 1,000 periods revenue is only 0.0455, 18.2 % of the commitment revenue, and the first-period price only 0.0909. This is the Coase conjecture proved by Gul, Sonnenschein and Wilson: the more periods and the cheaper waiting is, the closer a monopolist who cannot commit comes to pricing at marginal cost (Gul et al. 1986). A rule-maker who cannot bind her own future conduct will not have her rules taken seriously.
Third, communication and privacy. A direct mechanism asks each person to report his entire type. In a package auction with items, a type is a list of values for packages; reporting it is impractical and gives away business secrets. Among Rothkopf’s thirteen reasons why VCG is impractical is that bidders do not want to reveal their true values to the auctioneer, fearing that the auctioneer or later negotiating partners will exploit them (Rothkopf 2007; Rothkopf et al. 1990). In practice indirect mechanisms (such as clock auctions with rising prices) are used; they are only “equivalent” to some direct mechanism in theory.
Fourth, participation and budget. Incentive compatibility is only one constraint. Whether participants are willing to take part (individual rationality) and whether the designer must subsidise (budget balance) can conflict with incentive compatibility and efficiency; Chapter 5 is devoted to this.
Fifth, whether participants can see the dominant strategy. That a dominant strategy exists does not mean people use it. Kagel, Harstad and Levin found in the laboratory that bidders in sealed second-price auctions systematically bid above their values (Kagel et al. 1987); Shengwu Li introduced the notion of “obviously strategy-proof” mechanisms and showed experimentally that, although truth-telling is dominant in both, an ascending clock auction elicits more dominant-strategy play than a sealed second-price auction (Li 2017). Chapter 8’s experiment builds on this.
Evidence
The Gibbard–Satterthwaite theorem (Gibbard 1973; Satterthwaite 1975) is the negative counterpart of the revelation principle “without money”: with at least three alternatives, unrestricted preferences and a social choice function whose range is all alternatives, the only dominant-strategy incentive-compatible rules are dictatorships. Quasi-linear utility allows payments to balance incentives, which is why VCG can exist; Chapter 5’s Roberts theorem shows that even with payments, the rules that can be implemented on an unrestricted domain of valuations are quite limited.
Hypothesis · not established · Committable points rules
The author’s hypothesis (not established): in online communities, points rules that are published in advance and technically committed against retroactive change (for example by a third-party timestamp of each rule version) elicit more truthful reports of contributions and less “waiting for the rules to change” than rules applied at the moderators’ discretion after the fact. What would show it wrong: in a pre-registered randomised comparison (with communities as units, independent of the author’s communities), a confidence interval for the difference in verified truthful-report rates that includes zero or favours discretionary rules. The book does not run this test.
Chapter summary
The revelation principle says that the equilibrium outcome of any mechanism can be obtained from a direct mechanism in which people report truthfully; the proofs of the dominant-strategy and Bayesian versions both “load” the equilibrium strategies into the machine. It lets mechanism design study only incentive-compatible direct mechanisms, but it does not make the equilibrium unique, relies on the designer’s ability to commit, asks for complete types, and does not ensure that participants can see the dominant strategy. The program shows that the direct mechanism built from a first-price auction is only Bayesian incentive compatible, and that a seller who cannot commit not to cut her price earns, with many periods and cheap waiting, only a small part of the commitment revenue (18.2 % with and 1,000 periods).
References
Fan, Y. (2026). Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering: From Myerson's Optimal Auction and the Hurwicz Impossibility Theorem to Sybil-Resistant Reputation Games, Read Beside Classical Legalist Treatises on Rewards and Incentives [机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836274 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).