Sunday, 24 May 2015

In memoriam: John Nash

It is with great sorrow to report the news that one of the greatest minds in human history died yesterday in a car crash with his wife while they were returning home from an airport. John Forbes Nash Jr., to most widely known as one of the founders of cooperative game theory whose life story was captured by the 2001 film "A Beautiful Mind", is truly one of the greatest mathematicians of all time. His contributions in the field of game theory revolutionized the way we think about economics today, in addition to a whole number of fields - from evolutionary biology to mathematics, from computer science to political science. 


John Nash was born in 1928 in Bluefield, West Virgina. Even as a child he showed great potential and was taking advanced math courses in a local community college on his final year of high school. In 1945 he enrolled an undergraduate mathematics major at the Carnegie Institute of Technology (today Carnegie Mellon). He graduated in 1948 obtaining both a B.S. and an M.S. in mathematics and continued onto a PhD at the Department of Mathematics at Princeton University. There's a famous anecdote from that time where his CIT professor Richard Duffin wrote him a letter of recommendation containing a single sentence: "This man is a genius". Even though he got accepted into Harvard as well, he got a full scholarship from Princeton which convinced him that Princeton valued him more. 

While at Princeton, already on his first year (in 1949) he finished a paper called "Equilibrium Points in n-Person Games" (it's a single-page paper!) that got published in the Proceedings of the National Academy of Sciences (in January 1950). The next year he completed his PhD thesis entitled "Non-Cooperative Games", 28 pages in length, where he introduced the equilibrium notion that we now know as the Nash equilibrium, and for which he will be awarded the Nobel prize 34 years later. It took him only 18 months to get a PhD! He was 22 at the time. 

While at Princeton he finished another seminal paper "The Bargaining Problem" (published in Econometrica in April 1950), the idea for which he got from an undergraduate elective course he took back at CIT. It was Oskar Morgenstern (the co-founder of game theory and the co-author of the von Neumann & Morgenstern (1944) Theory of Games and Economic Behavior) who convinced him to publish that bargaining paper. The finding from this paper will later be known as the Nash bargaining solution. Princeton was full of top academics at the time and Nash took full advantage of that, even though he didn't learn maths by attending classes, he did it by trying out his own ideas. As he came to Princeton he sought out Albert Einstein to discuss physics with him (as physics was also one of his interests). Einstein reportedly told him that he should study physics after Nash presented his ideas on gravity, friction and radiation. 

Illness and impact

After graduating he took an academic position at MIT, also in the Department of Mathematics, while simultaneously taking a consultant position at a cold war think tank, the RAND Corporation. He continued to publish remarkable papers (his PhD thesis in The Annals of Mathematics in 1951, another paper called "Two-Person Cooperative Games" in Econometrica in 1953, along with a few math papers). He was given a tenure position at MIT in 1958 (at the age of 30), while he married his wife Alicia the year before. However, things started to go wrong from that point on in his personal life and career. In 1959 he was diagnosed with paranoid schizophrenia, forcing him to resign from MIT. He spent the next decade in and out of mental hospitals. Even though he and his wife divorced in 1963, she took him in to live with her after his final hospital discharge in 1970. 

Nash spent the next two decades in relative obscurity, but his work was becoming more and more prominent. Textbooks and journal articles using and applying the Nash equilibrium concept were flying out during that period, while most scholars that built upon his work thought he was dead. It was not only the filed of economics - where the concepts of game theory were crucial in developing the theory of industrial organizations, the public choice school and the field of experimental economics (among many other applications) - it was a whole range of fields; biology, mathematics, political science, international relations, philosophy, sociology, computer science, etc. The applications went far beyond the academia; governments started auctioning public goods at the advice of game theorists, business schools used it to teach management strategies. 

Arguably the most famous applications were to the cold war games of deterrence that explain to us why the US and Russia kept on building more and more weapons. The Nash equilibrium concept explains it very simply - it all comes down to a credible threat. If Russia attacks the US it must know that the US will retaliate. And if it does, it will most likely retaliate with the same fire-power Russia has. Which will lead to mutual destruction of both countries. In order to prevent a full-scale nuclear war (i.e. in order to prevent the other country from attacking), the optimal strategy for both countries is to build up as much nuclear weapons as they can to signal to the other player what they're capable of. This will prevent the other player from attacking. If they are both rational (i.e. if they want to avoid a nuclear war and total destruction) they will both play the same strategy and no one will attack. Paradoxically, peace was actually a Nash equilibrium of the arms race!

Long-overdue recognition 

Little did Nash have from all this. He had no income, no University affiliation and hardly any recognition for his work (not counting the citations). But this all changed in the 1990s when he was finally awarded an overdue Nobel Prize in Economics in 1994, with fellow game theorists John Harsanyi and Reinhard Selten "for their pioneering analysis of equilibria in the theory of non-cooperative games". Here is the Nobel Prize lecture and here is an interview with him conducted 10 years after winning the prize. 

His remarkable and actually very painful life story was perfectly depicted by his autobiographer and journalist Sylvia Nasar in her two books; "A Beautiful Mind", based on which the movie was made, and an even better one "The Essential John Nash", which she co-edited with Nash's friend from college Harold Kuhn (also a renowned mathematician). As Chris Giles from the FT said in his praise of the book: "If you want to see a sugary Hollywood depiction of John Nash's life, go to the cinema. Afterwards, if you are curious about his insights, pick up a new book that explains his work and reprints his most famous papers. It is just as amazing as his personal story." The book contains a facsimile of his original PhD thesis, along with eight of his most important papers (from game theory and mathematics) reprinted. 

After the Nobel Prize success things got better for Nash. By 1995 he recovered completely from his "dream-like delusional hypotheses", stating that he was "thinking rationally again in the style that is characteristic of scientists." Refusing medical treatment since his last hospital intake, he claimed to have beaten his delusions by gradually, intellectually rejecting their influence over him. He rejected the politically-oriented thinking as "a hopeless waste of intellectual effort". He remarried his wife Alicia in 2001, and started teaching again at Princeton. He continued his work in advanced game theory and has moved to the fields of cosmology and gravitation

The Phantom of Fine Hall, as they used to call him in Princeton due to his mystique and the fact that he used to leave obscure math equations on blackboards in the middle of the night, will never cease to raise interest, praise and awe. Nash was another perfect example of a thin line between a genius and a madman. Luckily in the end the genius side prevailed.  

So what is the Nash equilibrium? 

The reason why this concept was so revolutionary was because it significantly widened the scope of game theory at the time. In the beginning, following the von Neuman and Morgenstern setting, game theory was focused mostly on competitive games (when the players' interests are strictly opposed one to another). These types of games were known as zero-sum games, limiting to a significant extent the power of game theory. Nash changed that by introducing his solution concept so that basically any strategic interaction between two or more individuals can be modeled using game theory, where the most unique solution concept is the Nash equilibrium. Games are not zero-sum, they aren't pure cooperation nor pure competition. They are a mixture of both. 

The idea of the Nash equilibrium resonates from the simple assumption of rationality in economics. The term rationality in economics is not the same as common sense rationality we all think about upon hearing this term. It refers to the idea that each individual will act to achieve his or her own objective (maximize their utility), with respect to the information the person has at his/her disposal. The concept of rationality in economics is therefore idiosyncratic - it depends on whatever a particular individual deems rational for themselves at a given point of time. It rests upon the idea that a person will never apply an action that hurts him/her in any way (lowers his/her utility). 

The Nash equilibrium is the most general application of this idea. A non-cooperative game, according to Nash, is "a configuration of strategies, such that no player acting on his own can change his strategy to achieve a better outcome for himself". In other words if there exists another strategy that can make an at least one individual better off, then the outcome does not satisfy the condition for a Nash equilibrium. 

Let's look at an example. The most simplified example of how a Nash equilibrium solution concept works is the Prisoner's Dilemma game. Consider two robbers arrested for a crime. They are both being interrogated by the police in separate rooms. They are presented with two options (strategies): keep quiet (silent) or betray the other guy (betray). If they both remain silent, they both only get a light sentence of a year in prison for obstructing justice. If one betrays the other, and the other guy keeps silent, then the betrayer is released with zero imprisonment, and the other guy gets pinned for the whole crime and gets nine years in prison. If they both betray each other, they both get six years in prison. What's the optimal thing to do?

Applying the Nash equilibrium concept we need to find a strategy that is the best response of one player to whatever the other player may decide. When no players have any incentive to deviate from a set of strategies (strategies are always a pair in two-person games) we can say that this set of strategies is a Nash equilibrium. 

Consider the game depicted in the table below:

Prisoner 2
Silent (cooperate)
Betray (defect)
Prisoner 1
Silent (cooperate)
-1,-1
-9,0
Betray (defect)
0,-9
-6,-6 *

It would seem that the best strategy they can apply is for both to keep silent. If they do, they both get only a light sentence. However this strategy set (-1,-1) is not a Nash equilibrium since at least one person has an incentive to deviate. In fact, they both do. If Prisoner 1 decides to defect and betray Prisoner 2, he gets 0 years in prison, while Prisoner 2 gets 9 years (third cell, with payoffs 0,-9). Prisoner 2 applies the exact same reasoning (second cell with payoffs -9,0). In the end since the better strategy is always to betray, they both play the same strategy (betray, betray) and end up with payoffs (-6,-6) which is the Nash equilibrium of this game. From this point no player can deviate and make himself better off. If Prisoner 1 decides to go for silent he risks getting 9 years in prison instead of 6. There is no way for them to reach a cooperative equilibrium in this simplified scenario.

Naturally, cooperative games do exist (as I've discussed earlier on this blog) and they help us understand how game theory solves for example the free rider and the collective action problem. It was Elinor Ostrom (1990) who applied these concepts to reach her optimal solutions in solving the common pool resource problem in small groups with persistent interactions. Robert Axelrod (1984) is another, finding that even though the defection strategy is more rational, sometimes various other factors will result in a cooperative outcome between the players. The Nash equilibrium helped initiate a huge amount of research on these and many other problems within and outside the academia. The reason game theory is usually considered as the most applicable economic theory - in that it can be used to solve real-life problems - is purely thanks to John Nash. 

Rest in peace. 

Most notable papers: 

1 comment:

  1. great man, truly was a beautiful mind

    ReplyDelete