Mechanism Design in Cryptoeconomics
As the emerging of cryptocurrency and the development of blockchain techniques, traditional economic models have the potentiality to be extended to apply in the Crypto scenario. One of the killer application in crypto-economics is implementing smart contracts in blockchain. Smart contracts can be treated as protocols that govern the transactions in a decentralized digital market. They are executed among two or more players under the transaction protocols. During the execution of a smart contract, a player can react based on his own strategy to maximize personal payoff. As a smart contract designer, he has the responsibility to design a system that guarantee the good performance of players. Remember that those players have their own strategies, and they prefer the strategy that will maximize their payoffs in an online trade. A system designer can use mechanism design to design a good trading protocol or a smart contract that guarantee good properties for rational players.
Mechanism design is a major breakthrough in modern economics, it has been used to analyze the behavior of individuals in different institutions and markets by considering incentives and private information. Because of the big influence of mechanism design theory, Leonid Hurwics, Eric Maskin, and Roger Myerson were awarded the 2007 Nobel Prize in Economics. Before introducing the advantages of mechanism design. I would like to introduce an interesting example to illustrate how different mechanisms can influence the behavior of rational participants.
Sponsored Search Auction
In 1997, Overture used a generalized first-price auction to sell Internet advertising. In this first-price auction, advertisements were in descendant order based on bids, the higher bid obtains higher position. The payment of each click of the advertisement is the bidding price of that position. Because of the transparency of first price auction, Overture successfully attracted lots of advertisers. However, Overture found that the first-price auction is unstable as shown in Figure 1.
Figure 1 shows the top bids for a keyword in 14 hours from Overture. In point A, the top bid begins from a price that is higher than the bid of second highest advertiser. Then, the second highest auctioneer finds that he can win the top position by adding $0.01 to current highest bid. When the first auctioneer finds he has been overbid, he increases his bid in turn. This will continue until the bid reach the maximum budget of one of these two auctioneers in point B. An auctioneer chooses to reduce his bid to obtain the second position through a bidding which is higher than the third auctioneer. In point C, the second highest bidder finds he can overbid to gain the position again. This phenomenon continues to generate a saw-tooth pattern for the given keyword. First-price auction mechanism encourages a bidder to react from other bidders’ actions while suffers from the problem that the winner is not always the bidder who has the highest valuation for the top position.
To overcome these disadvantages of first-price auction, Google invented the generalized second price auction (GSP). In GSP, advertisers are sorted in descending order based on their bids. The advertiser in one position pays the bid of the advertiser in next position plus an increment ($0.01). For example, if you win the top position with bidding $2, and another bidder win the second position with bidding $1, you only need to pay $1.01. After several iterations of the auction, a bidder can find out all the bids of other bidders in previous auctions, that means the valuations of all participants become public information, and then GSP can reach to a stable status which is called “locally envy-free equilibrium”. In this equilibrium, all bidders have no intention to swap positions and payments with the bidder just above them. Currently, GSP is a dominant mechanism to sell Internet adverting for search engine companies.
The above example of sponsored search auctions tells us that the rules of a trading mechanism really matters. These rules can determine the behaviors of participants who are self-interested. Bad designed mechanisms will lead to unexpected behaviors and cause inefficient transactions. We need to avoid these shortages when we design and implement smart contract on the blockchain. Here comes an important question: Do we have a tool to design good smart contracts for strategic participants, and achieve the goals to predicate the behaviors of rational participants? YES! Mechanism design is a silver bullet to design smart contracts.
Myerson’s Lemma
To understand how mechanism design can be used to design systems that involved rational participants to generate desirable outcomes, we will introduce the Vickrey auction. As we mentioned in previous articles, the bidder in a Vickrey auction has a dominant strategy: bid his valuation to an item no matter what other bidders do. By bidding truthfully, the utility of a bidder will never be negative. The utility of a bidder is defined as a quasi-linear utility model. That is: if a bidder wins, he gets utility of v -p, where v is his valuation, p is his payment. All the losers get utility of 0. Formally, the Vickrey auction has three desirable properties:
1. The Vickrey auction is dominant-strategy incentive-compatible (DSIC).
2. If all bidders report truthfully, then the Vickrey auction maximizes the social welfare.
3. The Vickrey auction can be implemented in polynomial time.
These properties make the model of Vickrey auction an attractive mechanism to system designers. We would like to design some other mechanisms that possess the same properties as in the Vickrey auction: DSIC, Social welfare maximization, and Polynomial running time.
Now, the question becomes how to design a mechanism that have those properties? We can split the design into two phases: Winner determination to define the allocation rule, and Payment of participants to define the payment rule. To accomplish these two phases, I would like to introduce “Myerson’s Lemma”, which is a powerful tool to design incentive compatible mechanisms. Myerson’s Lemma requires a single-parameter environment.
A single-parameter environment has n players (bidders), Each player i has a private type (valuation v_i), which describes his preference over outcomes. The outcome is represented as a feasible set X, each element of X is an n-vector (x_1, x_2,…,x_n), where x_i denotes the amount of stuff given to player (bidder) i. For example, in a single-item auction, the set X is a set of 0–1 vectors, such as vector = (0, 1, 0, 0), where only one winner that own the item has value of 1. Player i’s value for outcome X is v_i * x_i.
In addition, I would like to introduce two definitions here to help us understand the meaning of Myerson’s Lemma.
Implementable allocation rule: An allocation rule for a single-parameter environment is implementable if there is a payment rule such the sealed-bid auction that is defined by the given rules is DSIC.
Monotone allocation rule: An allocation rule for a single-parameter environment is monotone if for every bidder i and the bids by the other bidders, the allocation to i is non-decreasing in its bid, i.e. bidding higher can get you more stuff.
Myerson’s Lemma: For a single-parameter environment,
1. An allocation rule is implementable if and only if it is monotone.
2. If the allocation rule is monotone, then there is a unique payment rule such that the mechanism is DSIC.
3. The payment rule is given by an explicit formula (the formula and proof can be found here).
Design a DSIC Sponsored Search Auction
As shown in Figure 2, for a given sponsored search auction there are k slots for sale, the click-through rate of a slot is α, bidder’s valuation for a slot is v. We would like to design an auction that satisfies the three properties of a Vickrey auction.
Actually, the sponsored search auction satisfies the single parameter environment setting: each bidder only bids one amount. Although there are several slots, a bidder bids only one value, each slot is assigned to at most one bidder and each bidder is assigned at most one slot. If bidder i is assigned to slot j, then the component x_i equals the click-through rate (CTR) α_j of this slot.
Thus, the Myerson’s Lemma can be used to redesign the sponsored search auction, so that we can get a new auction that is incentive compatible. As shown in Figure 2, we have n bidders and k positions. Each position has an click-through rate α, we also assume that higher position has higher CTR, i.e α_1>α_2>⋯>α_k>0. In this auction, we would like to assign player i to position j by defining following two rules.
The allocation rule: we can use a greedy rule to allocate the slot. The bidder with the highest bid wins the top position. Remove the assigned bidder and slot, then iterate until all the slots be allocated.
The payment rule: the payment of bidder i for each click for a slot is:
The payment equation shows that when a link is clicked, an advertiser pays a suitable convex combination of the lower bids.
Although the GSP auction that has been used by Google has several desirable properties, it is not incentive compatible. Search engine companies not using the incentive compatible sponsored search auction model is caused by historical reason.
Generally, we need to define three components in a mechanism design problem: an environment (e.g. the single parameter environment) where the game designer operates; a choice function that describes the designer’s preferred outcomes (e.g. give an item to the person who values it most); a solution concept which describes the kinds of strategy profiles of games (e.g. dominant strategy equilibrium).
Conclusion
The challenge for a smart contract designer is to design a system that will lead to good performance for strategic participants. As the designer would like to design a mechanism that could maximize social welfare while the players prefer to maximize their utility, the Myerson’s Lemma guarantee that the player has a dominant strategy to maximize his utility, while also maximized the social welfare. Mechanism design can be used to solve the problem of misalignment between the participant goals and designer goals. In this article, we introduced the mechanism design theory in a single-parameter environment, and we can use this theory to design a mechanism that can be implemented in polynomial time. However, there are many cases where we can not implement a given mechanism in linear time. For example, compute the outcome of a combinatorial auction mechanism is NP hard. We will talk about more complex mechanisms in future articles.
SECBIT was founded by a group of cryptocurrency-enthusiasts. We are doing research on smart contract security, smart contract formal verification, crypto-protocols, compilation, contract analysis, game theory and crypto-economics.
