Current location - Training Enrollment Network - Mathematics courses - Introduction to game theory
Introduction to game theory
Section 1 What is game theory? Talking from "Prisoner's Dilemma"

One day, the police station received a report that a rich man was killed in his villa and all his belongings were looted. After many investigations, the police finally locked the suspects in Jack and Adam, because they were seen running out of the victim's house in a panic that night. The police searched their homes and found some stolen property in the victims' homes, so they were detained as suspects of murder and theft.

However, when they arrived at the detention center, both of them denied killing anyone. They argued that they were just passing by and wanted to go in and steal something. As a result, when I went in, I found that my master had been killed, so I took something casually and left. This explanation is not convincing. Besides, as we all know, murder is much more serious than theft in sentencing. The police decided to isolate the two men for questioning.

During the interrogation in isolation, the police told Jack, "Although you don't admit it, I know that you two killed that man, and things will come out sooner or later. Now I'll give you a chance to confess. If you confess, and Adam refuses to admit it, then you should turn yourself in and help the police solve the case. You will be released immediately and Adam will be imprisoned 10 years. If you all confess, each of you will go to prison for eight years; If you don't confess, you may be sentenced to burglary 1 year. Think about how to choose yourself. " Similarly, the police also said to Adam.

Most people may think that Jack and Adam will choose not to confess, so they can only be sentenced for burglary, and each person only needs to spend 1 year in prison. This is the best ending for two people. But will the result be like this? The answer is no, both of them chose to confess, and each was sentenced to eight years.

Why is this happening? Why did Jack and Adam make such "irrational" choices? In fact, this result is caused by their reasons. Let's take a look at the matrix diagram of whether the two are honest or not and the ending:

When the police told Jack the consequences of confessing or not, Jack began to figure out whether confessing was beneficial to him. Jack will think that if he chooses to confess, he will either be released immediately or sit in prison with Adam for 8 years; If you choose not to confess, you may only go to jail for 1 year, but you may also go to jail for1year. Although (1, 1) is the best ending for both of them, there is no guarantee that the other party will choose to confess because of the unreasonable information in separate trials. The ending of choosing confession is 8 years or 0 years, and the ending of choosing not to confess is 10 or 1 year. Without knowing the other person's choice, choosing confession is a favorable strategy for yourself. So, Jack will choose to confess. At the same time, Adam will think so. In the end, both of them chose to confess, and each of them served eight years in prison.

The above case is the famous "prisoner's dilemma" model, which is the most famous model in game theory. Why did Jack and Adam choose the best strategy for themselves and get the worst result in the end? This contains the truth of game theory.

Game theory refers to the theory that two or more parties fully understand the information of all parties in the case of competition, cooperation and conflict, and then choose an optimal decision that can strive for the greatest benefit for themselves.

Jack and Adam are two players in the prisoner's dilemma, also known as game participants. They got into trouble because they didn't choose the best decision for them, that is, they didn't confess at the same time. The fundamental reason was that they were interrogated in isolation and could not grasp each other's information. Therefore, it seems that everyone has worked out the best strategy for themselves, but the result is both sides lose.

Game theory is also applied in many things and allusions around us, so we will use the familiar story "Tian Ji Horse Racing" to explain what game theory is.

Tian Ji, the general of Qi, likes to bet on horse races with nobles on weekdays. At that time, the rules of horse racing were that each side produced a first-class horse, a middle-class horse and an inferior horse, and played three races, whichever was the best among the three races. Because Tian Ji's horse is slightly inferior to the noble's horse, so ten loses nine. At that time, when Sun Bin was a guest in Tian Ji's mansion, he often saw Tian Ji and the nobles racing horses, and he knew the rules of horse racing and the strength gap between the two horses like the back of his hand. On this day, Tian Ji lost the horse race again and went home in frustration. Sun Bin saw it and said to Tian Ji, "You can gamble with those nobles tomorrow, and I promise to let you win back all your previous losses." Tian Ji believed Sun Bin, and the next day he had a horse race with the nobles, which was a good bet.

Why did Sun Bin dare to make a guarantee? Because he made an analysis of this horse race: each side sent first-class, middle-class and lower-class horses, and the horses of each class in Tian Ji were a little slower than those of the other side. Because there is no order of appearance, there may be six forms of competition, and the result of each form of competition is easy to guess:

The first situation: superior horse to superior horse, intermediate horse to intermediate horse, inferior horse to inferior horse. Outcome: zero win in three games. The second situation: excellent horse versus excellent horse, inferior horse versus middle horse, and middle horse versus inferior horse. Outcome: one win in three games.

The third situation: China and Malaysia are on the horse, the horse is on the horse, and the horse is dismounted. Outcome: one win in three games.

The fourth situation: Chinese horse vs excellent horse, inferior horse vs Chinese horse, excellent horse vs inferior horse. Outcome: one win in three games.

The fifth situation: the inferior horse is against the superior horse, the superior horse is against the middle horse, and the middle horse is against the inferior horse. Result: Two wins in three games.

The sixth situation: the bad horse versus the good horse, the middle horse versus the middle horse, and the good horse versus the bad horse. Outcome: one win in three games.

Of the six forms of confrontation, only one can make Tian Ji win, which is exactly what Sun Bin adopted. Before the game, Sun Bin said to Tian Ji, "You use your inferior horse against his superior horse, then use your superior horse against his middle horse, and finally use China horse against his inferior horse." After the game, Tian Ji won the game by winning two out of three games. Tian Ji was impressed by Sun Bin and recommended him to Qi Weiwang. The same horse, just by adjusting the order of appearance, has achieved the opposite result. Contains the truth of game theory.

In the story of horse racing in Tian Ji, Tian Ji and the nobles of Qi are both sides of the game, also known as the participants of the game. Sun Bin fully understood the information of all parties, that is, the rules of the race and the strength gap between the horses, and helped Tian Ji choose the party that can strive for the greatest benefit, that is, the optimal strategy. Therefore, this is a typical example of the application of game theory in practice.

Here, we should also distinguish the concepts of game and game theory to avoid confusion. They have both similarities and differences. The literal meaning of "game" refers to gambling and playing Go, which is a metaphor for competing for benefits. Games have existed since the day of human existence, and games are played all the time around us. Game theory is a systematic theory, which belongs to a branch of applied mathematics. It can be said that the game embodies the idea of game theory and is the embodiment of game theory in reality.

As a kind of interest competition, games are always accompanied by human development. However, as a scientific theory, game theory was established by Hungarian mathematician john von neumann in 1928. He is also the inventor of the computer. At first, the computer was just a huge and bulky calculator, but today it has deeply affected all aspects of our life and work. So is game theory. When von Neumann first proved the basic principles of game theory, it was only a mathematical theory, which had little influence on real life, so it did not attract people's attention. Until 1944, the book Game Theory and Economic Behavior co-authored by von Neumann and Morgenstein was published. The publication of this book is of great significance. Previously, Von Neumann's game theory mainly studied two-person game, and this book expanded the research scope to multi-person game. At the same time, the game theory is applied from simple theory to economic field. The application in the economic field has laid the foundation and theoretical system for the development of game theory as a discipline.

When it comes to the development of game theory, John Forbes Nash cannot be ignored. This is a legend. In 1950, he wrote the paper "Equilibrium Point in N-player Game", when he was only 22 years old. The following year, he published another paper, Non-cooperative Game. These two papers have greatly promoted the research scope and application field of game theory. Nash equilibrium proposed in this paper has become the most important and basic theory in game theory. So he became a grandmaster and won the Nobel Prize in Economics in 1994. Nash himself and Nash equilibrium theory will be introduced in detail later.

There are three great revolutions in the history of economics, namely, marginal analysis revolution, Keynesian revolution and game theory revolution. Game theory provides people with new methods to solve problems.

Today, game theory has become a relatively perfect discipline, and its application scope also involves various fields. Economists who study game theory have the highest proportion of Nobel Prize in Economics, which shows the importance and influence of game theory. In 2005, the Nobel Prize in Economics was again awarded to economists who studied game theory. The reason given by the Royal Swedish Academy Science is that "their analysis of game theory has deepened our understanding of cooperation and conflict".

So what impact does game theory have on our personal life? This influence can be said to be everywhere.

Suppose you go to a hotel to attend a classmate's birthday party. His relatives, friends, classmates and colleagues went to many people that night, and everyone had a good time. But at this moment, there was a sudden fire outside. The fire was too big to be put out, so we had to escape. There are many people in the hotel, but there are only two safety exits. A safety exit is close, but there are many people, and everyone is crowded; The other exit is less crowded, but it is far away. If you put aside moral factors, how should you choose?

This is a question of game theory. As we know, game theory is a theory that fully understands all aspects of information and makes the best decision under specific circumstances. In this example, when you are in a fire, you get the message that there are two safety doors in the distance and how crowded they are. Here, you need to make the best decision, which is the most likely choice to escape. So how should we choose?