Nash Equilibrium

choi

Game theory | Prison breakthrough; The fifth of our series on seminal economic ideas looks at the Nash equilibrium. Economist, Aug 20, 2016.
http://www.economist.com/news/ec ... -equilibrium-prison

Note:
(a) "JOHN NASH arrived at Princeton University in 1948 to start his PhD with a one-sentence recommendation: 'He is a mathematical genius.' He did not disappoint. Aged 19 and with just one undergraduate economics course to his name, in his first 14 months as a graduate he produced the work that would end up, in 1994, winning him a Nobel prize in economics for his contribution to game theory.  On November 16th 1949, Nash sent a note barely longer than a page to the Proceedings of the National Academy of Sciences [based in Washington DC], in which he laid out the concept that has since become known as the 'Nash equilibrium.' This concept describes a stable outcome that results from people or institutions making rational choices based on what they think others will do. In a Nash equilibrium, no one is able to improve their own situation by changing strategy: each person is doing as well as they possibly can, even if that does not mean the optimal outcome for society. With a flourish of elegant mathematics, Nash showed that every 'game' with a finite number of players, each with a finite number of options to choose from, would have at least one such equilibrium.
(i)
(A) John Forbes Nash Jr
https://en.wikipedia.org/wiki/John_Forbes_Nash_Jr.
(1928-2005; born and raised in West Virginia; graduating in 1948 (at age 19) with both a BS and MS in mathematics from then Carnegie Institute of Technology [which merged in 1967 to form Carnegie Mellon University (at Pittsburgh)] and went on to Princeton; [from Princeton mathematics department, see next)] earned a PhD degree in 1950 with a 28-page dissertation on non-cooperative games; in 1995 was diagnosed with paranoid schizophrenia)
(B) John F Nash Jr - Biographical. Nobel Prize, 1994
www.nobelprize.org/nobel_prizes/ ... /1994/nash-bio.html
("But while I was still at Carnegie I took one elective course in 'International Economics' and as a result of that exposure to economic ideas and problems, arrived at the idea * * * which led to 'Non-Cooperative Games' ")

That is what the Economist means when saying "with just one undergraduate economics course to his name."  A "course" -- not an undergraduate degree (in economics).
(ii) The English surname Nash meant "someone who lived by an ash tree, a variant of [another English surname] Ash by misdivision of Middle English atten ash 'at the ash' * * * [the same misdivision brought about] the many places in England and Wales named Nash."
Dictionary of American Family Names, by Oxford University Press.
(iii) "He is a mathematical genius."

Recommendation Letter for John Nash Is the Best We've Ever Seen. AOL News, June 9, 2015
www.aol.com/article/2015/06/09/r ... ever-seen/21193564/
(Nash and "his wife died in a tragic car accident last month and as a tribute, Princeton University published the original recommendations written for Nash when he applied to the prestigious school. [The recommendation letter at issue] spans just three sentences long" written by Carnegie Institute of technology's Richard J Duffin)
(iv)
(A) JF Nash Jr, Equilibrium Points in N-Person Games. PNAS, 36: 48-49 (January 1950)
www.pnas.org/content/36/1/48.full
(Kakutani's theorem)
(B) Kakutani fixed-point theorem
https://en.wikipedia.org/wiki/Kakutani_fixed-point_theorem
(was developed by Shizuo KAKUTANI 角谷 静夫 [PhD in Math from Osaka University (1941); math professor in Yale after 1949] in 1941)

(b)
(i) non-cooperative game
https://en.wikipedia.org/wiki/Non-cooperative_game
(in toto: "In game theory, a non-cooperative game is one in which players make decisions independently. Thus, while players could cooperate, any cooperation must be self-enforcing. A game in which players can enforce contracts through third parties is a cooperative game")
(ii)
(A) Nash equilibrium. Investopedia, undated.
www.investopedia.com/terms/n/nash-equilibrium.asp
(B) Nash equilibrium
https://en.wikipedia.org/wiki/Nash_equilibrium
(section 1 Applications)

choi

(c)
(i) Avinash Dixit and Barry Nalebuff, Game Theory. In David R Henderson, The Concise Encyclopedia of Economics, 2nd ed (2008)
www.econlib.org/library/Enc/GameTheory.html
("The prisoners' dilemma. Two suspects are questioned separately, and each can confess or keep silent. If suspect A keeps silent, then suspect B can get a better deal by confessing. If A confesses, B had better confess to avoid especially harsh treatment. Confession is B’s dominant strategy. The same is true for A. Therefore, in equilibrium both confess. Both would fare better if they both stayed silent")
(A) "Like the general, a game player must recognize his interaction with other intelligent and purposive people."

purposive (adj): "having or tending to fulfill a conscious purpose or design : PURPOSEFUL"
www.merriam-webster.com/dictionary/purposive

Indeed the authors later use "purposeful," twice.
(B) "This logical circle is squared (the circular reasoning is brought to a conclusion)"

Maybe this is authors' way to mean "is brought to a conclusion." I can not find another example of this use of the phrase.

squaring the circle
https://en.wikipedia.org/wiki/Squaring_the_circle
(C) "Players may be spiteful or envious as well as charitable and empathetic. Recall George Bernard Shaw's amendment to the Golden Rule: 'Do not do unto others as you would have them do unto you. Their tastes may be different.' "

Golden Rule
https://en.wikipedia.org/wiki/Golden_Rule
(section 1 Etymology; search text with "Shaw," which appears twice)
(D) "When Kodak entered the instant photography market [in 1976], Polaroid put all its resources into the fight; fourteen years later, Polaroid won a nearly billion-dollar [$909.5 million, to be exact] lawsuit against Kodak and regained its monopoly market."

Polaroid Wins $909 Million From Kodak. Los Angeles Times, Oct 13, 1990.
articles.latimes.com/1990-10-13/business/fi-1997_1_instant-photography
(E) "Recall Winston Churchill's dictum of hiding the truth in a 'bodyguard of lies.' "

"In time of war, when truth is so precious, it must be attended by a bodyguard of lies."  Winston Churchill, The Second World War, Volume V: Closing the Ring. Houghton Mifflin, 1051.
http://www.notable-quotes.com/c/churchill_sir_winston.html
(ii) Avinash Dixit, Game Theory Explained. PBS, 2001 (the year according to author's CV).
www.pbs.org/wgbh/amex/nash/sfeature/sf_dixit.html
("If you are a player in such a game, when choosing your course of action or 'strategy' you must take into account the choices of others. But in thinking about their choices, you must recognize that they are thinking about yours, and in turn trying to take into account your thinking about their thinking, and so on")
(A) A Brilliant Madness is a PBS American Experience documentary aired on Apr 28, 2002 (and remains available on CDs).
(B) "In Joseph Heller's novel Catch-22, allied victory in World War II is a foregone conclusion, and [John] Yossarian does not want to be among the last ones to die.  His commanding officer points out, 'But suppose everyone on our side felt that way?' Yossarian replies, 'Then I'd certainly be a damned fool to feel any other way, wouldn't I?' "
* Catch-22
https://en.wikipedia.org/wiki/Catch-22
(published in 1961; [plotline: airmen's "repeated attempts to avoid combat missions that appear to lead to certain death;"  Many events in the book are repeatedly described from differing points of view, so the reader learns more about each event from each iteration; section 7        Historical context)
* Catch-22. by Wikiquote.
https://en.wikiquote.org/wiki/Catch-22
(" 'From now on I'm thinking only of me.'   Major Danby replied indulgently with a superior smile: 'But, Yossarian, suppose everyone felt that way.'   'Then,' said Yossarian, "I'd certainly be a damned fool to feel any other way, wouldn't I?'  p. 446")
(C) Police: "If the other does not fink, then you can cut a good deal for yourself by giving evidence against the other; if the other finks and you hold out, the court will treat you especially harshly. Thus no matter what the other does, it is better for you to fink than not to fink -- finking is your uniformly best or 'dominant' strategy." This is the case whether the two are actually guilty, as in some episodes of NYPD Blue, or innocent, as in the film LA Confidential."
* fink (n): "INFORMER"
(vi): "to turn informer : SQUEAL"
www.merriam-webster.com/dictionary/fink
* LA Confidential (1990) was neo-noir novel by James Ellroy, from which a film of the same name was made in 1997.  The suspects might hae committed other crimes, but they did not a mass murder at the Nite Owl coffee shop (and yet they confessed).
* LA Confidential Interrogation Scene. YouTube.com, uploaded by NecroPhoenix on Mar 26, 2010
https://www.youtube.com/watch?v=ArrhM8UbTww
("Ed Exley interrogate a suspesct [sic] when Bud White comes to give a help. One of the BEST scenes of this wonderful movie of 1997")
* Here is the script of LA Confidential the film:
The Internet Movie Script Database (IMSDb)
http://www.imsdb.com/scripts/L.A.-Confidential.html

Read from "INT. OBSERVATION ROOM - DAY[;] Dudley watches intently as Ed Exley skims a report" until "You got a big guilty sign around your neck."
* LA Confidential (the book, by James Ellroy), page number erased
https://books.google.com/books?i ... confess&f=false
("Otis John Shortell, in prison on an accumulation of grand-theft auto convictions and frankly desiring a sentence reduction as a reward for his cooperation, confessed that he was one of the men Coates, Fontaine and Jones “sold” Inez Soto to. He was with Miss Soto and the three youths between the hours of 2:30 and 5:00 on the morning of the Nite Owl killings, during the entire murder time frame. He told the warden that he never came forward to exonerate the three for fear of rape charges being filed against him. He further stated that Coates had a large quantity of narcotics in his car and that that was the reason he never relinquished its location to the police. Shortell cited a recent conversion to Pentecostal Christianity as his reason for finally making his confession, but prison authorities were dubious. Shortell petitioned for an in-cell lie detector test to prove his veracity and was given a total of four polygraph examinations. He passed all four tests conclusively. Shortell's attorney, Morris Waxman, has sent notarized copies of the polygraph examiner’s reports to the Daily News and the LAPD. We have advanced this article. What will the LAPD do?
We decry the injustice of shotgun justice. We decry the motives of triggerman Ed Exley. We openly challenge the Los Angeles Police Department to reopen the Nite Owl Murder Case")

choi

Back to the Economist text.
(d) In "most markets * * *  the decisions of rivals and customers matter. From auctions to labour markets, the Nash equilibrium gave the dismal science a way to make real-world predictions based on information about each person’s incentives.  One example in particular has come to symbolise the [Nash] equilibrium: the prisoner's dilemma. * * * [(] Nash's thesis adviser, Albert Tucker, came up with it for a talk he gave to a group of psychologists.)  It involves two mobsters sweating in separate prison cells, each contemplating the same deal offered by the district attorney. * * * There is only one Nash-equilibrium solution to the prisoner's dilemma: both confess. Each is a best response to the other's strategy; since the other might have spilled the beans, snitching avoids a lifetime in jail. The tragedy is that if only they could work out some way of co-ordinating, they could both make themselves better off.  The example illustrates that crowds can be foolish as well as wise; what is best for the individual can be disastrous for the group. This tragic outcome is all too common in the real world. Left freely to plunder the sea, individuals will fish more than is best for the group, depleting fish stocks [this is, in economics, called 'tragedy of the commons'
https://en.wikipedia.org/wiki/Tragedy_of_the_commons
]. Employees competing to impress their boss by staying longest in the office will encourage workforce exhaustion. Banks have an incentive to lend more rather than sit things out when house prices shoot up.  The Nash equilibrium helped economists to understand how self-improving individuals could lead to self-harming crowds. Better still, it helped them to tackle the problem: they just had to make sure that every individual faced the best incentives possible. If things still went wrong—parents failing to vaccinate their children against measles, say—then it must be because people were not acting in their own self-interest. In such cases, the public-policy challenge would be one of information."

Albert W Tucker
https://en.wikipedia.org/wiki/Albert_W._Tucker
(1905 – 1995)

(e) "the concept [Nash equilibrium] has been used to solve a host of real-world policy problems.  One famous example was the American hospital system, which in the 1940s was in a bad Nash equilibrium. Each individual hospital wanted to snag the brightest medical students. With such students particularly scarce because of the war, hospitals were forced into a race whereby they sent out offers to promising candidates earlier and earlier. What was best for the individual hospital was terrible for the collective: hospitals had to hire before students had passed all of their exams. Students hated it, too, as they had no chance to consider competing offers.  Despite letters and resolutions from all manner of medical associations, as well as the students themselves, the problem was only properly solved after decades of tweaks, and ultimately a 1990s design by Elliott Peranson and Alvin Roth (who later won a Nobel economics prize of his own). Today, students submit their preferences and are assigned to hospitals based on an algorithm that ensures no student can change their stated preferences and be sent to a more desirable hospital that would also be happy to take them, and no hospital can go outside the system and nab a better employee. The system harnesses the Nash equilibrium to be self-reinforcing: everyone is doing the best they can based on what everyone else is doing."
(i) National Resident Matching Program
https://en.wikipedia.org/wiki/National_Resident_Matching_Program
(created in 1952 to help match medical school students with residency programs; The problem of matching hospitals to residents is a generalization of the stable marriage problem)

There is no need to read the rest of this particular Wiki page, but do read the Wiki page for "stable marriage problem."
(ii) Instantly I can discern unrealistic aspects of the stable marriage problem.
(A) "The traditional form of this problem is a bit unrealistic in practice, since it assumes that every boy ranks every girl and vice versa. In practice many people find certain others totally unacceptable, and prefer to be single than to marry them."
Matching Problem. Department of Mathematics, MIT (author and year of writing unknown)
(B) David Austin, The Stable Marriage Problem and School Choice. American Mathematical Society, March 2015 ("Featured Column").
www.ams.org/samplings/feature-column/fc-2015-03

Quote:

"Before we go any further, let's acknowledge that our aim here is to model a mathematical problem. We will not, for instance, consider the realities of same-sex marriage, that individuals don't necessarily identify as either strictly male or female, and that women often propose to men. These issues all lead to mathematical situations that differ significantly from this one, which we hope to apply, more realistically, to the problem of matching students with schools.

"We will show that revealing one's true preferences is, in the language of game theory, a dominant strategy for men. This means that, assuming all other men and women keep the same preferences, a man cannot obtain a more desirable match by misrepresenting his preferences.

choi

(f) "Nash's insights also help to explain why adding a road to a transport network can make journey times longer on average. Self-interested drivers opting for the quickest route do not take into account their effect of lengthening others’ journey times, and so can gum up a new shortcut. A study published in 2008 found seven road links in London and 12 in New York where closure could boost traffic flows."

Braess' paradox
https://en.wikipedia.org/wiki/Braess%27_paradox

, which cites

Youn H, Gastner M and Jeong H, Price of Anarchy in Transportation Networks; Efficiency and optimality control. Physical Review Letters, 101: 128701 (2008).
http://journals.aps.org/prl/abst ... sRevLett.101.128701

Click a tab on the top horizontal bar to read the full article, which is hard to read for laypersons like me. But you should read the abstract:

"Uncoordinated individuals in human society pursuing their personally optimal strategies do not always achieve the social optimum, the most beneficial state to the society as a whole. Instead, strategies form Nash equilibria which are often socially suboptimal. Society, therefore, has to pay a price of anarchy for the lack of coordination among its members.

(g) "The Nash equilibrium would not have attained its current status without some refinements on the original idea. First, in plenty of situations, there is more than one possible Nash equilibrium. * * * A second refinement involved accounting properly for non-credible threats. * * * Reinhard Selten, a German economist who shared the 1994 Nobel prize with Nash and John Harsanyi * * * Mr Selten's work let economists whittle down the number of possible Nash equilibria. Harsanyi addressed the fact that in many real-life games, people are unsure of what their opponent wants.* * * A different problem continued to lurk. The predictive power of the Nash equilibrium relies on rational behaviour. Yet humans often fall short of this ideal. In experiments replicating the set-up of the prisoner's dilemma, only around half of people chose to confess. * * * All was not lost. The experiments also showed that experience made players wiser; by the tenth round only around 10% of players were refusing to confess. That taught economists to be more cautious about applying Nash’s equilibrium. With complicated games, or ones where they do not have a chance to learn from mistakes, his insights may not work as well. * * * he [Nash] had received that joint Nobel—in recognition that the interactions of the group contributed more than any individual."