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

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

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

Конечная игра в развёрнутой форме — это структура ${\displaystyle \Gamma =\langle {\mathcal {K}},\mathbf {H} ,[(\mathbf {H} _{i})_{i\in {\mathcal {I}}}],\{A(H)\}_{H\in \mathbf {H} },a,\rho ,u\rangle }$ где:

• ${\displaystyle {\mathcal {K}}=\langle V,v^{0},T,p\rangle }$ — конечное дерево со множеством вершин ${\displaystyle V}$ , единственной начальной вершиной ${\displaystyle v^{0}\in V}$ , множеством терминальных вершин ${\displaystyle T\subset V}$ (пусть ${\displaystyle D=V\setminus T}$ есть множество нетерминальных вершин) и функцией ближайшего предшественника ${\displaystyle p:V\rightarrow D}$ .
• ${\displaystyle \mathbf {H} }$ — разбиение ${\displaystyle D}$ , называемое информационным разбиением.
• ${\displaystyle A(H)}$ — множество возможных действий для каждого информационного множества ${\displaystyle H\in \mathbf {H} }$ ; эти множества образуют разбиение множества всех возможных действий ${\displaystyle {\mathcal {A}}}$ .
• ${\displaystyle a:V\setminus \{v^{0}\}\rightarrow {\mathcal {A}}}$ отображение, ставящее в соответствии каждой вершине ${\displaystyle v}$ единственное действие ${\displaystyle a(v)}$ . Обозначим ${\displaystyle a_{v}}$ ограничение отображения ${\displaystyle a}$ на множестве ${\displaystyle s(v)}$ следующих за ${\displaystyle v}$ вершин. Отображение ${\displaystyle a}$ должно удовлетворять условию

${\displaystyle \forall H\in \mathbf {H} ,\forall v\in H}$ , ограничение ${\displaystyle a_{v}:s(v)\rightarrow A(H)}$ для ${\displaystyle a}$ на ${\displaystyle s(v)}$ биективно, и ${\displaystyle s(v)}$ есть множество вершин, следующих за ${\displaystyle v}$ .

• ${\displaystyle {\mathcal {I}}=\{1,...,I\}}$ — конечное множество игроков, ${\displaystyle 0}$ — специальный игрок « Природа », кортеж ${\displaystyle (\mathbf {H} _{i})_{i\in {\mathcal {I}}\cup \{0\}}}$ в качестве элементов ${\displaystyle \mathbf {H} _{i}}$ имеет специфическое для игрока ${\displaystyle i\in {\mathcal {I}}\cup \{0\}}$ подмножество информационного разбиения ${\displaystyle \mathbf {H} }$ . Пусть ${\displaystyle \iota (v)=\iota (H)}$ есть единственный игрок, совершающий ход в вершине ${\displaystyle v\in H}$ .
• ${\displaystyle \rho =\{\rho _{H}:A(H)\rightarrow [0,1]|H\in \mathbf {H} _{0}\}}$ — семейство распределений на множестве действий природы.
• ${\displaystyle u=(u_{i})_{i\in {\mathcal {I}}}:T\rightarrow \mathbb {R} ^{\mathcal {I}}}$ — функция выигрыша.

См. также

• Нормальная форма игры

Литература

• (англ.) ( . 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 .
• (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), , San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1 . An 88-page mathematical introduction; see Chapters 4 and 5. at many universities.
• Luce R. D. and (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 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), , New York: Cambridge University Press , ISBN 978-0-521-89943-7 . A comprehensive reference from a computational perspective; see Chapter 5. .