Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Концепция теории игр
Game theory concept
В теории игр, байесовская игра – это модель стратегического принятия решений, которая предполагает наличие у игроков неполной информации. Игроки обладают частной информацией, релевантной для игры, что означает, что выигрыши не являются общеизвестными. Бейесовские игры моделируют исход взаимодействия игроков, используя принципы байесовской вероятности. Они важны тем, что впервые в теории игр позволили определить решения для игр с неполной информацией. Венгерский экономист Джон К. Харсаньи представил концепцию байесовских игр в трех статьях, опубликованных в 1967 и 1968 годах: в 1994 году он был удостоен Нобелевской премии по экономическим наукам за эти и другие вклады в теорию игр. Если говорить упрощенно, Харсаньи определил байесовские игры следующим образом: в начале игры природа случайным образом наделяет игроков набором характеристик. Сопоставляя этим характеристикам распределения вероятностей и вычисляя исход игры с использованием байесовской вероятности, получается игра, решение которой, по техническим причинам, гораздо легче вычислить, чем решение аналогичной игры в небайесовском контексте. Подробности этих технических причин можно найти в разделе "Спецификация игр" данной статьи.
In game theory, a Bayesian game is a strategic decision making model which assumes players have incomplete information. Players hold private information relevant to the game, meaning that the payoffs are not common knowledge. Bayesian games model the outcome of player interactions using aspects of Bayesian probability. They are notable because they allowed, for the first time in game theory, for the specification of the solutions to games with incomplete information. Hungarian economist John C. Harsanyi introduced the concept of Bayesian games in three papers from 1967 and 1968: He was awarded the Nobel Memorial Prize in Economic Sciences for these and other contributions to game theory in 1994. Roughly speaking, Harsanyi defined Bayesian games in the following way: players are assigned by nature at the start of the game a set of characteristics. By mapping probability distributions to these characteristics and by calculating the outcome of the game using Bayesian probability, the result is a game whose solution is, for technical reasons, far easier to calculate than a similar game in a non Bayesian context. For those technical reasons, see the Specification of games section in this article.
Чистые стратегии
В стратегической игре чистая стратегия — это выбор игроком действия в каждой точке принятия решения.
In a strategic game, a pure strategy is a player's choice of action at each point where the player must make a decision.
Три этапа
В байесовских играх выделяют три этапа, каждый из которых описывает объем информации игроков о типах участников. Этап *ex ante*. Игроки не знают свои типы и типы других игроков. Игрок рассматривает выигрыши как математическое ожидание, основанное на априорном распределении вероятностей всех возможных типов. Этап *interim*. Игроки знают свой тип, но лишь вероятностное распределение типов других игроков. При оценке выигрышей игрок учитывает ожидаемое значение типа другого игрока. Этап *ex post*. Игроки знают свои типы и типы других игроков. Выигрыши известны всем игрокам.
There are three stages of Bayesian games, each describing the players' knowledge of types within the game. Ex ante stage game. Players do not know their own types or those of other players. A player recognises payoffs as expected values based on a prior distribution of all possible types. Interim stage game. Players know their own type, but only a probability distribution of other players. A player studies the expected value of the other player's type when considering payoffs. Ex post stage game. Players know their own types and those of other players. The payoffs are known to players.
Улучшения по сравнению с небайсианскими играми
Есть два важных и новых аспекта байесовских игр, которые сам Харсаньи и сформулировал. Первый заключается в том, что байесовские игры следует рассматривать и структурировать так же, как игры с полной информацией. Однако, при добавлении вероятностей, игра функционирует как игра с неполной информацией. Таким образом, игроков можно моделировать как обладающих неполной информацией, при этом пространство вероятностей игры по-прежнему подчиняется закону полной вероятности. Бейесовские игры также полезны тем, что избавляют от необходимости в бесконечных последовательных вычислениях. Такие вычисления возникают, когда игроки (по сути) пытаются предугадать мысли друг друга. Например, можно рассуждать так: "Если я ожидаю от игрока Б какого-то действия, то игрок Б предвидит, что я ожидаю этого действия, а значит, я должен предвидеть его предвидение" и так до бесконечности. Бейесовские игры позволяют вычислить эти исходы за один шаг, одновременно присваивая различные вероятностные веса разным результатам. В результате байесовские игры позволяют моделировать множество игр, вычисление которых в небайесовском контексте было бы нерациональным.
There are two important and novel aspects to Bayesian games that were themselves specified by Harsanyi. The first is that Bayesian games should be considered and structured identically to complete information games. Except, by attaching probability to the game, the final game functions as though it were an incomplete information game. Therefore, players can be essentially modelled as having incomplete information and the probability space of the game still follows the law of total probability. Bayesian games are also useful in that they do not require infinite sequential calculations. Infinite sequential calculations would arise where players (essentially) try to "get into each other's heads". For example, one may ask questions and decide "If I expect some action from player B, then player B will anticipate that I expect that action, so then I should anticipate that anticipation" ad infinitum. Bayesian games allows for the calculation of these outcomes in one move by simultaneously assigning different probability weights to different outcomes. The effect of this is that Bayesian games allow for the modeling of a number of games that in a non Bayesian setting would be irrational to compute.
Баезианское равновесие Нэша
Баезианское равновесие Нэша в байесовской игре является равновесием Нэша в соответствующей игре нормальной формы ex ante. В небайесовской игре профиль стратегий является равновесием Нэша, если каждая стратегия в этом профиле является наилучшим ответом на каждую другую стратегию в профиле; то есть, не существует стратегии, которую игрок мог бы выбрать, чтобы получить более высокую выплату, учитывая стратегии, выбранные другими игроками. Аналогичная концепция может быть определена для байесовской игры, при этом стратегия каждого игрока максимизирует его ожидаемую выплату, учитывая его убеждения относительно состояния природы. Убеждения игрока относительно состояния природы формируются путем обуславливания априорных вероятностей типом игрока в соответствии с правилом Байеса. Баезианское равновесие Нэша (BNE) определяется как профиль стратегий, максимизирующий ожидаемую выплату для каждого игрока, учитывая его убеждения и стратегии, выбранные другими игроками. То есть, профиль стратегий является байезианским равновесием Нэша тогда и только тогда, когда для каждого игрока, при фиксированных стратегиях всех остальных игроков, его стратегия максимизирует его ожидаемую выплату в соответствии с его убеждениями. Это расширяет число игроков от до , то есть каждый тип каждого игрока становится отдельным игроком. Вторая форма называется индуцированной нормальной формой (см. Раздел 6.3.3 в книге «Многоагентные системы»), которая по-прежнему имеет игроков, но расширяет число действий каждого игрока i от до , то есть чистая стратегия представляет собой комбинацию действий, которые игрок должен предпринять для различных типов. Равновесие Нэша (NE) может быть вычислено в этих двух эквивалентных представлениях, и BNE может быть получено из NE. Рассмотрим двух игроков с целевой функцией, представляющей собой игру с нулевой суммой. Для вычисления BNE можно построить линейную программу.
A Bayesian Nash Equilibrium of a Bayesian game is a Nash equilibrium of its associated ex ante normal form game. In a non Bayesian game, a strategy profile is a Nash equilibrium if every strategy in that profile is a best response to every other strategy in the profile; i. e., there is no strategy that a player could play that would yield a higher payoff, given all the strategies played by the other players. An analogous concept can be defined for a Bayesian game, the difference being that every player's strategy maximizes their expected payoff given their beliefs about the state of nature. A player's beliefs about the state of nature are formed by conditioning the prior probabilities on the player's own type according to Bayes' rule. A Bayesian Nash equilibrium (BNE) is defined as a strategy profile that maximizes the expected payoff for each player given their beliefs and given the strategies played by the other players. That is, a strategy profile is a Bayesian Nash equilibrium if and only if for every player keeping the strategies of every other player fixed, strategy maximizes the expected payoff of player according to that player's beliefs.) which expands the number of players from to , i. e., every type of each player becomes a player. The second is called the induced normal form (see Section 6.3.3 of Multiagent Systems) which still has players yet expands the number of each player i's actions from to , i. e., the pure policy is a combination of actions the player should take for different types. Nash Equilibrium (NE) can be computed in these two equivalent representations, and the BNE can be recovered from the NE. Consider two players with a zero sum objective function. A linear program can be formed to compute BNE.
Вступить на монополизированный рынок
Новая компания (игрок 1), стремящаяся выйти на рынок, монополизированный крупной компанией, столкнется с двумя типами монополистов (игрок 2): тип 1 – препятствующий, тип 2 – допускающий. У игрока 1 никогда не будет полной информации об игроке 2, но он может оценить вероятность появления типа 1 и типа 2, исходя из того, была ли заблокирована предыдущая компания, пытавшаяся выйти на рынок. Это – байесовская игра. Основанием для таких оценок является то, что у игрока 2 существуют издержки на блокировку, которые могут потребовать значительного снижения цен, чтобы не допустить выхода на рынок игрока 1. Поэтому игрок 2 будет блокировать игрока 1, когда прибыль, которую он потеряет из-за выхода игрока 1 на рынок, превысит издержки на блокировку.
A new company (player1) that wants to enter a market that is monopolised by a large company will encounter two types of monopolist (player2), type1 is prevented and type2 is allowed. Player1 will never have complete information about player2, but may be able to infer the probability of type1 and type2 appearing from whether the previous firm entering the market was blocked, it is a Bayesian game. The reason for these judgements is that there are blocking costs for player2, which may need to make significant price cuts to prevent player1 from entering the market, so it will block player1 when the profit it steals from entering the market is greater than the blocking costs.