Фиктивные игры: от теории Брауна к современным подходам
Fictitious play
Игровая теория: фиктивная игра — метод обучения, где игроки предполагают стационарные стратегии оппонентов и реагируют на частоту их ходов. Оптимально при стационарности.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В теории игр, фиктивная игра — это правило обучения, впервые предложенное Джорджем У. Брауном. В рамках этого правила каждый игрок исходит из предположения, что его противники придерживаются стационарных (возможно, смешанных) стратегий. В каждом раунде каждый игрок, таким образом, оптимально реагирует на эмпирическую частоту ходов противника. Такой подход, разумеется, оправдан, если противник действительно использует стационарную стратегию, однако он несостоятелен, если стратегия противника нестационарна. Например, стратегия противника может зависеть от последнего хода фиктивного игрока.
In game theory, fictitious play is a learning rule first introduced by George W. Brown. In it, each player presumes that the opponents are playing stationary (possibly mixed) strategies. At each round, each player thus best responds to the empirical frequency of play of their opponent. Such a method is of course adequate if the opponent indeed uses a stationary strategy, while it is flawed if the opponent's strategy is non stationary. The opponent's strategy may for example be conditioned on the fictitious player's last move.
История
Браун впервые предложил концепцию фиктивной игры как объяснение равновесия Нэша. Он представил, что игрок мысленно "проигрывает" варианты игры и корректирует свою дальнейшую стратегию на основе этого мысленного проигрыша; отсюда и название "фиктивная игра". В современном использовании это название несколько неточно, поскольку каждая партия игры действительно происходит. Игра не является полностью вымышленной.
Brown first introduced fictitious play as an explanation for Nash equilibrium play. He imagined that a player would "simulate" play of the game in their mind and update their future play based on this simulation; hence the name fictitious play. In terms of current use, the name is a bit of a misnomer, since each play of the game actually occurs. The play is not exactly fictitious.
Терминология
Бергер (2007) утверждает, что "то, что современные теоретики игр описывают как «фиктивную игру», – это не тот процесс обучения, который Джордж У. Браун определил в своей статье 1951 года": «оригинальная версия» Брауна отличается тонкой деталью в том, что в современной трактовке игроки обновляют свои убеждения одновременно, а Браун описал обновление игроков поочередно. Затем Бергер использует оригинальную формулировку Брауна, чтобы представить простое и интуитивно понятное доказательство сходимости в случае двух игроков в недегенерированных ординальных потенциальных играх. Термин «фиктивный» ранее имел другое значение в теории игр. Фон Нейман и Моргенштерн [1944] определили «фиктивного игрока» как игрока, имеющего только одну стратегию, добавляемого к игре с n игроками для преобразования ее в игру с нулевой суммой с (n + 1) игроками.
Berger (2007) states that "what modern game theorists describe as 'fictitious play' is not the learning process that George W. Brown defined in his 1951 paper": Brown's "original version differs in a subtle detail " in that modern usage involves the players updating their beliefs simultaneously, whereas Brown described the players updating alternatingly. Berger then uses Brown's original form to present a simple and intuitive proof of convergence in the case of two player nondegenerate ordinal potential games. The term "fictitious" had earlier been given another meaning in game theory. Von Neumann and Morgenstern [1944] defined a "fictitious player" as a player with only one strategy, added to an n player game to turn it into a (n + 1) player zero sum game.