Развёрнутой формой () игры называют её представление в виде дерева. Дерево состоит из вершин и соединяющих их рёбер. Вершины подразделяются на терминальные (конечные) и нетерминальные. Каждая нетерминальная вершина характеризуется множеством допустимых ходов и доступной для игрока информацией. Терминальные вершины сообщают о размере выигрыша, получаемого по их достижении.
В развёрнутой форме можно представить и игры неполной информации. В этом случае игра начинается с хода природы, то есть некого случайного события.
Определение для конечной игры Конечная игра в развёрнутой форме — это структура
где: — конечное дерево со множеством вершин , единственной начальной вершиной , множеством терминальных вершин (пусть есть множество нетерминальных вершин) и функцией ближайшего предшественника . — разбиение , называемое информационным разбиением. — множество возможных действий для каждого информационного множества ; эти множества образуют разбиение множества всех возможных действий . отображение, ставящее в соответствии каждой вершине единственное действие . Обозначим ограничение отображения на множестве следующих за вершин. Отображение должно удовлетворять условию , ограничение для на биективно, и есть множество вершин, следующих за . — конечное множество игроков, — специальный игрок «Природа», кортеж в качестве элементов имеет специфическое для игрока подмножество информационного разбиения . Пусть есть единственный игрок, совершающий ход в вершине . — семейство распределений на множестве действий природы. — функция выигрыша.
См. также Нормальная форма игры
Литература
Dresher M. (1961). The mathematics of games of strategy: theory and applications (Ch4: Games in extensive form, pp74-78). Rand Corp. Fudenberg D and Tirole J. (1991) Game theory (Ch3 Extensive form games, pp67-106). Mit press. . 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. Osborne MJ and Rubinstein A. 1994. A course in game theory (Ch6 Extensive game with perfect information, pp. 89-115). MIT press. . A comprehensive reference from a computational perspective; see Chapter 5. Downloadable free online.
Категория:Теория игр