What is game theory? As the old saying goes, things are like chess. Everyone in life is like a chess player, and every movement is like putting a coin on an invisible chessboard. Smart and cautious chess players try to figure out and contain each other, and everyone strives to win, playing many wonderful and changeable chess games. Game theory is to study the rational and logical part of chess player's "playing chess" and systematize it into a science. In other words, it is to study how individuals get the most reasonable strategies in complex interactions. In fact, game theory comes from ancient games or chess games. Mathematicians abstract concrete problems and study their laws and changes by establishing a self-complete logical framework and system. This is not an easy task. Take the simplest two-person game as an example. If you think about it, you will know that there is a great mystery. If it is assumed that both sides accurately remember every move of themselves and their opponents, and they are the most "rational" players, then A has to carefully consider B's idea in order to win the game when playing, and B has to consider A's idea when playing, then A has to think that B is considering his idea, and B certainly knows that A has already considered it.
Faced with such a fog, how can game theory begin to analyze and solve problems, how can it find the optimal solution, and how can abstract mathematical problems be summarized as reality, thus making it possible to guide practice in theory? Modern game theory was founded by Hungarian mathematician von Neumann in the 1920s. His magnum opus Game Theory and Economic Behavior published in 1944 in cooperation with economist Oscar Morgenstein marked the initial formation of modern system game theory. For non-cooperative and purely competitive games, Neumann only solves two-person zero-sum games-just like two people playing chess or table tennis, one person wins one game and the other loses the other, and the net profit is zero. The abstract game problem here is whether and how to find a theoretical "solution" or "balance", that is, the most "reasonable" and optimal specific strategy for both players, given the set of participants (both sides), the set of strategies (all moves) and the set of profits (winners and losers). What is "reasonable"? Applying the "min-max" criterion in traditional determinism, that is, each side of the game assumes that the fundamental purpose of all the advantages and disadvantages of the other side is to make itself suffer the most, and accordingly optimize its own countermeasures, Neumann mathematically proves that every two-person zero-sum game can find a "min-max solution" through certain linear operations. Through a certain linear operation, two competitors randomly use each step in a set of optimal strategies in the form of probability distribution, so as to finally achieve the maximum and equal profit for each other. Of course, the implication is that this optimal strategy does not depend on the opponent's operation in the game. Generally speaking, the basic "rational" thought embodied in this famous minimax theorem is "hope for the best and prepare for the worst".
2. In economics, "pig's income" is a famous game theory example.
This example is about: there are two * s in the circle, one is big and the other is small. There is a pedal on one side of the circle. Every time you step on the pedal, a small amount of food will fall on the feeding mouth on the other side of the circle away from the pedal. If one of them steps on the pedal, the other one will have a chance to eat the food dropped on the other side first. When Xiao * steps on the pedal, Da * will just finish all the food before Xiao * runs to the trough; If the big one steps on the pedal, the small one still has a chance to run to the trough and fight for the other half.
So, what strategies will the two * each adopt? The answer is: Xiao * will choose the "hitchhiking" strategy, that is, wait comfortably in the trough; And da * tirelessly runs between the pedal and the trough for a little leftovers.
What's the reason? Because you can get nothing if you pedal, but you can eat food if you don't pedal. For small *, whether big * tramples or not, it is always a good choice not to trample. On the other hand, big * knows little * won't step on the gas pedal. It's better to step on the gas myself than not to step at all, so I have to do it myself.
The phenomenon of "lying down and running" is caused by the rules of the game in the story The core indicators of the rules are: the number of things falling each time and the distance from the pedal to the feeding port.
If we change the core indicators, will there be the same scene of "lying down and running" in the circle? Give it a try.
Change scheme 1: reduction scheme. Feeding is only half of the original weight. As a result, the little guys stopped kicking. Small * to step on, big * to finish the food; If the big one steps on it, the small one will finish the food. Whoever pushes means contributing food to each other, so no one will have the motivation to push.
If the goal is to make children pedal more, the design of this game rule is obviously a failure.
Variation scheme 2: incremental scheme. Feed twice as much as before. As a result, both small and big people can pedal. Anyone who wants to eat will kick. Anyway, the other party won't eat all the food at once. Small * and big * are equivalent to living in a productive society with relatively rich materials, so the sense of competition is not very strong.
For the designer of the rules of the game, the cost of this rule is quite high (providing two meals at a time); Moreover, because the competition is not strong, it has no effect to let children push more.
Variant 3: Decreasing plus shifting scheme. Feed only half the original weight, but at the same time move the feeding port near the pedal. As a result, both Xiao * and Da * pushed hard. Those who wait will not eat, and those who work hard will get more. Every harvest is just a flower.
This is the best solution for game designers. The cost is not high, but the harvest is the biggest.
The original "intelligence game" story inspired the weak (small *) in the competition to wait for the best strategy. However, for the society, the allocation of social resources when Xiao * hitchhiked was not optimal because Xiao * failed to participate in the competition. In order to make the most efficient allocation of resources, the designers of rules don't want to see anyone hitchhiking, so does the government, and so does the boss of the company. Whether the phenomenon of "hitchhiking" can be completely eliminated depends on whether the core indicators of the rules of the game are set properly.
For example, the company's incentive system design is too strong, and it is still holding shares and options. All the employees in the company have become millionaires. Not to mention the high cost, the enthusiasm of employees is not necessarily high. This is equivalent to an "intellectual game"
The situation described by the incremental scheme. But if the reward is not strong, the audience will be divided (even the "small *" who doesn't work), and the big * who worked hard will have no motivation-just like the situation described in the first reduction plan of "Intelligence Game". The best incentive mechanism design is like changing the third scheme-reducing staff and changing shifts. Rewards are not shared by everyone, but for individuals (such as business proportion commission), which not only saves costs (for the company), but also eliminates the phenomenon of "hitchhiking" and can achieve effective incentives.
Many people haven't read the story of "Intelligence Games", but they are consciously using small strategies. Retail investors are waiting for the dealer to get on the sedan chair in the stock market; Waiting for profitable new products to appear in the industrial market, and then copying hot money on a large scale to make huge profits; People in the company who do not create benefits but share the results, and so on. Therefore, for those who make various rules of the game of economic management, they must understand the reasons for the change of the index of "intelligence game".
3. Background knowledge: the principle and application of Nash game theory.
Beijing Evening News
Nash's two important papers on non-cooperative game theory in 1950 and 195 1 completely changed people's views on competition and market. He proved the non-cooperative game and its equilibrium solution, and proved the existence of equilibrium solution, namely the famous Nash equilibrium. Thus, the internal relationship between game equilibrium and economic equilibrium is revealed. Nash's research laid the cornerstone of modern non-cooperative game theory, and later game theory research basically followed this main line. However, Nash's genius discovery was flatly denied by von Neumann, and before that, he was also given a cold shoulder by Einstein. But the nature of challenging and despising authority in his bones made Nash stick to his point of view and eventually become a master. If it weren't for more than 30 years of serious mental illness, I'm afraid he would have
Standing on the podium of the Nobel Prize, I will never share this honor with others.
Nash is a very talented mathematician, and his major contributions were made when he was studying for a doctorate at Princeton from 1950 to 195 1. But his genius found that the equilibrium of non-cooperative game, namely "Nash equilibrium", was not smooth sailing.
1948 Nash went to Princeton University to study for a doctorate in mathematics. He was less than 20 years old that year. At that time, Princeton was outstanding and talented. Einstein, von Neumann, Levshetz (Head of the Department of Mathematics), Albert Tucker, Alenzo Cech, Harold Kuhn, Norman Sting Rhodes, Fawkes, etc. It's all here. Game theory was mainly founded by von Neumann (1903-1957). He is a talented mathematician who was born in Hungary. He not only founded the economic game theory, but also invented the computer. As early as the beginning of the 20th century, zermelo, Borer and von Neumann began to study the exact mathematical expressions of games. Until 1939, von Neumann got to know the economist oskar morgenstern and cooperated with him, which made game theory enter the broad field of economics.
From 65438 to 0944, his masterpiece Game Theory and Economic Behavior, co-authored with Oscar Morgenstein, was published, which marked the initial formation of modern system game theory. Although the research on the nature of games can be traced back to19th century or even earlier. For example, the Cournot simple duopoly game of 1838; Bertrand of 1883 and Edgeworth of 1925 studied the output and price monopoly of two oligarchs; More than 2,000 years ago, Sun Bin, a descendant of Sun Wu, a famous military strategist in China, used game theory to help Tian Ji win the horse race, and so on, all of which were the seeds of early game theory, characterized by scattered research, great contingency and no system. The concepts and analytical methods of standard, extended and cooperative game model solutions put forward by von Neumann and Morgan Stern in Game Theory and Economic Behavior laid the theoretical foundation of this discipline. The cooperative game reached its peak in the 1950s. However, the limitations of Neumann's game theory are increasingly exposed. Because it is too abstract, its application scope is greatly limited. For a long time, people know little about the study of game theory, which is only the patent of a few mathematicians, so its influence is very limited. It is at this time that the non-cooperative game-"Nash equilibrium" came into being, which marked the beginning of a new era of game theory! Nash is not a step-by-step student. He often plays truant. According to his classmates' recollection, they can't remember when they had a complete required course with Nash, but Nash argued that he had at least taken Steen Rhodes' algebraic topology. Steen Rhodes was the founder of this subject, but after several classes, Nash decided that this course was not to his taste. So he left again. However, Nash is, after all, an extraordinary person with talent. He is deeply fascinated by every branch of the kingdom of mathematics, such as topology, algebraic geometry, logic, game theory and so on. Nash often shows his distinctive self-confidence and conceit, full of aggressive academic ambitions. 1950 all summer, Nash was busy with nervous exams, and his game theory research was interrupted. He thought it was a great waste. I don't know this temporary "giving up", but under the subconscious constant thinking, it has gradually formed a clear vein, and I was inspired by generate! In the month of 10 this year, he suddenly felt a surge of talent and dreams. One of the most dazzling highlights is the concept of non-cooperative game equilibrium, which will be called "Nash equilibrium" in the future. Nash's main academic contributions are embodied in two papers (including a doctoral thesis) of 1950 and 195 1. It was not until 1950 that he wrote a long doctoral thesis entitled "Non-cooperative Game", which was published in 1950+0 1 Monthly Bulletin of the American Academy of Sciences and immediately caused a sensation. Speaking of it, it all depends on the work of Brother David Gale. Just a few days after being demoted by von Neumann, he met Gail and told him that he pushed von Neumann's minimax solution into the field of non-cooperative games and found a universal method and equilibrium point. Gail, listen carefully. He finally realized that Nash's idea, Beavon Neumann's cooperative game theory, can better reflect the real situation, and his rigorous and beautiful mathematical proof left a deep impression on him. Gail suggested that he tidy it up and publish it immediately, lest others beat him to it. Nash, a fledgling boy, didn't know the danger of competition and never thought about it. So Gail acted as his "agent" and drafted a short message to the Academy of Sciences on his behalf. Lev Shetz, the head of the department, personally submitted the manuscript to the Academy of Sciences. Nash doesn't write many articles, just a few, but it's enough, because they are among the best. This is also worth pondering. How many articles does a domestic professor need to publish in "core journals"? According to this standard, Nash may not be qualified.
Morris, winner of the Nobel Prize in Economics from 65438 to 0996, did not publish any articles when he was a professor of economics in edgeworth at Oxford University. Special talents should have special selection methods.
Nash University began to study the game theory of pure mathematics, and it became more comfortable after entering Princeton University from 65438 to 0948. In his early twenties, he had become a world-famous mathematician. Especially in the field of economic game theory, he has made epoch-making contributions and is one of the greatest game theory masters after von Neumann. His famous Nash equilibrium concept plays a central role in the theory of non-cooperative game. Later researchers' contributions to game theory are all based on this concept. The presentation and continuous improvement of Nash equilibrium has laid a solid theoretical foundation for the wide application of game theory in economics, management, sociology, political science, military science and other fields.
The plight of prisoners
A short story in Dali's theory
To understand Nash's contribution, we must first know what is a non-cooperative game problem. At present, almost all game theory textbooks will talk about the example of "prisoner's dilemma", and the examples in each book are similar.
Game theory is, after all, mathematics, or rather, a branch of operational research. When talking about classics and theories, mathematical language is indispensable, which is just a lot of mathematical formulas in the eyes of laymen. Fortunately, game theory is concerned with daily economic life, so we have to eat fireworks. This theory is actually a term borrowed from chess, poker, war and other issues with the nature of competition, confrontation and decision-making. It sounds a bit mysterious, but it actually has important practical significance. Game theory masters look at economic and social issues just like playing chess, and often have profound truth in the game. Therefore, it is not boring to start with trivial matters in daily life and explain them with stories around us as examples. One day, a rich man was killed at home and his property was stolen. During the investigation of this case, the police arrested two suspects, Scafi and Nakul, and found the lost property in the victim's house from their residence. But they denied that they killed anyone, arguing that they killed the rich first, and then they just stole something. So the police isolated the two and put them in different rooms for trial. The D.A. will talk to everyone individually. The prosecutor said, "Because you have conclusive evidence of theft, you can be sentenced to one year in prison." But I can make a deal with you. If you plead guilty to murder alone, I will only sentence you to three months' imprisonment, but your partner will get ten years' imprisonment. If you refuse to confess and are reported by your partner, you will be sentenced to ten years in prison, and he will only be sentenced to three months in prison. However, if you all confess, then you will all be sentenced to five years in prison. "What should Scalfi and Nacoors do? They are faced with a dilemma-confession or denial. Obviously, the best strategy is that both sides deny it, and as a result, everyone only gets one year. However, because the two are in isolation, they cannot confess. Therefore, according to Adam Smith's theory, everyone starts from self-interest, and they choose repentance as the best strategy. Because if you confess, you can expect three months of short-term imprisonment, but only if your partner denies it, which is obviously better than your own denial of 10 years imprisonment. This strategy is at the expense of others. Not only that, but confession has more benefits. If the other party denies it frankly, they will go to jail 10 years. It's so uneconomical! Therefore, in this case, you should still choose to confess. Even if two people confess at the same time, they will only be sentenced to five years at most, which is better than 10 years. Therefore, the reasonable choice of the two is confession, and the strategy (denial) and the ending (sentence 1 year imprisonment) that were originally beneficial to both sides will not appear. In this way, both of them chose Frank's strategy and were sentenced to five years' imprisonment. The result is called "Nash equilibrium", which is also called non-cooperative equilibrium. Because, when each party chooses a strategy, there is no "collusion" (collusion), they just choose the strategy that is most beneficial to them, regardless of social welfare or the interests of any other opponent. In other words, this strategy combination is composed of the best strategy combination of all participants (also called parties and participants). No one will take the initiative to change the strategy in order to strive for greater benefits for themselves. " Prisoner's Dilemma "has extensive and profound significance. The conflict between individual rationality and collective rationality and everyone's pursuit of their own interests lead to a "Nash equilibrium", which is also an unfavorable outcome for everyone. Both of them think of themselves first in the strategy of frank denial, so they are bound to serve long sentences. Only when everyone thinks of each other first, or colludes with each other, can we get the result of the shortest imprisonment. Nash equilibrium first challenges Adam Smith's "invisible hand" principle. According to Smith's theory, in the market economy, everyone starts from the purpose of self-interest, and finally the whole society achieves the effect of altruism. Let's review the famous saying of this economic sage in The Wealth of Nations: "By pursuing (personal) self-interest, he often promotes social interests more effectively than he actually wants to do. "The paradox of the principle of" invisible hand "leads from Nash equilibrium: starting from self-interest, the result is not self-interest, neither self-interest nor self-interest. This is the fate of two prisoners. In this sense, the paradox put forward by Nash equilibrium actually shakes the cornerstone of western economics. Therefore, from Nash equilibrium, we can also realize a truth: cooperation is a favorable "self-interest strategy". But it must conform to the following Huang Jinlv: Treat others as you want them to treat you, but only if others do the same. That's what China people say, "Don't do to others what you don't want others to do to you". But only if you don't do to me what you don't want me to do. Secondly, Nash equilibrium is a non-cooperative game equilibrium. In reality, non-cooperation is more common than cooperation. Therefore, "Nash equilibrium" is a significant development of the cooperative game theory of von Neumann and Morgan Stern, and even a revolution.
From the general sense of Nash equilibrium, we can deeply understand the common game phenomena in economy, society, politics, national defense, management and daily life. We will give many examples similar to the "prisoner's dilemma". Such as price war, military competition, pollution and so on. The general game problem consists of three elements: players, also known as the set of parties, participants and strategies. Each player's strategy and payoff. Among them, the so-called win refers to the utility that people in each game get if they choose a specific strategic relationship. All game problems will encounter these three elements.
Price war game:
Now we often encounter all kinds of home appliance price wars, such as color TV wars, refrigerator wars, air conditioning wars, microwave oven wars ... The beneficiaries of these wars are consumers first. Every time I see the price war of home appliances, ordinary people will "have nothing to steal." It can be explained here that the outcome of the price war of manufacturers is also a "Nash equilibrium", and the result of the price war is that no one has money to earn. Because the profits of both sides of the game are exactly zero. The result of competition is stable, that is, a "Nash equilibrium". This result may be beneficial to consumers, but it is disastrous to manufacturers. Therefore, the price war means suicide for manufacturers. From this case, we can draw two questions. First of all, competitive price reduction or "Nash equilibrium" may lead to efficient zero-profit results. Second, if the price war is not adopted, what will happen as a hostile game? Every enterprise will consider adopting normal price strategy or high price strategy to form a monopoly price and try its best to obtain monopoly profits. If a monopoly can be formed, the profits of both sides of the game will be the greatest. This kind of situation is what monopoly does, which usually raises the price. At the other extreme, if the manufacturer uses the normal price, both parties can make a profit. From this point, we draw another basic rule: "Build your own strategy on the assumption that your opponent will act in his best interests." In fact, the equilibrium of perfect competition is Nash equilibrium or non-cooperative game equilibrium. In this state, each manufacturer or consumer makes decisions based on all the prices set by others. In this equilibrium, every enterprise should maximize its profit, and consumers should also maximize its utility, resulting in zero profit, that is, price equals marginal cost. In the case of perfect competition, non-cooperative behavior leads to the state of economic efficiency expected by society. If manufacturers take cooperative actions and decide to turn to monopoly prices, the economic efficiency of society will be destroyed. This is why it is of great significance for WTO and governments to strengthen anti-monopoly.
Pollution game:
If there is pollution in the market economy, but the government does not control the environment, in order to maximize profits, enterprises would rather sacrifice the environment and never take the initiative to increase investment in environmental protection equipment. According to the invisible hand principle, all enterprises will start from self-interest and adopt the strategy of ignoring the environment, thus entering the "Nash equilibrium" state. If an enterprise invests in pollution control for altruistic purposes, while other enterprises still ignore environmental pollution, then the production cost of this enterprise will increase, the price will increase, its products will not be competitive, and even the enterprise will go bankrupt. This is an example of the failure of the "effective and complete competition mechanism of the invisible hand" Until the mid-1990s, the blind development of Chinese township enterprises caused serious pollution. Only when the government strengthens pollution control will enterprises adopt a low-pollution strategy combination. In this case, enterprises will get the same profits as high pollution, but the environment will be better.