Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Формальное правило для предсказания хода игры.
Formal rule for predicting how a game will be played
В теории игр концепция решения — это формальное правило для предсказания того, как будет развиваться игра. Эти предсказания называются «решениями» и описывают, какие стратегии выберут игроки и, следовательно, каков будет исход игры. Наиболее распространенными концепциями решения являются концепции равновесия, наиболее известной из которых является равновесие Нэша. Для многих игр различные концепции решения могут привести к нескольким решениям. Это ставит под сомнение любое из них, поэтому теоретик игр может применить уточнение, чтобы сузить круг возможных решений. Каждая последующая концепция решения, представленная далее, улучшает предыдущую, отсеивая неправдоподобные равновесия в более сложных играх.
In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium. Many solution concepts, for many games, will result in more than one solution. This puts any one of the solutions in doubt, so a game theorist may apply a refinement to narrow down the solutions. Each successive solution concept presented in the following improves on its predecessor by eliminating implausible equilibria in richer games.
Формальное определение
Пусть 𝒢 будет классом всех игр, и для каждой игры G ∈ 𝒢, пусть S(G) будет множеством профилей стратегий. Концепция решения — это элемент прямого произведения ∏_{G∈𝒢} S(G), то есть функция f: 𝒢 → ∪_{G∈𝒢} S(G) такая, что f(G) ∈ S(G) для всех G ∈ 𝒢.
Let be the class of all games and, for each game , let be the set of strategy profiles of A solution concept is an element of the direct product i. e., a function such that for all
Рационализаторство и повторяемое доминирование
В этой концепции решения предполагается, что игроки рациональны, поэтому строго доминируемые стратегии исключаются из набора стратегий, которые могут быть реализованы. Стратегия строго доминируется, когда существует другая стратегия, доступная игроку, которая всегда обеспечивает более высокую выплату, независимо от стратегий, выбранных другими игроками. (Строго доминируемые стратегии также важны при поиске в дереве игры методом minimax.) Например, в дилемме заключённого (один период) (см. ниже), стратегия "дефект" строго доминирует над стратегией "сотрудничество" для обоих игроков, поскольку любому игроку всегда выгоднее выбирать "дефект", независимо от выбора его оппонента.
In this solution concept, players are assumed to be rational and so strictly dominated strategies are eliminated from the set of strategies that might feasibly be played. A strategy is strictly dominated when there is some other strategy available to the player that always has a higher payoff, regardless of the strategies that the other players choose. (Strictly dominated strategies are also important in minimax game tree search.) For example, in the (single period) prisoners' dilemma (shown below), cooperate is strictly dominated by defect for both players because either player is always better off playing defect, regardless of what his opponent does. Prisoner 2 Cooperate Prisoner 2 Defect Prisoner 1 Cooperate −0.5, −0.5 −10, 0 Prisoner 1 Defect 0, −10 −2, −2
In this solution concept, players are assumed to be rational and so strictly dominated strategies are eliminated from the set of strategies that might feasibly be played. A strategy is strictly dominated when there is some other strategy available to the player that always has a higher payoff, regardless of the strategies that the other players choose. (Strictly dominated strategies are also important in minimax game tree search.) For example, in the (single period) prisoners' dilemma (shown below), cooperate is strictly dominated by defect for both players because either player is always better off playing defect, regardless of what his opponent does. Prisoner 2 Cooperate Prisoner 2 Defect Prisoner 1 Cooperate −0.5, −0.5 −10, 0 Prisoner 1 Defect 0, −10 −2, −2
Равновесие Нэша
Равновесие Нэша — это профиль стратегий (профиль стратегий определяет стратегию для каждого игрока, например, в вышеуказанной игре «дилемма заключённых» профиль (сотрудничать, предать) означает, что заключённый 1 выбирает сотрудничество, а заключённый 2 — предательство), в котором стратегия каждого игрока (агента i) является оптимальным ответом на стратегии всех остальных игроков (агентов j при всех j≠i). Стратегия игрока считается оптимальным ответом на стратегию другого игрока, если не существует другой стратегии, которая принесла бы более высокую выплату в любой ситуации, когда другой игрок придерживается своей стратегии.
A Nash equilibrium is a strategy profile (a strategy profile specifies a strategy for every player, e. g. in the above prisoners' dilemma game (cooperate, defect) specifies that prisoner 1 plays cooperate and prisoner 2 plays defect) in which every strategy played by every agent (agent i) is a best response to every other strategy played by all the other opponents (agents j for every j≠i) A strategy by a player is a best response to another player's strategy if there is no other strategy that could be played that would yield a higher pay off in any situation in which the other player's strategy is played.
Подигрыш: идеальное равновесие Нэша
Обобщением обратной индукции является совершенство подигры. Обратная индукция предполагает, что вся дальнейшая игра будет рациональной. В подигрово-совершенных равновесиях игра в каждой подигре рациональна (в частности, является равновесием Нэша). Обратную индукцию можно применять только к конечным играм с определенной длиной, и она не применима к играм с неполной информацией. В таких случаях используется совершенство подигры. Устраненное выше равновесие Нэша является подигрово-несовершенным, поскольку оно не является равновесием Нэша в подигре, начинающейся в узле, достигнутом после входа игрока.
A generalization of backward induction is subgame perfection. Backward induction assumes that all future play will be rational. In subgame perfect equilibria, play in every subgame is rational (specifically a Nash equilibrium). Backward induction can only be used in terminating (finite) games of definite length and cannot be applied to games with imperfect information. In these cases, subgame perfection can be used. The eliminated Nash equilibrium described above is subgame imperfect because it is not a Nash equilibrium of the subgame that starts at the node reached once the entrant has entered.
Совершенное байесовское равновесие
Иногда совершенство подигры не накладывает достаточно строгих ограничений на нерациональные исходы. Например, поскольку подигры не могут пересекать информационные множества, игра с неполной информацией может иметь только одну подигру – саму себя – и, следовательно, совершенство подигры нельзя использовать для исключения каких-либо равновесий Нэша. Совершенное байесовское равновесие (PBE) – это спецификация стратегий игроков и их убеждений относительно того, какой узел в информационном множестве был достигнут в ходе игры. Убеждение относительно узла принятия решения – это вероятность, с которой конкретный игрок считает, что этот узел находится или будет в игре (на равновесном пути). В частности, суть PBE заключается в том, что оно определяет стратегии игроков, которые рациональны, учитывая указанные убеждения игроков, и убеждения, которые согласуются с указанными стратегиями. В байесовской игре стратегия определяет действия игрока в каждом информационном множестве, контролируемом этим игроком. Требование согласованности убеждений со стратегиями не является частью совершенства подигры. Следовательно, PBE представляет собой условие согласованности убеждений игроков. Как и в равновесии Нэша, ни одна стратегия игрока не является строго доминируемой, так и в PBE для любого информационного множества ни одна стратегия игрока не является строго доминируемой, начиная с этого множества. То есть, для каждого убеждения, которое игрок может иметь в этом информационном множестве, не существует стратегии, обеспечивающей большую ожидаемую выгоду для этого игрока. В отличие от вышеупомянутых концепций решения, ни одна стратегия игрока не является строго доминируемой, начиная с любого информационного множества, даже если оно находится вне равновесного пути. Таким образом, в PBE игроки не могут угрожать применением стратегий, которые строго доминируются, начиная с любого информационного множества, отклоняющегося от равновесного пути. Название этой концепции решения, содержащее слово «Байесовский», указывает на то, что игроки обновляют свои убеждения в соответствии с теоремой Байеса, вычисляя вероятности на основе уже произошедшего в игре.
Sometimes subgame perfection does not impose a large enough restriction on unreasonable outcomes. For example, since subgames cannot cut through information sets, a game of imperfect information may have only one subgame – itself – and hence subgame perfection cannot be used to eliminate any Nash equilibria. A perfect Bayesian equilibrium (PBE) is a specification of players' strategies and beliefs about which node in the information set has been reached by the play of the game. A belief about a decision node is the probability that a particular player thinks that node is or will be in play (on the equilibrium path). In particular, the intuition of PBE is that it specifies player strategies that are rational given the player beliefs it specifies and the beliefs it specifies are consistent with the strategies it specifies. In a Bayesian game a strategy determines what a player plays at every information set controlled by that player. The requirement that beliefs are consistent with strategies is something not specified by subgame perfection. Hence, PBE is a consistency condition on players' beliefs. Just as in a Nash equilibrium no player's strategy is strictly dominated, in a PBE, for any information set no player's strategy is strictly dominated beginning at that information set. That is, for every belief that the player could hold at that information set there is no strategy that yields a greater expected payoff for that player. Unlike the above solution concepts, no player's strategy is strictly dominated beginning at any information set even if it is off the equilibrium path. Thus in PBE, players cannot threaten to play strategies that are strictly dominated beginning at any information set off the equilibrium path. The Bayesian in the name of this solution concept alludes to the fact that players update their beliefs according to Bayes' theorem. They calculate probabilities given what has already taken place in the game.
Индукция вперед
Индукция вперед называется так, потому что, подобно обратной индукции, предполагающей рациональность будущей игры, индукция вперед предполагает рациональность прошедшей игры. Если игрок не знает, к какому типу принадлежит другой игрок (то есть имеет место неполная и асимметричная информация), этот игрок может сформировать убеждение относительно типа другого игрока, наблюдая за его прошлыми действиями. Таким образом, убеждение игрока относительно вероятности того, что противник принадлежит к определенному типу, основано на предположении о рациональности прошлых действий этого противника. Игрок может сигнализировать о своем типе посредством своих действий. Колберг и Мертенс (1986) представили концепцию решения – стабильное равновесие, уточнение, удовлетворяющее индукции вперед. Был найден контрпример, демонстрирующий, что такое стабильное равновесие не удовлетворяет обратной индукции. Для разрешения этой проблемы Жан-Франсуа Мертенс ввел концепцию стабильного равновесия Мертенса, которую теоретики игр теперь так и называют, и которая, вероятно, является первым решением, удовлетворяющим как индукции вперед, так и обратной индукции. Индукция вперед дает единственное решение для игры с уничтожением денег.
Forward induction is so called because just as backward induction assumes future play will be rational, forward induction assumes past play was rational. Where a player does not know what type another player is (i. e. there is imperfect and asymmetric information), that player may form a belief of what type that player is by observing that player's past actions. Hence the belief formed by that player of what the probability of the opponent being a certain type is based on the past play of that opponent being rational. A player may elect to signal his type through his actions. Kohlberg and Mertens (1986) introduced the solution concept of Stable equilibrium, a refinement that satisfies forward induction. A counter example was found where such a stable equilibrium did not satisfy backward induction. To resolve the problem Jean François Mertens introduced what game theorists now call Mertens stable equilibrium concept, probably the first solution concept satisfying both forward and backward induction. Forward induction yields a unique solution for the burning money game.