2. Алгоритм построения оптимального пути

В этом разделе мы предложим метод построения решения игры $\Gamma_f(x_0)$, который приведет также к построению соответствующего оптимального пути.

Решение игры $\Gamma_f(x_0)$ строим методом обратной индукции, двигаясь от окончательных позиций к начальной. Процедура поиска решения игры $\Gamma_f(x_0)$ напоминает схему построения равновесия по Нэшу в обычной позиционной игре. Существующие различия заключаются в следующем. Предположим, что поддерево $K(x)$ принадлежит области кооперативного поведения игрока $i$. Как указывалось выше, кооперативная функция $f$ определяет для каждой позиции некоторую коалиционную структуру. Тогда на множестве окончательных позиций поддерева $K(x)$ вместо выигрышей игрока $i$ необходимо рассматривать выигрыши коалиций, включающих игрока $i$. На поддереве $K(x)$, используя схему Нэша, решение игрока $i$, максимизирующего выигрыш коалиции, к которой он принадлежит, может быть легко определено. Однако, поскольку выигрыш игрока $i$ не выделен из коалиционного выигрыша, при определении решений игрока $i$ в его личных позициях, находящихся между позицией $x$ и начальной позицией $x_0$, где игрок $i$ играет индивидуально, возникают трудности. Если доля игрока $i$ в коалиционном выигрыше известна, то, применяя снова схему Нэша, мы можем найти решения игрока $i$ в его личных позициях вдоль пути $\{x_0,\ldots,x\}$. Таким образом, определение изменений выигрыша при переходе игрока с кооперативного поведения на индивидуальное является главной проблемой, рассматриваемой в предлагаемом алгоритме.

В дальнейшем мы будем использовать следующие обозначения. Пусть $x$ - некоторая позиция. Обозначим через $Z(x)$ множество позиций, непосредственно следующих за $x$. Обозначим игрока, принимающего решение в позиции $x$, $x\in P_i$, в игре $\Gamma$ через $i(x)\in N$. Будем говорить, что решение игрока $i(x)$ в позиции $x$ ведет в позицию $\bar x\in Z(x)$. Введем вспомогательную функцию $c_f$, определяемую с помощью кооперативной функции $f=(f_1,\ldots,f_n)$:

$$c_f(x)=\left\{ \begin{array}{rl} 1,&\ \ \mbox{ если \ \ $f_{... ...x] 0,&\ \ \mbox{ если \ \ $f_{i(x)}(x)=0$.} \end{array}\right.$$ (2.1)

Предположим, что длина игры $\Gamma_f(x_0)$ составляет $T+1$ позицию. Рассмотрим разбиение множества всех позиций дерева игры $K(x_0)$ на $T+1$ множеств $X_0$, $X_1,\ldots,X_t,\ldots,X_T=\{x_0\}$, где множество $X_t$ состоит из позиций достигаемых из начальной позиции $x_0$ за $T-t$ ходов. Обозначим множество позиций, принадлежащих множеству $X_t$, через $x_t$, $t=1,\ldots,T$.

Начальный шаг. Рассмотрим множество окончательных позиций
$P_{n+1}$. Коалиционная структура в позиции $x\in P_{n+1}$ совпадает с коалиционной структурой в позиции $x_1$, $x\in Z(x_1)$. Согласно кооперативной функции $f$, в позиции $x_1$ формируются коалиции $S_f(x_1)$, $\{j_1\},\ldots,\{j_{\vert N\setminus S_f(x_1)\vert}\}$. Выигрыш игрока $i_f=S_f(x_1)$ в позиции $x\in Z(x_1)$ равен

$$\sum_{i\in S_f(x_1)}h_i(x).$$ (2.2)

Выигрыш игрокa $i_f=\{j_k\}$, $k=1,\ldots,\vert N\setminus S_f(x_1)\vert$, в окончательной позиции $x$ составляет $h_{j_k}(x)$.

Шаг 1. Перейдем из окончательных позиций $Z(x_1)$, $x_1\in X_1$, к предшествующим. Рассмотрим окончательную позицию $x_1$. Предположим, что $c_f(x_1)=1$. Тогда игрок $i(x_1)\in N$ кооперируется, и в позиции $x_1$ делает ход игрок $i_f(x_1)=S_f(x_1)$, $i_f(x_1)\in N_f$. Мы предписываем игроку $i_f(x_1)$ выбрать позицию $\bar x_1\in Z(x_1)$ из условия

$$\max_{x\in Z(x_1)}\sum_{i\in S_f(x_1)}h_i(x)= \sum_{i\in S_f(x_1)}h_i(\bar x_1).$$ (2.3)

Если $c_f(x_1)=0$, то игрок $i(x_1)$ не кооперируется. Отсюда $i_f(x_1)=\{i(x_1)\}$. В этом случае мы предписываем игроку $i_f(x_1)$ выбрать позицию $\bar x_1$ из условия

$$\max_{x\in Z(x_1)} h_{i(x_1)}(x)= h_{i(x_1)}(\bar x_1).$$ (2.4)

Применяя аналогичные рассуждения, можно построить путь с началом в $x_1\in X_1$ для каждой позиции $x_1$ множества $X_1$. Таким образом, на каждом поддереве $K(x_1)$, $x_1\in X_1$, фиксируется позиция $\bar x_1$, являющаяся предполагаемой окончательной позицией строящегося пути игры $\Gamma_f(x_0)$. Поэтому вместо рассмотрения терминальных функций $h_i$, $i\in N$, на множестве $P_{n+1}$ окончательных позиций мы можем использовать функции $r^1_i\colon X_1\to R^1_+$, $i\in N$, задаваемые на множестве $X_1$:

$$r^1_i(x_1)=\left\{ \begin{array}{ll} h_i(\bar x_1),&\quad\mb... ...1),&\quad\mbox{ если \ \ $x_1\in P_{n+1}$.} \end{array}\right.$$ (2.5)

Шаг 2. Продолжим движение по направлению к корню дерева игры. Найдем решения игроков $i_f\in N_f$ в позициях $x_2\in X_2$. Если на множестве $X_1$ известны выигрыши каждого игрока $i_f(x_2)\in N_f$, $x_2\in X_2$, то мы можем построить путь игры на поддеревьях $K(x_2)$, $x_2\in X_2$.

Рассмотрим множество

$$Y(x_2)=Y_1(x_2)\cup Y_2(x_2),$$ (2.6)

где

$$Y_1(x_2)=\Bigl\{x\in Z(x_2)\Bigl\vert\ c_f(x_2)=0\quad \mbox{ и } \quad i(x_2)\in S_f(x)\Bigr\}$$ (2.7)

и

$$Y_2(x_2)=\Bigl\{x\in Z(x_2)\Bigl\vert\ c_f(x_2)=1\quad \mbox{ и } \quad S_f(x)\setminus S_f(x_2)\not=\emptyset\Bigr\}.$$ (2.8)

В каждой позиции множества $Y(x_2)\subset Z(x_2)$ выигрыш либо коалиции $i_f(x_2)=\{i(x_2)\}$ при $c_f(x_2)=0$, либо коалиции $i_f(x_2)=S_f(x_2)$ при $c_f(x_2)=1$ не выделен из выигрыша $\sum_{i\in S_f(x_1)}r_i^1(x_1)$ коалиции $i_f(x_1)=S_f(x_1)$, $x_1\in Z(x_2)$.

В качестве примера, подтверждающего существование непустого множества $Y_2(x_2)$, предположим, что игрок $i(x_2)$ делает ход в поддереве $K(x_2)$ дважды, т.е. существует позиция $y_1\in Z(x_2)$ такая, что $i(y_1)$ и $i(x_2)$ есть один и тот же игрок. Допустим, что $c_f(x_2)=0$ и $c_f(y_1)=1$. Тогда игрок $i(x_2)$ принадлежит коалиции $S_f(y_1)$ на поддереве $K(y_1)$ и играет индивидуально в позиции $x_2$. Поскольку выигрыш игрока $i(x_2)$ не выделен из выигрыша $\sum_{i\in S_f(y_1)}r^1_i(\bar y_1)$ коалиции $S_f(y_1)$, то его выигрыш в позиции $y_1\in Z(x_2)$ не известен.

В общем случае отсутствие информации о выигрыше происходит в позициях, где изменяется коалиционная структура, и это изменение касается текущего игрока, принимающего решение. Для каждой позиции $x_2\in X_2$ мы рассмотрим два основных случая.

1) Предположим, что $Y(x_2)=\emptyset$. Пусть $c_f(x_2)=0$. Следовательно, в позиции $x_2$ принимает решение игрок $i_f(x_2)=\{i(x_2)\}$. Мы предписываем игроку $i_f(x_2)$ выбрать позицию $\bar x_2\in Z(x_2)$ из условия

$$\max_{x\in Z(x_2)} r^1_{ i(x_2)}(x)= r^1_{ i(x_2)}(\bar x_2).$$ (2.9)

Теперь допустим, что $c_f(x_2)=1$. Коалиция $S_f(x_2)$ является подмножеством коалиции $S_f(x_1)$ для каждой позиции $x_1\in Z(x_2)$. Поэтому, поскольку $Y(x_2)=\emptyset$, коалиции $S_f(x_2)$ и $S_f(x_1)$ совпадают. В этом случае мы предпишем игроку $i_f(x_2)=S_f(x_2)$ выбрать позицию $\bar x_2\in Z(x_2)$ из условия

$$\max_{x\in Z(x_2)} \sum_{i\in S_f(x_2)} r^1_i(x)= \sum_{i\in S_f(x_2)} r^1_i(\bar x_2).$$ (2.10)

2) Предположим, что $Y(x_2)\not=\emptyset$. Как выше указывалось, возникает неопределенность с выигрышами коалиции $i_f(x_2)=\{i(x_2)\}$ при $c_f(x_2)=0$ и коалиции $i_f(x_2)=S_f(x_2)$ при $c_f(x_2)=1$. Чтобы построить путь игры на поддереве $K(x_2)$, необходимо найти некоторый дележ выигрыша коалиции $S_f(y_1)$ для каждой позиции $y_1\in Y(x_2)$. Определим требуемый дележ, рассматривая вспомогательную кооперативную игру $G_f(y_1,S_f(y_1))$ на поддереве $K(y_1)$ с множеством игроков $S_f(y_1)$ и х. ф. $v_f(y_1,R)$, $R\subset S_f(y_1)$, для каждой позиции $y_1\in Y(x_2)$.

Для связности изложения детальное объяснение построения х. ф.
$v_f(y_1,R)$ приводится ниже. Сейчас же будем предполагать лишь, что х. ф. $v_f(y_1,R)$ известна.

Выигрыш наибольшей коалиции в кооперативной игре $G_f(y_1,S_f(y_1))$ равен

$$v_f(y_1,S_f(y_1))=\sum_{i\in S_f(y_1)} r^1_i(y_1).$$ (2.11)

Мы предлагаем рассматривать вектор Шепли [5]

$$Sh^f(y_1)=\Bigl(Sh^f_{k_1}(y_1),\ldots, Sh^f_{k_{\vert S_f(y_1)\vert}}(y_1)\Bigr),$$ (2.12)

где

$$\sum_{j=1}^{\vert S_f(y_1)\vert} Sh^f_{k_j}(y_1)=v_f(y_1,S_f(y_1)),$$ (2.13)

в качестве оптимального дележа в игре $G_f(y_1,S_f(y_1))$. Если игрок $\{i(x_2)\}\in N_f$ в позиции $x_2$ выбирает позицию $y_1\in Y(x_2)$, то его выигрыш определяется с помощью вектора Шепли $Sh^f(y_1)$ и равен $Sh^f_{i(x_2)}(y_1)$. Таким образом, на множестве $X_1$ задается новая функция выигрышей $\bar r^1_i\colon X_1\to R^1_+$, $i\in N$, такая, что для $x_1\in Z(x_2)$

$$\bar r^1_i(x_1)=\left\{ \begin{array}{ll} Sh^f_i(x_1),&\quad... ...1_i(x_1),&\quad\mbox{ в противном случае. } \end{array}\right.$$ (2.14)

Предположим, что $c_f(x_2)=0$. Тогда для игрока $i_f(x_2)=\{i(x_2)\}$ является оптимальным реализация пути, проходящего через позицию $\bar x_2\in Z(x_2)$, которая удовлетворяет условию:

$$\max_{x\in Z(x_2)}\bar r^1_{i(x_2)}(x)=\bar r^1_{i(x_2)}(\bar x_2).$$ (2.15)

Теперь пусть $c_f(x_2)=1$. Так как игрок $i(x_2)$ кооперируется, то в позиции $x_2$ совершает ход коалиция $i_f(x_2)=S_f(x_2)$. Мы предписываем ей выбрать позицию $\bar x_2$, удовлетворяющую условию:

$$\max_{x\in Z(x_2)}\sum_{i\in S_f(x_2)}\bar r^1_{i(x_2)}(x)= \sum_{i\in S_f(x_2)} \bar r^1_{i(x_2)}(\bar x_2).$$ (2.16)

Таким образом, путь на каждом поддереве $K(x_2)$, $x\in X_2$, построен. Отсюда, чтобы построить путь игры на поддеревьях $K(x_3)$, $x_3\in X_3$, достаточно определить решения игроков $i_f(x_3)\in N_f$, $x_3\in X_3$. Зададим на множестве $X_2$ функции $r^2_i\colon X_2\to R_+^1$, $i\in N$, такие, что для $x_2\in X_2$ и $i\in N$

$$r^2_i(x_2)=\left\{ \begin{array}{ll} r^1_i(\bar x_2),&\quad\... ..._2),&\quad\mbox{ если\ \ $x_2\in P_{n+1}$.} \end{array}\right.$$ (2.17)

Дальнейшие шаги процедуры аналогичны шагу 1 и 2. Опуская изложение каждого шага, рассмотрим шаг $t$. Предположим, что продолжая двигаться к корню $x_0$ дерева игры, мы достигли позиций $x_t\in X_t$. Пусть функции $r^{t-1}_i\colon X_{t-1}\to R^1_+$, $i\in N$, определяют, какие выигрыши получают игроки $i\in N$ после выполнения игроками $i_f(x_{t-1})\in N_f$, $x_{t-1}\in X_{t-1}$, предписанных нами решений.

Шаг t. Мы не будем затрагивать окончательные позиции из множества $X_t\cap P_{n+1}$, потому что они могут быть рассмотрены точно так же, как в разделе 3.2. Определим решения игроков $i_f\in N_f$ в промежуточных позициях $X_t\setminus P_{n+1}$. Пусть

$$Y(x_t)=Y_1(x_t)\cup Y_2(x_t),$$ (2.18)

где

$$Y_1(x_t)=\{x\in Z(x_t)\vert \ c_f(x_t)=0\ \ \mbox{ и } \ \ i(x_t)\in S_f(x)\}$$ (2.19)

и

$$Y_2(x_t)=\{x\in Z(x_t)\vert\ c_f(x_t)=1\ \ \mbox{ и } \ \ S_f(x)\setminus S_f(x_t) \not=\emptyset\}.$$ (2.20)

Сначала обсудим случай, когда построение новых функций выигрыша не является необходимым.

1) Допустим, что $Y(x_t)=\emptyset$ для всех позиций $x_t\in X_t\setminus P_{n+1}$. Согласно функциям $r_i^{t-1}$, $i\in N$, если решение игрока $i_f(x_t)$ приводит игру в позицию $\bar x_t\in Z(x_t)$, то выигрыши, получаемые игроками $i_f\in N_f$ в конце игры, будут равны $\sum_{i\in S_f(x_t)} r_i^{t-1}(\bar x_t)$ для игрока $i_f=S_f(x_t)$ и $r_{j_k}^{t-1}(\bar x_t)$ для игроков $i_f=\{j_k\}$, $k=1,\ldots,\vert S_f(x_t)\vert$, соответственно. Если $c_f(x_t)=0$, то в позиции $x_t$ делает ход игрок $i_f=\{i(x_t)\}$ и мы предпишем ему выбрать позицию $\bar x_t$ удовлетворяющую условию

$$\max_{x\in Z(x_t)} r^{t-1}_{i(x_t)}(x)= r^{t-1}_{i(x_t)}(\bar x_t).$$ (2.21)

Если же $c_f(x_t)=1$, то в позиции $x_t$ делает ход игрок $i_f=S_f(x_t)$. Мы предпишем ему выбрать позицию $\bar x_t$ из условия

$$\max_{x\in Z(x_t)} \sum_{i\in S_f(x_t)} r^{t-1}_{i(x_t)}(x)= \sum_{i\in S_f(x_t)}r^{t-1}_{i(x_t)}(\bar x_t).$$ (2.22)

2) Предположим, что для некоторой позиции $x_t$ множество $Y(x_t)\subset Z(x_t)$, состоящее из позиций, для которых выигрыш игрока $i_f(x_t)\in N_f$ не определен, не пусто.

Чтобы узнать решение игрока $i_f(x_t)$ в позиции $x_t$, для каждой позиции $y_{t-1}\in Y(x_t)$ рассмотрим кооперативную игру $G_f(y_{t-1},S_f(y_{t-1}))$ $\vert S_f(y_{t-1})\vert$ лиц с х. ф. $v_f(y_{t-1},R)$, $R\subset S_f(y_{t-1})$. Выигрыш наибольшей коалиции в этой кооперативной игре равен

$$v_f(y_{t-1},S_f(y_{t-1}))=\sum_{i\in S_f(y_{t-1})}r^{t-1}_i(y_{t-1}).$$ (2.23)

Мы будем рассматривать вектор Шепли

$$Sh^f(y_{t-1})=\Bigl(Sh^f_{k_1}(y_{t-1}),\ldots, Sh^f_{k_{\vert S_f(y_{t-1})\vert}}(y_{t-1})\Bigr),$$ (2.24)

где

$$\sum_{j=1}^{\vert S_f(y_{t-1})\vert}Sh^f_{k_j}(y_{t-1})= v_f(y_{t-1},S_f(y_{t-1})),$$ (2.25)

как оптимальный дележ выигрыша коалиции $S_f(y_{t-1})$. Тогда измененные выигрыши задаются на $X_{t-1}$ функциями $\bar r^{t-1}_i\colon X_{t-1}\to R^1_+$, $i\in N$, где для $x_{t-1}\in Z(x_t)$

$$\bar r^{t-1}_i(x_{t-1})=\left\{ \begin{array}{ll} Sh^f_i(x_{... ...(x_{t-1}),&\quad\mbox{ в противном случае.} \end{array}\right.$$ (2.26)

Если $c_f(x_t)=0$, мы предписываем игроку $i_f(x_t)=\{i(x_t)\}$ выбрать позицию $\bar x_t\in Z(x_t)$ из условия

$$\max_{x\in Z(x_t)}\bar r^t_{i(x_t)}(x)=\bar r^t_{i(x_t)}(\bar x_t).$$ (2.27)

Если $c_f(x_t)=1$, в позиции $x_t$ принимает решение игрок $i_f(x_t)=S_f(x_t)$. Предписываем ему выбрать позицию $\bar x_t$ из условия

$$\max_{x\in Z(x_t)}\sum_{i\in S_f(x_t)}\bar r^t_{i(x_t)}(x)= \sum_{i\in S_f(x_t)} \bar r^t_{i(x_t)}(\bar x_t).$$ (2.28)

В итоге, так как решения игроков $i_f\in N_f$ были определены для каждой позиции $x_t\in X_t$, развитие игры $\Gamma_f(x_0)$ на каждом поддереве $K(x_t)$, $x_t\in X_t$, найдено. Кроме этого, на шаге $t$ процедуры были построены функции $r^t_i\colon X_t\to R^1_+$, определяющие, какой выигрыш получат игроки $i\in N$ после принятия игроками $i_f\in N_f$ в позициях $x_t\in X_t$ предписанных нами решений. Для $i\in N$ и $x_t\in X_T$ функция $r^t_i$ задается следующим образом:

$$r^t_i(x_t)=\left\{ \begin{array}{ll} r^{t-1}_i(\bar x_t), &\... ...), &\quad\mbox{ если \ \ $x_t\in P_{n+1}$.} \end{array}\right.$$ (2.29)

Продолжая спускаться по дереву игры $K(x_0)$ к начальной позиции $x_0$ и последовательно определяя решения игроков $i_f\in N_f$ на оставшихся множествах $X_\tau$, $\tau=t+1,\ldots,T$, мы построим путь, который реализуется в игре $\Gamma$ при задании кооперативной функции $f=(f_1,\ldots,f_n)$. Мы будем называть данный путь оптимальным путем частично-кооперативной игры $\Gamma_f(x_0)$ и обозначать его через $x(f)$.

Кооперативные игры

Обсудим построение кооперативных игр $G_f(x,S_f(x))$, $x\in Y(x_t)$. Укажем метод построения х. ф. $v_f(x,R)$, $R\subset S_f(x)$, игры $G_f(x,S_f(x))$.

При построении оптимального пути развития игры $\Gamma_f(x_0)$ в разделах 3.2-3.5 было определено поведение игроков $i_f\in N_f$ в каждой личной позиции принятия решения. Такое поведение, как функция от текущих позиций, называется стратегией. Обозначим через $\psi^*(\cdot)=\Bigl(\psi^*_1(\cdot),\ldots,\psi^*_n(\cdot)\Bigr)$ набор стратегий, определенных в разделах 3.2-3.5, приводящий к оптимальному пути $x(f)$ игры $\Gamma_f(x_0)$. Кооперативная игра $G_f(x,S_f(x))$ строится с помощью этих стратегий. Рассмотрим след $\psi^*_x(\cdot)=\Bigl(\psi^*_{1x}(\cdot),\ldots, \psi^*_{nx}(\cdot)\Bigr)$ набора $\psi^*$ на поддереве $K(x)$. Для игроков $i\not\in S_f(x)$ зафиксируем стратегии $\psi^*_{ix}(\cdot)$ и рассмотрим подыгру $\overline\Gamma_f(x)$ игры $\Gamma_f(x_0)$, в которой выборы игроков $i\not\in S_f(x)$ в их личных позициях зафиксированы в соответствии со стратегиями $\psi^*_{ix}(\cdot)$. Таким образом, игра $\overline\Gamma_f(x)$ есть игра между игроками из коалиции $S_f(x)$. Для каждой подкоалиции $R\subset S_f(x)$ рассмотрим ассоциированную с $\overline\Gamma_f(x)$ игру с нулевой суммой $\overline{\overline\Gamma}_R(x,S_f(x))$ между двумя игроками: коалицией $R$, являющейся максимизирующим игроком (выигрыш коалиции $R$ равен сумме выигрышей игроков из $R$), и коалицией $S_f(x)\setminus R$, являющейся минимизирующим игроком (выигрыш коалиции $S_f(x)\setminus R$ равен выигрышу коалиции $R$ с обратным знаком). Можно показать, что выигрыш каждой коалиции $R$, определенный таким образом, не может превысить величины $v_f(x,S_f(x))$, поскольку по построению коалиция $S_f(x)$ получает выигрыш $v_f(x,S_f(x))$, используя наилучшие ответные стратегии против стратегий $\psi^*_{ix}(\cdot)$ игроков $i\not\in S_f(x)$. Пусть $v_f(x,R)$ будет значением игры $\overline{\overline\Gamma}_R(x,S_f(x))$. С помощью выигрышей $v_f(x,R)$, $R\subset S_f(x)$, вектор Шепли строится в игре $\Gamma_f(x)$ обычным способом.