Lecture
Game theory — a mathematical method for studying optimal strategies in games. A game is understood as a process in which two or more parties take part, struggling to realize their interests. Each of the parties has its own goal and uses a certain strategy, which may lead to a win or a loss — depending on the behavior of the other players. Game theory helps to choose the best strategies while taking into account one's assumptions about the other participants, their resources, and their possible actions.
Game theory — a branch of applied mathematics, more precisely of operations research. Most often, the methods of game theory find application in international relations, economics, and somewhat less often in other social sciences — sociology, political science, psychology, ethics, jurisprudence, and others. Beginning in the 1970s, it was adopted by biologists to study animal behavior and the theory of evolution. It is of very great importance for artificial intelligence and cybernetics, especially with the emergence of interest in intelligent agents.
Optimal solutions or strategies in mathematical modeling were proposed as far back as the 18th century. Problems of production and pricing under conditions of oligopoly, which later became textbook examples of game theory, were considered in the 19th century by A. Cournot and J. Bertrand. At the beginning of the 20th century, Emanuel Lasker, Ernst Zermelo, and Émile Borel put forward the idea of a mathematical theory of a game-like conflict of interests.
The mathematical theory of games originates from neoclassical economics. The mathematical aspects and applications of the theory were first set out in the classic 1944 book by John von Neumann and Oskar Morgenstern, «Theory of Games and Economic Behavior[eng.]» (Eng. Theory of Games and Economic Behavior).
This area of mathematics has found some reflection in popular culture. In 1998, the American writer and journalist Sylvia Nasar published a book about the fate of John Forbes Nash, laureate of the Prize in Economic Sciences in Memory of Alfred Nobel and a scholar in the field of game theory; and in 2001 a film based on the book, «A Beautiful Mind», was made. Some American television shows, for example «Friend or Foe?», «Alias», or «NUMB3RS», periodically reference the theory in their episodes.
John Nash wrote his dissertation on game theory in 1949, and 45 years later he received the Nobel Prize in Economics. After graduating from the Carnegie Institute of Technology with two degrees — a bachelor's and a master's — Nash entered Princeton University, where he attended lectures by John von Neumann. In his works Nash developed the principles of «managerial dynamics». The first concepts of game theory analyzed antagonistic games, where there are losers and players who win at their expense. Nash developed methods of analysis in which all participants either win or suffer defeat. These situations came to be called «Nash equilibrium», or «non-cooperative equilibrium»; in such a situation the parties use an optimal strategy, which leads to the creation of a stable equilibrium. It is advantageous for the players to maintain this equilibrium, since any change would worsen their position. These works of Nash made a serious contribution to the development of game theory, and the mathematical tools of economic modeling were revised. Nash showed that the classical approach to competition of A. Smith, where everyone is for himself, is not always optimal. More advantageous are strategies in which each tries to do better for himself by doing better for others.
Although game theory originally considered economic models, up until the 1950s it remained a formal theory within the framework of mathematics. But already from the 1950s attempts began to apply the methods of game theory not only in economics, but in biology, cybernetics, engineering, and anthropology. During the Second World War and immediately after it, the military took a serious interest in game theory, seeing in it a powerful apparatus for studying strategic decisions.
In 1960—1970 interest in game theory waned, despite the significant mathematical results obtained by that time. From the mid-1980s the active practical use of game theory began, especially in economics and management. Over the last 20 — 30 years the significance of game theory and interest in it have grown considerably; some areas of modern economic theory cannot be set out without applying game theory.
Historically, the first games to fall within the sphere of mathematicians' interests were games with complete information, in which it is relatively simple to analyze the strategy of all participants. Then the attention of researchers was drawn to «games with incomplete information». After analyzing poker and the rest of the games of this class, mathematicians tried to apply the mathematical apparatus to games of «global scale» — wars, economics, and even ordinary divorces.
The mathematical theory of games is now developing rapidly; dynamic games are being considered. However, the mathematical apparatus of game theory is costly. It is applied to warranted problems: politics, the economics of monopolies and the distribution of market power, and so on. A number of well-known scholars became Nobel laureates in economics for their contribution to the development of game theory, which describes socioeconomic processes. J. Nash, thanks to his research in game theory, became one of the leading specialists in the field of waging the «Cold War», which confirms the scale of the problems that game theory addresses.
Laureates of the Prize in Economic Sciences in Memory of Alfred Nobel for achievements in the field of game theory and economic theory have been: Robert Aumann, Reinhard Selten, John Nash, John Harsanyi, William Vickrey, James Mirrlees, Thomas Schelling, George Akerlof, Michael Spence, Joseph Stiglitz, Leonid Hurwicz, Eric Maskin, Roger Myerson, Lloyd Shapley, Alvin Roth, Jean Tirole, Paul Milgrom, Robert Wilson.
Games are strictly defined mathematical objects. A game is formed by players, a set of strategies for each player, and a specification of the payoffs, or payments, of the players for each combination of strategies. Most cooperative games are described by a characteristic function, while for the remaining types the normal or extensive form is more often used. The characterizing features of a game as a mathematical model of a situation are:
The «Ultimatum» game in extensive form
Games in extensive form are represented in the form of a directed tree, where each vertex corresponds to a situation of a player choosing his strategy. Each player is assigned an entire level of vertices. The payoffs are written at the bottom of the tree, beneath each leaf vertex.
In the figure — a game for two players. Player 1 moves first and chooses strategy F or U. Player 2 analyzes his position and decides — whether to choose strategy A or R. Most likely, the first player will choose U, and the second — A (for each of them these are the optimal strategies); then they will receive 8 and 2 points respectively.
The extensive form is very illustrative; with its help it is especially convenient to represent games with more than two players and games with sequential moves. If, however, the participants make simultaneous moves, then the corresponding vertices are either connected by a dotted line or enclosed by a solid line.
| Player 2 strategy 1 |
Player 2 strategy 2 |
|
| Player 1 strategy 1 |
4, 3 | –1, –1 |
| Player 1 strategy 2 |
0, 0 | 3, 4 |
| Normal form for a game with 2 players, each of whom has 2 strategies. | ||
In the normal, or strategic, form the game is described by a payoff matrix. Each side (more precisely, dimension) of the matrix — is a player, the rows determine the strategies of the first player, and the columns — the second. At the intersection of two strategies one can see the payoffs that the players will receive. In the example on the right, if player 1 chooses the first strategy and the second player — the second strategy, then at the intersection we see (−1, −1), which means that as a result of the move both players lost one point each.
The players chose strategies with the maximum result for themselves, but lost because of not knowing the other player's move. Usually the normal form represents games in which the moves are made simultaneously, or at least it is assumed that all players do not know what the other participants are doing. Such games with incomplete information will be considered below.
In cooperative games with transferable utility, that is, with the possibility of transferring funds from one player to another, it is impossible to apply the concept of individual payments. Instead, the so-called characteristic function is used, which determines the payoff of each coalition of players. In doing so, it is assumed that the payoff of the empty coalition equals zero.
The foundations of such an approach can be found as far back as the book by von Neumann and Morgenstern. Studying the normal form for coalition games, they reasoned that if in a game with two sides a coalition C is formed, then the coalition N \ C opposes it. A game for two players is, as it were, formed. But since there are many variants of possible coalitions (namely 2N, where N — is the number of players), the payoff for C will be a certain characteristic quantity depending on the composition of the coalition. Formally a game in such a form (also called a TU-game) is represented by a pair (N, v), where N — is the set of all players, and v : 2N → R — is the characteristic function.
Such a form of representation can be applied to all games, including those without transferable utility. At present there exist ways to convert any game from normal form into characteristic form, but conversion in the reverse direction is not possible in all cases.
Game theory, as one of the approaches in applied mathematics, is used to study the behavior of humans and animals in various situations. Originally game theory began to develop within the framework of economic science, making it possible to understand and explain the behavior of economic agents in various situations. Later the scope of application of game theory was extended to other social sciences; at present game theory is used to explain the behavior of people in political science, sociology, and psychology. Game-theoretic analysis was first used to describe animal behavior by Ronald Fisher in the 1930s (although even Charles Darwin used ideas of game theory without formal justification). In Ronald Fisher's work the term «game theory» does not appear. Nevertheless, the work is essentially carried out along the lines of game-theoretic analysis. The developments made in economics were applied by John Maynard Smith in the book «Evolution and the Theory of Games». Game theory is used not only to predict and explain behavior; attempts have been made to use game theory to develop theories of ethical or reference behavior. Economists and philosophers have applied game theory to better understand good (worthy) behavior.
Originally game theory was used to describe and model the behavior of human populations. Some researchers believe that by determining the equilibrium in the corresponding games they can predict the behavior of human populations in a situation of real confrontation. Such an approach to game theory has lately been subjected to criticism for several reasons. First, the assumptions used in modeling are often violated in real life. Researchers may assume that players choose behaviors that maximize their total benefit (the model of economic man), yet in practice human behavior often does not correspond to this premise. There are many explanations of this phenomenon — irrationality, modeling of deliberation, and even various motives of the players (including altruism). The authors of game-theoretic models object to this, saying that their assumptions are analogous to similar assumptions in physics. Therefore, even if their assumptions are not always fulfilled, game theory can be used as a reasonable ideal model, by analogy with such models in physics. However, a new wave of criticism fell upon game theory when, as a result of experiments, it was revealed that people do not follow equilibrium strategies in practice. For example, in the games «Centipede», «Dictator» participants often do not use the strategy profile that constitutes a Nash equilibrium. Disputes continue about the significance of such experiments. According to another point of view, the Nash equilibrium is not a prediction of expected behavior; it merely explains why populations already at a Nash equilibrium remain in this state. However, the question of how these populations arrive at a Nash equilibrium remains open. Some researchers, in search of an answer to this question, switched to studying evolutionary game theory. Models of evolutionary game theory assume limited rationality or irrationality of the players. Despite the name, evolutionary game theory deals not only with questions of the natural selection of biological species. This branch of game theory studies models of biological and cultural evolution, as well as models of the learning process.
On the other hand, many researchers regard game theory not as a tool for predicting behavior, but as a tool for analyzing situations in order to identify the best behavior for a rational player. Since a Nash equilibrium includes strategies that are the best response to the behavior of the other player, using the concept of Nash equilibrium to choose behavior looks quite justified. However, such use of game-theoretic models has also been subjected to criticism. First, in some cases it is advantageous for a player to choose a strategy not belonging to the equilibrium, if he expects that the other players will also not follow equilibrium strategies. Second, the famous game «Prisoner's Dilemma» allows one to provide another counterexample. In the «Prisoner's Dilemma», following one's personal interests leads to both players ending up in a worse situation compared to the one in which they would have sacrificed their personal interests.
A game is called cooperative, or coalitional, if the players can unite into groups, taking on certain obligations to other players and coordinating their actions. In this it differs from non-cooperative games, in which each is obliged to play for himself. Recreational games are rarely cooperative, however such mechanisms are not uncommon in everyday life.
It is often assumed that cooperative games differ precisely in the possibility of the players communicating with one another. In the general case this is not true. There exist games where communication is permitted, but the players pursue personal goals, and vice versa.
Of the two types of games, non-cooperative ones describe situations in the finest details and yield more precise results. Cooperative ones consider the process of the game as a whole. Attempts to combine the two approaches have yielded considerable results. The so-called Nash program has already found solutions to some cooperative games as equilibrium situations of non-cooperative games.
Hybrid games include elements of cooperative and non-cooperative games. For example, the players may form groups, but the game will be conducted in a non-cooperative style. This means that each player will pursue the interests of his group, while at the same time trying to achieve personal benefit.
| A | B | |
| A | 1, 2 | 0, 0 |
| B | 0, 0 | 1, 2 |
| Asymmetric game | ||
A game will be symmetric when the corresponding strategies of the players are equal, that is, have identical payoffs. In other words, if the players can swap places and their payoffs for the same moves do not change. Many of the games studied for two players — are symmetric. In particular, the following are such: «Prisoner's Dilemma», «Stag Hunt», «Hawks and Doves». As examples of asymmetric games one can cite «Ultimatum» or «Dictator».
In the example on the right the game may at first glance seem symmetric because of the similar strategies, but this is not so — for the payoff of the second player under the strategy profiles (A, A) and (B, B) will be greater than that of the first.
| A | B | |
| A | −1, 1 | 3, −3 |
| B | 0, 0 | −2, 2 |
| Zero-sum game | ||
Zero-sum games — a special variety of constant-sum games, that is, ones where the players cannot increase or decrease the available resources, or the fund of the game. In this case the sum of all winnings equals the sum of all losses for any move. Look at the table — the numbers denote the payments to the players — and their sum in each cell equals zero. Examples of such games can be poker, where one wins all the bets of the others; reversi, where the opponent's pieces are captured; or banal theft.
Many games studied by mathematicians, including the already mentioned «Prisoner's Dilemma», are of a different kind: in non-zero-sum games the payoff of some player does not necessarily mean the loss of another, and vice versa. The outcome of such a game may be less than or greater than zero. Such games can be transformed to zero-sum — this is done by introducing a fictitious player who «appropriates to himself» the surplus or makes up the shortfall of funds. Thus, whether a game will be considered «zero»-sum or «non-zero»-sum — actually depends on its formalization.
Another game with a nonzero sum can be trade, where each participant derives benefit by exchanging a resource less needed by him for a more needed one (the possibility of benefit to both players arises because the same resource has different value for different players). A widely known example where it decreases is a full-scale industrial war (in the wars of the past the infrastructure and economy of the warring sides often suffered nowhere near as severely as in the industrial wars of the 20th century).
In parallel games the players move simultaneously, or, at the very least, they are not aware of the choices of others until everyone has made his move. In sequential, or dynamic, games the participants may make moves in a predetermined or random order, but in doing so they receive some information about the preceding actions of others. This information may even be not entirely complete; for example, a player may learn that his opponent, out of his ten strategies, definitely did not choose the fifth, learning nothing about the others.
The differences in the representation of parallel and sequential games were considered above. The former are usually represented in normal form, and the latter — in extensive form.
An important subset of sequential games is made up of games with perfect information. In such a game the participants know all the moves made up to the current moment, as well as the possible strategies of the opponents, which allows them to predict the subsequent development of the game. Examples of games with perfect information are checkers and chess. Perfect information is not available in parallel games, since in them the opponents' current moves are unknown. Often the concept of perfect information is confused with a similar one — complete information. For the latter, knowledge of only all the strategies available to the opponents is sufficient; knowledge of all their moves is not required. At the same time, many of the games studied in mathematics — are games with incomplete information, in which it is unknown exactly which strategy a player has chosen: «Prisoner's Dilemma» or «Matching Pennies». At the same time there are interesting examples of games in which, in the general case, the players have complete information: «Ultimatum», «Centipede».
Games in the real world or games studied in economics, as a rule, last a finite number of moves. Mathematics is not so limited, and, in particular, in set theory games are considered that are capable of continuing infinitely long. Moreover, the winner and his payoff are not determined until the completion of all moves.
The problem usually posed in this case consists not in finding an optimal solution, but in finding at least a winning strategy. Using the axiom of choice, it can be proved that sometimes even for games with complete information and two outcomes — «won» or «lost» — neither of the players has such a strategy. The existence of winning strategies for certain specially constructed games plays an important role in descriptive set theory.
Most of the games studied are discrete: in them there is a finite number of players, moves, events, outcomes, and so on. However, these constituents can be extended to the set of real numbers. Games including such elements are often called differential. They are associated with some real scale (usually — a time scale), although the events occurring in them may be discrete in nature. Differential games are also considered in optimization theory, and find their application in engineering and technology, and in physics.
These are games whose result is a set of rules for another game (called the target game or object game). The goal of metagames — is to increase the utility of the produced set of rules. The theory of metagames is connected with the theory of optimal mechanisms.
The study of sequential games with perfect information and comparatively complex sets of possible strategies is set apart into a separate area called combinatorial game theory (or the theory of combinatorial games). This theory operates with such tools as the Sprague—Grundy function. To a significant degree this area was shaped by John Conway, Elwyn Berlekamp, and Richard Guy in the books «On Numbers and Games» and «Winning Ways for your Mathematical Plays».
Comments