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

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

Игра в развёрнутой форме

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

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

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

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

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

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

См. также

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

Литература

• Hart, Sergiu. Games in extensive and strategic forms // Handbook of Game Theory with Economic Applications. — Elsevier, 1992. — Vol. 1. — ISBN 978-0-444-88098-7.
• Binmore, Kenneth. Playing for real: a text on game theory. — Oxford University Press US, 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.