Lecture
Двое преступников, А и Б, попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (10 лет). Если оба молчат, их деяние проходит по более лёгкой статье, и они приговариваются к 6 месяцам. Если оба свидетельствуют против друг друга, они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдёт?
| Criminal B Silent strategy |
Criminal B Strategy "betray" |
|
|---|---|---|
| Criminal A Silent strategy |
Half a year to each | 10 years to criminal A Release the criminal B |
| Criminal A Strategy "betray" |
10 years to criminal B Release the criminal A |
2 years each |
In conclusion, it should be emphasized that game theory is a very complex area of knowledge. When referring to it, it is necessary to observe a certain caution and clearly know the limits of application. Too simple interpretations pose a hidden danger. Analysis and consultations based on game theory because of their complexity are recommended only for particularly important problem areas. Experience shows that the use of appropriate tools is preferable when making one-time, fundamentally important strategic planning decisions, including when preparing large cooperation agreements.
If the topic turns out to be interesting for the community, in the following articles I will try to reveal the types of games and their strategies in more detail.
The theory of games is a mathematical method for studying optimal strategies in games. A game is a process in which two or more parties take part in the struggle for the realization of their interests. Each side has its own goal and uses some strategy that can lead to winning or losing - depending on the behavior of other players. Game theory helps to choose the best strategies taking into account ideas about other participants, their resources and their possible actions. [one]
Game theory is a branch of applied mathematics, more precisely, operations research. Most often, the methods of game theory are used in economics, more rarely in other social sciences - sociology, political science, psychology, ethics, jurisprudence, and others. Since the 1970s, biologists have adopted it to study the behavior of animals and the theory of evolution. It is very important for artificial intelligence and cybernetics, especially with an interest in intellectual agents.
Optimal solutions or strategies in mathematical modeling were proposed as early as the 18th century. The tasks of production and pricing in the conditions of oligopoly, 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. E.Lasker, E.Termelo, E.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, the mathematical aspects and applications of the theory were presented in the classic 1944 book by John von Neumann and Oscar Morgenstern, Game Theory and Economic Behavior [2] ( Theory of Games and Economic Behavior ).
This area of mathematics has found some reflection in social culture. In 1998, American writer and journalist Sylvia Nazar published a book [3] about the fate of John Nash, a Nobel laureate in economics and a scientist in the field of game theory; and in 2001, based on the book, the film “Mind Games” was shot. Some American television shows, such as Friend or Foe, Alias, or NUMB3RS, periodically refer to theory in their episodes.
J. Nash in 1949, wrote his thesis on game theory, after 45 years he received the Nobel Prize in Economics. After graduating from the Carnegie Polytechnic Institute with a bachelor’s and master’s degree, J. Nash enrolled at Princeton University, where he attended the lectures of John von Neumann. In his writings, J. 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 develops analysis methods in which all participants either win or lose. These situations are called “Nash equilibrium,” or “noncooperative equilibrium,” in a situation the parties use the optimal strategy, which leads to the creation of a stable equilibrium. It is beneficial for players to maintain this balance, since any change will worsen their situation. These works of J. Nash made a significant contribution to the development of game theory, mathematical tools of economic modeling were revised. J. Nash shows that A.Smith’s classic approach to competition, when every man for himself, is not optimal. More optimal strategies when everyone tries to do better for themselves, doing better for others.
Although game theory initially considered economic models, it remained a formal theory within mathematics until the 1950s. But since the 1950s. Attempts are being made 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 was seriously interested in the theory of games, who saw in it a powerful apparatus for researching strategic decisions.
In 1960-1970 interest in game theory is fading away, despite significant mathematical results obtained by that time. Since the mid 1980s. begins active practical use of game theory, especially in economics and management. Over the past 20–30 years, the value of game theory and interest has increased significantly, some areas of modern economic theory cannot be expounded without the use of game theory.
A major contribution to the application of game theory was the work of Thomas Schelling, the Nobel Prize winner in economics in 2005, “The Strategy of Conflict”. T. Schelling considers various "strategies" of behavior of the parties to the conflict. These strategies coincide with the tactics of conflict management and the principles of conflict analysis in conflict management (this is a psychological discipline) and in the management of conflicts in an organization (management theory). In psychology and other sciences, the word "game" is used in other ways than in mathematics. Some psychologists and mathematicians are skeptical about the use of this term in other senses, which were formed earlier. The culturological concept of the game was given in Johan Huizing’s work “Homo Ludens” (articles on cultural history), the author talks about the use of games in justice, culture, ethics, that the game is older than man himself, as animals also play. The concept of the game is found in the concept of Eric Burne "Games that people play, people who play games." These are purely psychological games based on transactional analysis. The concept of a game in J. Hösing is different from the interpretation of the game in the theory of conflict and the mathematical theory of games. Games are also used for training in business cases, seminars of G. P. Schedrovitsky, the founder of the organizational activity approach. During Perestroika in the USSR, G. P. Shchedrovitsky held many games with Soviet managers. According to the psychological intensity, ODI (organizational activity games) were so strong that they served as a powerful catalyst for change in the USSR. Now in Russia, the whole movement of ODI has taken shape. Critics point out the artificial uniqueness of ODI. The basis of the ODI was the Moscow Methodological Circle (CMI).
The mathematical theory of games is now rapidly developing, dynamic games are considered. However, the mathematical apparatus of game theory is costly [4] . It is used for justified tasks: politics, the economy of monopolies and the distribution of market power, etc. A number of well-known scientists became Nobel laureates in economics for contributing to the development of game theory, which describes social and economic processes. J. Nash, thanks to his research in game theory, has become one of the leading experts in the field of cold war, which confirms the magnitude of the tasks involved in game theory.
Nobel laureates in economics for achievements in the field of game theory and economic theory are: Robert Aumann, Reinhard Zelten, John Nash, John Harsanyi, William Vickrey, James Mirrlis, Thomas Schelling, George Akerlof, Michael Spence, Joseph Stiglitz, Leonid Gurwitz, Eric Merskin , Roger Myerson, Lloyd Shapley, Alvin Roth.
Games are strictly defined mathematical objects. The game is formed by players, a set of strategies for each player and an indication of 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, the normal or extensive form is used more often. Characterizing the signs of the game as a mathematical model of the situation:
Games in the extensive or extended form [5] are represented in the form of an oriented tree, where each vertex corresponds to the player's choice of their strategy. Each player is assigned a whole level of vertices. Payments are recorded at the bottom of the tree, under each leaf top .
The picture on 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 - choose strategy A or R. Most likely the first player chooses 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 visual, with its help it is especially convenient to represent 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 dotted line, or outlined 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 the game with 2 players, each with 2 strategies. | ||
In normal or strategic form, the game is described by a payment matrix . [6] Each side (more precisely, the dimension) of the matrix is the player, the rows determine the strategies of the first player, and the columns define the second. At the intersection of the two strategies, you can see the winnings that players will receive. In the example to 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 as a result of the move both players lost one point each.
Players chose strategies with the maximum result for themselves, but lost, due to ignorance of another player's move. Usually, in normal form, games are presented in which moves are made simultaneously , or at least it is assumed that all players do not know what other participants are doing. Such games with incomplete information will be discussed below.
In cooperative games with transferable utility, that is, the possibility of transferring funds from one player to another, it is impossible to apply the concept of individual payments . Instead, a so-called characteristic function is used, which determines the winnings of each coalition of players. It is assumed that the winning empty coalition is zero.
The basis of 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 game with two sides, then the N \ C coalition stands against it. Formed as a game for two players. But since there are many variants of 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 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.
This form of presentation can be applied to all games, including without transferable utility. Currently, there are ways to translate any game from normal to characteristic form, but the conversion in the opposite direction is not possible in all cases.
Теория игр, как один из подходов в прикладной математике, применяется для изучения поведения человека и животных в различных ситуациях. Первоначально теория игр начала развиваться в рамках экономической науки, позволив понять и объяснить поведение экономических агентов в различных ситуациях. Позднее область применения теории игр была расширена на другие социальные науки; в настоящее время теория игр используется для объяснения поведения людей в политологии, социологии и психологии. Теоретико-игровой анализ был впервые использован для описания поведения животных Рональдом Фишером в 30-х годах XX века (хотя даже Чарльз Дарвин использовал идеи теории игр без формального обоснования). В работе Рональда Фишера не появляется термин «теория игр». Тем не менее, работа по существу выполнена в русле теоретико-игрового анализа. Разработки, сделанные в экономике, были применены Джоном Майнардом Смитом в книге «Эволюция и теория игр». Теория игр используется не только для предсказания и объяснения поведения; были предприняты попытки использовать теорию игр для разработки теорий этичного или эталонного поведения. Экономисты и философы применяли теорию игр для лучшего понимания хорошего (достойного) поведения. Вообще говоря, первые теоретико-игровые аргументы, объясняющие правильное поведения, высказывались ещё Платоном.
Первоначально теория игр использовалась для описания и моделирования поведения человеческих популяций. Некоторые исследователи считают, что с помощью определения равновесия в соответствующих играх они могут предсказать поведение человеческих популяций в ситуации реальной конфронтации. Такой подход к теории игр в последнее время подвергается критике по нескольким причинам. Во-первых, предположения, используемые при моделировании, зачастую нарушаются в реальной жизни. Исследователи могут предполагать, что игроки выбирают поведения, максимизирующее их суммарную выгоду (модель экономического человека), однако на практике человеческое поведение часто не соответствует этой предпосылке. Существует множество объяснений этого феномена — нерациональность, моделирование обсуждения, и даже различные мотивы игроков (включая альтруизм). Авторы теоретико-игровых моделей возражают на это, говоря, что их предположения аналогичны подобным предположениям в физике. Поэтому даже если их предположения не всегда выполняются, теория игр может использовать как разумная идеальная модель, по аналогии с такими же моделями в физике. Однако, на теорию игр обрушился новый вал критики, когда в результате экспериментов было выявлено, что люди не следуют равновесным стратегиям на практике. Например, в играх «Сороконожка», «Диктатор» участники часто не используют профиль стратегий, составляющий равновесие по Нэшу. Продолжаются споры о значении подобных экспериментов. Согласно другой точке зрения, равновесие по Нэшу не является предсказанием ожидаемого поведения, оно лишь объясняет, почему популяции, уже находящиеся в равновесии по Нэшу, остаются в этом состоянии. Однако вопрос о том, как эти популяции приходят к равновесию Нэша, остается открытым. Некоторые исследователи в поисках ответа на этот вопрос переключились на изучение эволюционной теории игр. Модели эволюционной теории игр предполагают ограниченную рациональность или нерациональность игроков. Несмотря на название, эволюционная теория игр занимается не только и не столько вопросами естественного отбора биологических видов. Этот раздел теории игр изучает модели биологической и культурной эволюции, а также модели процесса обучения.
С другой стороны, многие исследователи рассматривают теорию игр не как инструмент предсказания поведения, но как инструмент анализа ситуаций с целью выявления наилучшего поведения для рационального игрока. Поскольку равновесие Нэша включает стратегии, являющиеся наилучшим откликом на поведение другого игрока, использование концепции равновесия Нэша для выбора поведения выглядит вполне обоснованным. Однако, и такое использование теоретико-игровых моделей подверглось критике. Во-первых, в некоторых случаях игроку выгодно выбрать стратегию, не входящую в равновесие, если он ожидает, что другие игроки также не будут следовать равновесным стратегиям. Во-вторых, знаменитая игра «Дилемма заключенного» позволяет привести ещё один контрпример. В «Дилемме заключенного» следование личным интересам приводит к тому, что оба игрока оказываются в худшей ситуации в сравнении с той, в которой они пожертвовали бы личными интересами.
A game is called cooperative, or coalitional , if players can unite in groups, taking on some obligations to other players and coordinating their actions. This makes it different from non-cooperative games in which everyone is obliged to play for himself. Entertainment 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. In general, this is not true. There are games where communication is allowed, but players have personal goals, and vice versa.
Из двух типов игр, некооперативные описывают ситуации в мельчайших деталях и выдают более точные результаты. Кооперативные рассматривают процесс игры в целом. Попытки объединить два подхода дали немалые результаты. Так называемая программа Нэша уже нашла решения некоторых кооперативных игр как ситуации равновесия некооперативных игр.
Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды.
| BUT | B | |
| BUT | 1, 2 | 0, 0 |
| B | 0, 0 | 1, 2 |
| Несимметричная игра | ||
Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков — симметричные. В частности, таковыми являются: «Дилемма заключённого», «Охота на оленя», «Ястребы и голуби». [8] В качестве несимметричных игр можно привести «Ультиматум» или «Диктатор».
В примере справа игра на первый взгляд может показаться симметричной из-за похожих стратегий, но это не так — ведь выигрыш второго игрока при профилях стратегий (А, А) и (Б, Б) будет больше, чем у первого.
| BUT | B | |
| BUT | −1, 1 | 3, −3 |
| B | 0, 0 | −2, 2 |
| Игра с нулевой суммой | ||
Игры с нулевой суммой — особая разновидность игр с постоянной суммой , то есть таких, где игроки не могут увеличить или уменьшить имеющиеся ресурсы, или фонд игры. В этом случае сумма всех выигрышей равна сумме всех проигрышей при любом ходе. Посмотрите направо — числа означают платежи игрокам — и их сумма в каждой клетке равна нулю. Примерами таких игр может служить покер, где один выигрывает все ставки других; реверси, где захватываются фишки противника; либо банальное воровство .
Многие изучаемые математиками игры, в том числе уже упоминавшаяся «Дилемма заключённого», иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой сумме — это делается введением фиктивного игрока , который «присваивает себе» излишек или восполняет недостаток средств. [9]
Ещё игрой с отличной от нуля суммой является торговля , где каждый участник извлекает выгоду. Широко известным примером, где она уменьшается, является война .
В параллельных играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все не сделают свой ход. В последовательных, или динамических , играх участники могут делать ходы в заранее установленном либо случайном порядке, но при этом они получают некоторую информацию о предшествующих действиях других. Эта информация может быть даже не совсем полной , например, игрок может узнать, что его противник из десяти своих стратегий точно не выбрал пятую, ничего не узнав о других.
Различия в представлении параллельных и последовательных игр рассматривались выше. Первые обычно представляют в нормальной форме, а вторые — в экстенсивной.
Важное подмножество последовательных игр составляют игры с полной информацией. В такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Полная информация не доступна в параллельных играх, так как в них неизвестны текущие ходы противников. Большинство изучаемых в математике игр — с неполной информацией. Например, вся «соль» Дилеммы заключённого или Сравнения монеток заключается в их неполноте.
В то же время есть интересные примеры игр с полной информацией: «Ультиматум», «Многоножка». Сюда же относятся шахматы, шашки, го, манкала и другие.
Often the concept of complete information is confused with similar - perfect information . For the latter, it suffices only to know all the strategies available to opponents; knowledge of all their moves is optional.
Games in the real world or games studied in economics tend to last for a finite number of moves. Mathematics is not so limited, and in particular, in set theory, games are considered that can last indefinitely. And the winner and his winnings are not determined until the end of all moves.
Задача, которая обычно ставится в этом случае, состоит не в поиске оптимального решения, а в поиске хотя бы выигрышной стратегии . Используя аксиому выбора, можно доказать, что иногда даже для игр с полной информацией и двумя исходами — «выиграл» или «проиграл» — ни один из игроков не имеет такой стратегии. Существование выигрышных стратегий для некоторых особенным образом сконструированных игр имеет важную роль в дескриптивной теории множеств.
Большинство изучаемых игр дискретны : в них конечное число игроков, ходов, событий, исходов и т. п. Однако эти составляющие могут быть расширены на множество вещественных чисел. Игры, включающие такие элементы, часто называются дифференциальными. Они связаны с какой-то вещественной шкалой (обычно — шкалой времени), хотя происходящие в них события могут быть дискретными по природе. Дифференциальные игры также рассматриваются в теории оптимизации, находят своё применение в технике и технологиях, физике.
Это игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом ). Цель метаигр — увеличить полезность выдаваемого набора правил. Теория метаигр связана с теорией оптимальных механизмов ( англ. ).
Comments
To leave a comment
Mathematical methods of research operations. The theory of games and schedules.
Terms: Mathematical methods of research operations. The theory of games and schedules.