Blockchains mechanism design

Interesting: when actual people solve cake division problem in game-theoretic experiments, called Dictator and Ultimatum, they show results, which are far away from equilibriums, predicted by standard solution concepts. Empirical tests even demanded creation of new solution concept, quantal response equilibrium. Still, it is not used in blockchains and cryptocurrencies.

But let's get back to our deeds. Note that the mother does not know preferences of her kids concerning division of the cake: she does not know what her kids consider to be «fair». Just like Nasreddin does not know true speeds of donkeys. But both of them want to achieve fairness in some sense. Mechanism, which they design, reveals this private information. This anectodal situation with cake division is analysed in a number of papers and surveys. Among them there is doctoral dissertation of Swaprava Nath "Mechanism Design for Strategic Crowdsourcing" (introduction to mechanism design is on the page 23). The introductory chapter of the work contains very concise and simple, although technically sound explanation of mechanism design environment, social choice functions, direct/indirect mechanism, revelation principle, and several other important notions of mechanism design.

To cut a long story short, mother and Nasreddin need to implement social choice functions mapping preferences of agents — kids and traders — to outcome. But it may be rational for agents to lie strategically, i.e. for kids — to show mother inflated preferences toward the cake, for traders — to decelerate donkeys to zero speed. There is direct mechanism that reveals donkeys' speed and kids' preferences: simply truthfully reports speed and preferences to partner-trader or mother. But this mechanism is never turned on since agents resort to strategic lie. (And where everybody lies, we have untrusted environment — remember the definition of distributed ledgers from the first chapter.)

Then there is indirect mechanism which basically does the same as direct one only implementing complex set of rules. «One divides the cake, the other selects the share» and «change donkeys» are examples of such indirect mechanisms. Finally, there is revelation principle which connects direct and indirect mechanisms and makes the whole mechanism design possible. More technical introduction to revelation principle can be found here, for example.

One of the most important and widely discussed concept in cryptoeconomic mechanism design is incentive compatibility (you can read about it in Wikipedia or Britannica). The concept itself was introduced in the paper by Hurwicz (1972) to describe games in which it is not beneficial for a rational player to violate game protocol. Historically, the idea of incentive compatibility could be traced back to famous «laissez-faire» concept coined by Adam Smith.

Remember the case of Nasreddin. At first, the merchants were in an incentive incompatible system — it was not profitable for them to speed up the donkeys. But then they got into another system that was incentive compatible. Let's recall the imaginary cryptoeconomic system from the first longread of our course as well as the Bitcoin and blockchain systems. At first glance, it seems that although none of the miners think about the well-being of the system, nevertheless, the existing system of incentives allows them to achieve the benefit of maintaining the system. However, it is not: Ittay Eyal and Emin Gun Sirer from the Department of Computer Science of Cornell University show in their seminal paper "Majority is not Enough: Bitcoin Mining is Vulnerable" that the Bitcoin protocol is incentive incompatible due to vulnerability of selfish mining.

The main idea of the article is that it may be beneficial for rational miners to pool together (which they already have done) and mine their version of the blockchain overtaking all the others by several blocks, and then rolling out this version, canceling all transactions in a competing fork. A group of researchers from Stanford University in their paper "Incentive Compatibility of Bitcoin Mining Pool Reward Functions" also examines this issue and offers a number of solutions to motivate miners in order to avoid a selfish mining attack. Make sure to read this article too, it is simple and short, co-authored by Tim Roughgarden, the author of several notable courses on algorithmic mechanism design (we also recommend you to go through them; at least, read this piece on incentives in Bitcoin mining).

Another example of incentive incompatibility in Bitcoin protocol is the paper by the group of researchers from Microsoft and Cornell University "On Bitcoin and Red Balloons". Decentralized currencies like Bitcoin rely on competition of nodes which in turn relies on information propagation (about transactions and recent blocks) between them. But Bitcoin and some other cryptocurrencies have no proper incentives for nodes to share information about transactions and recent blocks. In fact, the authors conclude that for rational node it is irrational to propagate information.

The researchers also propose to alter just a notch incentives in Bitcoin protocol and show using game-theoretic approach that this altered version of protocol is Sybil-proof (we will talk about this notion in one of the several coming longreads) and is the best strategy for rational player.

Finally, the research paper "Optimal Selfish Mining Strategies in Bitcoin" by the group of Israeli scientists further extends Eyal et al. (2013) by developing optimal algorithm for selfish miner and thus, determining minimal fraction of computational power that an attacker has to possess for successful attack.

We got to the main topic of the longread. But before moving forward, we will check the mastery of the main topics of the longread. Is Vickrey auction from the previous video compatible by incentive? And what do direct and indirect mechanisms look like for him?

Yes, the auction is incentive-compatible. Again, like in examples with Nasreddin and cake division, we do not know true types of agents (or their preferences) and we design mechanism to reveal it.

One more question. Remember the story with focal points last week and the article by Vitalik Buterin, and then read this article. Now try to look at the article from the formal point of view. What are the agents and their preferences? What is social choice function? What is revealed in the equilibrium?

At the end of this longread, I recommend you to listen to the podcasts below to learn more about mechanism design in cryptoeconomic systems.