Русская Википедия:Развёрнутая форма игры
Развёрнутой формой (Шаблон:Lang-en) игры называют её представление в виде дерева. Дерево состоит из вершин и соединяющих их рёбер. Вершины подразделяются на терминальные (конечные) и нетерминальные. Каждая нетерминальная вершина характеризуется множеством допустимых ходов и доступной для игрока информацией. Терминальные вершины сообщают о размере выигрыша, получаемого по их достижении.
В развёрнутой форме можно представить и игры неполной информации. В этом случае игра начинается с хода природы, то есть некого случайного события.
Определение для конечной игры
Конечная игра в развёрнутой форме — это структура <math> \Gamma = \langle\mathcal{K}, \mathbf{H}, [ (\mathbf{H}_i)_{i \in \mathcal{I} } ], \{ A(H) \}_{H \in \mathbf{H} }, a , \rho, u \rangle</math> где:
- <math>\mathcal{K} = \langle V, v^0, T, p\rangle</math> — конечное дерево со множеством вершин <math> V </math>, единственной начальной вершиной <math>v^0 \in V</math>, множеством терминальных вершин <math>T \subset V</math> (пусть <math>D = V \setminus T</math> есть множество нетерминальных вершин) и функцией ближайшего предшественника <math> p: V \rightarrow D </math>.
- <math>\mathbf{H}</math> — разбиение <math>D</math>, называемое информационным разбиением.
- <math> A(H) </math> — множество возможных действий для каждого информационного множества <math>H \in \mathbf{H}</math>; эти множества образуют разбиение множества всех возможных действий <math>\mathcal{A}</math>.
- <math>a: V \setminus \{ v^0 \} \rightarrow \mathcal{A}</math> разбиение множества действий, отображающее каждую вершину <math>v</math> в единственное действию <math>a(v)</math> и удовлетворяющее условию
<math> \forall H \in \mathbf{H}, \forall v \in H </math>, ограничение <math>a_v: s(v) \rightarrow A(H)</math> для <math>a</math> на <math>s(v)</math> биективно, и <math> s(v) </math> есть множество вершин, следующих за <math>v</math>.
- <math>\mathcal{I} = \{ 1, ..., I \} </math> — конечное множество игроков, <math>0</math> — специальный игрок «Природа», <math> (\mathbf{H}_i)_{i \in \mathcal{I} \cup \{ 0 \} }</math> специфическое для игрока разбиение информационного множества <math>\mathbf{H}</math>. Пусть <math>\iota(v) = \iota(H)</math> есть единственный игрок, совершающий ход в вершине <math>v \in H</math>.
- <math>\rho = \{ \rho_H: A(H) \rightarrow [0, 1] | H \in \mathbf{H}_0 \}</math> — семейство распределений на множестве ходов природы.
- <math>u = (u_i)_{i \in \mathcal{I}}: T \rightarrow \mathbb{R}^\mathcal{I}</math> — функция выигрыша.
См. также
Литература
- Шаблон:Книга
- Шаблон:Книга
- Dresher M. (1961). The mathematics of games of strategy: theory and applications (Ch4: Games in extensive form, pp74-78). Rand Corp. Шаблон:ISBN
- Fudenberg D and Tirole J. (1991) Game theory (Ch3 Extensive form games, pp67-106). Mit press. Шаблон:ISBN
- Шаблон:Citation. 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
- Osborne MJ and Rubinstein A. 1994. A course in game theory (Ch6 Extensive game with perfect information, pp. 89-115). MIT press. Шаблон:ISBN
- Шаблон:Citation. A comprehensive reference from a computational perspective; see Chapter 5. Downloadable free online.
