Развёрнутая форма игры

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Игра в развёрнутой форме

Развёрнутой формой (англ. extensive form) игры называют её представление в виде дерева. Дерево состоит из вершин и соединяющих их рёбер. Вершины подразделяются на терминальные (конечные) и нетерминальные. Каждая нетерминальная вершина характеризуется множеством допустимых ходов и доступной для игрока информацией. Терминальные вершины сообщают о размере выигрыша, получаемого по их достижении.

В развёрнутой форме можно представить и игры неполной информации. В этом случае игра начинается с хода природы, то есть некого случайного события.

Определение для конечной игры

[править | править код]

Конечная игра в развёрнутой форме — это структура где:

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

, ограничение для на биективно, и есть множество вершин, следующих за .

  • — конечное множество игроков, — специальный игрок «Природа», кортеж в качестве элементов имеет специфическое для игрока подмножество информационного разбиения . Пусть есть единственный игрок, совершающий ход в вершине .
  • — семейство распределений на множестве действий природы.
  • — функция выигрыша.

Литература

[править | править код]
  • Hart, Sergiu[англ.]. Games in extensive and strategic forms // Handbook of Game Theory with Economic Applications (англ.) / Aumann, Robert; Hart, Sergiu. — Elsevier, 1992. — Vol. 1. — ISBN 978-0-444-88098-7.
  • Binmore, Kenneth. Playing for real: a text on game theory (англ.). — Oxford University Press, 2007. — ISBN 978-0-19-530057-4.
  • Dresher M. (1961). The mathematics of games of strategy: theory and applications (Ch4: Games in extensive form, pp74-78). Rand Corp. ISBN 0-486-64216-X
  • Fudenberg D and Tirole J. (1991) Game theory (Ch3 Extensive form games, pp67-106). Mit press. ISBN 0-262-06141-4
  • Leyton-Brown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1. An 88-page mathematical introduction; see Chapters 4 and 5. Free online at many universities.
  • Luce R. D. and Raiffa H. (1957). Games and decisions: introduction and critical survey. (Ch3: Extensive and Normal Forms, pp39-55). Wiley New York. ISBN 0-486-65943-7
  • Osborne MJ and Rubinstein A. 1994. A course in game theory (Ch6 Extensive game with perfect information, pp. 89-115). MIT press. ISBN 0-262-65040-1
  • Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 978-0-521-89943-7. A comprehensive reference from a computational perspective; see Chapter 5. Downloadable free online.