I Threw Away $7.6 Million In Bitcoin Five years ago, I threw away a hard drive. An utterly generic 250GB portable hard drive, already a few years old, with a duo of dings and scrapes in its shell and with the beginnings of an audible click that would have eventually killed it. It had a […]
What is Cryptocurrency Game Theory: A Basic introduction
An in-depth guide by BlockGeeks
What is Cryptocurrency Game Theory? One of the greatest innovations of the 21st century is, undoubtedly, the advent of cryptocurrency.
What is that makes the blockchain technology such a breakthrough? Let’s look at the real world and how fiat currency is maintained and stored. No matter who you are, your money is going to be stored in a centralized location, i.e. the bank. The problem with this model is that you are providing your money over to an entity and it is at the risk of getting compromised because of a diversity of reasons. The blockchain solves this problem by being fully decentralized and corruption free internally. The way it achieves this is by the incorporation of cryptography and game theory.
What are market structures?
Picture Courtesy: ThingLink
Before we understand the concept, we need to go through some basics very first. The organization and fundamental characteristics of any market are called market structure. The market structures are differentiated based on many factors like a number of producers, control over prices and barriers to entry. Based on these factors, there are four different kinds of market structures:
Ideal competition is a market place where it is effortless for anyone to get into the market and individual sellers don’t have any power over the price of the product. Think of mangoes. It is effortless for anyone to get into the market, all that anyone has to do is to grow mangoes. Plus, they can’t willingly switch the price of the mangoes. If one person sells a mango for $Ten then the buyer can simply buy it from someone who is selling mangoes for $Five.
A monopoly is the polar opposite of a ideal competition. This is a market place which is predominated by one corporation and the barriers to entry are so high that nobody else can inject it. De beers diamonds are a excellent example of a monopolistic market.
This is a marketplace which has a lot of sellers and very low barriers. Their products are similar but not truly identical. Think of the pizza delivery service. Now, dominoes and pizza hut have the same product with subtle differences. Obviously one can slightly price their product a little higher based on factors like customer preferences. However, if dominoes price their pizzas way too high, then people will simply go over to pizza hut. Consequently, if dominoes and pizza hut both begin overcharging, since the barriers to entry is so low, another player can come in and take all the customers.
Oligopolies are market places which are predominated by a few markets and the barriers to entry are high. One of the best examples of an oligopoly is the smartphone market. The market is predominated by few number of companies like Samsung, Apple, and Huawei. Much like monopolistic competitions, the products are similar but not identical. While this does give them some control over their prices, they don’t truly have much of a leeway. If tomorrow, Apple determines to price their iPhones at $4000, apart from the Apple fanatics, most will simply opt for an Android phone. Obviously, they can always get together and determine as a group to mutually increase the prices, but this is called “collusion” and is illegal in many countries, including the United States.
So, when they can’t rival by switching prices, how can they get that edge over their competitors? They do so by “non-price competition”, which means challenging without switching the price. How do they do that? They do so by switching the look and style of their products and providing a unique practice. However, the most recognizable form of non-price competition is advertising.
Advertising is one of the most effective ways of displaying unique qualities of your products and to introduce fresh products. But then again, there is a problem. How many of the advertisements do you see actually stick? Chances are that you have been bombarded by tons of ads today itself, how many of them do you actually reminisce? If you are a player in an oligopoly and you keep blindly advertising, you are going to be spending a lot of money.
As a result of that, in order to make up all that money, you are going to invariably have to increase the price of your products. If that happens, your buyers are simply going to go to your competitors. So how do you go about this? How do you advertise your products without losing out on your customers? You will have to basically take decisions based on the deeds that your competitors will take. In order to do that, you will have to use Game Theory.
What is the Game theory?
Game theory is the probe of strategic decision making. This is how many corporations make decisions while keeping in mind the deeds that their competitors will take. Game theory was devised by John Van Neumann and Osker Morgenstern in one thousand nine hundred forty four and was considered a breakthrough in the investigate of oligopoly markets.
Since then the game theory has found a life of its own and has seen widespread implementations in various other technologies and fields.
A game theory model has at least three components:
- Players: The decision makers. Eg. The managers in the firms.
- Strategies: The decisions they want to take to further their companies.
- Payoff: Outcome of the strategies.
In game theory, there are two types of games.
- Zero sum game: It is a game in which the build up of one player comes at the expense of another player.
- Non zero sum game: A game where the build up of one player doesn’t come at the expense of another player.
So, how does one apply game theory? Let’s go back to what we were discussing again, should or shouldn’t a company advertise a particular aspect of their product. Suppose there are two firms A and B.
The table that you see above is called a “payoff matrix”. The table basically reads like this:
- If Hard A and B both determine to advertise then the payoff for both of them is four and three respectively.
- If Stiff A doesn’t advertise and B determines to advertise, then the payoff is two and Five.
- If Rock hard A advertises and B doesn’t advertise then the payoff is five and 1.
- If both Firms A and B don’t advertise then the payoff is three and Two.
So, what decision should both A and B take which will give them the best pay off? To solve this, we need to look at the script that serves both A and B.
Firstly, let’s look at Hard B.
Then Rigid B has a payoff of three if they advertise and one they don’t advertise. So, obviously, their best payoff lies in advertising.
Then Rock hard B has a payoff of five if they advertise and two if they don’t advertise. In this case their best payoff lies in advertising.
- Conclusion: Regardless of what Rock-hard A does, Rock hard B should advertise.
Now, let’s look at Stiff A.
The Stiff A has a payoff of four if they advertise and two if they don’t advertise. So, once again, their best payoff lies in advertising.
In this case, Hard A has a payoff of five if they advertise and a payoff of three if they don’t advertise. Once again, their best payoff lies in advertising.
- Conclusion: Regardless of what Rock hard B does, Stiff A’s best strategy lies in advertising.
So, in this example, for both Rock-hard A and Hard B, their most stable state will be if they both advertise, which is:
For both Hard A and Rock hard B, this is their superior strategy. A superior strategy is the best course of activity for a player regardless of what the opponent does. In this example, (Four,Three) is also the Nash Equilibrium.
What is Nash Equilibrium?
Pic Courtesy: ICMIZER
The Nash equilibrium is a solution to a game where each player chooses their optimal strategy given the strategy was chosen by the other and they have nothing to build up by shifting their strategy. This was formulated by John F Nash who was portrayed by Russell Crowe in the movie, “A Beautiful Mind”. This has humongous implications in a distributed computer system like the blockchain. In fact, the blockchain is “cheat-free” because the entire protocol is in a Nash Equilibrium. We will discuss this later, but for now, let’s see the Nash Equilibrium in act in one of the most famous game theory concepts.
The Prisoner’s Dilemma
Pic Courtesy: “This Place” youtube channel.
Ahh.. the good old prisoner’s dilemma. Chances are that if you have any idea about game theory then you must have come across this problem. Anyway, let’s get right to it. Suppose Rob and Ben were caught stealing a liquor shop and during the investigation, it was discovered that both of them have committed a far more serious crime in the past, say a bank robbery. During the investigation, the cops interrogate both of them and present them with a proposition.
- Proposition 1: If you both don’t rat the other dude out then you will both get four years in jail.
- Proposition Two: If one of you rats the other one out then the person who confessed will get zero years while the other gets seven years.
- Proposition Trio: If both of you confess then you will both get two years each.
So, to put this is a pay off matrix:
Anything that is in Crimson is Ben’s and anything in BLUE is Rob’s.
So, now let’s analyze.
Obviously, Rob and Ben are hardened criminals and they won’t rat anyone out because there is “honor among thieves.” As romantic as that notion may sound, behavioral psychology and game theory tells us otherwise. Let’s look deep into it.
If they both confess, then the payoff matrix says that the outcome is (Four,Four). Meaning they both get four years each. However, that is a very unstable state because they both know that they have a better deal on the table. If they do rat the other person out, then they will have zero years to serve. Because of this, this case is a very unstable screenplay.
This is why, contrary to what pop culture tells us, in a situation like this, Nash Equilibrium happens when both of them rats the other one out. This is how Rob and Ben reach their optimal solution keeping the other’s strategy in mind.
But this brings us to a problem.
What if there is a script where the optimal solution for both the players lies in the screenplay which has bad implication towards the society? Think of this script where Rob and Ben are planning a bank heist. Let’s make a matrix of positive payoffs that they will get in this screenplay:
As you can see, in this hypothetical script, the best and most optimal strategy lies in both Rob and Ben stealing. While this might be good for both of them, it is not a good script for the society.
This is where the idea of “punishment” comes in.
What is Penalty?
The world is not necessarily a kind and fair place. Fellows are generally very corruptible and if not kept under check. In the real world, people will generally have a lot of opportunities to get corrupted without any consideration for the society in general. So the way we keep things like this in check is by implementing a penalty strategy.
So suppose in the example shown above we have a penalty strategy that goes like this:
“For every -0.Five of utility taken from the public a penalty factor of -7 will be given.”.
In other words, every act that is considered “bad” for the society will have their payoff deduced by seven and that will cost -0.Five in utilities for the society. Now, you may be thinking why will society do anything like that? There is a loss of utility for the society which can be money, time anything and on the other mitt, the people who are committing a crime are getting a terrible penalty as well.
But the truth of the matter is that we, as a society, have always integrated this in our daily life. What adding the penalty factor does is that it reduces the payoff from “bad” activities and switches the matrix like this:
See how the payoff from the “bad” activity for deduced by a factor of 7?
As you can see, by adding the penalty factor, the Nash Equilibrium switches from something that could have been bad for the society to something that is good for the society. So it switches from, Ben and Rob doing the bank heist to Ben and Rob doing the bank heist but also facing the consequences of a penalty.
So, going back to the question, what is the incentive for a society to go through the penalty? Why will they want to waste their utilities? The way that people have answered this question is by making penalty mandatory. In, other words, if someone is a society doesn’t go along with the penalty, then they themselves become criminals and are subject to penalty.
How does that apply in a civilized society? Think of a police force that is funded by tax taken from the people. In this case, we have a specialized force which will dole out the penalty and the way the society takes part in it is by paying their taxes which fund the force. If you do not pay the taxes, then you are subject to penalty as well.
Another interesting example of “punishing the non-punishable” is social ostracization. Think of a society where a person, says Max, has committed a crime. Instantly he becomes an outcast in the society. This is a script where everyone in that society is participating in the penalty. Now suppose, someone does mix with Max, that person also, by association, will become “bad” and he/she, in turn, will be ostracized by the society as well.
It wouldn’t be a spread to say that this very concept is the reason why we aren’t all dead right now.
The concept of Nash Equilibrium and Penalty has powerful implications in blockchain and keeping the miners fair. We will explore that in a bit. But before doing so, we must go through some more basic game theory models.
The Schelling (Focal) Point
The excellent economist Thomas Schelling conducted an experiment with a group of students asking them a ordinary question: “Tomorrow you have to meet a stranger in NYC. Where and when do you meet them?” He found out that the most common reaction was, “Noon at the Grand Central Terminus.” This happened because the Grand Central Terminus, for Fresh Yorkers is a natural focal point, the focal point is also known as a “Schelling point”.
So, to define a Schelling point: It is a solution that people will tend to use in the absence of communication because it feels special, relevant or natural to them.
Let’s demonstrate this concept with a game. Suppose there are two prisoners kept in two different rooms and they are given a random series of numbers. Then they are told to guess the number that they another prisoner will guess, without any communication inbetween the two. If they guess the wrong number, then they will be killed (just to up the ante).
The numbers that they are given are:
- 7816239, 676716313, one hundred million and 871823719.
- Which number do you think they will choose?
Why? Because it is different and special when compared with the rest of the numbers and that is why it is Schelling point. Across our history, human beings have unknowingly sub consciously converged in various places such as bars, churches, community centers, etc. because in a society those places are common Schelling points.
A very famous example of the Schelling point in activity is a game that we hope you have never played in your life called “The Chicken Game.” This is how it works, two people rail towards each other on a bike. If they collide head on, they die. However, the very first person who swerves away from the incoming rider is a “chicken”.
So, in this game, there are two scripts which can end in a crash:
Photo Courtesy: Mind Your Decisions blog
- Case 1: Both riders head towards one another.
- Case Two: One rider swerves left and the other swerves right.
Thomas Schelling gave the solution to this using the concept of focal points. He said, that the best solution to this game is to not look at the other rider in the eye (i.e. cut off communication with the other rider) but concentrate on one’s own instincts. Since, in the United States, people drive on the right side of the road, if we let our instincts take over, we will automatically steer the bike towards the right side, because that’s where our Schelling point lies.
Grim Trigger Equilibrium
In order to understand how a grim trigger equilibrium works we need to think of a script. Let’s imagine a social situation where monarchy still exists and it is believed that kings get to rule over others because of a divine right from the Gods. However, in a society like this, if the king is killed then automatically the law of divine right vanishes because it will be apparent to everyone that the king is not a divine being. What this will do is that it will open all the floodgates.
Now that it is apparent to everyone that the king is killable, it will embark an endless cycle of bloody revolutions where nothing can stop from all the subsequent future kings from getting murdered. The only way to stop this perverse cycle is by NOT killing the king in the very first place and to maintain the notion of “divine right”. This is called a Grim Trigger Equilibrium. Think of it as a state wherein if you deviate even a little bit you are going to cause an endless cycle of recursive penalty.
Now, if you see this matrix, there are two Nash Equilibria: (A, A) and (B, B), deviation from either of the state won’t benefit them. The idea of this game is how can you persuade people to go from (A, A) to (B, B)? If there are a puny group of people involved then that is relatively ordinary, you can simply coordinate via phone or emails. But, this switches when we are talking about a massive group of people.
The fundamental difference inbetween prisoner’s dilemma and coordination problem is that in prisoner’s dilemma, both the players had to choose (B, B) because that was the choice that had the most payoff even however (A, A) is a morally better solution. In Co-ordination problem, it is not about the morality or the payoff, it is the incentive for a person to go from one state to another. Why should a fat group of people switch the way they do things?
A coordination game fails when an only minority of the group switch their state, and the majority don’t, and inversely, it is a success when a majority of the group switches their state. Let’s see that with an example.
Suppose we want to switch the language to a symbol based language. Eg:
If only you speak using this language, it will be a failure because the majority won’t understand what you are talking about and you will be shunned from conversations aka the payoff for you is very low, and you have no incentive to switch.
However, if the majority of your society shifts to this language and use it exclusively, you will have to switch your language otherwise you will never be able to fit in. Now the incentive for you to join is high.
Why do you think nobody speaks in ye olde English anymore? If you talk like that in your society, you will be shunned, and everyone will think “thou art a knave sirrah!”
The concept of Bounded Rationality
Imagine this script, Sarah goes to the grocer’s shop every single day and buys an apple. She does this every single day as a ritual. However, every day she faces a situation. Every day, whenever she is in the shop, the shopkeeper leaves for five mins and there are no security cameras in place. She can lightly shoplift an apple and nobody will get to know about it. Yet she never does that.
What Sarah does here is called “Bounded Rationality”. Bounded rationality basically means that when given a choice, people will always go after a path that is elementary and something they are used to. This path may not be what is best suited for them and it may not give them the highest pay offs, yet they will always go after the simplest path. The reason why Sarah chose the virtuous path of following her elementary routine everyday instead of shoplifting and getting away with no repercussions is that the 2nd screenplay is a little more sophisticated than her ordinary everyday routine.
Now that we have gone through some game theory models, let’s see its implication in cryptocurrency and how it helps keep the system floating.
Blockchain and Cryptocurrency Game Theory
A block is a series of blocks which contains individual transactions in it. Each block also contains the hash of the previous block and this, in turn, links each subsequent block to the previous block making a chain. Hence the term, “blockchain.” This is a rough visual representation of a blockchain.
- Genesis block: The very first block of the blockchain is called a “genesis” block.
- Proof of work: The amount of computational work required to create the block.
- Parent block: The block that instantaneously precedes a block is the parent block of that block. So in the diagram above, Block fifty is the parent block of Block 51.
Every block in the blockchain has a scoring function.
- Score(genesis) = 0.
- Score(Block) = Score (parent block) + Proof of work
The current state of the chain is the block with the highest score.
In a system based on blockchain Bitcoin there are two players:
Users, in bitcoin, have only two functions available to them:
In order to do that they need two keys, the public, and the private key. What miners do is that they authenticate the transactions AND they do the process of mining. Mining is how fresh blocks are discovered and added to the blockchain.
Through a series of computations, miners find a block and add it to the blockchain.In Ethereum, adding the block gives the miner(s) a prize of five ether and In bitcoin, the mining prize is twenty five BTC (both as of writing). Miners have a lot of power in the blockchain system and if they do choose to cheat for their own individual build up, they can cause havoc in the system.
To mitigate that, the blockchain uses game theory mechanics to keep the system bulletproof. In order to understand how game theory keeps the miners fair, let’s take a look at another peer-to-peer system which has permitted its users to, time and again, get away with cheating.
Torrenting is one most popular peer to peer systems in the world. While using torrents, users have two roles: downloading and seeding. After downloading a file, they are supposed to share it the network via a method called seeding. However, they get no compensation for seeding the said file and hence more often than not they deny to do so. Most torrent users are “cheats” because they do not seed their files. They can get away with cheating because the system doesn’t have a “punishment model” the way blockchain does.
How can miners cheat? – Cryptocurrency Game Theory
- They can include an invalid transaction and give themselves extra coins.
- Add blocks randomly without worrying about Proof of work.
- Mine on top of invalid blocks to get more BTC.
- Mine on top of a sub-optimally scoring block.
Let’s take an example. Consider the block below:
The blocks in blue are the main chain. Now suppose there is a miner who, in blue block 51, spends twenty bitcoins to get five hundred litecoins (hypothetically). And now he wants to create a parallel chain with a fresh block fifty one (crimson), where in he never did this transaction. So, to simplify what he just did, let’s do a quick recap:
- In blue block fifty one spends twenty bitcoins to get five hundred litecoins.
- Creates a fresh chain (fork) from block fifty and in the alternate block 51, he doesn’t do the litecoin transaction.
- In the end, he comes out with his original twenty BTC and five hundred fresh litecoins.
What just happened here is called “double spending.” Obviously now miners can, theoretically, mine on top of the fresh crimson chain and keep dual spending and mining extra bitcoins. As you can imagine, this can ruin the bitcoin system.
So why don’t miners do that? Is it because they are all good and honorable people? You can’t make a system based on the morals of a person, morality is not quantifiable after all. This is where the true genius of blockchain comes in. The blockchain was designed in a way that it is a self-enforcing Nash Equilibrium. The reason why that happens is that mining has a recursive penalty system.
The Nash Equilibrium in mining and the penalty system.
- If a miner creates an invalid block then others won’t mine on top of it because of a rule that has been defined in blockchain mechanics. Any block that is mined on top of an invalid block becomes an invalid block. Using this rule, miners will simply disregard the invalid block and keep on mining on top of the main chain aka the blue chain in the diagram.
- This similar logic stands for sub-optimally scoring block. Look at the diagram again. No miner will want to mine on Crimson Block fifty two because the Blue Block fifty three will have a higher score than the crimson block.
Both of these screenplays get mitigated because miners., as a group will choose the most stable state aka the state with a Nash Equilibrium. Obviously, you can make all the miners mine on the crimson block and make it the fresh blockchain, however, the number of miners is so vast that an event like that simply cannot be coordinated (we will talk about this in a bit). As the co-ordination game states, if a majority of the people in the group are not switching their state, the minority will not have any incentive to stay in the fresh state. Eyeing this, why will a miner spend all their computation power and risk ostracization in a futile cause?
Why will users use the main chain instead of the other chain?
So, now that we have seen the reason WHY miners will choose the blue chain…What about the users? In the blockchain game, there are two players, miners, and users. Why will users choose the blue chain over the crimson chain? Once again, game theory mechanics come into play.
- The very first thing that you need to keep in mind is that cryptocurrency has value is because the people give it value. So, why will a normal user assign a value to coins coming out of the blue chain and not to the coins coming out of the crimson chain? The reason is ordinary. The main chain is a Schelling point from the users perspective. They give it value because the main chain seems natural and special to them.
- Bounded Rationality: Another reason why users will value the main chain more is that they are simply used to it. Like bounded rationality states, people will simply opt for the simplest solution every time. Moving through a newer chain needlessly complicates things.
What is the Proof Of Work Takeover Problem?
Before we embark explaining this, let’s bring back our old diagram again for reference:
Vitalik Buterin gave a good example of the Takeover problem and we are going to expand on it. Suppose, someone makes a hypothetical wise contract for an activity. The terms of the contract go like this:
- Any miner can join the activity by sending a very large deposit into the contract.
- The miners must send shares of the partially finished blocks that they have mined into the contract and the contract verifies it and also verifies that you are a miner and that you have sufficient hash power.
- Before 60% of the miners in the system join you can leave anytime you want.
- After 60% of the miners join, you will be trussed to the contract until the twenty blocks have been added to the hard fork chain aka the crimson chain.
Yes, it is indeed very diabolical and you can see the problem that this attack can have. Not only will the fresh chain grow fatter and longer, since 60% of the entire miners are strapped contractually to this fresh chain this will quickly make the original older chain aka the blue chain irrelevant. This will make dual spends all over the place and the value of the currency will fall quick.
Now, you might be asking why miners will join in a takeover?
Well, let’s see their incentive for joining:
- The possible prize at the end.
- No risk of joining on their part.
What is their incentive to go after through with the contract?
- The giant amount they have deposited in the beginning.
- Once again, the possibility of a fine prize.
Theoretically, a takeover like this can end any currency, but this is not that likely to happen because of…You guessed it…. game theory mechanics.
Grim Trigger argument to the rescue!
Think of our king argument when we very first talked about grim triggers. If a king is killed and usurped, what will stop the fresh king from getting killed and from this becoming an endless bloody cycle? To stop this from happening, the best course of act is to not kill the original king in the very first place.
Similarly, let’s use this logic for blockchains. If a blockchain is taken over and demolished and the miners are diverted into a fresh chain, what is stopping that fresh chain from being taken over by the majority anytime soon? To stop these endless hardforks (aka the crimson chains in the diagram) from happening, it is significant that we don’t do the takeover in the very first place.
However, there are certain places where the Grim Trigger argument does fail, and obviously, there are places where it works pretty spectacularly:
- The argument fails when the miners are not strapped to singular currency. If the miners are working on several currencies, then they can simply group to take over a low-value currency.
- The argument holds up if they are tied and loyal to a particular currency. After all, it is in their direct interest to uphold and maintain the value and legitimacy of the currency.
- If the currency requires specialized ASICs, then the grim trigger argument holds up. If a currency can only be mined by specialized software, then miners will make sure that nothing happens to that particular currency and that it doesn’t lose value. Specialized ASICs after all, can only work for a particular currency. Otherwise, it is futile. Plus, they are expensive.
- The argument doesn’t hold up if the currency can be mined using CPUs. CPUs are not expensive after all, and it can be used to mine other currencies.
- However, if the miners who own the CPUs have a stake in the currency, the argument holds up because they don’t want to lose the stake that they have invested in the currency. This is a sort of proof-of-stake.
As can be seen, game theory mechanics are what make blockchains so special. Nothing about the technology or mechanics is fresh, but it is the marriage of these two fascinating concepts that has made cryptocurrency secure from internal corruption. Even if bitcoin and Ethereum do fail for whatever reason, cryptocurrency will always live on because of this path violating a partnership.