duminică, 24 mai 2015

Explaining a Cornerstone of Game Theory: John Nash’s Equilibrium



John Forbes Nash Jr. was best known for advances in game theory, which is essentially the study of how to come up with a winning strategy in the game of life — especially when you do not know what your competitors are doing and the choices do not always look promising.


Dr. Nash did not invent game theory; the mathematician John von Neumann did the pioneering work to establish the field in the first half of the 20th century. But Dr. Nash extended the analysis beyond zero-sum, I-win-you-lose types of games to more complex situations in which all of the players could gain, or all could lose.


The central concept is the Nash equilibrium, roughly defined as a stable state in which no player can gain advantage through a unilateral change of strategy assuming the others do not change what they are doing.


The film “A Beautiful Mind,” based on Dr. Nash’s life, tries to explain game theory in a scene in which Russell Crowe, playing Dr. Nash, is at a bar with three friends, and they are all enraptured by a beautiful blond woman who walks in with four brunette friends.


While his friends banter about which of them would successfully woo the blonde, Dr. Nash concludes they should do the opposite: Ignore her. “If we all go for the blonde,” he says, “we block each other and not a single one of us is going to get her. So then we go for her friends, but they will all give us the cold shoulder because nobody likes to be second choice. But what if no one goes to the blonde? We don’t get in each other’s way and we don’t insult the other girls. That’s the only way we win.”


While this never-happened-in-real-life episode illustrates some of the machinations that game theorists consider, it is not an example of a Nash equilibrium.


A simpler example is what is known as the Prisoner’s Dilemma. Two conspirators in a crime are arrested and offered a deal: “If you confess and testify against your accomplice, we’ll let you off and throw the book at the other guy — 10 years in prison.”


If both stay quiet, the prosecutors cannot prove the more serious charges and both would spend just a year behind bars for lesser crimes. If both confess, the prosecutors would not need their testimony, and both would get eight-year prison sentences.


At first glance, keeping quiet might seem the best strategy. If both did so, both would get off fairly lightly.


But the calculation of the Nash equilibrium shows they should both confess.


This type of problem is called a noncooperative game, which means the two prisoners cannot convey intentions to each other. Without knowing what the other prisoner is doing, each is faced with this choice: If he confesses, he could end up with freedom or eight years in prison. If he stays quiet, he goes to prison for one year or 10 years.


In that light, confessing is the better option. And he knows that the other prisoner has the same incentive to confess, so it is less likely he would stay quiet.


Further, changing strategy to staying mum would be a bad move — longer prison term — unless the other prisoner somehow also decided to do that. Without any communication, that would be a highly risky guess, and thus, this strategy represents a Nash equilibrium.


The bar scene, however, does not. With four men chasing four brunettes, any of the men could be tempted to chase the blonde instead, a more desirable outcome if his friends did not also change strategy.




Source link








- http://bit.ly/1LAk56B

Niciun comentariu:

Trimiteți un comentariu

searchmap.eu