RSS feeds in the directory: 374
Added today: 0
Added yesterday: 0
The prisoner's Dilemma and game theory
Two crooked financier, al and Bernie was arrested for fraud. While they are awaiting trial, the police keep them in separate cells. Meanwhile, the Prosecutor is considering a small problem. At the moment the evidence is sufficient only to condemn them for relatively minor tax offence. For charges of fraud, he only needs one of them testified against the other.
after considering this situation, the Prosecutor comes into the camera to al and offers him the following deal:
1. If you testify against your accomplice, and he is against you, then using your statement, we can condemn him for fraud. Give him 10 years in prison, and you will be released;
2. If you refuse to cooperate, and your accomplice will testify against you, everything will be exactly the opposite. You will be given 10 years in prison, and he will be released;
3. If neither of you turns on the other, then to us remains nothing how to bring less serious charges of tax evasion. Each of you will receive 2 years in prison;
4. If you both testify of each other, you will each get 8 years in prison;
When al went to ponder over it, the Prosecutor went over to Bernie and gave him the exact same offer. Let's say that neither al nor Bernie do not feel remorse about their crimes, and they don't care about things like fairness and justice. They also do not have the slightest interest in the fate of his accomplice. The only thing they care about is how to minimize the impending deadline. Hence the question: what these crooks to choose the tactics?
Left alone in his cell, al ponders the possible: "For both of us, the best option is the third. There is the smallest period among all proposed. So maybe it is better to sit down and shut up and hope that Bernie will behave the same. Although, wait a minute... if he talks, I'm facing 10 years. If you think well, what would choose Bernie, what is most advantageous to take it". With, al decided to cooperate with the police. Bernie is in his cell and talks in exactly the same way and comes to the same conclusion. They pass each other, and thus, there is a situation number 4.
This task is known as a prisoner's dilemma. The reason why it is of interest to mathematicians in its paradoxical connotation. Looking from a distance at all the options, described above, and treating the inmates as a couple, we see that the third option is really the best. However, the optimal tactics for each of them separately would take another, which leads us to the fourth option, which for both of them the worst.
More than just a game
the prisoner's Dilemma described above is the starting point in such a thing as game theory. We have a long history in the sense that people have long used mathematical reasoning to explore traditional Board games such as chess and go. However, only recently in the work of John von Neumann, Theory of games and economic behavior, written with Oscar Morgenstern in 1944, it declared itself as an independent discipline.
However, as shown by this example, game theory can have many applications other than games. Modern game theory is a strategy as a science in all its forms. Today it is used in various fields ranging from the economy to evolutionary biology, and applies to many social Sciences and even to international relations.
the mind Games and equilibrium
One of the most prominent figures in game theory — John Nash. His doctoral thesis at Princeton in 1950 was a key work in this science.
the prisoner's Dilemma
In 1994, Nash was awarded the Nobel prize in Economics. The scientist later developed schizophrenia. That's about it took Hollywood biographical film a beautiful mind. The situation when neither side has an incentive to change tactics, even if aware of the intentions of other participants, is equilibrium. In the prisoner's dilemma the fourth option is the balance. This is the second version — no. If al decides not to cooperate with the police, but then he reported that Bernie plans to take it, it will have an incentive to change their plans.
other applications may be more than one equilibrium, but one of the outstanding achievements of John Nash was that he showed every game has at least one equilibrium. It concerns not only games for two players, but three, four or any other number of players. Moreover, he proved it for the so-called games with mixed strategies, in which the same player in the same situation can make different moves, because it does not adhere to strict policies and makes decisions to some extent by chance.
As the prisoner's dilemma, the equilibrium state is not obliged to submit the best score. It just means that no player can improve his own result unilaterally. In this sense, the equilibrium state becomes a trap into which all players can get together. And the only way for them to get out will be a multi-pronged strategy that entails the emergence of a new component — the hard contracts.
How to keep a promise?
Let us return to the prisoner's dilemma, but with one small change. This time let's assume that on police oversight, al and Bernie for a few minutes left together in one cell and they had the opportunity to discuss further tactics. Thinking each of them understands that they face eight years in prison. However, if they act together, they will be able to reduce the period to two years. Therefore, they agree that none of them testify will not. As soon as al returned to his cell, confident in the fact that Bernie is not going to take it, he gets even more tempted to tell Bernie the truth and go free.
the prisoner's Dilemma with tough contract
At the same time, he knows what Bernie is a crook, and in any case does not believe that he will keep his word. So al decides to break the contract. In another cell, Bernie, of course, comes to the same conclusion. Thus, they end up back where we started. This story could have developed differently if there would be an opportunity to strengthen the contract that they sign. Suppose (for serious police malpractice) Carlos, the local mafia was allowed to meet with both of them. In his presence, each of them swears that he will not testify. Carlos gives them to understand that if any of them break the promise, waiting for his fate is much worse than someone in prison. This time everything goes smoothly, and eventually each of them make 2 years in prison.
From this example we see that the introduction of strict contract completely changes the rules of the game. Maybe it's a surprise, but it opens up previously inaccessible opportunities that can be mutually beneficial. These insights are Central to the economy. Indeed, it was a crucial moment in the history of mankind, where trade in goods and services based on performed mandatory contract law, allowing to punish cheaters and keep the trust of customers. The theory of cooperative games (i.e., games in which permitted contracts) is the subject of intense study and is of great importance for the economy.
the Treaties, of course, not always useful. In the prisoner's dilemma, the police certainly would have wanted to avoid the scenario described above. (To avoid such cases in criminal circles often opened unchanged the order not to cooperate with the authorities.
This vow of silence is a serious difficulty for the police in the investigation of organized crimes, since witnesses are often too afraid to break it, knowing full well how it may end.) Another example: if a group of competing companies, for example, the mobile operators agree not to lower their prices below a certain level, it will prevent competition between them and will force buyers to pay more. So we have competition laws that do not allow for the emergence of such cartels.
Computer games change the world
game Theory is rooted in the study of ancient Board games such as chess in India, in China, mill in Rome and Mancala in Africa. This is an unusual branch of mathematics continues to be of great interest. This is especially true since the advent of computers. One of the fathers of modern computer science was Claude Shannon (see How to talk to the computer). In 1950 he wrote an article "Programming a computer for playing chess".
In it, he argued that, although the problem "has no practical significance", it deserves attention, since "chess in General is considered a game that requires "thinking"; training the computer to play chess, will force us either to admit the possibility of thinking machines, or to limit our understanding of thinking."
these were prophetic words. Since the work of Shannon game theory became closely associated with the pursuit of artificial intelligence, and Board games, like chess, turned out to be excellent prototypes for studying it. Therefore, when historians of the future will look back on the developing relationship between humans and machines, a turning point date, which they note may be 11 may 1997. On this day, the computer Deep Blue defeated Garry Kasparov, the champion on chess among men. He struck him with the score 2-1 in six games, three of which ended in a draw.
the Strong side Deep Blue was partly in its exceptional computing power: the computer can analyze 200 million gaming positions per second. Of course, it sounds like a lot, but chess is a very challenging game. Shannon estimated the approximate number of different possible chess positions is 10^43, that is 1 with 43 zeros. Deep Blue would require far more time than the lifetime of the Universe to consider only a tiny part of them. So Deep Blue it was necessary to iterate through all positions in succession, and to apply the strategy to a number of options under consideration was foreseeable.
Checkers is the game simpler than chess, but even with that the number of positions on the Board equal to 5 x 10^20, it is still too complex to directly calculate all possible moves. However, in 2007, the team led by programmer Jonathan Schaeffer announced that they managed to finish the unusual analysis of this game. With a network of dozens of computers working simultaneously since 1989, and the latest technology in the field of artificial intelligence, Schaeffer and his colleagues were able to identify that "secret checkers secret." They found the perfect strategy game — the kind that can never be beaten nor the greatest of players among the people, nor any car that you can imagine.
the Passage from the book of Elsa Richard "How to solve the da Vinci code and 34 amazing ways to apply mathematics"
Inflation and Multilingua 27.06.2016 at 12:29
The focus of research 01.06.2016 at 17:24
The dead ends of bourgeois technicism 25.05.2016 at 11:16
How strong feelings towards religion among the peoples of different countries 04.05.2016 at 05:50
Thanks to deep learning, work can be a lot of cars 31.03.2016 at 09:45