Game theory

Optimal solutions or strategies in mathematical modeling were proposed as early as the 18th century. The problems of production and pricing under oligopoly conditions, which later became textbook examples of game theory, were considered in the 19th century. A. Cournot and J. Bertrand . At the beginning of the XX century. Emanuel Lasker , Ernst Zermelo and Emil Borel put forward the idea of ​​a mathematical theory of conflict of interest.

The mathematical theory of games originates from neoclassical economics . For the first time, mathematical aspects and applications of the theory were presented in the classic book of 1944 by John von Neumann and Oscar Morgenstern "Game Theory and Economic Behavior" ^[2] ( eng. Theory of Games and Economic Behavior ).

This area of ​​mathematics has found some reflection in public culture. In 1998, Sylvia Nazar , an American writer and journalist, published a book ^[3] on the fate of John Forbes Nash , an economics prize winner in memory of Alfred Nobel and a game theory scientist; and in 2001, based on the book, the film " Mind Games " was shot. Some American television shows, such as Alias, or NUMB3RS, periodically refer to theory in their episodes.

John Nash wrote a dissertation in game theory in 1949; after 45 years he received the Nobel Prize in economics. After graduating from the Carnegie Polytechnic Institute with two diplomas - a bachelor and a master - Nash entered Princeton University , where he attended lectures by John von Neumann . In his writings, Nash developed the principles of "managerial dynamics." The first concepts of game theory were analyzed by antagonistic games , when there are losers and winners at their expense. Nash is developing analysis methods in which all participants either win or lose. These situations are called " Nash equilibrium ", or "non-cooperative equilibrium", in a situation the parties use the optimal strategy, which leads to the creation of a stable equilibrium. It is beneficial for the players to maintain this balance, since any change will worsen their situation. These works of Nash made a significant contribution to the development of game theory, and mathematical tools for economic modeling were revised. Nash shows that A. Smith’s classical approach to competition, when each for itself, is not optimal. Strategies are more beneficial when everyone is trying to do better for themselves, doing better for others.

Although game theory initially considered economic models, until the 1950s it remained a formal theory within the framework of mathematics. But since the 1950s. attempts are beginning to apply the methods of game theory not only in economics, but in biology, cybernetics , technology , and anthropology . During the Second World War and immediately after it, the military became seriously interested in the theory of games, who saw in it a powerful apparatus for studying strategic decisions.

In 1960-1970. interest in game theory is dying away, despite the significant mathematical results obtained by then. Since the mid-1980s begins the active practical use of game theory, especially in economics and management. Over the past 20 - 30 years, the importance of game theory and interest in it has grown significantly, some areas of modern economic theory cannot be stated without the application of game theory.

The mathematical theory of games is now booming, dynamic games are being considered. However, the mathematical apparatus of game theory is expensive ^[4] . It is used for justified tasks: politics, the economy of monopolies and the distribution of market power, etc. A number of famous scientists have become Nobel laureates in economics for their contribution to the development of game theory, which describes socio-economic processes. J. Nash, thanks to his research in game theory, has become one of the leading experts in the field of the Cold War , which confirms the magnitude of the tasks that game theory deals with.

The winners of the Economics Prize in memory of Alfred Nobel for achievements in the field of game theory and economic theory were: Robert Aumann , Reinhard Zelten , John Nash , John Harsanyi , William Wickrey , James Mirrlis , Thomas Schelling , George Akerlof , Michael Spence , Joseph Stiglitz , Leonid Hurwitz , Eric Maskin , Roger Myerson , Lloyd Shapley , Alvin Roth , Jean Tyrol .

Games are strictly defined mathematical objects. The game is formed by players, a set of strategies for each player and indicating winnings, or payments , players for each combination of strategies. Most cooperative games are described by a characteristic function, while for the rest of the species they usually use a normal or extensive form. Characteristic features of the game as a mathematical model of the situation:

1. the presence of several participants;
2. the uncertainty of participants' behavior associated with the presence of each of them several options for action;
3. the difference (mismatch) of the interests of the participants;
4. the interconnectedness of the participants' behavior, since the result obtained by each of them depends on the behavior of all participants;
5. the presence of rules of conduct known to all participants.

Expanded Form

Games in expanded form ^{[5] are} presented in the form of an oriented tree , where each vertex corresponds to a situation when a player chooses his own strategy. Each player is associated with a whole level of peaks. Payments are recorded at the bottom of the tree, under each leaf top .

In the picture to the left is a game for two players. Player 1 goes 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 one will choose A (for each of them these are optimal strategies ); then they will receive 8 and 2 points, respectively.

The expanded form is very visual, with its help it is especially convenient to present games with more than two players and games with consecutive moves. If the participants make simultaneous moves, then the corresponding vertices are either connected by a dashed line or circled by a solid line.

Normal form

In a normal, or strategic, form, a game is described by a payment matrix . ^[6] Each side (more precisely, the dimension) of the matrix is ​​a player, the rows determine the strategies of the first player, and the columns determine the strategies of the second. At the intersection of the two strategies, you can see the winnings that the players will receive. In the example on the right, if player 1 chooses the first strategy, and the second player chooses the second strategy, then we see (−1, −1) at the intersection, which means that both players lost one point as a result of the move.

Players chose strategies with the maximum result for themselves, but lost due to ignorance of another player’s move. Usually in a normal form, games are presented in which moves are made simultaneously , or at least it is assumed that all players are not aware of what other participants are doing. Such games with incomplete information will be discussed below.

Characteristic Function

In cooperative games with transferable utility , that is, the ability to transfer funds from one player to another, it is impossible to apply the concept of individual payments . Instead, they use the so-called characteristic function, which determines the payoff of each coalition of players. Moreover, it is assumed that the gain of the empty coalition is zero.

The grounds for this approach can be found in the book of von Neumann and Morgenstern. Studying the normal form for coalition games, they reasoned that if a coalition C is formed in a two-sided game, then the N \ C coalition is opposed to it. A kind of game for two players is formed. But since there are a lot of options for possible coalitions (namely 2 ^N , where N is the number of players), the gain for C will be some characteristic value , depending on the composition of the coalition. Formally, a game in this form (also called a TU-game ^[7] ) is represented by a pair (N, v) , where N is the set of all players, and v: 2 ^N → R is a characteristic function.

A similar form of presentation can be applied to all games, including those without transferable utility. Currently, there are ways to transfer any game from a normal form to a characteristic one, but conversion in the opposite 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. Initially, the theory of games began to develop within the framework of economic science, allowing us to understand and explain the behavior of economic agents in various situations. Later, the scope of game theory was expanded to other social sciences; game theory is currently used to explain people's behavior in political science, sociology, and psychology. Game-theoretic analysis was first used to describe the behavior of animals by Ronald Fisher in the 30s of the XX century (although even Charles Darwin used the ideas of game theory without formal substantiation). In the work of Ronald Fisher does not appear the term "game theory". However, the work is essentially done in line with game-theoretic analysis. Developments made in economics were applied by John Maynard Smith in the book Evolution and Game Theory. Game theory is not only used 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 (decent) behavior.

Description and Modeling

Initially, 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. This approach to game theory has recently been criticized 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 (economic person model), but in practice human behavior often does not meet this premise. There are many explanations for this phenomenon - irrationality, modeling discussions, and even various motives of players (including altruism). The authors of game-theoretic models object to this, saying that their assumptions are similar 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 the same models in physics. However, a new wave of criticism fell upon the theory of games 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 makes up the 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 only explains why populations already in Nash equilibrium remain in this state. However, the question of how these populations come to Nash equilibrium remains open. Some researchers, in search of an answer to this question, switched to studying the evolutionary theory of games. Models of evolutionary game theory suggest limited rationality or irrationality of players. Despite its name, the evolutionary theory of games deals not so much with issues of natural selection of biological species. This section of game theory studies models of biological and cultural evolution, as well as learning process models.

Regulatory analysis (identifying best behavior)

On the other hand, many researchers view 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 the Nash equilibrium includes strategies that are the best response to the behavior of another player, the use of the concept of Nash equilibrium to choose a behavior seems reasonable. However, this use of game-theoretic models has been criticized. First, in some cases, it is beneficial for a player to choose a strategy that is not in equilibrium if he expects other players to not follow equilibrium strategies as well. Secondly, the famous game “ Prisoner 's Dilemma ” allows us to give one more counterexample. In the Prisoner 's Dilemma, pursuing personal interests leads both players to find themselves in a worse situation than those in which they would sacrifice personal interests.

Cooperative and non-cooperative

A game is called cooperative, or coalition , if players can join in groups, taking on some obligations to other players and coordinating their actions. In this, it differs from non-cooperative games in which everyone is obliged to play for themselves. Entertaining games are rarely cooperative, but such mechanisms are not uncommon in everyday life.

It is often assumed that cooperative games differ precisely in the ability of players to communicate with each other. This is generally not true. There are games where communication is allowed, but players pursue personal goals, and vice versa.

Of the two types of games, non-cooperative ones describe situations in great detail and produce more accurate results. Cooperatives consider the game process 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 a situation of equilibrium of non-cooperative games.

Hybrid games include elements of cooperative and non-cooperative games. For example, players can form groups, but the game will be played 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 gain.

Symmetric and Unbalanced

The game will be symmetric when the respective strategies of the players are equal, that is, have the same payments. In other words, if the players can switch places and at the same time their winnings for the same moves will not change. Many of the studied games for two players are symmetrical. In particular, these are: “ Prisoner 's Dilemma ”, “ Deer Hunting ”, “ Hawks and Pigeons ”. ^[8] As an asymmetric game, you can cite the Ultimatum or the Dictator .

In the example on the right, the game at first glance may seem symmetrical due to similar strategies, but this is not so - after all, the gain of the second player with the profiles of strategies (A, A) and (B, B) will be greater than that of the first.

With a zero sum and a non-zero sum

Zero-sum games are a special kind of games with a constant sum , that is, those where players cannot increase or decrease the available resources, or the fund of the game. In this case, the sum of all wins is equal to the sum of all losses in any move. Look to the right - numbers mean payments to players - and their sum in each cell is zero. Examples of such games are poker , where one wins all the bets of others; reverse , where enemy chips are captured; or commonplace theft .

Many games studied by mathematicians, including the already mentioned Prisoner's Dilemma, are of a different kind: in games with a nonzero sum, winning a player does not necessarily mean losing another player, and vice versa. The outcome of such a game may be less or more than zero. Such games can be converted to a zero amount - this is done by introducing a fictitious player who "appropriates" the surplus or makes up for the lack of funds. ^[9]

Another game with a non-zero amount is trading , where each participant benefits. A widely known example of where it decreases is war .

Parallel and Serial

In parallel games, players walk at the same time, or at least they are not aware of the choice of others until everyone makes their move. In sequential or dynamic games, participants can make moves in a predetermined or random order, but at the same time they receive some information about the previous actions of others. This information may not even be completely complete , for example, a player can find out that his opponent from his ten strategies did not choose the fifth one without learning anything about the others.

Differences in the presentation of parallel and sequential games were discussed above. The former are usually presented in normal form, and the latter in extensive form.

With complete or incomplete information

An important subset of consecutive games are games with full information. In such a game, participants know all the moves made up to the current moment, as well as the possible strategies of opponents, which allows them to some extent predict the subsequent development of the game. Full information is not available in parallel games, since the current moves of opponents are unknown in them. Most of the games studied in mathematics are with incomplete information. For example, all the “salt” of the Prisoner’s Dilemma or Coin Comparison is their incompleteness.

At the same time, there are interesting examples of games with full information: Ultimatum, Millipede . This also includes chess, checkers, go, mancala and others.

Often the concept of complete information is confused with similar - perfect information . For the latter, knowledge of all the strategies available to opponents is sufficient; knowledge of all their moves is optional.

Endless Step Games

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, set theory considers games that can go on forever . Moreover, the winner and his winnings are not determined until the end of all moves.

The task that is usually posed in this case is not to find the optimal solution, but to find at least a winning strategy . Используя аксиому выбора , можно доказать, что иногда даже для игр с полной информацией и двумя исходами — «выиграл» или «проиграл» — ни один из игроков не имеет такой стратегии. Существование выигрышных стратегий для некоторых особенным образом сконструированных игр имеет важную роль в дескриптивной теории множеств .

Дискретные и непрерывные игры

Большинство изучаемых игр дискретны : в них конечное число игроков, ходов, событий, исходов и т. п. Однако эти составляющие могут быть расширены на множество вещественных чисел . Игры, включающие такие элементы, часто называются дифференциальными. Они связаны с какой-то вещественной шкалой (обычно — шкалой времени), хотя происходящие в них события могут быть дискретными по природе. Дифференциальные игры также рассматриваются в теории оптимизации , находят своё применение в технике и технологиях , физике .

Метаигры

Это игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом ). Цель метаигр — увеличить полезность выдаваемого набора правил. Теория метаигр связана с теорией оптимальных механизмов .

Изучение последовательных игр с совершенной информацией и сравнительно сложными наборами возможных стратегий выделяют в отдельную область, называемую комбинаторной теорией игр (или теорией комбинаторных игр). Эта теория оперирует такими инструментами, как функция Шпрага — Гранди . В значительной степени эту область сформировали Джон Конвей с соавторами в книгах «On Numbers and Games» и «Winning Ways for your Mathematical Plays».

• Нейман Дж. фон , Моргенштерн О. Теория игр и экономическое поведение . — М.: Наука , 1970 ( англ. Theory of Games and Economic Behaviour , 1944).
• Петросян Л. А. Зенкевич Н.А., Семина Е.А. Теория игр: Учеб. пособие для ун-тов. — М. : Высш. шк., Книжный дом «Университет», 1998. — С. 304. — ISBN 5-06-001005-8 , 5-8013-0007-4.
• Мазалов В.В. Математическая теория игр и приложения. — Санкт-Петербург - Москва - Краснодар: Лань, 2010. — 446 с. — ISBN 978-5-8114-1025-5 .
• Позиционные игры / ред. Воробьев Н.Н. , Врублевская И. Н.. — Москва: Наука, 1967. — 522 с.