Пусть задан конечный древовидный граф G=(X,F), где X - конечное множество вершин, а F - отображение, ставящее в соответствие каждой точке xX подмножество F_x X.

Подграфом G_z древовидного графа G, где zX, называется граф с начальной вершиной z, вложенный в дерево графа G и содержащий все вершины, в которые возможен переход из вершины z (рис.1).

Перейдем к определению многошаговой игры с полной информацией Г на древовидном конечном графе G.

Пусть G=(X,F) - древовидный граф. Рассмотрим разбиение множества вершин X на n+1 множество X₁, …, X_n,

где F_x = для xX_n+1. Множество X_i, i=1, …, n, называется множеством очередности i-го игрока, а множество X_n+1 - множеством окончательных позиций. На множестве окончательных позиций X_n+1 определены n вещественных функций H₁(x), …, H_n(x), xX_n+1. Функция H_i(x), i=1, …, n, называется выигрышем i-го игрока.

Игра происходит следующим образом. Задано множество N игроков, перенумерованных натуральными числами 1, …, i, …, n (в дальнейшем N={1,2, …, n}. Пусть x₀X_i1; тогда в вершине (позиции) x₀ “ходит” игрок i₁ и выбирает вершину x₁F_x0. Если x₁ X_i2, то в вершине x₁ “ходит” игрок i₂ и выбирает следующую вершину (позицию) x₂ F_x1, и т.д. Таким образом, если на m-м шаге реализована вершина (позиция) x_m-1X_ik, то в ней “ходит” игрок i_k и выбирает следующую вершину (позицию) из множества F_xk-1. Игра прекращается, как только достигается окончательная вершина (позиция) x_l X_n+1, то есть такая, для которой F_xl=.

В результате последовательного выбора позиций однозначно реализуется некоторая последовательность x₀, …, x_k, …, x_l, определяющая путь в древовидном графе G, исходящий из начальной позиции x₀ и достигающий одной из окончательных позиций игры. Такой путь в дальнейшем будем называть партией. Из-за древовидности графа G каждая партия однозначно определяет окончательную позицию x_l, в которую она приводит, и, наоборот, окончательная позиция x_l однозначно определяет партию. В позиции x_l каждый из игроков i, i=1, …, n, получает выигрыш H_i(x_l).

Будем предполагать, что игрок i при совершении выбора в позиции xX_i знает эту позицию x, а следовательно, из-за древовидности графа G может восстановить и все предыдущие позиции. В таком случае говорят, что игроки имеют полную информацию. Примером игр с полной информацией служат шахматы и шашки, поскольку в них игроки могут записывать ходы и поэтому можно считать, что они знают предысторию игры при совершении каждого очередного хода.

Определение 1. Однозначное отображение u_i, которое каждой вершине (позиции) xX_i ставит в соответствие некоторую вершину (позицию) yF_x, называется стратегией игрока i.

Множество всевозможных стратегий игрока i будем обозначать U_i.

Таим образом, стратегия i-го игрока предписывает ему в любой позиции x из множества его очередности X_i однозначный выбор следующей позиции.

Упорядоченный набор u=(u₁, …, u_i, …, u_n), где u_iU_i, называется ситуацией в игре, а декартово произведение - множеством ситуаций. Каждая ситуация u=(u₁, …, u_i, …, u_n) однозначно определяет партию в игре, а следовательно, и выигрыш игроков. Действительно, пусть x₀X_i. Тогда в ситуации u=(u₁, …, u_i, …, u_n) следующая позиция x₁ определяется однозначно по правилу u_i1(x₀)=x₁. Пусть теперь x₁ X_i2. Тогда x₂ определяется однозначно по правилу x_m= u_ik(x_m-1), и т.д.

Пусть ситуации u=(u₁, …, u_i, …, u_n) в указанном смысле соответствует партия x₀, …, x_k, …, x_l. Тогда можно ввести понятие функции выигрыша K_i игрока i, положив ее значение в каждой ситуации u равным значению выигрыша H_i в окончательной позиции партии x₀, …, x_l, соответствующей ситуации u=(u₁, …, u_i, …, u_n), то есть K_i(u₁, …, u_i, …, u_n)=H_i(x_l),i=1, …, n.

Функции K_i, i=1, …, n, определены на множестве ситуаций .

Таким образом, определив множество стратегий игроков и функции выигрыша, мы определили некоторую игру Г, которую и будем называть многошаговой игрой с полной информацией на древовидном конечном графе G.

Для дальнейшего исследования игры Г необходимо ввести в рассмотрение понятие подыгры, то есть игры на подграфе графа G основной игры.

Пусть zX. Рассмотрим подграф G_z=(X_z,F), с которым свяжем подыгру Г_z следующим образом. Множества очередности игроков в подыгре Г_z определяем по правилу =X_i X_z, i=1, …, n, множество окончательных позиций =X_n+1 X_z, выигрыш игрока i в подыгре полагаем равным H_i^z

H_i^z(x)=H_i(x), x, i=1, …, n.

В соответствии с этим стратегия i-го игрока в подыгре Г_z определена как сужение стратегии u_i i-го игрока в игре Г на множество , то есть

= u_i(x), x= X_i X_z, i=1, …, n.

Множество всех стратегий i-го игрока в подыгре обозначается . В результате с каждым подграфом G_z мы связываем подыгру в нормальной форме

Г_z=(N, {}, {}),

где функции выигрыша , i=1, …, n, определены на декартовом произведении

.

В указанных обозначениях игра Г может быть записана так:

Г_x0=(N, {U_i^x0}, {K_i^x0})=(N, {U_i}, {K_i})=Г

1.4. Ситуация равновесия по Нэшу