Smart Contract and Nash Equilibrium
Smart contracts are the application of blockchain, and they are on the center of the blockchain storm in the year of 2018. Smart contracts are used to launch Token, Initial Coin Offerings (ICO), exchange Tokens, and design games. Generally, a smart contract is a computer program that is capable of monitoring, executing and enforcing an agreement. It can improve the efficiency of transactions by removing of intermediaries, and establish trust through certainty of execution, tractable and irreversible transactions. All the players act based on the protocols that are defined in a specific smart contract. Meanwhile, the protocols of a smart contract can be modeled as a game. A game models a situation where two or more players have to take some decisions that will influence one another's welfare in game theory. We may interest in finding the game-theoretic properties of a game. In this article, we will discuss the most influential concept in game theory: the Nash equilibrium.
Prisoner’s Dilemma and the Definition of Nash Equilibrium
Before describing the definition of Nash equilibrium, I would like to introduce the game of Prisoner’s Dilemma to illustrate the idea of Nash equilibrium. Assume that there are two prisoners Alice and Bob. They are interviewed separately so that they cannot communicate with each other. Each of them has two strategies, called “Confess” and “Deny”. They aim to minimize the year of imprisonment.
Table 1 shows the payoff of this game. If both of them choose “Deny”, they will both serve 2 years in prison. If one of them chooses “Confess”, the confessor will serve 1 year and the other will serve 5 years. If both of them choose “Confess”, both of them will serve 3 years. Remember that we assume that Alice and Bob cannot communicate with each other, and they are interested in their own payoff. If prisoner Alice chooses “Confess”, the better response of prisoner Bob is “Confess”. If prisoner Alice changed to choose “Deny”, the better choice for prisoner Bob is still “Confess”. The case of prisoner Bob is symmetric. According to this reasoning, both of them will choose “Confess”. In this game, (Confess, Confess) is a Nash equilibrium, which means that it is the set of strategies that maximize each prisoner’s payoff given the strategies of all the other players. The prisoner’s dilemmas game also indicates that rational actions can lead to bad outcomes. The state (Deny, Deny) is a better result for both of Alice and Bob compare to the state of (Confess, Confess), but rational choice will lead to a worse state which is the Nash equilibrium.
A Nash equilibrium is a combination of strategies, one for each player, such that no player can increase her payoff by unilaterally changing her action.
In next section, I will introduce Nash equilibrium in a specific Non-cooperative game, the Vickrey auction.
Nash Equilibrium and Vickrey Auction
The Vickrey auction, which is named after Nobel Laureate William Vickrey, is a type of sealed-bid auction where a bidder submits her bids without knowing the other bidders’ bid. The highest bidder wins, and the payment of the winner is the second highest bid in the auction. The dominant strategy in a Vickrey auction for each bidder is bidding their valuations, which means that bidding truthfully is the best strategy for a bidder no matter how others behave. Furthermore, bidding truthfully is a Nash equilibrium of the Vickrey auction. In this equilibrium, where each bidder submits her valuation, there is no incentive for a bidder to unilaterally deviate. The Nash equilibrium in a Vickrey auction relies upon the private values assumptions that each bidder’s valuation only depends on her own information. The lesson we can learn from this model is that well designed trading mechanism can achieve truthfulness.
To implement the Vickery auction as a smart contract, we could design two stages in this contract: the submission stage and the bid opening stage. In the submission stage, the bid that submitted by each bidder should be encrypted using a nonce to keep the bid sealed. Each bidder also should send a certain amount of deposit to the auctioneer. The deposit will be refund to the bidder when the submitted bid has been revealed. In the bid opening stage, each bidder sends their nonce to the auctioneer, so that their bid can be revealed. At last, the winner is the bidder has he highest bid and her payment is the second highest bid. All the deposit should be refund.
The property that every bidder can achieve their best payoffs by bidding their valuation is called incentive compatible. Another influential auction that has the property of incentive compatible is Vickrey-Clarke-Groves (VCG) auction. A VCG auction is a generalization of a Vickrey auction for multiple items. I will describe this model together with mechanism design in a future article. In the following section, I will describe another widely used auction, the Dutch auction.
Symmetric Equilibrium and Dutch Auction
The Dutch Auction is used to sell flowers in Holland, and it has been used in an IPO or to sell Treasury bills for government agencies. Dutch auctions are interactive auctions in which the seller gradually decreases the price of the item from a highest bidding amount. A Dutch auction ends when the first moment a bidder accepts the offered bidding price. The payment of the winner is the accepted price.
On the platform of Ethereum, Dutch auction was used by Gnosis to sell Tokens and they reached their goal of 250K ETH in less than 15 minutes. Meanwhile, the popular game CryptoKitties is using Dutch auction to sell their cats. We can imagine that Dutch auction will be used in more and more smart contracts to figure out the optimum price of various commodities.
A Dutch auction can also be modeled as a noncooperative game. Is truthful bidding a Nash equilibrium in a Dutch auction compared to the Vickrey auction? The answer is no. However, there exists another equilibrium by assuming the distribution of each bidder’s valuation in a Dutch auction: symmetric equilibrium. Symmetric means that the bidding values of two bidders are equal if they have the same valuations.
In a Dutch auction with n risk-neutral (a bidder is indifferent to risk when making decision) bidders whose valuations are independently drawn from a uniform distribution on [0,1], a symmetric equilibrium is given by the strategy profile
, where v represents the valuation of a bidder.
The Dutch auction used by GNOSIS is different from the standard model we talked above. They modified the payment mechanism. The GNOSIS Dutch auction starts at a high price for their token, and the price decreases with every block. In code:
The parameter priceFactor is initialized by the author of the code. The auction closes when the sale cap is reached, and the payment of each bidder is the same that equals to the value of the final bid in the auction. Here comes a question, is truthful bidding a dominant strategy in GNOSIS Dutch auction?
Since the smart contract that implements auctions are executed automatically, it is valuable to analyze the game-theoretic properties of a given smart contract before deploying it on blockchain.
Verification of Game-theoretic Properties in a Smart Contract
Vitalik Buterin mentioned the challenge of “differences between implementation and intent” for the security of smart contracts in his blog. He also worried about the “game-theoretic vulnerability” in blockchain-based market. The potential solution for these challenges is combining game theory with formal verification. We can design a trading mechanism that has some desirable game-theoretic properties, and then verify that the smart contract implemented this mechanism really contain the declared game-theoretic property. For example, for a given smart contract of Vickrey auction, we can prove and verify that this program really contains a Nash equilibrium.
Conclusion
In this article, I illustrate that a smart contract can be modeled as a game, thus we can analyze the game-theoretic properties, such as Nash equilibrium, of the smart contract. Carefully designed mechanism that has desirable game
theoretic properties has been used by giants to make profit decades ago. The “generalized second price auction”, which has been used by Google and Yahoo! to sell online advertising, is a robust mechanism which has a locally envy-free equilibrium in static environment. Although we still need to adjust the standard game theory models to fit to the actual implementation of smart contracts in decentralized platforms such as Ethereum. It is a promising direction to apply game theory and formal verification to design and analyze smart contracts, so that we can eliminate the gap between intention and implementation. Furthermore, we can not only avoid the “game-theoretic vulnerability” but also bring “game-theoretic properties” into smart contracts.
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.
