Exploring and understanding the paper “Credible, Optimal Auctions Via Blockchains” by Tarun Chitra et al.

Auctions everywhere

Google Ad Auctions

Every day we find ourselves on the internet for various reasons, be it searching for things, buying, selling and surfing/browsing the internet for work or otherwise. The economy of the internet runs on ads. Every time you visit a website, you are welcome with various ads by companies; website publishing companies sell these “ad slots” in the website to advertisers. Website publishers sell about 5 trillion ads to advertisers yearly, i.e. 13 billion ads daily, just in the US. These ads generate about 20 billion$ worth of revenue annually for companies, which is again just in the united states.

How does one go about selling an advertisement to an interested party? There is an exchange where website publishers list the ad space for sale, and advertisers buy it from them. The Department of Justice recently accused Google of justice for “monopolizing Digital Advertising technologies”.

Ad spaces are sold using auctions, where google acts as the auctioneer, the publishers are the sellers and businesses interested are bidders. Over the past decade, it has been found that google engaged in various manipulation practices to ensure its monopoly in the space and extract as much value as possible in the system. These include:

• They configured google ads to bid higher to increase the cost of advertising to the detriment of advertising customers/benefit of publishers. This led to publishers choosing google over competitors and google extracting value.

• In second-bid auctions, google usually placed two bids to anchor the auction price higher so that they could profit from the ultimate settlement price of the auction.

• When google did move to the first price auctions, it justified the move to prevent bidders from preferencing rival ad exchanges.

While a thorough coverage of the antitrust case is not this article's purpose, Auctions are ubiquitous in the shadows of everything we use on the internet. Participants in auctions need to trust the auctioneer not to engage in unfair practices, thus undermining the experience and the real value of the assets auctioned for the sake of profits.

Art Auctions

Another class of assets quite exclusively exchanged/sold/bought through auctions is Art. An auction house’s private sales data aren’t available to the public.

There’s been a recent trend of the cost of expensive Art rising. In 2018, Sotheby’s, Christie’s and Phillips sold art pieces worth 1 million dollars or more, cumulatively yielding 7.44B $ in volume, which has grown to 8.15B $ by 2022. The average art piece price in this bracket was 5.3M $ in 2018, while it was 6M $ in 2022.

The Sotheby’s art auction is a first price ascending bid auction where bidders continuously bid till the highest bid wins. Also, a reserve price ensures that the seller makes some profit relative to how they value the art piece. Many bidders are not present in the auction room at all but instead bid over the internet or telephone. Christie’s and Sotheby’s are legally permitted to call out fake bids to give the impression of higher demand.

The recent work of Tarun Chitra et al. in the paper “Credible, Optimal Auctions Via Blockchains” focuses on how we can achieve auctions which hold the auctioneer accountable while also being optimal. Smart contracts allow one to extend the concept of credibility to settings where the auctioneer does not have a reputation/it also enables you to hold trustless auctions if you have an asset you want to sell. As digital frontiers expand, a significant need for trustless credible auctions also grows.

A brief primer on Auctions

Auctions are a mechanism for buying and selling goods and services in marketplaces where goods are sold. From art auctions to online marketplaces, auctions allocate resources, determine prices, and facilitate transactions between buyers and sellers. However, not all auctions are created equal, and the design of the auction can have a significant impact on its outcome.

There are several types of auctions seen in the wild, but the major ones are as follows:

1. English auction: Also known as an “open ascending price auction”, this is the most common type of auction where participants openly bid against each other, with each bid higher than the previous one. The auction ends when no one is willing to bid higher, and the highest bidder wins. We usually see this type of auction on Foundation for Art 1/1s.

2. Dutch auction: Also referred to as an “open descending price auction”, the auctioneer starts with a high asking price and gradually lowers it until a bidder accepts the current price or the reserve price is reached. We saw a form of this in Gradual dutch auctions in the recent art gobblers mint.

3. First-price sealed-bid auction: In this type of auction, participants submit their bids in sealed envelopes without knowing the bids of others. Once the bids are opened, the highest bidder wins the item and pays the price they bid. These are also known as first-price auctions.

4. Second-price sealed-bid auction: Also known as a Vickrey auction, participants submit sealed bids, and the highest bidder wins. However, the winner pays the price offered by the second-highest bidder instead of their bid. These are also known as second-price auctions.

While the 3rd and 4th auctions are sealed bids as in private auctions where other participants are not aware of the bids of other participants, these aren’t possible on-chain today.

Credible Auctions: A Trillema

The paper “Credible Auctions: A trilemma” by Akbarpour et al. primarily studies incentive compatibility for an Auctioneer.

As discussed earlier, Second price auctions are a type of auction in which the highest bidder wins the auction but pays the second-highest bid as the price rather than their bid. In a second price auction, bidders are incentivised to bid their true valuation of the goods, as they will never pay more than their valuation and may pay less if other bidders bid less than their true valuation. The issue with a Second-price auction is that the auctioneer can profit by exaggerating the second-highest bid. Therefore special arrangements have to be made to tie the auctioneer’s hands.

If the way of communicating bids is public, then the problem is trivial since everyone is aware of everyone else’s bids, so it’s trivial and strategy-proof. Most real-world auctions are not publicly communicated. If we then assume the auctioneer communicates privately with each bidder, this allows the auctioneer to misrepresent any bidders’ preferences to other bidders.

Some properties of auctions

Suppose there’s a protocol of strategy profiles for bidders and also an extensive-form mechanism. This mechanism decides how the auctioneer runs the auction. Starting from initial history, the auctioneer conveys a message to the bidder, who then bids. The auctioneer keeps collecting the bids until they reach a terminal history, and the auctioneer chooses who wins.

Assume that there’s some utility function for the auctioneer. This could be a variety of things, but usually profit. By participating in a protocol, each bidder observes the communication between himself and the auctioneer and some features of the outcome. Even if the auction deviates from the assigned strategy of the bidder, the observation could have some innocent explanation. For example, in a second price auction, when a bidder bids 100$ and wins and has to pay 99$, this observation has an innocent explanation, the second highest bid was 99$.

Given any protocol, some deviations may be safe, i.e. for every bidder’s observation, there is some innocent explanation. Thus in a second price auction, the auctioneer can safely deviate by exaggerating the second-highest bid. Instead of exaggerating, the auctioneer can also communicate differently. E.g., the seller chooses a price, and the auctioneer tells it to the buyer and the object is sold to the buyer only if they accept (no negotiations) and the auctioneer takes a commission. The safe deviation here is the auctioneer can quote a higher price to the buyer and pocket the difference. A protocol is “credible” if running the mechanism is incentive compatible for the auctioneer over any safe deviation, i.e. the auction prefers playing by the book.

A first price auction is “static” - each bidder is called to play exactly once and has no information about the play history when selecting his action/bid.

The ascending auction is “strategy-proof”. Thus it needs no or very less strategic planning from bidders.

The second price auction is “static” and “strategic-proof”. It combines the virtues of the first price auction and the ascending auction but is not credible, as seen in our examples.

Ultimately the paper presents the auction mechanism trilemma. Static, strategy-proof or credible. An optimal auction can have any two of these properties but not all three at once. Should an auction be static, strategy-proof and credible? While an opportunity for a nuanced discussion presents itself, here are some base arguments for every parameter. Advertisement auctions must be conducted in milliseconds or faster, so latency disallows multi-round auctions, so static auctions might be preferred. Strategy-proof-ness matters when bidders are inexperienced or have opportunities for rent-seeking. Credibility matters, especially when bidders are anonymous to each other or require that the bids are kept private. In this case, an auctioneer has all the information to deviate safely.

Ultimately, The paper shows that the ascending price auction (with reserves) is credible, and under some conditions, it is a unique, credible strategy-proof optimal auction. The conditions being it requires an unbounded number of rounds.

Deferred Revelation Auctions

In the paper, “Credible, Truthful and Two-Round (Optimal) Auctions via Cryptographic Commitments”, Ferreira et al. design an auction that avoids the trilemma and provides a truthful, truthful, revenue-maximizing, credible, two-round auction under the assumption of basic cryptographic primitives.

The cryptographic primitive that they use is commitment schemes. A commitment scheme is a cryptographic primitive that allows a person to commit to a chosen value while keeping it hidden from others. It ensures that the person cannot change the value after committing to it, which can be revealed later. Commitment schemes are essential for maintaining trust, integrity, and security in various cryptographic applications.

So the skeleton of the auction is as follows:

• Ask each bidder to commit to their bid

• forward these commitments to all other bidders

• ask each bidder to reveal

• forward the revealed bids to all other bidders

This auction is truthful, revenue optimal and two-round. The auctioneer can deviate primarily by submitting fake bids, but if we assume that all committed bids must be revealed, then the auctioneer cannot deviate and submit fake bids. While this is sound, auction design should involve the edge case where some bids are concealed, and the auction is not stalled. For this, the authors suggest fining any bidder that does not reveal and paying this fine to the winning bidder. The auctioneer now faces a tradeoff between submitting as many fake bids as they want and paying the penalty for every bid they conceal.

Ferreira et al. paper designed Deferred revelation auctions as a communication efficient auction assuming the existence of cryptographic commitments and that all bidder valuations are MHR (Monotonic hazard rate). They also showed that DRA is not credible in settings where bidder valuations are α-strongly regular unless α>1. We will take a brief moment to understand MHR and α-strongly regular distributions.

α-strongly Regular Distribution

The paper “The sample complexity of Revenue Maximization” by Cole and Roughgarden originally studied alpha-strongly regular distributions. The main focus of their work was to study auctions, particularly in Myerson’s auction, when distributions are known only approximately and how to analyze the resulting expected revenue as a function of the number of samples.

where the virtual value function is given as follows

Alpha-strongly regular distributions, also known as alpha-regular distributions, are a class of probability distributions used in auction theory to analyze bidder valuations. An alpha-strongly regular distribution satisfies the following condition for some constant alpha (α):

• The virtual value function is non-decreasing.

The virtual valuation function is derived from the probability distribution of bidder valuations and is crucial in determining the optimal auction mechanism. In particular, the α-strongly regular condition guarantees that the virtual valuation function is well-behaved and allows for tractable analysis of the auction.

Alpha-strongly regular distributions are a more general class than Monotone Hazard Rate (MHR) distributions. MHR distributions are a special case of α-strongly regular distributions, where α = 1. This means that all MHR distributions are α-strongly regular, but not all α-strongly regular distributions are MHR.

What does “bidders valuations” being MHR mean? It means that the valuations satisfy the Monotone Hazard Rate (MHR) condition. The Monotone Hazard Rate condition states that the ratio of the probability density function to the complementary cumulative distribution function is non-decreasing. In simpler terms, the probability of a higher bid occurring increases as the bid value increases. MHR distributions have certain desirable properties in auction design, such as leading to higher revenue for the seller and promoting more efficient allocations. Intuitively, MHR bidder valuations can be thought of as having exponential tails where the buyer valuation/bidding follows an exponential curve.

Credible auctions on blockchain

Summing up what we’ve seen so far:

• An auction is credible if safe deviations cannot increase the auctioneer’s revenue

• Akbarpour et al. showed the auction trilemma, and that credibility cannot coexist with truthfulness and bounded communication complexity.

• Ferreira et al., in private channel auctions, cryptographic auctions (specifically cryptographic commitments) can achieve credibility, truthfulness and bounded communication complexity if buyer valuations satisfy a regularity condition. The collateral requirements ensure that an auctioneer cannot add and refuse to reveal fake bids for free (since there’s a penalty).

Can we design auctions without requiring regularity conditions? Ferreira et al proposes the Ascending Deferred Revelation Auction (ADRA). It is similar to an ascending auction, but prices increase exponentially from one round to the next. Even this auction, if done using commitment schemes, can ensure that the auction is strategy-proof and revenue optimal, but it has some limitations. One crucial underlying assumption that the Ferreira et al. paper has is that the buyers and auctioneers communicate over private channels. In other words, All communication between bidders can only happen through the auctioneer. This needs the auctioneer, to be honest. Otherwise, the auctioneer can launch a man-in-the-middle attack by censoring and injecting messages.

What if there was a censorship-resistant public channel over which the commitments could take place? In this case, any message sent by a bidder will be seen by all other bidders and any message received by a bidder is also received by all other bidders. In Chitra et al., the authors ask, “How would auctions look like if they were conducted on a blockchain?” and “what guarantees or features would this auction have?”. They find the following.

• They expand the work done by Ferreira et al. and show that Deferred Revelation auctions (DRAs), when done over a secure, censorship-resistant ledger, are credible for α-strongly distributions as long as α>0. In simpler words, conducting auctions over public channels can expand the domains for which these options are credible.

• DRAs are not credible if buyer valuations are regular or α-strongly regular for α=0, i.e. blockchains are not a panacea and don’t make auctions universally credible.

The paper designs a single-item auction with n buyer auctions with independent valuations and shows that it is credible. Blockchains in the past decade have then and again proven to be the gold standard of censorship-resistant public channels where agents can not only communicate but also do computations. This also makes it very appealing for mechanism designers because “a public channel” in its true sense does not exist in the credibility framework of Akbarpour et al. because they assume auctions would run over the internet, which is private, i.e. happen across private channels.

An intuitive way of thinking about auctions, and this paper is:

• Usually, in single-item auctions, you have multiple bidders, let’s say who bid 10$, 5$, 20$ etc to win the item, ultimately the winner in case of a second-price auction would be the person who bid 20$ but would end up paying only 10$.

• There are some properties that we want the auctions we design to have, the most important of them being the auction should be credible,

  • credibility in auctions can be thought of as when the auctioneer who wants to profit from the auction should conduct it fairly and not resort to malicious behaviour like misquoting the bids to increase his profit share.

• While it was earlier shown that the properties we like are impossible to attain in an auction design, Deferred revelation auctions were proposed by Ferreira et al. who found a 2 round auction design with commitment schemes to make it happen.

• In formulating auctions, we need a way to model bidder valuations since we cannot assume the values of the bids directly. This is because it would not generalise.

• We model bidder valuations by assuming they are sampled as values from a distribution, i.e. the user’s bidding behaviour could follow values along distributions.

• DRA, aka Deferred revelation auctions, showed that the auction design is reliable when you assume that the bidder valuations were Exponential distributions.

  • Exponential distributions are used infrequently and only represent a subset of all possible distributions. (D2 in the image above)

• The paper “Credible auctions on Blockchains” expands the distributions we can assume bidders to have, which is a far larger class of distributions compared to just exponential distributions. For example, this includes Pareto distributions. (D1, D3 etc., in the image above)

• While the paper ultimately mentions that when α=0, the auction is unreliable.

• A major takeaway of the paper (which might not be understood) is distributions which are 0<α<1 are a far bigger class of distributions than α>1, which was proved in the earlier paper by Ferreira et al. and which encompasses just exponential distributions.

Where could these credible auctions be used?

• NFTs: NFT volumes have reduced in the past six months but have seen a steady influx of participants and transactions overall. The authors of the paper “A framework for single-item NFT auction mechanism design” show that NFT auctions cannot achieve incentive compatibility and collusion resistance. DRAs can be one answer to this, especially for auctions for 1/1 art pieces like those on foundation.

• MEV (Miner extractable value): Flashbots runs the most popular auction on ethereum, and the majority of MEV has been extracted through these auctions run by validators. What does an auction look like?

  • MEV refers to the excess value validators can extract by reordering, adding or removing transactions to a blockchain.

  • Bidders (also known as MEV searchers) bid on transaction priority for sequences of transactions.

  • If a bidder wins an auction, they are guaranteed their bundle of transactions is included in the block, and the auction revenue is distributed to the validator who proposes this block.

  • Flashbots currently runs these first-price, sealed bid auctions as a monopoly, but there is an active need for decentralizing this aspect of auctions. The condition stems from the ability to censor or delay time-sensitive transactions as these preferences can be expressed by the auctioneer, in this case, Flashbots.

  • A credible and truthful auction can make sure nobody can manipulate the outcomes.

In the current transaction market, the block proposer (today: a miner, post-merge: a validator) directly chooses which transactions to include in the next block by looking at which transactions in the mempool pay the highest priority fee.

Proposer/builder separation (PBS) fixes this by splitting the block construction role from the block proposal role. A separate class of actors called builders build exec block bodies (essentially an ordered list of transactions that becomes the main “payload” of the block), and submit bids. The proposer’s job is only to accept the exec block body with the highest bid. Notably, the proposer (and everyone else) does not learn the contents of any exec block body until after they select the header (and hence the body) that wins the auction.

• From “Notes of Ethereum: Increasing Censorship Resistance through PBS” by Vitalik Buterin

• Proposer-Builder separation: In proof of work consensus, a block has to be determined before validator selection, while in proof of stake, the block content can be determined after the validator is selected. Thus the validator can auction away the privilege to build the next block. These are single-item (just one block) auctions. This separation between the proposer and the builder is meant to increase the decentralization of block production in blockchains.

  • The collateral requirements of DRA can be used to formalize censorship-resistant bounds, and perhaps even under auctioneer deviation, a PBS auction following a DRA can make it incentive compatible.

DRA over a ledger

The overall protocol looks similar to what was done in a normal DRA, where the auctioneer has a private channel for each bidder, except for some details.

Commitment Phase

The auctioneer writes into the ledger, and each buyer draws a random number from their distribution and commits to the ledger. Each buyer either aborts or deposits collateral, which all participants observe.

Revelation Phase

Each buyer reveals their commitment, and all other buyers observe this.

Smart Contract Resolution

The highest bidder is awarded the item, and the smart contract transfers the collateral from those who didn’t reveal their commits to losing the collateral. Those who didn’t win and revealed their commits are given their collateral back.

Tiebreaking

All ties are broken lexicographically.

The significant difference between this mechanism and Ferreira et al. is the public communication channel ensures all buyers receive messages. Buyers do not rely on the auctioneer's reputation for receiving the item or their collateral back because all of this is implanted through a smart contract.

The paper's proofs are beyond this blog's scope but are straightforward and concisely written. The paper can be found here. One thing to note is that commitments can be done using ZKPs or alternative commitment schemes like EIP-5732 when it is added.

The paper ultimately shows that DRA is credible for all α-strongly regular distributions for α>0 and not for regular distributions, i.e. where α=0. This leaves an open question and design problem for other settings, including regular distributions and multi-item auctions.

References

• To read the original Trilemma paper, refer to “Credible Auctions: A Trilemma”.

• To read the paper introducing Deferred Revelation auctions, refer to “Credible, Truthful and Two-round (Optimal) Auctions via Cryptographic Commitments”.

• To read the paper introducing α-strongly regular distributions, refer to “The sample complexity of Revenue Maximization”.

• To read the paper expanding the work on α-strongly regular distributions, refer to "Applications of α-strongly regular distributions to Bayesian auctions”.

• To listen to a talk on this paper, you can look at