Game Theory
by Joachim Pietzsch
John von Neumann was a genius and not a diplomat. “I refuse to accept the stupidity of the Stock Exchange boys as an explanation of the trend of stocks”, he remarked in 1939. “Those boys are stupid alright, but there must be an explanation of what happens, which makes no use of this fact”.[1] In quest of this explanation, the mathematician of Hungarian origin who had been appointed professor at the Princeton Institute for Advanced Studies at the age of 30, joined forces with the economist Oskar Morgenstern. During the war years, both worked intensively on a Theory of Games and Economic Behavior, despite of Neumann’s obligations as a consultant to the US army and to the Manhattan project. “Johnny would get home in the evening after having zig-zagged through a number of meetings up and down the coast”, his wife later recalled. “As soon as he got in, he called Oskar and then they would spend the better half of the night writing the book…this went on for nearly two years.”[2] The result was a monumental study of 673 pages, which was published in 1944 and became the cornerstone of game theory as a science of strategy.
A long road to recognition
Exactly fifty years later, in 1994, when von Neumann and Morgenstern had long passed away, the Royal Swedish Academy of Sciences (RSAS) decided for the first time to award the The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel that had been established in 1968 to three pioneers of game theory, which in the meantime had proven to be so useful and successful in economic analysis that at least a quarter of all papers in economic theory were based on its models[3]. Why did it take half a century for game theory to be recognized? A crucial fact was “that von Neumann’s theory was too highly mathematical for economists”, so that “the theory of games was developed almost exclusively by mathematicians during this period”.[4] Or to put it differently: “Game theory would have found a more ready acceptance in its early years if enthusiasts hadn’t made it all seem so difficult.”[5]
The analysis of von Neumann and Morgenstern focused on two-person zero-sum games, in which the gains of one player equal the losses of the other one. It mirrors the situation of two enemies whose interests conflict totally and thus was appropriate for the war situation in which the book was conceived. Drawing on his first paper on game theory[6], von Neumann together with Morgenstern worked out the minimax theorem for the solutions of games of pure conflict. These solutions are equilibria where each player succeeds in minimizing the maximum gain of his opponent and thereby also his own maximum loss. Mathematically elegant as it was, however, this theorem only rarely applies to real-life situations beyond the military field. The games people play in real-life are in most cases simply not games of pure conflict, but blended with a pragmatic wish for cooperation.
A game-changing thesis
Imagine for example that you are driving through a narrow street when you suddenly face another car coming from the opposite direction. You can decide to either slow down or speed up, and so can the other driver. What would be the best solution of this game called “chicken”? Or imagine another situation, which game theorists exaggeratedly call “battle of the sexes” although it is not necessarily gender-related and each of us certainly has encountered similar problems: A newly married couple is honeymooning in a big city. At breakfast, they discuss whether to go to a football match or to the opera in the evening. The man prefers the sport event, the woman Verdi. So they postpone their decision. Later, while on a sightseeing tour, they get separated in the crowds and now each has to decide independently where to go in the evening (mobile phones had not yet been invented at the time this game was devised). Will their day end happily?
It was a twenty-one year old graduate student who first found the clue to answer questions like this mathematically. He did so in his doctoral thesis, which comprised 27 pages. It was entitled “Non-cooperative games” and submitted to the Mathematics Department of Princeton University in May 1950. The young man’s name was John Nash. The two major insights that he developed in this thesis were precisely those to which the RSAS referred when they awarded him with a share of the Nobel Memorial Prize 1994: Nash introduced the distinction between non-cooperative games and cooperative games. And he proved that there existed at least one optimal solution for each finite non-cooperative game. This solution became to be known as the “Nash equilibrium”. The term “non-cooperative game” does not mean that its players are not allowed to cooperate. It just means that there are no binding agreements between them, while in cooperative games such contracts may exist. In a non-cooperative game, a “Nash equilibrium” is reached when each player chooses his best response to what the other does. In a game with simultaneous moves this is not as trivial as it sounds, because in order to determine their strategy and to make a decision both players find themselves caught in a logical circle: “I think that he thinks that I think…” In a Nash equilibrium, this circular reasoning finds it conclusion.[7]
Consequently, for both of our examples where simultaneous decisions are required, there are two Nash equilibria: In the first, one driver has to slow down and the other to speed up, because only then a crash is avoided and the situation is relatively quickly cleared. If both speeded up, they’d encounter an accident; if both slowed down, they’d loose time. In the second example, the couple will only enjoy a happy evening together, if both either show up in the football stadium or in the opera house. Yet not all interactions will so easily yield win-win-solutions.
The prisoner’s dilemma
The best-known example for such a difficulty is the prisoner’s dilemma, which was formalized for game theory by Nash’s Ph.D. adviser Al Tucker. In the traditional version of this game, the district attorney has arrested two gangsters. He knows that they are guilty of a major crime, but cannot convict either unless one of them confesses. The two suspects have promised each other to keep silent should they ever come in such a situation. The attorney therefore separately offers each the following deal: If you confess and your accomplice doesn’t, then you go free. If you don’t confess but your accomplice does, then you will be sentenced to the maximum term in jail. If you both confess, then you will both be convicted, but not receive the maximum sentence. If none of you confesses, you both will be put in prison on a minor charge for which a conviction is certain. Will the two suspects under these circumstances keep their promise and cooperate? Nash’s theory predicts that both will cheat each other and confess, because it is in their best private interest to avoid the maximum term. So both are sentenced to a sub-maximal, but still very long term. They would have been better off and faced only a minimal term in jail, however, if they had kept their promise.
Following best private interests does obviously not always lead to collectively optimal results. While it perhaps would go too far to state that the prisoner’s dilemma contains the essence of the problem of human cooperation, it nevertheless is helpful for studying quite a lot of business problems. Consider two companies selling similar products and having to decide on a pricing strategy each. “They best exploit their joint market power when both charge a high price; each makes a profit of ten million dollars per month. If one sets a competitive low price, it wins a lot of customers away from the rival. Suppose its profit rises to twelve million dollars, and that of the rival falls to seven million. If both set low prices, the profit of each is nine million dollars. Here, the low-price strategy is akin to the prisoner’s confession, and the high-price akin to keeping silent.“[8]
Between evolution and economics
At this point it is important to note that equilibria in non-cooperative games according to Nash’s thesis allow for two interpretations. One based on mass action, i.e. on repeated sequential games in statistical populations (p. 21f.), one based on rational prediction of behavior (p. 23ff.). The first has mainly become important in biology, with John Maynard Smith as its best-known proponent. “Evolution and the theory of games”, published in 1982, was his most influential book in this field. The latter is primarily of importance in economics and politics.
“[The Nash] equilibrium is without doubt the single game theoretic solution concept that is most frequently applied in economics. Economic applications include oligopoly, entry and exit, market equilibrium, search, location, bargaining, product quality, auctions, insurance, principal-agent [problems], higher education, discrimination, public goods, what have you. On the political front, applications include voting, arms control and inspection, as well as most international political models (deterrence, etc.)[9]“, writes Robert Aumann, a recipient of the Nobel Memorial Prize 2005, and ever since a regular guest at the Lindau Meetings on Economic Sciences. At the beginning of his lecture in 2011, Aumann therefore paid tribute to John Nash who was present in the audience.
(00:00:10 - 00:00:38)
According to the official website of the Nobel Prize, John Nash constantly ranks among the most popular laureates in economic sciences. His fame as an ingenious mathematician has been multiplied by the movie A beautiful mind which features the story of his life and won four Oscars in 2001. In 1959, John Nash fell prey to a mental illness and experienced the dramatic “change from scientific rationality of thinking into the delusional thinking characteristic of persons who are psychiatrically diagnosed as ‚schizophrenic’[10]“. He suffered from schizophrenia for many years, yet succeeded in recovering in the early 1990s. In Lindau, Nash lectured for the first time in 2006, and discussed a specific form of cooperative games.
(00:05:08 - 00:06:55)
Refinements with respect to reality
The concept of the Nash equilibrium is the most widely used tool in game theory. Yet it is no perfect foundation for predicting the outcome of each non-cooperative game, especially if it has several equilibria. Refinements of Nash’s concept therefore needed to be developed to better adapt it to reality and to avoid equilibria that are unreasonable in economic terms. Reinhard Selten and John Harsanyi shared the Nobel Memorial Prize 1994 with John Nash in recognition of such refinements. “The three laureates constitute a natural combination”, the RSAS stated”, Nash provided the foundations for the analysis, while Selten developed it with respect to dynamics, and Harsanyi with respect to incomplete information.“[11] Harsanyi never came to Lindau, but Selten frequently. Speaking at the chemistry meeting in 1997, he fascinated the audience by the description of a game, in which both dynamics and incomplete information are important.
(00:10:00 - 00:18:00)
Theoreticians early knew both the implications and the applications of games like the stealing game to real-world situations. Practical business men and women remained skeptical however about the utility of game theory. They tended to neglect it as just another branch of useless social science. This changed quickly during the 1990s when game theorists began to advise governments how to best auction off the rights to use radio frequencies for beepers or mobile phones with tremendous success. Reinhard Selten explains how they did this with an early example from the US.
(00:28:04 - 00:32:22)
William Vickrey had been advocating the use of specially designed auctions for the sale of major public assets already 30 years before, when he elaborated on the game-theoretic aspects of auctions in his article "Auctions and Bidding Games" (1962). Vickrey died on October 11, 1996, three days after receiving the announcement that he would share the Nobel Memorial Prize 1996 with James Mirrlees "for their fundamental contributions to the economic theory of incentives under asymmetric information".
The choice between conflict and cooperation
Nine years later, the Prize in Economic Sciences 2005 was awarded jointly to Robert Aumann and Thomas Schelling "for having enhanced our understanding of conflict and cooperation through game-theory analysis". Both scientists began to conduct their research in the late 1950 against the background of the Cold War and the nuclear arms race between the superpowers, Schelling as an economist, Aumann as a mathematician. Schelling initially was primarily interested in bargaining situations. This included negotiations between two countries or between business partners, but also the analysis of acute crises. Schelling sharpened the „chicken“ game: He noted that it could also be regarded as a bargaining situation when two trucks loaded with dynamite meet on a road wide enough for one. His thorough analyses of interactions where two countries in a territorial conflict have the choice to either mobilize or to refrain from mobilization, to keep peace or to enter into war, culminated in his book „The Strategy of Conflict“, which was published in 1960 and remains to be an influential classic in economics and social sciences. Schelling’s work helped to both understand and foster the gradual development of cooperation between stakeholders who initially lacked confidence in one another. Schelling, whose most popular book „Micromotives and Macrobehavior“ (1978) examined the tension between individual plans and social conventions in everyday encounters and situations, presents his ideas with a minimum of mathematics and thus quite understandably. It’s a pity that he never lectured in Lindau.
His Co-Laureate Robert Aumann on the other hand, is a regular guest and one of the most entertaining presenters at the Lindau Meetings on Economic Sciences, although he is a mathematician. His original game-theoretical interest focused on the analysis of repeated games, i.e. interactions in which the players interact many times over a long period. He has shown how long-term cooperation can lead to a peaceful equilibrium. The prisoner’s dilemma, for example, could find an optimal solution, if both prisoners could decide every day again whether to keep their promise (cooperate) or to break it. „In this case, it can be shown that cooperation in every period is an equilibrium outcome. The reason is that players can now threaten to punish any deviation from cooperative play today by refusing to cooperate in the future. That is, the short-term gain from defection today is more than outweighed by the reduction in future cooperation.“ Aumann’s theory of repeated games has proven to be a fruitful tool and found many practical applications that „extend from competing firms, which collude to maintain a high price level, and farmers who share pastures or irrigation systems, to countries, which enter into environmental agreements or are involved in territorial disputes.“[13]
With their research, both Schelling and Aumann succeeded in integrating human behavior that in tradional economics used to be classified as irrational into the realm of rational understandability. Aumann gave an interesting example of this integration in his Lindau lecture in 2008, when he introduced a game originally devised by Selten’s student Werner Güth:
(00:07:01 - 00:13:27)
Institutions under scrutiny of game designers
While for Aumann and Schelling conflict and cooperation take center stage in their game-theoretical considerations, the search for optimal resource allocation mechanisms under realistic market conditions (where there is for example no perfect competition or freely available information) lies at the heart of mechanism design theory, for whose foundation and development Leonid Hurwicz, Eric S. Maskin and Roger B. Myerson jointly received the Nobel Memorial Prize 2007. Mechanism design theory addresses the basic problem „that people have an incentive to economize with their private information“. An example can be found in sickness insurance, which „is typically criticized either for offering too little coverage or for inviting misuse“, because „some insurance-policy sellers claim that their costs are high in order to increase the price; some beneficiaries of joint projects such as insurance-policy holders claim that their benefits are low in order to reduce their own contributions to the project; some well-insured workers claim that they are sick, in order to reduce their workload“.[14] Mechanism design theory strives to find ways to minimize the economic losses that are caused by such asymmetric information. It defines institutions and the interaction between them or with them as non-cooperative games, and compares different institutions in terms of the equilibrium outcomes of these games. It allows analyzing the performance of institutions relative to the theoretical optimum, for example in regulation, corporate governance and finance, taxation, voting procedures and bilateral trade. Partly drawing on William Vickrey’s work, mechanism design theory was also applied to optimize the profitability of auctions of public goods.
The development of mechanism design theory originates from Leonid Hurwicz’ study on the “Optimality and informational efficiency in resource allocation processes“, which he published in 1960. Leonid Hurwicz was 90 years when he was awarded the Prize in 2007, the oldest Laureate in Economic Sciences ever. He died in 2008. His Co-Laureates Roger Myerson and Eric Maskin were in their fifties when they received the Prize and have been lecturing in Lindau three times and twice, respectively. Their major contributions to mechanism design theory date back to the late 1970s and early 1980s when Myerson formulated the so-called revelation principle and Maskin developed the implementation theory, two concepts that quickly became indispensable corner stones of the design of optimal allocation procedures. An important element in Myerson’s general description of the revelation principle – which allows to solve a “design” problem by taking an oversimplified mathematical approach and then translating the sketched solution back into a more realistic design – is “moral hazard”, a situation where an actor not only capitalizes on private information but also takes unobserved actions. In his talk “Leadership, Trust, and Power: Dynamic Moral Hazard in High Office“, which he gave in Lindau in 2008, he put this concept into a wider historical perspective:
(00:27:29 - 00:31:49)
In 2011, he considered a model of moral-hazard credit cycles and concluded that to efficiently solve financial moral-hazard problems, bankers must form some kind of long-term relationship with communities of investors.
(00:33:18 - 00:34:21)
Eric Maskin discussed a totally different topic, which nevertheless can be effectively analyzed with the tools of mechanism design theory, in 2014. He asked why certain phenomena of the current era of globalization (as opposed to that of the 19th century) couldn’t be satisfyingly explained by the theory of comparative advantage. His answer is thought provoking enough to enjoy a rather long snippet of his presentation.
(00:17:31 - 00:27:50)
Priceless matching of supply and demand
In 2012, the conjecture that there is a backlog demand in honoring achievements based on game theory, appeared to be endorsed again by the RSAS, when it awarded the Economics Prize jointly to Alvin E. Roth and Lloyd S. Shapley "for the theory of stable allocations and the practice of market design". Shapley, whom Aumann had respected as „the high priest of game theory“ in his Lindau lecture in 2011, was 89 years old when he received the Prize. He had begun his research on game theory in Princeton in the 1950s and soon became the primary architect of the theory of cooperative games. In these games individuals try to realize optimal outcomes cooperatively, bound by agreements. If they are engaged in mutual trade, for example, then the result of this trade should be efficient. If it is not, some players would devise new trades that earned them more. At some point, however, an allocation will be realized where no players perceive any gains from further trade. Stability is reached. „Unrestricted trading is a key presumption underlying the concept of stability...In 1962, Shapley applied the idea of stability to a special case. In a short paper, joint with David Gale, he examined the case of pairwise matching: how individuals can be paired up when they all have different views regarding who would be the best match.“[15] The algorithm, which Gale and Shapley proposed in their paper, always leads to a stable matching. The application of this algorithm can be of enormous practical importance in markets where supply and demand cannot be brought into an equilibrium by prices, for example in the case of organ transplantation. Shapley’s Co-Laureate Alvin Roth succeeded - among other achievements – in designing a market for kidney exchange as he impressively explained in his Lindau lecture on „Repugnant markets and prohibited transactions“ in 2014.
(00:21:21 - 00:27:42)
The rules of the game oligopoly
Game theory is here to stay. Without its practical applications, our world would probably look worse. In our times of accelerating interconnectivity it is gaining increasing importance. On this account, it was a good thing that five of the 17 Nobel Memorial Laureates who participated in the 5th Lindau Meeting on Economic Sciences in August 2014 were game theorists. The sixth would have been John Nash, but caused by illness he unfortunately had to decline his participation on short notice. Only a few weeks later, the The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2014 was awarded to Jean Tirole - the twelfth scientist since 1994 whose research has been deeply influenced by game theory. The French economist has used it to systematically study how firms react to different conditions and to each other’s behavior. He especially reflected the consequences of privatizations of formerly public monopolies, for example in the railway, post and telecommunication sector. Thereby he learned to understand the game by the name “oligopoly”, i.e. the rules of markets, which are dominated by only a few powerful firms. He recommended measures how to regulate the power of these firms both for the sake of their customers and of the common welfare. Thus he helped to realize the much lower prices for e. g. telephone calls and air fares that we enjoy today. The telling title of his Nobel Lecture is “The science of taming powerful firms – Market failures and public policy”. Perhaps he will share his insights on this topic also with young researchers in Lindau soon.
Footnotes:
[1] George Dyson. Turing’s Cathedral. The Origins of the digital universe. New York 2012, p.44
[2] ibid., p. 44f.
[3] „Between a quarter and a half of all papers in economic theory are based on game theory models“, said Robert Aumann in his Lindau lecture in 2011.
[4] Harold Kuhn in: The Work of John Nash in game theory. Nobel Seminar, December 8, 1994, p. 161.
[5] Ken Binmore. Game theory. A very short introduction. Oxford University press 2007, p. 32. The description of some examples in this topic cluster has been inspired by this illustrative and informative book.
[6] Von Neumann J. (1928) Zur Theorie der Gesellschaftsspiele. Mathematische Annalen 100 (1), p. 295-320.
[7] cf. Dixit A and Nalebuff B. Game theory. In: The concise encyclopaedia of economics. 2008. Library of Economics and Liberty. 14 September 2014. <http://www.econlib.org/library/Enc/GameTheory.html>.
[8] Dixit A and Nalebuff B. Prisoners’ Dilemma.The Concise Encyclopedia of Economics. 2008. Library of Economics and Liberty. 18 September 2014. <http://www.econlib.org/library/Enc/PrisonersDilemma.html>.
[9] Aumann, R. Game theory. In The new Palgrave dictionary of economics, edited by M. Milgate and P. Newman, 1987, 460 – 482; quoted from The Work of John Nash in game theory. Nobel Seminar, December 8, 1994, p. 164.
[10] cf. http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/1994/nash-bio.html
[11] cf. http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/1994/press.html
[12] http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/2005/advanced-economicsciences2005.pdf, p.13f.
Additional Lindau lectures related to Game theory:
John Nash (2011): Ideal Money and the Motivation of Savings and Thrift
Eric Maskin (2011): Elections and Strategic Voting: Condorcet and Borda
Robert Aumann (2014): Collectives as individuals
Roger Myerson (2014): Moral-Hazard Credit Cycles with Risk-Averse Agents