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

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

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

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

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

Конечная игра в развёрнутой форме — это структура $\mathrm{\Gamma }=⟨𝒦,𝐇,[({𝐇}_i{)}_{i\in ℐ}],\{A(H){\}}_{H\in 𝐇},a,\rho ,u⟩$ где:

• $𝒦=⟨V,v^0,T,p⟩$ — конечное дерево со множеством вершин $V$, единственной начальной вершиной $v^0\in V$, множеством терминальных вершин $T\subset V$ (пусть $D=V\setminus T$ есть множество нетерминальных вершин) и функцией ближайшего предшественника $p:V\to D$.
• $𝐇$ — разбиение $D$, называемое информационным разбиением.
• $A(H)$ — множество возможных действий для каждого информационного множества $H\in 𝐇$; эти множества образуют разбиение множества всех возможных действий $𝒜$.
• $a:V\setminus \{v^0\}\to 𝒜$ отображение, ставящее в соответствии каждой вершине $v$ единственное действие $a(v)$. Обозначим $a_v$ ограничение отображения $a$ на множестве $s(v)$ следующих за $v$ вершин. Отображение $a$ должно удовлетворять условию

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• 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.