theory of games
Also found in: Dictionary, Thesaurus, Medical, Financial, Wikipedia.
games, theory of,group of mathematical theories first developed by John Von NeumannVon Neumann, John
, 1903–57, American mathematician, b. Hungary, Ph.D. Univ. of Budapest, 1926. He came to the United States in 1930 and was naturalized in 1937. He taught (1930–33) at Princeton and after 1933 was associated with the Institute for Advanced Study.
..... Click the link for more information. and Oskar Morgenstern. A game consists of a set of rules governing a competitive situation in which from two to n individuals or groups of individuals choose strategies designed to maximize their own winnings or to minimize their opponent's winnings; the rules specify the possible actions for each player, the amount of information received by each as play progresses, and the amounts won or lost in various situations. Von Neumann and Morgenstern restricted their attention to zero-sum games, that is, to games in which no player can gain except at another's expense.
This restriction was overcome by the work of John F. NashNash, John Forbes, Jr.,
1928–2015, American mathematician, b. Bluefield, W.Va., grad. Carnegie Institute of Technology (now Carnegie-Mellon Univ., B.A. and M.A. 1948), Ph.D. Princeton 1950.
..... Click the link for more information. during the early 1950s. Nash mathematically clarified the distinction between cooperative and noncooperative games. In noncooperative games, unlike cooperative ones, no outside authority assures that players stick to the same predetermined rules, and binding agreements are not feasible. Further, he recognized that in noncooperative games there exist sets of optimal strategies (so-called Nash equilibria) used by the players in a game such that no player can benefit by unilaterally changing his or her strategy if the strategies of the other players remain unchanged. Because noncooperative games are common in the real world, the discovery revolutionized game theory. Nash also recognized that such an equilibrium solution would also be optimal in cooperative games. He suggested approaching the study of cooperative games via their reduction to noncooperative form and proposed a methodology, called the Nash program, for doing so. Nash also introduced the concept of bargaining, in which two or more players collude to produce a situation where failure to collude would make each of them worse off.
The theory of games applies statistical logic to the choice of strategies. It is applicable to many fields, including military problems and economics. The Nobel Memorial Prize in Economic Sciences was awarded to Nash, John Harsanyi, and Reinhard Selten (1994), to Robert J. Aumann and Thomas C. Schelling (2005), and to Lloyd Shapley and Alvin Roth (2012) for work in applying game theory to aspects of economics.
See J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (3d ed. 1953); D. Fudenberg and J. Tirole, Game Theory (1994); M. D. Davis, Game Theory: A Nontechnical Introduction (1997); R. B. Myerson, Game Theory: Analysis of Conflict (1997); J. F. Nash, Jr., Essays on Game Theory (1997); A. Rapoport, Two-Person Game Theory (1999).
theory of gamesmathematical accounts of the hypothetical decision-making behaviour of two or more persons in situations where:
- each has a finite choice between two or more courses of action ('strategies’);
- the interests of each may be partly or wholly in conflict;
- and for each person, numerical values can be attached to the ‘utility’ of every combination of outcomes. Developed especially by Von Neumann (see Von Neumann and Morgenstern (1944)), the theory of games builds on more conventional forms of rational modelling in ECONOMICS.Various real-world situations (e.g. the arms race, military alliances) possess at least some of the properties that allow them to be analysed in such terms. However, although it has had some influence on the way in which STRATEGIC INTERACTION is discussed in sociology (see also RATIONAL CHOICE THEORY, EXPLOITATION), the abstract mathematical theory of games makes assumptions, about the measurement of social utilities and the availability of information to actors, which in the social sciences are only infrequently justified. See also PRISONERS’ DILEMMA, ZERO-SUM GAME, RATIONALITY, FREE RIDER.
Games, Theory of
a branch of mathematics that studies formal models of optimal decision-making in conflict situations. Conflict here means an event in which different parties take part having different interests and opportunities to select actions available to them in accordance with these interests. Individual mathematical problems involving conflicts have been examined by many scientists since the 17th century. A systematic mathematical theory of games was worked out in detail by the American scientists J. von Neumann and O. Morgenstern (1944) to provide a mathematical approach to the phenomena of economic competition. In the course of its development the theory outgrew this framework and became a general mathematical theory of conflicts. In principle, military and legal conflicts, sports events, “parlor” games, and events connected with the biological struggle for existence are capable of mathematical description within the framework of the theory of games.
In situations of conflict the opponent’s desire to conceal his forthcoming actions gives rise to uncertainty. On the other hand, uncertainty during decision-making (for example, on the basis of insufficient data) may be interpreted as a conflict of the decision-making individual with nature. Therefore, the theory of games is also considered as the theory of optimal decision-making in the face of uncertainty. It makes it possible to mathematicize some important aspects of decision-making in technology, agriculture, medicine, and sociology. An approach from the viewpoint of game theory to the problems of management, planning, and forecasting is promising.
Basic to the theory of games is the concept of a game, which is a formalized conception of conflict. An adequate description of conflict in the form of a game, therefore, consists in an indication of who takes part in the conflict and how, what outcomes of the conflict are possible, and who is interested in these outcomes and in what manner. The parties to the conflict are called coalitions of action, the actions available to them are called their strategies, the possible outcomes of the conflict are called situations (usually each situation is construed as the result of the selection of some individual strategy by each of the coalitions of action), and the parties interested in the outcomes of a conflict are called the coalitions of interests. Their interests are described by the preferences for various situations (these preferences are often expressed in terms of numerical payoffs). The concrete realization of the enumerated objects and of the relations among them gives rise to various particular classes of games.
If there is a single coalition of action in a game, then this coalition’s strategies may be identified with the situations and the strategies no longer need be mentioned. Such games are called nonstrategic games. The class of nonstrategic games is extremely broad. Among them, in particular, are cooperative games.
A simple game consisting of the following may serve as an example of a nonstrategic (cooperative) game. All possible distributions (divisions) among the players of some quantity of homogeneous utility (such as money) in the game are the set of situations. Each division is described by those sums that the individual players obtain in the process. A coalition of interests is said to be winning if, in the face of opposition from all other players, it is able to acquire and divide among its own members all existing utility. All coalitions that are not winning cannot acquire any share of the utility. Such coalitions are said to be losing coalitions. It is natural to assume that a winning coalition prefers one division over another if the share of each of its members is greater in the first than in the second. Losing coali-’ tions cannot compare divisions in terms of preference (this condition is also quite natural: a coalition of interests that is not in a position to achieve anything itself must agree to any division and lacks the opportunity to choose among divisions).
If there is more than one coalition of action in a game, then the game is called a game of strategy. Noncooperative games, in which the coalitions of action coincide with the coalitions of interests (they are called players) and the preferences for the players are described by their payoff functions, constitute an important class of games of strategy: a player prefers one situation to another if in the former situation he receives a greater payoff than in the latter.
The following variant of morra may serve as one of the simplest examples of a noncooperative game. Three players simultaneously show one or two fingers each. If all three players show the same number, then the payoff of each is equal to zero. Otherwise, one of the players shows a (= 1 or 2) and receives b from some source (for example, from the bank formed by the antes), while the other two players who show the same number b (≠ a) receive nothing.
If two players are participating in a noncooperative game and the values of their payoff functions in any situation differ only in sign, then the game is called a zero-sum game; here, the payoff of one of the players is equal precisely to the loss of the other. If the sets of strategies of both players are finite in a zero-sum game, then the game is called a matrix game in view of some specific possibility of describing it.
Chess is another example of a noncooperative game. Two players (white and black) take part in the game. The strategy of each player is any conceivable rule (which in practice may not be susceptible to a detailed description) for selecting in each possible position some move allowed by the movements of the pieces. Two such rules (for the white and for the black) make up a situation that completely defines the progression of the chess game, including its outcome. The payoff function for white has the value 1 in won games, 0 in draws, and— 1 in lost games (this method of counting points is virtually the same as that used in tournament practice). The payoff function for black differs from the payoff function for white only in sign. From this it can be seen that chess is simultaneously a zero-sum game and a matrix game. In chess, the strategies are not selected by the players before the start of the game but are realized gradually, move by move. This means that chess belongs to the category of position games.
The theory of games is a normative theory, that is, the subject of its study is not so much the very models of conflicts (games) per se as (1) the content of the principles of optimality used in the games, (2) the existence of situations in which these principles of optimality are realized (such situations or sets of situations are called decisions in the sense of the corresponding principle of optimality), and (3) the methods of finding sueh situations.
The objects examined in game theory—games—are extremely diverse, and as yet it has not been possible to establish principles of optimality common to all classes of games. In practice this means that no single interpretation of the concept of optimality that applies to all games has been worked out. Therefore, before discussing the most advantageous behavior for a player in a game, for example, it must be established in what sense this advantageousness is construed. All principles of optimality used in the theory of games, for all their outward diversity, directly or indirectly reflect the idea of the stability of situations or the sets of situations that constitute solutions. In noncooperative games, the principle of the possibility of attaining the goal, which leads to equilibrium situations, is considered to be the main principle of optimality. These situations are characterized by the property that any player who deviates from an equilibrium situation (on the condition that the other players do not change their strategies) will not thus increase his own payoff.
In the particular case of zero-sum games, the principle of the possibility of attaining the goal is converted into the so-called principle of the maximin (which reflects the desire to maximize the minimum payoff).
The principles of optimality (which were initially selected intuitively) are derived on the basis of some preset properties that have the character of axioms. It is significant that different principles of optimality used in game theory may contradict each other.
In game theory, existence theorems are proved primarily by the same nonconstructive means as in other branches of mathematics: by means of fixed-point theorems, by the selection of a convergent subsequence from an infinite sequence, and so on or, in contrast, in extremely narrow cases, through intuitive identification of the form of the solution and the subsequent determination of the solution in this form.
The actual solution of some classes of zero-sum games reduces to the solution of differential and integral equations, while the solution of matrix games reduces to the solution of the standard problem of linear programming. Approximate and numerical methods of solving games are being worked out. So-called mixed strategies, that is, strategies selected at random (for example, by drawing lots), prove to be optimal for many games.
The theory of games, created for the mathematical solution of problems of economic and social origin, cannot be reduced on the whole to classical mathematical theories, which were devised to solve physical and technical problems. However, in various specific problems of game theory extremely broad use is made of various classical mathematical methods. Moreover, game theory is intrinsically connected with a number of mathematical disciplines. The concepts of probability theory are of necessity systematically used in game theory. Most problems of mathematical statistics can be formulated in the language of game theory. The necessity of the quantitative consideration of uncertainty in the analysis of a game predetermines the importance of the theory of games and thus its relation to information theory and, through it, with cybernetics. Moreover, game theory, as a theory of decision-making, may be considered as an essential component of the mathematical apparatus of operations research.
The theory of games is used in economics, technology, the military, and even anthropology. The principal difficulties of the practical application of game theory are connected with the economic and social nature of the phenomena that it models and with the inadequate ability to construct such models at a quantitative level.
By the 1970’s the number of publications on scientific problems of the theory of games had reached the hundreds (including several dozen monographs). Courses on game theory are taught at many higher educational institutions for students specializing in mathematics and economics (this has been done since 1956 in the USSR).
International conferences on the theory of games have been held in Princeton (1961), Jerusalem (1965), Vienna (1967), and Berkeley (1970). In the USSR, All-Union conferences have been held in Yerevan (1968) and Vilnius (1971).
REFERENCESNeumann, J. von, and O. Morgenstern. Teoriia igr i ekonomicheskoe povedenie. Moscow, 1970. (Translated from English.)
Luce, R., and Raiffa, H. Igry i resheniia. Moscow, 1961. (Translated from English.)
Karlin, S. Matematicheskie melody v teorii igr, programmirovanii i ekonomike. Moscow, 1964. (Translated from English.)
Vorob’ev, N. N. “Sovremennoe sostoianie teorii igr.” Uspekhi matemati-cheskikh nauk, 1970, VOL. 25, NO. 2 (152), PP. 80–140.
Owen, G. Teoriia igr. Moscow, 1971. (Translated from English.)
Contributions to the Theory of Games, vols. 1–4. Princeton, N. J., 1950–59.
Advances in Game Theory. Princeton, 1964.
N. N. VOROB’EV