We lost a genius with Nash, but not his equilibrium

John Forbes Nash
Photo: Peter Badge (Wikipedia), CC BY-SA 3.0, (Crop Image)

One of the fathers of game theory, died together with his wife in a car accident last weekend. John Forbes Nash, aged 86, had just came back from Oslo where he collected the prestigious Abel Prize from the Norwegian Academy of Science and Letters for his mathematical work. Interestingly, 21 years ago now he also came back from Scandinavia with another prize. On that occasion he was awarded the Nobel Prize in Economics for his pioneering mathematical work in the 1950s. The prize recognized his work on the concepts of equilibrium in game theory.

His analyses in cooperative and non-cooperative games, known as the Nash Equilibrium, provide solutions to situations in which two or more parties interact to make decisions. His work have played since an essential role in the development of many branches of science, such as politics, biology, philosophy, computer science and of course economics.

“A set of strategies, in which no player acting alone can change your strategy to achieve a better outcome for himself,” is the definition devised by Nash equilibrium and has great importance in a situation where it does not exist trust between the parties, whatever its nature.

Coinffeine’s protocol allows decentralized exchange of bitcoins and has been developed based on Nash’ work and game theory as there is no trust between the parties and there is not a trusted third party. To exchange bitcoins and fiat money in Coinffeine both counterparties are matched automatically, without knowing who your counterparty is. This could have big risks if not for beautiful minds like Nash who have made this possible.

With the death of Nash, the world lost a genius. But fortunately his legacy will remain and the applications it may have, will be immortal.

R.I.P John Forbes Nash

We lost a genius with Nash, but not his equilibrium

Understanding Coinffeine’s protocol (II)

Chicken
Photo: W_Minshull , CC BY 2.0 (Not changes made)

In our first post we saw how useful game theory is for analyzing strategic situations, and in this second post of our series Understanding Coinffeine’s protocol we will return to game theory.

Mutual assured destruction

The next concept that interests us is mutual assured destruction, a concept closely related to the years of the Cold War. To get some atmosphere going, we can think of the cult film classic: Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb where Peter Sellers plays a scientist who is actually a parody of our friend Von Neumann (or if you prefer film in color, watch WarGames).

Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb

In this game, which is the Cold War, we have two rational players, USA and the USSR, both with a high regard for their own survival. At that time nuclear power was already developed, and had sadly been used as a closing ceremony of the Second World War. Both powers had entered into an arms race which, if continued, could have ended with humanity on several occasions.

For years it seemed that nuclear war was about to happen anytime, but it never did. The answer to this is the fact that both players had the ability to respond to a nuclear attack, even if it was a last resort and losses would be dramatic on both sides. The advantage of being the first to attack was insignificant compared to the losses it would cause. And it justified the cost of always having intercontinental missiles ready, and nuclear submarines or planes circling the Arctic to be able to respond to an attack.

Table mutually assured destruction

Nash Equilibrium

If we take stock of the possible outcomes in a table, we can see that the best answer to not attack is not attack, and in the event that the other player attacks it is indifferent what we do. Unlike the prisoner’s dilemma it is not enough to find the dominant solutions. In this case, we need the next best thing, a Nash equilibrium (and yes, there is a film about it).

These equilibrium situations occur when each player can not improve his situation by changing his strategy if the other player persists. In the game we have presented as an example, we find two equilibriums: (Not attack, Not attack) and (Attack, Attack).

A Nash equilibrium is a stable situation by definition and, therefore, in real life are often end up giving or aspire to these kind of results. However, not all equilibriums does necessarily happen. Given the consequences in this game, we get a happy ending (Not attack, Not attack), as happened for example during the Cuban Missile Crisis.

The only winning move is not to play

The lesson we can draw from this game is that you do not need a trusted third party if we have a mechanism that makes you lose more than you could win when the path of collaboration is left behind. This principle is very important to design a decentralized exchange protocol as Coinffeine, and to avoid aberrations such as “preventive wars”.

The game of “chicken”

The next ingredient we need to get familiar with is the concept of strategic moves. We will illustrate it with the game of “chicken” (Yes, you are right! Rebel Without a Cause is a representation of this game).

Rebel Without a Cause

The term “chicken” is a metaphor in which two sides are locked in an escalating situation, where none have nothing to gain and where only pride prevents them from pulling out. It is represented as a race in which two vehicles deliberately are driving on a collision course. The first to swerve is a coward ( or a “chicken”) he loses pride and the other wins. If both swerve no one loses anything, whereas if both continue they will crash and die.

Table game of the chicken

A quick glance at the table makes us realize that it does not exist a dominant strategy. If one of the drivers swerves, the best strategy for the other driver is to continue. However, if one of the drivers does not swerve, the best strategy for the other driver would be to swerve. As in the prisoner’s dilemma, this type of situations are common in the real world.

A strategic move is to modify the game to change the outcome and to change the balance. This would happen if driver 1 rips off the steering wheel, and throws it out of the window so the other driver realizes that his choices have been reduced dramatically.

Table strategic move - game of the chicken

As a result we have a new game where there is a dominant strategy for driver 2: Swerve is the only option, as death (-∞) awaits him if he continues.

We can say that by restricting the options, “rip off the steering wheel”, we make the threat of staying on the collision course even more credible, and it changes the rules of the game. The strategic moves are terribly useful, because we can use it to design games where collaboration is the dominant path. However, I do not recommend you to do this at home… you could see the steering wheel of the other driver go out of the window as well…

In the next post we will present the Coinffeine protocol as a game, applying all these concepts.

 

Links:

 

Understanding Coinffeine’s protocol (II)

Understanding Coinffeine’s protocol (I)

Deal
Photo: Brian Alano CC BY 2.0, (Not changes made)

Coinffeine is a company, a desktop application and, most importantly, a protocol that allows decentralized exchange of bitcoins. This is the first of a series of posts in which we will explain the basics of Coinffeine’s protocol.

Let’s start with the following scenario, by the way very cinematic, in which two people who do not trust each other want to trade. This scenario implies a risk, because if the first person surrenders his briefcase before the other person gives him the goods, he runs the risk of being left with nothing and vice versa.

Trust without a third party

This situation is analogous to what we have in an exchange of bitcoins in Coinffeine: briefcase → FIAT goods → bitcoin. It does not exist trust between the parties, because there is not a third party that both trust. The parties have been matched without knowing who is their counterpart.

This situation seems unresolvable in principle, except for the fact that we can rely on two powerful tools: The first is that we are talking about rational agents, that is, looking for their own benefit, and the second is that we assume the presence of bitcoin. To solve the first we can use game theory to analyse the problem, and thanks to the second we have mechanisms such as multisig, allowing us to use the funds in new and creative ways.

Game theory

In this post we will focus on the first tool – game theory – which is a discipline midway between mathematics and economics, and applicable to situations in which rational agents make decisions in a well-defined scenario.

Although there are reminiscences of the kind of reasoning that is done in game theory in many ancient texts such as The Art of War by Sun Tzu or in the work of Charles Darwin, one can say that this concept appears in 1944 with John von Neumann and Oskar Morgenstern’s book entitled Theory of Games and Economic Behavior. Von Neumann is an old acquaintance of computer engineers because he is, along with the great Alan Turing, one of the fathers of computing.

Game theory fits well with the era in which it was formalized, and during the Cold War it seems like military terminology leaked and was adopted as the jargon of this field. The “games” can be seen as war scenarios, and the term “strategies” is frequent… The Cold War was actually brought to an end through mutual assured destruction. This is another game theory concept, which we will discuss in greater detail in the next post.

The Prisoner’s Dilemma

A good starting point to get into game theory is the prisoner’s dilemma. It is probably the best known game, and it will serve to identify the elements in the games before we can analyse them and draw conclusions. The game is set in a police station, where we have two members of a criminal gang arrested and imprisoned. Each prisoner is in solitary confinement with no means of speaking to or exchanging messages with the other. The rational actors will be, in this case, the two prisoners.

The next thing to consider in any game is the available actions of each actor. In this case, both prisoners face a difficult decision: the police are pushing them to collaborate with justice and testify (or defect, D), but they can as well keep strong and silent (and collaborate, C, with the other prisoner). The police admit they don’t have enough evidence to convict any of the prisoners on the principal charge, and plan to sentence both to a year in prison on a lesser charge. Each prisoner is given an opportunity to freedom: testifying that the other committed the crime for which he will be sentenced ten years in prison. However both prisoners have a problem. If both of them decide to collaborate with justice they will both go to jail, but only for five years each. These sentences are possible incentives or costs of this game, and is the third element to look for when characterizing a game.

We can set all the options on a table. The rows represent the possible actions of one player and the columns of the possible actions of the other player. In the cells we place the appropriate incentives to each of the scenarios. The result is known as a normal-form game, and in the specific case of the prisoner’s dilemma it looks like this:

The players actions and incentives in the prisoner’s dilemma

Prisoners Dilemma

Dominant strategy

Now we have enough elements to analyse this game. For our example, we can apply a simple concept called dominant strategy. In other cases you have to use other solution concepts that are more complicated. Strategic dominance are those moves that are the best answer to anything the other player does, and by definition, will be the preferred strategy by the player.

To analyse the dominant strategies of the blue prisoner, we have to look at the most convenient depending on the actions of the orange prisoner:
– If the orange prisoner decides to cooperate (C), and the blue prisoner does so as well (C) both will get only one year in prison. But if the orange defects (D) he will be set free, so in this case the blue prisoner should choose D.

– If the orange prisoner decides to defect (D), the blue prisoner will prefer to do the same and spend five years in jail rather than the 10 years he would get to cooperate (C) and be betrayed.

Regardless of what the other player does, the best response for both players is to defect. This is because the game and table are symmetrical and it is said that there is an equilibrium in (D, D). This game and its solution are very interesting because it helps us to understand why it may be wise to be rational and not cooperate in certain situations, although you could gain from it.

Games in everyday situations

There are many situations around us that can be expressed through games with incentives that have different values, but with the same relationships among them and with the same practical result. This helps us understand why it is rational not get informed before voting (rational ignorance), or why it is so hard to take care of the environment (tragedy of the commons), among other situations.

Let us go back to our cinematic scenario and the exchange of bitcoins in Coinffeine. It is clear that there are rational players, who can take a number of actions and that we can conceive this situation as a game. However, we still do not have all the pieces. We have to design the possible actions so that instead of no collaboration, as in the prisoner’s dilemma, both players choose to collaborate as the only option. In order to achieve this we need to understand the concepts of mutually assured destruction and throwing away the steering wheel. But, that is the topic for the next post.

If you want to go deeper into game theory:

– Game Theory: http://en.wikipedia.org/wiki/Game_theory

– Good introductory book: http://artofstrategy.net/

– Introductory course in Coursera: http://online.stanford.edu/gametheory-wi13

Understanding Coinffeine’s protocol (I)