Studying a field deeply teaches you to recognize problems that arise in the real world as thinly disguised versions or minor variations of problems that are already well solved. For example, when I teach the fundamentals of algorithms, students learn how to recognize problems that boil down to, say, a shortest-path computation or linear programming.
Such pattern-matching can be equally potent in mechanism design, a type of “inverse game theory” that uses incentives to achieve desirable outcomes. The tools and lessons of mechanism design are especially useful in auction theory, market design, and social choice theory.
Crypto and web3 are rife with mechanism design problems. One might expect many of them to be solvable by copy-pasting from a textbook, using minor variations of age-old ideas. But the unique challenges and constraints of permissionless blockchain protocols often force a rethinking from first principles of seemingly well-solved problems. This makes mechanism design in web3 complex. But these challenges also make mechanism design in web3 deeply fascinating.
In this post, I explore some of the challenges with web3 mechanism design. These challenges may be familiar to the crypto-native, but understanding mechanism design more deeply should offer all builders a fresh perspective on why these problems are so difficult to solve. As for mechanism designers, if you’re looking for new applications, you will likely be intrigued by the challenges posed by a permissionless environment.
As a field, mechanism design goes back at least to 1961, when William Vickrey, a Columbia University economist and future Nobel Prize recipient, formally described a sealed-bid second-price auction. This same style of auction was used as early as 1797, when Johann Wolfgang von Goethe, the author, sold the manuscript for his epic poem Hermann and Dorothea. It was also commonly used by stamp collectors in the nineteenth century but wasn’t formally described until Vickrey and is now commonly known as the “Vickrey auction.” In the Vickrey auction, the highest bidder wins but pays the second highest bid. This auction elicits the true preferences of the bidders, and also gives the item in question to the person who values it the most.
The Vickrey auction is an elegant and efficient design that has been applied in the real world, modified and updated for new circumstances, with practice informing theory, and vice versa. Like the Vickrey Auction, mechanism design as a formal discipline has a history of intertwined theory and practice. It is both deep and beautiful.
As opposed to game theory — which establishes the dimensions of a strategic interaction and then explores the most behaviorally plausible outcomes — the field of mechanism design begins not with the game but with a desired outcome. Mechanism design aims to reverse engineer a game of some form so that this desired outcome — perhaps characterized by efficiency, fairness, or certain sets of behaviors — is an equilibrium. In the case of the Vickrey auction, the goal is to elicit the maximum amount participants are willing to pay while not punishing them for doing so.
Opportunities to apply mechanism design abound in web3. For example, a blockchain protocol might want to achieve the outcome that the participants running the protocol do so honestly, without any deviations from the intended behavior. Or a protocol might want to elicit accurate information about the value of transactions, to efficiently allocate block space to the most valuable transactions.
Such mechanism design problems are always challenging, and they are uniquely challenging in a blockchain context.
Without the assumption of a trusted party to carry out a mechanism, design in the blockchain space becomes that much harder.
The whole point of using a permissionless blockchain protocol is you don’t have to trust any one entity or individual, only the “on-average” trust assumption that a sufficiently large fraction of the nodes running the protocol are doing so correctly.
But the irony of many blockchain architectures is that each batch of transactions added to the history of the chain, for execution in the virtual machine maintained by the protocol, is the product of a unilateral decision made by a single node.
It is this single node that you cannot know if you can trust.
This is why it’s rare to see Vickrey auctions in a blockchain context. Implementing a Vickrey auction naively quickly runs into problems with manipulation by untrusted block producers. The issue is that a block producer can manufacture a “shill bid” — a fake bid whose bid is slightly under what’s going to be the winning bid, thereby forcing the winner to pay nearly their full bid (as opposed to the second-highest genuine bid).
Shill bids by untrusted block producers effectively cause Vickrey auctions to revert to first-price auctions, which is one of the reasons why first-price auctions are so prevalent in web3. (The recent branch of the traditional mechanism design literature on “credible mechanisms” also considers auction design with an untrusted auctioneer, though from a somewhat different perspective.)
Another reason mechanism design in blockchains is difficult concerns collusion among blockchain participants. For example, second-price auctions are vulnerable to collusion with side payments. The intuition is simple: The winning bidder pays the second highest bid, so that bidder can simply bribe the second highest bidder into bidding much lower.
The academic literature on mechanism design hasn’t worried too much about collusion. One reason might be that collusion, especially with side payments, is difficult to pull off in the real world. It’s hard to have credible side payments after the conclusion of some collusive action when the winner could simply decline to pay the bribe. (“No honor among thieves,” as they say.)
In a blockchain setting, however, would-be colluders can often use smart contracts to commit credibly to the side payments needed to make collusion work. A second reason is the paucity of mechanisms that disincentivize collusion with side payments — “posted price” mechanisms that make only take-it-or-leave-it offers, and not much else.
To make matters worse, the users of a protocol might collude not only with each other, but also with the (untrusted) block producer (the equivalent of a bidder colluding with the auctioneer in a real-world auction).
Resilience to this last type of collusion was one of the primary motivations for burning a portion of the transaction fees in Ethereum’s EIP-1559 transaction fee mechanism. Without the “burn” (or otherwise withholding those revenues from the block producer), a block producer and end- users could collude and evade through side payments whatever reserve price the mechanism attempts to impose.
Collusion is obviously not a new issue. It’s plagued various mechanisms in real life for centuries, yet if you examine the mechanism design literature, you might be surprised how little it addresses collusion. The literature does address head-on the incentives for unilateral manipulations by individual participants of a mechanism — but generally punts on collusion, leaving it to some unmodeled notion of “rule of law.” For example, participants in the mechanism might sign a legal contract that specifies that they will not collude. If collusion is detected, addressing it is then handed off to a legal channel. Mechanism designers can help by creating a mechanism in which collusion is relatively easy to detect.
This is an unspoken secret in much of the mechanism design literature: reliance on the rule of law. While one can’t say there’s no rule of law around permissionless blockchain protocols — we frequently see law enforcement successfully prosecute criminal behavior on permissionless blockchains — there is a lot less of it than in traditional mechanism design applications.
And if you can’t rely on the rule of law outside the mechanism, then it’s incumbent on the designer to handle it inside the mechanism. This approach pervades mechanism design decisions in the blockchain space. In the Ethereum protocol in particular, examples range from burning base fee revenues in EIP-1559 to slashing misbehaving validators in its consensus protocol.
The design space in web3 is bigger than mechanism designers are accustomed to. As a result, they have to think about any given problem anew. For example, many mechanisms involve payments; in a traditional mechanism design application, these payments would be in some fiat currency like USD. Many blockchain protocols have their own native currency, and mechanisms within such a protocol are in a position to manipulate that currency.
Imagine if you wrote a traditional mechanism design paper, and part of your mechanism’s description was: “Print a bunch of new money, and give that to a bunch of the participants.” It would look ridiculous outside of a blockchain context. But you can do exactly that when you’re talking about mechanism design in the context of a blockchain protocol. The protocol controls the currency, and so a mechanism that’s part of that protocol can mint or burn it.
This means that some designs that would be impossible without access to a native currency become possible. For example, how do you incentivize Bitcoin miners to carry out the protocol as intended? Through inflationary rewards: printing new Bitcoins to motivate these block producers. Without access to a native currency, such a design would be impossible.
Reason #4 highlights the power of native currency. The two obvious things you can do with a native currency are “mint” (the way the Bitcoin protocol mints new bitcoins to incentivize miners) and “burn” (the way Ethereum’s EIP-1559 transaction fee mechanism burns ETH to achieve collusion-resilience). But there is a danger lurking in native currencies that does not exist in traditional mechanism design: microeconomic design decisions may have macroeconomic consequences.
In traditional mechanism design, there’s no reason to worry about macroeconomic forces. No traditional auction has had a meaningful effect on the U.S. monetary supply or the inflation rate. This challenge is wholly new to the web3 design space. What could go wrong? Let me tell you about two examples, one about minting in Bitcoin, one about burning in Ethereum.
By virtue of using block rewards — by printing new money to motivate miners — Bitcoin is forced to have inflation. As a result, it must also have a monetary policy to decide on inflation rates and how that rate evolves over time. Nakamoto also created a hard supply cap of 21 million Bitcoins. Because the number of bitcoins has a hard cap, the inflation rate must go to zero.
If it does go to zero, what would motivate miners to continue running the protocol and contributing security to Bitcoin? The hope has always been that transaction fees would make up for the missing block reward, although the evidence that that will happen is quite weak. It’s always been known that if transaction fees stay close to zero, then the Bitcoin protocol is going to suffer from major security issues.
A paper by Princeton University computer scientists Miles Carlston, Harry Kalodner, Matthew Weinberg, and Arvind Narayanan points out another difference between transaction fees and block rewards. While block rewards are the same for every block (at least between successive “halvings” of the block reward, which occur every four years), transaction fees can vary by orders of magnitude — which in turn introduces new game-theoretic instability into the protocol. In this sense, the macroeconomic decision of a fixed supply cap has negative microeconomic consequences for the protocol and its participants.
Just as the minting of block rewards acts as an inflationary force with Bitcoin, the burning of transaction fees in EIP-1559 acts as a deflationary force with Ethereum. In the Ethereum protocol (which does use inflationary validator rewards), there is a tug of war between these two forces, with the deflationary forces generally winning. The fact that ETH is now a net deflationary currency is a macroeconomic consequence of microeconomically motivated design decisions in the protocol’s transaction fee mechanism.
Is deflation good or bad for the Ethereum protocol? ETH holders like deflation because, all else equal, it makes their tokens more valuable over time. (Indeed, this byproduct may have been what eventually tipped public opinion in favor of the switch to the EIP-1559 transaction fee mechanism.) Yet the idea of a deflationary currency makes traditionally trained macroeconomists recoil, recalling stagflation in 1990s Japan.
Who’s right? Personally, I’m not convinced that a sovereign fiat currency is the right analogy for a cryptocurrency like ETH. But then, what is the correct analogy? This remains an open question, and the ball is in the court of blockchain researchers to explore further: Why is it okay to have a deflationary currency as the cryptocurrency that powers a blockchain protocol but not as the fiat currency that powers a sovereign nation?
In computer science, one of the things we aspire toward is modularity and clean abstraction, which grants the ability to rely on parts of your system on faith. When designing and analyzing one part of a system, you presumably need to know the functionality exported by the other parts of the system; but ideally, you don’t need to know how that functionality is actually implemented under the hood.
We haven’t reached this ideal yet in blockchain protocols. While builders and mechanism designers might like to focus on, say, the application layer, they cannot afford to ignore the reality and details of how the infrastructure layer works.
For example, if you’re designing an automated market maker, you have to think about the fact that untrusted block producers are in charge of transaction ordering. Or when you’re thinking about transaction fee mechanism design for a (layer-2) rollup, not only do you have to pay for resource consumption at layer 2, you also have to pay for any costs incurred on the underlying layer-1 protocol (for example, from storing calldata).
In both examples, effective mechanism design at one layer requires detailed expertise about other layers. Maybe, as blockchain technology matures, we’ll have a clean separation of the different layers. But we certainly don’t have it now.
The “computer in sky” that a blockchain protocol implements is a computation-limited environment. Traditional mechanism design focused solely on economic incentives and ignored computational issues (for example, the famous Vickrey-Clarke-Groves mechanism is infeasible to implement for sufficiently complex allocation problems).
When Nisan and Ronen introduced algorithmic mechanism design in 1999, they noted that we do indeed need some kind of computational tractability for mechanisms to have any actual meaning in the real world. So they proposed restricting attention to mechanisms that use an amount of computation and communication that scales as a polynomial (as opposed to exponential) function of the problem parameters.
Because computation in a blockchain protocol’s virtual machine is so scarce, on-chain mechanisms must be very lightweight — polynomial time and communication is necessary but not sufficient. This scarcity, for example, is the primary reason why automated market makers completely dominate Ethereum DeFI, as opposed to more traditional solutions like limit order books.
Usually, when people say it’s still early in web3, they’re referring either to investment opportunities or to adoption numbers. But from a scientific perspective, we’re even earlier than that. This fact only makes things harder — even though it represents an enormous opportunity.
Working in a mature research area provides benefits that everyone takes for granted. There are agreed-upon models and definitions. There is consensus around the most important problems. There is non-trivial coordination on how to measure progress. There exists a common vocabulary and a large common knowledge base. On-ramps exist to get up to speed, including well-vetted textbooks, online courses, and other resources.
In many parts of the blockchain space, meanwhile, we don’t yet know the “right” models and definitions to think clearly about and make progress on important problems. For instance, what’s the most important notion of incentive compatibility in the context of blockchain protocols? What are the layers of the web3 stack? What should be counted as part of maximal extractible value (MEV)? These are just some of the open questions.
***
For those interested in working in the science of blockchain, the immaturity of the area presents a challenge. But coming to it early — now — also represents a unique opportunity.
Mechanism design has always been a useful tool at the application layer of the internet — take for example real-time advertising auctions, or the design of two-sided marketplaces that pervade most online consumer apps today, from ecommerce to ridesharing.
But in web3, mechanism design is also informing design decisions within the infrastructure itself.
Think back to the 1970s and 80s, when internet routing protocols were still being discussed and designed. As far as I know, no one with expertise in incentives and mechanism design had a seat at that table. In hindsight, we now realize that such a person could have usefully informed the design. In web3, meanwhile, incentives have been part of the discussion since day one, with the publication of the original Bitcoin whitepaper.
The confusion around the “right” models, definitions, and success metrics for web3 is really the universe telling us that we’re in the middle of a golden era. Later generations of students and scientists will envy us being here, in the right place at the right time, with the opportunity to shape the trajectory of this technology. So while there may not be many textbooks in the area, someday there will be, and the work that’s going to be described in them is the work that is being done right now.
***
Tim Roughgarden is a Professor of Computer Science and a member of the Data Science Institute at Columbia University, and Head of Research at a16z crypto.
***
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles mnaged by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.
Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.
