On Paper to On-Chain: How Auction Theory Informs Implementations

Michael Zhu

Editor’s note: This piece is part of our ongoing series on all things ‘auctions for web3’. Part 1 was an overview of auction designs, and technical challenges (and opportunities) specific to mechanism design in a permissionless blockchains context. Part 2 was a piece on clearing the market and avoiding gas wars.

Auctions are ubiquitous in crypto. From Maker collateral auctions, to Flashbots’ sealed-bid blockspace auctions and NFT auctions on OpenSea, auctions are suitable for a wide array of situations where price discovery, liquidity, or allocation of scarce resources is needed, both on and off-chain. 

However, juxtaposed against the vast (and growing) body of academic research on auctions, it’s clear that we’ve only scratched the surface of what these mechanisms might be able to offer on-chain — for example, optimizing for privacy, efficiency, buyer surplus, and other key design objectives. Given the “Cambrian explosion” of automated market maker (AMM) designs following Curve and Sushiswap in 2020 — and the concurrent explosion of third-generation blockchains — it’s plausible (inevitable, perhaps) that on-chain auctions are ripe for a similar evolutionary upsurge. 

Whereas auction formats were once loosely adopted for (and constrained by) the technical limits of blockchains, we’re now starting to see more novel designs adapted especially for blockchains. Following in the tradition of market design, this post is part of a series that aims to bridge the gap between auction theory and practice: How can theoretical principles inform implementation decisions? And how can on-chain implementations, in turn, inform new directions of theoretical research? Though theory can guide us toward a certain auction design, a seemingly innocuous implementation detail itself may be interesting to analyze with a theoretical lens. 

We begin by comparing the four canonical auction types along three axes: information revelation, bidding strategy, and on-chain implementation considerations. Then we’ll focus on sealed-bid formats specifically, dive deeper into the implementation subtleties that have made them relatively unexplored on-chain, and introduce our open source Solidity implementation of a Vickrey auction — which we hope others can use as a reference and basis for further experimentation. 

But first, a brief primer on auction formats

We’ve previously covered auction design — in both traditional formats and as applied and adapted to blockchains — in great detail on a recent podcast with a16z crypto research partner (and Harvard Business School professor) Scott Kominers and a16z crypto head of research (and professor at Columbia University) Tim Roughgarden. Drawing on their expertise advising crypto protocols, they provide an overview of auction types and incentive design, in both theory and practice — including the nuances of market-clearing prices and gas wars (which we covered in part two of this ongoing series on auction design for web3).

But to set some quick context for the implementation below: auction theory has historically centered around four canonical auction types, first taxonomized by William Vickrey in 1961 and described here in the context of an auction for a single good.

A snapshot of auction designs available off chain. Source: Wikipedia

  • English (ascending-price): In an English, or ascending-price auction, the auctioneer opens bidding at a reserve (minimum) price, and bidders place incrementally higher bids until only one bidder willing to pay the current price is left, at which point the last bidder wins. This is the auction format most commonly portrayed in popular culture and media, often in the context of selling antiques, artwork, or uncut gems
  • Dutch (descending-price): In a Dutch, or descending-price auction, the opening price decreases according to a prescribed schedule. In a Dutch auction, the first to bid is the winner and the auction instantly ends. Historically, multi-unit versions of Dutch auctions have often been used to sell large quantities of goods that have a limited shelf life, such as cut flowers, fish, or tobacco. More recently, the U.S. Treasury introduced the use of Dutch auctions for securities (1974), and the Google IPO in 2004 (infamously) sold its shares via Dutch auction.
  • Sealed-bid first-price: Each bidder submits a sealed bid (e.g. in a sealed envelope) to the auctioneer. Once all bids are submitted, the auctioneer privately reads them and announces the winner (the highest bidder). The winner then pays the amount that they bid. Sealed-bid first-price auctions are often used in real estate when a property garners interest from multiple buyers. 
  • Sealed-bid second-price (the Vickrey auction”): Vickrey’s namesake auction is the same as the sealed-bid first-price auction, except the winner in this auction type pays the value of the second-highest bid. Despite having interesting theoretical properties, the Vickrey auction is rarely seen on-chain (partly due to the difficulty of implementing sealed bids).

These four auction types have different properties and dynamics which are further complicated when translated to smart contract implementations (and which we’ll detail later).

Comparing auction types by information revelation

One of the more natural ways to characterize each auction type is by bid visibility (open vs sealed-bid). Even with all else held equal, changing bid visibility can have profound impact on the dynamics and outcome of an auction.

English and Dutch auctions are open-outcry auctions, meaning prices are announced verbally as they ascend or descend, and bids (including their amounts) are public to all potential buyers. Sealed-bid auctions, however, may employ a few different flavors of privacy:

  • Eventually public: all bids are revealed publicly after the auction ends
  • Public price: only the winning price is revealed, and not other bids
  • Fully private: nothing is revealed publicly about the bids or winning price

These assumptions around bid visibility mean that the auctions also differ in terms of information revelation; different auction formats reveal different amounts of information about bidders’ valuations (often an upper or lower bound) at different stages of the process. In an English auction, placing a bid effectively establishes a lower bound on that bidder’s valuation. In a Dutch auction, on the other hand, the current price can be interpreted as an upper bound on all the bidders’ valuations. Sealed-bid auctions reveal information only after the auction ends, if at all. 

It’s worth noting that Dutch auctions can take on qualities of both open and sealed-bid auctions. Single-item Dutch auctions have similar privacy properties to public-price sealed-bid auctions (since the first bid wins, all other, lower bids are kept private). But as we’ll see later, these properties change significantly when Dutch auctions are run on-chain. 

Common and private values

Examining sales of private and common value goods across open-bid and sealed-bid auctions can provide another lens for comparing these formats. In an auction selling a common value good, the item has some intrinsic value that is shared among all bidders, but the bidders may have different or incomplete information about that value. In Nobel-prize winning behavioral economist Richard Thaler’s canonical example of common value, a jar of coins is up for auction; none of the bidders knows the exact value contained in the jar, but everyone has their own estimate. In an auction selling a private value good, each bidder has an individual value for the auctioned item, independent of their peers. To draw examples from web3, an NFT bought purely for personal enjoyment (with no intention of resale or expectation of future utility) is a private value good, while the collateral from a liquidated Maker vault is a common value good.

Meanwhile, the authors of another paper looking at data from timber auctions found that sealed-bid auctions “attract more small bidders, shift the allocation toward these bidders, and can also generate higher revenue” compared to their open-bid counterparts. Notably, the authors found that these results could be accounted for by a private value model (where private values vary based on idiosyncrasies of timber auctions, like “differences in bidder costs and contractual arrangements”), omitting common values from their model entirely. This suggests that a seller may benefit from choosing a sealed-bid auction for sales where bidders have disparate motivations, contexts, or uses for the auctioned item.

English auctions can be useful in settings where common values dominate and price discovery is an objective — as mentioned, the bidders learn how others are valuing the item as bids come in, and can adjust their strategy accordingly. In one study of reverse auctions in online labor markets, the authors found that while sealed-bid auctions attracted more bids, open-bid auctions resulted in these buyers getting a better price (or a greater buyer surplus). The analysis suggests that the differences “largely depend on the relative importance of the common value (versus the private value) component of the auctioned IT services.” In other words, the open-bid format allows bidders to dynamically recalibrate their understanding of how much the service is worth, which is often unclear at the start of the auction.

In practice, auctions typically display a combination of both common and private-value characteristics. The interplay between the characteristics of these goods, and how (and when) information is revealed by the auction format has complex downstream effects on bidding strategy. This leads us to the question: Can we formalize the notion of a “simple” bidding strategy (I don’t need to think too hard about how you might bid); and are there auctions where such strategies are optimal?

Comparing auction types by bidding strategy

Of the four canonical auction types, one that has been conspicuously absent from our analysis so far is the Vickrey auction. A careful reader may raise an eyebrow at the Vickrey auction’s payment rule: the winner pays the second highest bid instead of what they themselves bid. This may seem counterintuitive at first, but English auctions ultimately settle in a similar way. An English auction ends with the lowest bid that no other bidder is willing to meet; the winner has no reason to bid any further, even if their own valuation is much higher. In fact, English and Vickrey auctions share a nice theoretical advantage over Dutch and sealed-bid first-price auctions: dominant-strategy incentive-compatibility (DSIC). 

At a high level, this means that each bidder’s utility-maximizing strategy is simply to bid whatever they actually believe the auctioned item is worth (in a common value auction, this is just the expected value of the item, conditioned on the bidder’s information). For a deeper dive, these lecture notes serve as an excellent primer.

In a first-price auction, there is no such dominant bidding strategy. Bidders need to shade (or reduce) their bids to be lower than their valuation to obtain positive utility. Exactly how much lower they can get away with while still outbidding fellow participants is a Bayesian game. A Dutch auction is strategically similar. In order to obtain positive utility, a bidder must wait until the price drops below their valuation, but how long to wait after that threshold is another Bayesian game. Perhaps more surprisingly, the expected revenue for all four auction types is the same (under certain assumptions; see Theorem 1). 

Despite the theoretical advantages of Vickrey auctions, they are somewhat uncommon in practice. In The Lovely but Lonely Vickrey Auction, economists Lawrence Ausubel and Paul Milgrom provide several explanations why this may be the case. The authors note that despite being strategically equivalent, English auctions are intuitively easier for bidders to reason about than Vickrey auctions. This intuition is formalized in Obviously Strategy-Proof Mechanisms, which shows that English auctions are not only DSIC, but bidding truthfully is “obviously dominant”. 

To provide a real-world example, Google announced last year that AdSense — a program where advertisers bid for ad space on content — would be moving from second-price to first-price auctions, citing simplicity and alignment with the rest of the digital advertising ecosystem. In addition to these usability considerations, platforms like AdSense assume a position of trust when running second-price auctions: by overreporting the second-highest bid, a dishonest auctioneer could extract more payment from the winner. 

Although these concerns have slowed adoption, the Vickrey auction could find new use cases when extended to new environments. Public blockchains, in particular, provide a credibly neutral platform that may help circumvent issues such as the dishonest auctioneer. This, coupled with the diversity of potential on-chain applications, suggest that smart contracts may provide a uniquely effective testbed for the Vickrey auction mechanism.

Comparing auction types through implementation considerations

Bringing auctions on-chain can sometimes pose new challenges, relative to off-chain counterparts. In the following sections, we’ll explore the current landscape of on-chain auctions and implementation considerations for each auction type. 

On-chain English auctions

The majority of on-chain auctions found in the wild today fall into the open-bid category (i.e. English or Dutch). These include ascending-price OpenSea auctions, Maker collateral auctions, and the Zora Auction House contract. 

Under the hood of OpenSea, bids are off-chain messages that encode the bid value, signed by the bidder. As prospective buyers place their bids, the OpenSea UI surfaces the bid values to the seller and to potential bidders. In Maker collateral and Zora auctions, however, bidders submit a transaction to indicate their bid; then the bid transaction escrows the bidder’s collateral in an auction contract. By virtue of being an unobfuscated on-chain transaction, the bid is inherently open — anyone can see what their fellow bidders are offering by looking at incoming transactions to the auction contract (either in the public mempool, or as they get included in the chain). 

Overall, English auction dynamics remain relatively intact when translated into a smart contract. One notable difference is that on-chain bids incur a gas cost, which is priced into the de facto bid value. As gas prices fluctuate over the bidding period of an auction, a bidder who otherwise would’ve had the highest offer may be temporarily priced out by expensive gas fees.

On-chain Dutch auctions

On-chain Dutch auctions have seen significant traction, from facilitating NFT sales to rebalancing TokenSets (and spawning variants like Gradual Duction Auctions and Variable Rate GDAs). This popularity is for good reason –– a simple Dutch auction is relatively easy to implement as a smart contract and requires just two on-chain transactions (one to create the auction, one for the first and only bid). Most importantly, it doesn’t lock bidders’ funds, unlike other auctions with on-chain bids.   

The dynamics of off-chain Dutch auctions depend on bidding being effectively instantaneous. A single-item Dutch auction ends as soon as a bid is announced, and no other bids can be placed. When conducted on-chain, however, there is a gap in time between when the bid is broadcast and when it is included in the chain, which can have some unexpected consequences. If the first bid is broadcast to the public mempool (as opposed to a private transaction pool like Flashbots), it may kick off a gas war, with other prospective buyers broadcasting bids with incrementally higher gas prices. As a result, the gas-adjusted price can rise suddenly as the off-chain, ascending-price auction for transaction ordering eclipses the Dutch auction itself. 

The time-dependent nature of the descending-price mechanism brings other drawbacks as well. Assuming a continuous price decay function, a bidder must be online exactly when necessary to place a bid at a specific price, or set up a bot (e.g. using Gelato Network) to bid for them. Network congestion that incidentally (or maliciously) coincides with the broadcast of the first bid can lower the final settled price to the detriment of the seller’s revenue. Worse yet, a denial of service (DoS) attack could cost the rightful winner the auction. 

On-chain sealed-bid auctions, demonstrated by a new open source implementation

Platforms that utilize off-chain bids (e.g. OpenSea) could easily implement sealed-bid auctions, but they would require trusting an auctioneer to (a) not reveal any bids, (b) not censor any bids, and (c) correctly determine the result of the auction. Ideally, a smart contract would trustlessly facilitate the auction, while preserving some degree of bid privacy. 

To demonstrate, we open sourced a Solidity implementation of an overcollateralized sealed-bid auction at github.com/a16z/auction-zoo, as a single-item (ERC721) Vickrey auction with bids denominated in ETH. We approached the implementation with three requirements for a sealed-bid auction smart contract in mind: 

  1. Privacy: Bid values should remain private, meaning observers can’t infer the values while bidding is ongoing. We allow some information leakage (e.g. revealing that a bid lies in some large interval), but there should be a reasonable degree of ambiguity. 
  2. Censorship resistance: This can typically be accomplished by posting bids on-chain.
  3. Bid commitment: A prospective buyer shouldn’t be able to back out of their bid. The winning bidder should be locked into paying the settled price, and similarly, the seller should be locked in to selling the item to the highest bidder (possibly subject to a reserve price).

First we need to solve the issue of posting private bids on-chain, according to the first two requirements. A commit-reveal scheme lends itself to “eventually public” bids (when bid values are revealed after the auction ends). Instead of bidding in the open, prospective buyers can provide a hash commitment of their bid to the auction contract during the designated bidding period. Later, after the bidding period ends, each prospective buyer reveals the bid that they committed to. When the bids are revealed, the smart contract can determine the winner. In our implementation, hash commitments are computed as keccak256(abi.encode(nonce, bidValue)) and passed to the commitBid function. For gas efficiency, we store only the upper 20 bytes of this hash. Once the bidding period is over, users call the revealBid and the contract checks that the provided nonce and bidValue match the stored commitment.

Remember to drink water and pack your storage variables.

We uncover a bit more complexity when moving to the third requirement. To ensure winners pay up, the smart contract must lock in bids. We could require that bidders send ETH to collateralize their bids along with each commitment — note that the commitBid function is payable and records how much ETH the user has locked — but the ETH attached to these transactions is public and impossible to obfuscate; in “locking in” bids, we lose privacy.

Fortunately, there is an easy way to prop our strawman back up: allowing (and encouraging) bidders to overcollateralize their bids, i.e. lock up more ETH than their bid value itself requires. With bids being potentially overcollateralized, an observer can only learn an upper bound of a bid’s value. Note that our commitBid function allows the user to lock up any amount of ETH with their transaction; any excess gets returned to the winner at the end of the auction (and a bid will be ignored if it’s undercollateralized).

Unfortunately, this quick fix comes with a downside: Overcollateralization creates a direct tradeoff between privacy and capital efficiency. The opportunity cost of locking up a large amount of capital may outweigh the marginal privacy, and capital-constrained bidders are at a disadvantage. 

That said, the overcollateralized design serves as a useful baseline as we continue to explore different approaches. An evolution of this implementation could be particularly useful in settings where a user may be bidding in a large number of auctions and collateral can be reused for each. In this case, it would then be natural for collateral to be much bigger than the bid in any given auction.

**

Can we find even better on-chain solutions? Although overcollateralization may be appropriate for some scenarios, the tradeoff between capital efficiency and bid privacy can present bidders with a difficult decision: lock up more capital for stronger privacy, or sacrifice some privacy to free up capital for use elsewhere. But as on-chain auctions continue to proliferate and build on previous work, we expect auction designers will have many more formats and implementations to choose from based on which tradeoffs they’re willing to make. 

In the next part of this series, we dive further into the design space and consider the question: Can we guarantee strong privacy without overcollateralization? This repository will continue to serve as a practical reference for ideas we discuss throughout the series and provide a basis for even further exploration. We hope you’ll follow along, fork, and experiment with more implementations, as they’re added.

Acknowledgements: Thanks to Joe Bonneau, Scott Kominers, Sonal Choksi, and Tim Roughgarden for invaluable feedback on this post; and Noah Citron, Sam Ragsdale, and Matt Gleason for reviewing the code. Special thanks to Stephanie Zinn for editing.

**
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 current or 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 managed 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/.

Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. 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





podcast: web3 with a16z

a show about building the next internet, from a16z crypto

newsletter:
web3 weekly

a newsletter from a16z crypto that's your go-to guide on the next internet