5D Library › Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering · 中文

Preface: Making the Truth the Best Choice

Note

Purpose and scope: please read this first. This book presents mathematical models and a review of the literature for teaching and research. It is not legal, business, investment, marketing or platform-compliance advice. Every bid, valuation, community, point, badge, identity and reputation figure in the book is fictional or simulated, not data from any real platform, advertising system, community or business. The auction and community rules in the book hold only under the assumptions stated; real platforms are also bound by law, tax, privacy and competition rules. Bid rigging, collusive tendering, fake orders, fake identities and manipulated ratings are illegal or against platform rules in many jurisdictions; the book analyses them only as weaknesses of mechanisms and gives no instructions for carrying them out. The book makes no promise of anything that “guarantees”, “always wins” or “raises conversion by X %”.

A platform wants to sell a few advertising slots to dozens of advertisers; it would like each to bid truthfully, so that each slot goes to whoever values it most. An online learning community wants to use points and badges to encourage members to answer questions and share, without some members farming points or opening second accounts to like their own posts. A broker wants to know the true reservation prices of creators and brands, but both sides have reasons to hide them. The three share one question: can a set of rules be designed so that each person, acting in his own interest, does exactly what the designer wants him to do? Mechanism design exists to answer that question, and its landmark results are both constructive (the Vickrey–Clarke–Groves mechanism makes truth-telling a dominant strategy) and negative (some combinations of goals cannot be met by any rule at all). This book asks which of the claims in the author’s framework can be proved rigorously, which need their conditions stated, and which are popular misreadings.

Answering takes four layers of tools. The first is the revelation principle: why it is enough to study mechanisms that ask people to report their private information directly, and what this simplification relies on (above all, the ability to commit). The second is auctions: multi-item VCG, the generalized second-price (GSP) auction of search advertising, and Myerson’s revenue-maximizing auction. The third is impossibility: under what conditions efficiency, truth-telling, voluntary participation and a balanced budget cannot all be had. The fourth is communities: points and badges as a kind of money and as signals, and how rules break when one person can cheaply register many identities.

What the book covers

Chapter 1 proves the dominant-strategy and Bayesian versions of the revelation principle and uses a program to show its dependence on commitment; Chapter 2 treats VCG with many items and package bids: pricing of externalities, the core, and false-name bidding (the Sybil attack of auctions); Chapter 3 treats GSP and VCG in position auctions, locally envy-free equilibria and revenue comparisons; Chapter 4 derives Myerson’s optimal auction, virtual values and the optimal reserve, the Bulow–Klemperer theorem and ironing for non-regular distributions; Chapter 5 treats Hurwicz’s 1972 impossibility for exchange economies, the Green–Laffont uniqueness of Groves mechanisms and their budget imbalance, and Roberts’ affine-maximiser theorem; Chapter 6 treats points inflation in communities, behavioural evidence on badges, reputation systems and Sybil attacks; Chapter 7 reads these beside passages on reward, punishment and settled shares in the Book of Lord Shang (“Rewards and Punishments”, “Fixing Shares”), the Lüshi chunqiu, the Han Feizi and the History of the Former Han; and Chapter 8 offers a four-step checklist and a pre-registered, incentivised laboratory experiment.

The book neighbours several others in 5D Library; where they overlap, it only recaps briefly, cites the earlier book and does not repeat its programs. Book 27, on mechanism design, incentive compatibility and negotiation games, is this book’s predecessor: it treated the idea of the revelation principle, the weak dominance of truthful bidding in Vickrey’s second-price auction (verified by program over 1,030,301 combinations), the first-price equilibrium bid b=(n−1)v/nb = (n-1)v/n, revenue equivalence, the possibility of zero VCG revenue and its fragility to collusion among losers, the four conditions of the Myerson–Satterthwaite theorem and the figure 84.375 %, the budget imbalance of the Clarke pivot mechanism, Goodhart’s law and the “names and realities” of reward and punishment in the Han Feizi (“The Two Handles”). This book only recaps those points; its new material is multi-item auctions and false-name bidding, GSP equilibria, the full derivation of the optimal auction with ironing, the impossibility results of Hurwicz, Green–Laffont and Roberts, and community points and Sybil attacks. Book 24, on attention networks, working-memory bottlenecks and the self-determination theory of intrinsic motivation, treated the crowding-out of intrinsic motivation by external rewards (Chapter 6 only recaps). Book 32, Algorithmic Game Theory, Braess’s Paradox and the Price of Anarchy in Traffic and Attention Networks, treated the price of anarchy, multi-armed bandits and the Gale–Shapley algorithm, but not GSP. Book 35, on evolutionary games, direct and indirect reciprocity and the emergence of cooperation, treated reputation norms such as image scoring, simple standing and stern judging (Chapter 6 only recaps). Book 33, Scientific Methodology, Falsifiability and the Mathematical Statistics of the Replication Crisis, treated pre-registration, power and decision rules (Chapter 8 follows it).

Claims corrected after checking

Several points in the author’s framework needed correcting, supplementing or qualifying after checking. Each chapter says so where it arises, and the accompanying editorial notes list them together.

  1. “A rigorous proof of the revelation principle”. The principle has two versions: the dominant-strategy version (Gibbard 1973 (Gibbard 1973)) and the Bayes–Nash version (Myerson 1979, Dasgupta, Hammond and Maskin 1979, Harris and Townsend 1981 (Myerson 1979; Dasgupta et al. 1979; Harris and Townsend 1981)). Both proofs are short and the book gives them; but it must also say what the principle does not say. It guarantees only that “some truthful direct mechanism yields the same outcome”, not that truth-telling is that mechanism’s only equilibrium (the problem of full implementation (Maskin 1999)); and it assumes the designer can commit to the rules, so the result must be restated when commitment is imperfect (Bester and Strausz 2001). The program shows that a seller who cannot commit not to cut her price earns, over 1,000 periods with a discount factor of 0.99, only 18.2 % of the commitment revenue (the Coase problem (Coase 1972; Gul et al. 1986)) (Chapter 1).
  2. “VCG is the ideal mechanism”. With private values and quasi-linear utility VCG makes truth-telling a dominant strategy and is efficient (Vickrey 1961; Clarke 1971; Groves 1973); the program checks this with 20,000 misreports in a three-item package auction. But its revenue can fall below the core (12 against 13 in the example), and it is not robust to false-name bids: Yokoo, Sakurai and Matsubara proved that VCG cannot withstand a bidder bidding under several identities, and that no package-auction rule is both Pareto efficient and false-name-proof (Yokoo et al. 2004). In the example, one bidder splitting into two identities cuts his payment from 8 to 0. Their sufficient condition, “the surplus function is concave over bidders”, must hold over the whole domain of types; the program shows that checking only the real bidders is not enough (of the 406 markets in which it holds for the real bidders, 169 still admit a profitable split) (Chapter 2).
  3. GSP and “truth-telling is not a dominant strategy”. True, and it can be put more strongly: in GSP truth-telling is generally not even an equilibrium (it is one in only 0.0–4.2 % of random instances). Edelman, Ostrovsky and Schwarz and Varian proved that the revenue of locally envy-free (symmetric Nash) equilibria is at least that of VCG, and the lowest of them reproduces the VCG outcome exactly (Edelman et al. 2007; Varian 2007); in the example equilibrium revenue runs from 920 to 1,000. “GSP earns at least as much as VCG” is guaranteed only for this class of equilibria; other Nash equilibria can earn as little as 605, or more than VCG (up to 1,355 in the example). In the laboratory the two rules give similar revenue and efficiency (Fukuda et al. 2013). In 2019 Google moved Ad Manager (display advertising) to a unified first-price auction (Bigler 2019); this did not concern search advertising, and the book mentions it only in a note (Chapter 3).
  4. Myerson’s optimal auction and “the optimal reserve”. The virtual value ψ(v)=v−(1−F(v))/f(v)\psi(v) = v – (1-F(v))/f(v) and “expected revenue equals expected virtual surplus” are as stated (Myerson 1981); but “a second-price auction with reserve ψ−1(0)\psi^{-1}(0) is the optimal auction” holds only when bidders are identically distributed and the distribution is regular (ψ\psi increasing). That the uniform distribution gives a reserve of 1/2 whatever the number of bidders checks out. Non-regular distributions require “ironing”; in the program’s example the optimal auction earns 1.4–3.3 % more than a second-price auction with the best reserve. With differently distributed bidders the optimal auction is not a second-price auction with a reserve either. The Bulow–Klemperer theorem likewise assumes identical, regular distributions (Bulow and Klemperer 1996) (Chapter 4).
  5. “The Hurwicz impossibility theorem”. Hurwicz’s 1972 result has a definite scope: in a pure exchange economy with two people and two goods and classical preferences, there is no mechanism under which truthful reporting is an equilibrium at every preference profile (with private values, equivalent to dominance) and whose outcome is always Pareto efficient and individually rational (Hurwicz 1972). It is not a general theorem that “incentive compatibility is impossible”. Zhou later proved that in two-person exchange economies every efficient, strategy-proof mechanism must be “dictatorial” in the sense that one person always gets nothing, without any individual-rationality condition (Zhou 1991) (Chapter 5).
  6. Green and Laffont 1977. That paper proves that when valuations are unrestricted, the efficient, dominant-strategy incentive-compatible mechanisms are exactly the Groves family (Green and Laffont 1977) (Holmström 1979 extended this to smoothly connected restricted domains (Holmström 1979)). “Groves mechanisms generally cannot balance the budget” is a separate result in the same line of work (Green and Laffont’s 1979 monograph and Walker 1980 (Green and Laffont 1979; Walker 1980)); relaxing to Bayesian incentive compatibility, efficient mechanisms with a balanced budget exist (d’Aspremont and Gérard-Varet 1979). The program gives the minimum imbalance in a two-person public project and shows that when valuations have mean zero the Clarke taxes do not shrink relative to welfare as the number of people grows (they stay at about 42–50 % of total welfare) (Chapter 5).
  7. Roberts’ 1979 theorem requires at least three alternatives, an unrestricted domain of (arbitrary real) valuations and an onto rule. Under these conditions every social choice function implementable in dominant strategies is an affine maximiser (Roberts 1979); on restricted domains such as single-parameter ones (auctions), there are implementable rules that are not affine maximisers, for example Myerson’s optimal auction when bidders are differently distributed with non-linear virtual values; with identical regular distributions Myerson’s auction (a second-price auction with a reserve) is itself an affine maximiser (Chapter 5).
  8. Sybil attacks and the cost boundary. The term “Sybil attack” comes from Douceur (2002) (Douceur 2002); Cheng and Friedman proved that symmetric reputation functions (such as PageRank) cannot be sybilproof, whereas asymmetric flow-based functions can (Cheng and Friedman 2005). The framework’s “cost boundary” (the ratio of the cost cc of each fake identity to the gain it brings) is the author’s model, not a published theorem (Chapter 6).
  9. Points inflation and badges. The “inflationary instability” of points is the author’s model; Fisher’s quantity equation is borrowed only as an analogy (Fisher 1911). There is observational evidence that badges steer behaviour (Anderson et al. 2013); meta-analytic effects of gamification on learning are small (close to medium for cognitive outcomes), and only the cognitive outcomes are stable in rigorous studies (Sailer and Homner 2020) (Chapter 6).
  10. The source of “rewards reliable, punishments certain” (xin shang bi fa). The four characters do not occur in the Book of Lord Shang; they occur in the Han Feizi, “Outer Collections of Sayings, Right, Upper”, in Hu Yan’s answer to Duke Wen of Jin (“信赏必罚,其足以战”), and in the eulogy of the “Annals of Emperor Xuan” in the History of the Former Han (“孝宣之治,信赏必罚,综核名实”) (陈奇猷 2000; 班固 1962). What the “Rewards and Punishments” chapter of the Book of Lord Shang says is “壹赏,壹刑,壹教” (one reward, one punishment, one teaching) (蒋礼鸿 1986). The Chinese subtitle therefore names “the ‘Rewards and Punishments’ chapter of the Book of Lord Shang and the Han Feizi” side by side: the phrase comes from the Han Feizi, the reward-and-punishment structure from the Book of Lord Shang. “One hare runs, a hundred chase it” occurs both in the “Fixing Shares” chapter of the Book of Lord Shang and in the words of Shen Dao quoted in the Lüshi chunqiu, “Being Careful about Power”, with different wording (陈奇猷 2002). Legalist “reward and punishment” and the “incentive compatibility” of mechanism design share a name but not a meaning (Chapter 7).
  11. Chapter 8’s outcome. The author’s framework proposed either “the share of rounds in which the bid equals the value” or “efficiency” as the primary outcome. A pre-registered protocol can have only one; the book chooses the former and makes efficiency secondary, for reasons given in Chapter 8 (Chapter 8).

How to read the boxes

As in the other books of 5D Library, different kinds of statement are marked separately.

Evidence

Evidence boxes report published research findings, with sources.

Calculation

Calculation boxes give short Python programs. Each runs unchanged in a standard Python 3 environment (3.8 or later), uses only the standard library and fixes its random seed; its actual output is printed below it. All bids, valuations, community and reputation data in the book are fictional or synthetic, and parameters are illustrative, not estimates for any real platform.

Hypothesis · not established

Hypothesis boxes contain the author’s ideas, marked “not established”, together with the result that would show them wrong. The author’s own models and definitions are labelled “the author’s model” in the text.

Source text

Source boxes quote ancient texts with a plain-language rendering.

Note

Note boxes give reminders and explain choices.

About this edition

This is version 1.0.0, the first complete edition: a preface and eight chapters, in Chinese and English. It is the fiftieth book of 5D Library. It contains 16 Python programs and 5 vector figures. The text, boxes and code were drafted with an AI writing tool from the author’s title, framework and notes; the author is responsible for reviewing and revising them and for checking sources. AI-drafted text can get bibliographic details wrong; corrections are welcome through the 5D Library website. The points-inflation model and the Sybil cost boundary of Chapter 6, the hare-chasing and reward-and-punishment models of Chapter 7 and the planning assumptions of Chapter 8 are the author’s models; their mathematical properties are not evidence of predictions about any real community or platform.

Disclosure

The author uses the works of 5D Library, including this book, as the methodological basis of his community courses, the 5D Ascension Cards (Dimensional Shift Card Decks) and the Yafu AI knowledge base, and therefore has a commercial interest in the subject of this book. The book promotes no course, card deck or service; the Chapter 8 trial is designed to be run and analysed by researchers independent of the author’s business and does not recruit from the author’s community, students or customers; all the code and the study protocol are published openly for anyone to check. The author runs online learning communities and designs their points and incentive rules, and founded and operates Asia Influencer X and Yafu Global (whose influencer-marketing business involves price quotes, bidding and reputation ratings between creators and brands), and therefore has a direct commercial interest in the subject of this book; the book uses no data from the author’s communities or businesses as evidence and does not promote their services.

References

Anderson, Ashton, Daniel Huttenlocher, Jon Kleinberg, and Jure Leskovec. 2013. “Steering User Behavior with Badges.” Proceedings of the 22nd International Conference on World Wide Web (WWW ’13), 95–105.
Bester, Helmut, and Roland Strausz. 2001. “Contracting with Imperfect Commitment and the Revelation Principle: The Single Agent Case.” Econometrica 69 (4): 1077–98.
Bigler, Jason. 2019. Rolling out First Price Auctions to Google Ad Manager Partners. Google, The Keyword (company blog), 5 September 2019.
Bulow, Jeremy, and Paul Klemperer. 1996. “Auctions versus Negotiations.” American Economic Review 86 (1): 180–94.
Cheng, Alice, and Eric Friedman. 2005. “Sybilproof Reputation Mechanisms.” Proceedings of the 2005 ACM SIGCOMM Workshop on Economics of Peer-to-Peer Systems (P2PECON ’05), 128–32. https://doi.org/10.1145/1080192.1080202.
Clarke, Edward H. 1971. “Multipart Pricing of Public Goods.” Public Choice 11: 17–33.
Coase, Ronald H. 1972. “Durability and Monopoly.” Journal of Law and Economics 15 (1): 143–49.
d’Aspremont, Claude, and Louis-André Gérard-Varet. 1979. “Incentives and Incomplete Information.” Journal of Public Economics 11 (1): 25–45.
Dasgupta, Partha, Peter Hammond, and Eric Maskin. 1979. “The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility.” Review of Economic Studies 46 (2): 185–216.
Douceur, John R. 2002. “The Sybil Attack.” Peer-to-Peer Systems: First International Workshop, IPTPS 2002, Lecture notes in computer science, vol. 2429: 251–60.
Edelman, Benjamin, Michael Ostrovsky, and Michael Schwarz. 2007. “Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords.” American Economic Review 97 (1): 242–59.
Fisher, Irving. 1911. The Purchasing Power of Money. Macmillan.
Fukuda, Emiko, Yoshio Kamijo, Ai Takeuchi, Michiharu Masui, and Yukihiko Funaki. 2013. “Theoretical and Experimental Investigations of the Performance of Keyword Auction Mechanisms.” RAND Journal of Economics 44 (3): 438–61. https://doi.org/10.1111/1756-2171.12026.
Gibbard, Allan. 1973. “Manipulation of Voting Schemes: A General Result.” Econometrica 41 (4): 587–601.
Green, Jerry R., and Jean-Jacques Laffont. 1977. “Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods.” Econometrica 45 (2): 427–38.
Green, Jerry R., and Jean-Jacques Laffont. 1979. Incentives in Public Decision-Making. North-Holland.
Groves, Theodore. 1973. “Incentives in Teams.” Econometrica 41 (4): 617–31.
Gul, Faruk, Hugo Sonnenschein, and Robert Wilson. 1986. “Foundations of Dynamic Monopoly and the Coase Conjecture.” Journal of Economic Theory 39 (1): 155–90.
Harris, Milton, and Robert M. Townsend. 1981. “Resource Allocation under Asymmetric Information.” Econometrica 49 (1): 33–64.
Holmström, Bengt. 1979. “Groves’ Scheme on Restricted Domains.” Econometrica 47 (5): 1137–44.
Hurwicz, Leonid. 1972. “On Informationally Decentralized Systems.” In Decision and Organization: A Volume in Honor of Jacob Marschak, edited by C. B. McGuire and Roy Radner. North-Holland.
Maskin, Eric. 1999. “Nash Equilibrium and Welfare Optimality.” Review of Economic Studies 66 (1): 23–38.
Myerson, Roger B. 1979. “Incentive Compatibility and the Bargaining Problem.” Econometrica 47 (1): 61–73.
Myerson, Roger B. 1981. “Optimal Auction Design.” Mathematics of Operations Research 6 (1): 58–73.
Roberts, Kevin. 1979. “The Characterization of Implementable Choice Rules.” In Aggregation and Revelation of Preferences, edited by Jean-Jacques Laffont. North-Holland.
Sailer, Michael, and Lisa Homner. 2020. “The Gamification of Learning: A Meta-Analysis.” Educational Psychology Review 32 (1): 77–112. https://doi.org/10.1007/s10648-019-09498-w.
Varian, Hal R. 2007. “Position Auctions.” International Journal of Industrial Organization 25 (6): 1163–78.
Vickrey, William. 1961. “Counterspeculation, Auctions, and Competitive Sealed Tenders.” Journal of Finance 16 (1): 8–37. https://doi.org/10.1111/j.1540-6261.1961.tb02789.x.
Walker, Mark. 1980. “On the Nonexistence of a Dominant Strategy Mechanism for Making Optimal Public Decisions.” Econometrica 48 (6): 1521–40.
Yokoo, Makoto, Yuko Sakurai, and Shigeo Matsubara. 2004. “The Effect of False-Name Bids in Combinatorial Auctions: New Fraud in Internet Auctions.” Games and Economic Behavior 46 (1): 174–88. https://doi.org/10.1016/S0899-8256(03)00045-9.
Zhou, Lin. 1991. “Inefficiency of Strategy-Proof Allocation Mechanisms in Pure Exchange Economies.” Social Choice and Welfare 8 (3): 247–54.
班固. 1962. 汉书. 中华书局.
蒋礼鸿. 1986. 商君书锥指. 新编诸子集成. 中华书局.
陈奇猷. 2000. 韩非子新校注. 上海古籍出版社.
陈奇猷. 2002. 吕氏春秋新校释. 上海古籍出版社.

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).