Вычисление оптимальных стратегий в бесконечных играх

Описание бесконечной игры

Общие методы вычисления оптимальных стратегий в бесконечных играх в настоящее время еще мало разработаны. Поэтому рассмотрим только некоторые частные игры, которые представляют практический интерес и допускают сравнительно простой подход при вычислении оптимальных стратегий (Абчук В.А., Емельянов Л.А., Матвейчук Ф.А., Суздаль В.Г. "Введение в теорию выработки решений" В. издательство, Москва, 1972.) .

К бесконечным играм относятся модели конфликтных ситуаций, в которых каждая из противоположных сторон выбирает некоторые значения непрерывно меняющегося параметра (процентное соотношение распределения поисковых сил по районам поиска или бюджета между компаниями). В этом случае чистые стратегии игроков представляют выборы тех или иных чисел из некоторого интервала. Без потери общности можно считать, что эти стратегии являются точками отрезка единичной длины $$[0,1]$$. Тогда такую игру можно описать следующим образом.

Игрок I выбирает чистую стратегию $$x$$, где $$0\le x\le 1$$, а игрок II выбирает чистую стратегию $$y$$, где $$0\le y\le 1$$. Выбранные стратегии $$x$$ и $$y$$ определяют ситуацию $$(x,y)$$, в которой игрок I получает выигрыш $$K(x,y)$$. Множество ситуаций заполняет единичный квадрат (рис. 10.1).

По этому иногда такие игры называют играми на единичном квадрате. Функция, ставящая в соответствие каждой ситуации выигрыш, который получает игрок I, называется функцией выигрыша.

Предположим, что функция $$K(x,y)$$ имеет минимум по $$y$$ для $$0\le y \le 1$$ и максимум $$x$$ для $$0\le y \le 1$$. Тогда, если игрок I выберет $$x$$, то как бы ни действовал игрок II, первый может рассчитывать выиграть по меньшей мере

$$\mathop{min}\limits_y K(x,y)$$.

Поскольку игрок I может выбрать любое $$x$$ из интервала $$[0,1]$$, он может выбрать и такое $$x$$, при котором его выигрыш будет максимальным, то есть игрок I при надлежащим выборе $$x$$ гарантирует себе выигрыш не меньше чем

$$\mathop{max}\limits_x \mathop{min}\limits_y K(x,y)$$.

Аналогично игрок II может выбрать такое y, при котором игрок I не выиграет более чем

$$\mathop{min}\limits_y \mathop{max}\limits_x K(x,y)$$.

Следовательно, существует неравенство

$$\mathop{max}\limits_x \mathop{min}\limits_y K(x,y)\le \mathop{min}\limits_y \mathop{max}\limits_x K(x,y)$$

Если в (9.1.) имеет место равенство, то есть

$$\mathop{max}\limits_x \mathop{min}\limits_y K(x,y)= \mathop{min}\limits_y \mathop{max}\limits_x K(x,y)$$,

то функция выигрыша $$K(x,y)$$ имеет седловую точку, то есть существуют такие $$x_0$$ и $$y_0$$, при которых $$K(x_0,y_0)$$ является одновременно минимальным по $$y$$ и максимальным по $$x$$. Очевидно, что в этом случае

$$и \left \begin{array}{ccc} K(x_0,y) \ge K(x_0,y_0)\text{ для }0\le y\le 1\\ K(x,y_0) \le K(x_0,y_0) \text{ для }0\le x\le 1 \end{array} \right\rangle$$

Если при любых $$x$$ и $$y$$ пара $$(x_0,y_0)$$ удовлетворяет неравенствам (2), то эта пара называется решением игры в чистых стратегиях. Соответственно этому игроки должны применять чистые стратегии $$x_0$$ и $$y_0$$, которые называются оптимальными. При

$$\mathop{max}\limits_x \mathop{min}\limits_y K(x,y) < \mathop{min}\limits_y \mathop{max}\limits_x K(x,y)$$

игроки должны применять смешанные стратегии.

Смешанная стратегия в бесконечной игре на единичном квадрате представляет собой случайный выбор числа из интервала $$[0,1]$$, то есть если задана смешанная стратегия, то это определяет закон распределения, в соответствии с которым игрок выбирает число из интервала $$[0,1]$$. Для математического описания такого закона распределения удобно пользоваться функцией распределения.

Предположим, что игрок I выбирает число $$x$$ из интервала $$[0,1]$$ согласно функции распределения $$F(x)$$. Тогда для любой чистой стратегии $$y$$ игрока II математическое ожидание выигрыша $$M(F,y)$$, если оно существует, будет равно

$$\int\limits_{0}^{1}K(x,y)dF(x)$$.

Пусть игрок II выбирает число $$y$$ из интервала $$[0,1]$$ согласно функции распределения $$G(y)$$. Тогда математическое ожидание выигрыша $$M(F,G)$$, если оно существует, будет равно

$$\int\limits_{0}^{1}\int\limits_{0}^{1} K(x,y)dF(x)dG(y)$$.

Предположим, что существует

$$\mathop{max}\limits_F \mathop{min}\limits_G M(F,G)$$ и $$\mathop{max}\limits_G \mathop{min}\limits_F M(F,G)$$

Выражение $$\mathop{min}\limits_G M(F,G)$$ означает, что определяется такой вид функции распределения $$G(y)$$, который минимизирует выражение $$M(F,G)$$ при заданной функции распределения $$F(x)$$. Тогда выполняется следующее неравенство:

$$\mathop{max}\limits_F \mathop{min}\limits_G M(F,G) \le \mathop{max}\limits_G \mathop{min}\limits_F M(F,G)$$.

В теории игр доказывается, что, если функция выигрыша непрерывна по $$x$$ и $$y$$, то

$$\mathop{max}\limits_F \mathop{min}\limits_G M(F,G) = \mathop{max}\limits_G \mathop{min}\limits_F M(F,G)$$

Общее значение обеих частей этого равенства называется значением игры и обозначается $$\nu$$.

Если существуют такие $$x_0$$ и $$y_0$$, что выполняются неравенства (10.2.), то значение игры равно $$K(x_0,y_0)$$.

Если выполняется (10.4.), то у игрока I имеется такая стратегия (функция распределения) $$F^*(x)$$, что математическое ожидание выигрыша будет

$$M(F,G^*)\ge\nu$$

для любой стратегии игрока II $$G(y)$$.

Аналогично, если выполняется (10.4.) , то существует функция распределения $$G^*(y)$$ игрока II, при использовании которой математическое ожидание выигрыша будет

$$M(F,G^*)\le\nu$$

для любой стратегии игрока I $$F(x)$$.

Стратегии $$F^*(x)$$ и $$G^*(y)$$ называются оптимальными стратегиями игроков I и II, соответственно. Пара $$(F^*,G^*)$$ называется решением игры в смешанных стратегиях, а значение игры равно

$$M(F^*,G^*)$$.

Свойства оптимальных стратегий

Математическое ожидание выигрыша игрока I, применяющего чистую стратегию против оптимальной смешанной стратегии игрока II, не может быть больше значения игры.

Математическое ожидание выигрыша игрока I, применяющего оптимальную смешанную стратегию против чистой стратегии игрока II, не может быть меньше значения игры.

У каждого игрока имеется по меньшей мере одна чистая стратегия, применение которой против оптимальной стратегии другого игрока дает математическое ожидание выигрыша, равное значению игры.

Вычисление оптимальных смешанных стратегий в играх на единичном квадрате

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

Функция $$K(u)$$ называется выпуклой по $$u$$ на интервале $$[0,1]$$, если

$$K[\lambda u_1 + (1-\lambda)u_2]\le \lambda K(u_1) +(1-\lambda)K(u_2);\\ (u_1,u_2\in u;0 \le \lambda\le 1)$$.

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

Если в выражении 9.5. имеет место строгое неравенство при $$u_1\ne u_2$$ и $$0 < \lambda < 1 $$, то функция $$K(u)$$ называется строго выпуклой. График строго выпуклой функции всегда проходит ниже отрезка прямой, проведенной между любыми его точками. (См. рисунок (10.2).)

В некотором смысле обратным понятию выпуклости является понятие вогнутости.

Функция $$K(u)$$ называется вогнутой по $$u$$ на интервале $$[0,1]$$, если

$$K[\lambda u_1 + (1-\lambda)u_2]\ge \lambda K(u_1) +(1-\lambda)K(u_2);\\ (u_1,u_2\in u;0 \le \lambda\le 1)$$.

Если в выражении 9.6. имеет место строгое неравенство при $$u_1\ne u_2$$ и $$0 < \lambda < 1$$, то функция $$K(u)$$ называется строго вогнутой. График такой функции всегда проходит выше отрезка прямой, проведенной между любыми его точками (рис. 10.3).

Свойство выпуклости или строгой выпуклости функции выигрыша $$K(x,y)$$ по $$y$$ для любого $$x$$ устанавливается путем вычисления ее вторых производных по $$y$$ (если они существуют):

при $$\frac{\partial^2 k}{\partial y^2}\ge 0$$ функция $$K(x,y)$$ является выпуклой по $$y$$ ;

при $$\frac{\partial^2 k}{\partial y^2} > 0$$ функция $$K(x,y)$$ является строго выпуклой по $$y$$.

Допустим, что функция выигрыша $$K(x,y)$$ при любом является строго выпуклой по $$y$$ и что игра имеет решение $$(F^*,G^*)$$.

Предположим, что игрок I выбирает число $$x$$ из интервала $$[0,1]$$ согласно функции распределения $$F^*(x)$$. Тогда для любой чистой стратегии $$y$$ игрока II

математическое ожидание выигрыша $$M(F^*,y)$$ будет равно

$$\int\limits_{0}^{1} K(x,y)dF^*$$.

Функция $$M(F^*,y)$$ является строго выпуклой , так как

$$\frac{\partial^2 M(F^*,y)}{\partial y^2} = \int\limits_{0}^{1} \frac{\partial^2 K(x,y)}{\partial y^2} dF^*(x) > 0$$

Поэтому $$M(F^*,y)$$ принимает минимальное значение в одной точке. Следовательно, оптимальной стратегией игрока II является чистая стратегия $$y^*$$, при которой достигается минимум функции $$M(F^*,y)$$. Такую стратегию можно задать одноступенчатой функцией распределения

$$I_{y_1}(y)=\left \begin{array}{aaa} 1\text{ при }y > y_1;\\ 0\text{ при }y < y_1. \end{array} \right$$

Значение игры в этом случае равно

$$\mathop{min}\limits_y \mathop{max}\limits_x K(x,y) = \mathop{max}\limits_x K(x,y^*)$$,

а константа $$y_1$$

есть решение уравнения

$$\nu=\mathop{max}\limits_x K(x,y^*)$$.

Аналогично для функции выигрыша $$K(x,y)$$, строго вогнутой по $$x$$ для любого $$y$$, игрок I имеет единственную оптимальную стратегию, являющуюся одноступенчатой функцией $$I_{x_1}(x)$$. Значение игры $$\nu$$ в этом случае равно

$$\mathop{max}\limits_x \mathop{min}\limits_y K(x,y) = \mathop{min}\limits_y K(x^*,y)$$,

а константа $$x_1$$ есть решение уравнения

$$\nu=\mathop{min}\limits_y K(x_1,y)$$.

Заметим, что свойство вогнутости или строгой вогнутости функции выигрыша $$K(x,y)$$ по $$x$$ для любого $$y$$ устанавливается путем вычисления ее вторых производных по $$x$$, если они существуют:

при $$\frac{\partial^2 k}{\partial x^2}\le 0$$ функция $$K(x,y)$$ является вогнутой по $$x$$ ;

при $$\frac{\partial^2 k}{\partial x^2} < 0$$ функция $$K(x,y)$$ является строго вогнутой по $$x$$.

Оптимальные смешанные стратегии игрока I, если функция выигрыша $$K(x,y)$$ строго выпукла по $$y$$, и игрока II, если функция выигрыша $$K(x,y)$$ строго вогнута по $$x$$, определяются на основании следующих теорем ( доказательство которых дается в Мак-Кенси Д. Введение в теорию игр. М. , Изд-во физико-математической литературы, 1960.).

Т е о р е м а 1. Пусть $$K(x,y)$$ — функция выигрыша бесконечной игры на единичном квадрате, непрерывная по двум по двум переменным и строго выпуклая по $$y$$ для любого $$x$$. Пусть $$I_{y_1}(y)$$ — единственная оптимальная стратегия игрока II, и $$\nu$$ — значение игры. Если $$y_1=0$$ или $$y_1=1$$, то у игрока I имеется оптимальная стратегия $$I_{b}$$, где константой b может быть любое число, удовлетворяющее условиям:

$$0\le b\le 1;\\ K(b,y_1)=\nu$$

$$\frac{\partial k(b,y_1)}{\partial y} \left< \begin{array}{ccc} \ge 0 \text{ для }y_1=0;\\ \le 0 \text{ для }y_1=1. \end{array}\right$$

Если $$0 < y_1 < 1$$, то у игрока I имеется оптимальная стратегия следующего вида:

$$F^*(x)=\alpha I_{x_1}(x)+(1-\alpha)I_{x_2}(x)$$,

где $$\alpha, x_1$$ и $$x_2$$ — любые числа, удовлетворяющие условиям:

$$0\le x_1 \le 1; \le x_2 \le 1; \le \alpha \le 1;\\ K(x_1,y_1)=\nu; K(x_2,y_1)=\nu;\\ \frac{\partial k(x_1,y_1)}{\partial y} \ge 0 \ge \frac{\partial k(x_2,y_1)}{\partial y};\\ \alpha \frac{\partial k(x_1,y_1)}{\partial y} +(1-\alpha) \frac{\partial k(x_2,y_1)}{\partial y} =0$$.

Т е о р е м а 2. Пусть $$K(x,y)$$ — функция выигрыша бесконечной игры на единичном квадрате, непрерывная по двум по двум переменным и строго вогнутая по $$x$$ для любого $$y$$. Пусть $$I_{x_1}(x)$$ — единственная оптимальная стратегия игрока I, и $$\nu$$ — значение игры. Если $$x_1=0$$ или $$x_1=1$$, то у игрока II имеется оптимальная стратегия $$I_b$$, где константой b может быть любое число, удовлетворяющее условиям:

$$0\le b\le 1;\\ K(x_1,b)=\nu$$

$$\frac{\partial k(x_1,b)}{\partial y} \left< \begin{array}{ccc} \le 0 \text{ для }x_1=0;\\ \ge 0 \text{ для }x_1=1. \end{array}\right$$

Если $$0 < x_1 < 1$$, то $$у$$ игрока II имеется оптимальная стратегия следующего вида:

$$G^*(x)=\alpha I_{y_1}(x)+(1-\alpha)I_{y_2}(y)$$,

где $$\alpha, y_1$$ и $$y_2$$ — любые числа, удовлетворяющие условиям:

$$0\le y_1 \le 1; \le y_2 \le 1; \le \alpha \le 1;\\ K(x_1,y_1)=\nu; K(x_1,y_2)=\nu;\\ \frac{\partial k(x_1,y_1)}{\partial x} \ge 0 \ge \frac{\partial k(x_1,y_2)}{\partial x};\\ \alpha \frac{\partial k(x_1,y_1)}{\partial x} +(1-\alpha) \frac{\partial k(x_1,y_2)}{\partial x} =0$$.

Из теорем 1 и 2 вытекает, что оптимальная стратегия игрока I для функции выигрыша, строго выпуклой по $$y$$, есть чистая стратегия, представляющая одну из точек интервала $$[0,1]$$, если $$y^*=0$$ или 1. Если $$0 < y^* < 1$$, то оптимальная стратегия игрока I состоит в случайном выборе одного из двух значений $$x_1,x_2$$ по закону двухступенчатой функции распределения вида 9.6. Для функции выигрыша, строго вогнутой по $$x$$, оптимальная стратегия игрока II есть чистая стратегия, представляющая одну из точек интервала [0,1], если $$x^*=0$$ или $$x^*=1$$. Если $$0 < x^* < 1$$, то оптимальная стратегия игрока II

Состоит в случайном выборе одного из двух значений $$y_1,y_2$$ по закону двухступенчатой функции вида (10.8.)

Реализация смешанной стратегии вида (10.6) или (10.8.) заключается в том, что с помощью случайного механизма выбирается число $$\alpha^*$$ из интервала $$[0,1]$$ и $$x(y)$$ принимает значение $$x_1(y_1)$$, если $$\alpha^* < \alpha$$ и $$x_2(y_2)$$, если $$\alpha^* \ge \alpha$$.

Решение игры на единичном квадрате с выпуклой (вогнутой) функцией выигрыша можно найти аналогично решению игры, функция выигрыша которой является строго выпуклой (вогнутой). Однако в этом случае оптимальная стратегия игрока I, указанная в теореме 9.2. (или игрока I в теореме 9.1.), вообще уже не является единственной.

Игры на единичном квадрате с выбором момента времени

Другим важным классом игр на единичном квадрате, для которых можно найти решение, являются игры с выбором момента времени. В этих играх чистой стратегией каждого игрока является выбор момента времени для выполнения определенных действий. Например в военном деле к таким действиям относится применение оружия каждым из противников друг против друга. Поэтому такие ситуации называются дуэльными или просто дуэлями . Характерной особенностью дуэли является то, что каждый из противников стремится по возможности задержать свой выстрел, так как вероятность поражения с течением времени увеличивается. Однако задержка в применении своего оружия имеет разумные пределы, обусловленные тем, что противник может применить свое оружие раньше и выиграть дуэль.

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

Дуэльная ситуация хорошо моделируется антагонистической бесконечной игрой на единичном квадрате, если считать, что стратегиями игроков являются числа $$x,y \in [0,1]$$, которые можно интерпретировать как нормированные моменты времени применения оружия каждым из игроков.

Функция выигрыша в ситуации $$(x,y)$$ такой игры представляет вероятности поражения игроком I игрока II и определяется следующим соотношением:

$$K(x,y)= \left< \begin{array}{ccc} L(x,y) \text{ если }x < y;\\ F(x) \text{ если }x = y;\\ N(x,y) \text{ если }x > y; \end{array}\right$$

где $$L(x,y)$$ — вероятность поражения игроком I игрока II, если игрок I упреждает игрока II в применении оружия;

$$F(x)$$ — вероятность поражения игроком I игрока II, если оба игрока применяют оружие одновременно;

$$N(x,y)$$ — вероятность поражения игроком I игрока II, если игрок II упреждает игрока I в применении оружия.

При задании функции выигрыша принимается, что если игрок II предполагает применить свое оружие в некоторый фиксированный момент времени $$y$$, то игрок I

увеличивает свой выигрыш, выжидая сколько возможно, но действуя все же раньше игрока II. Если же игрок I применяет свое оружие после применения игроком II, то он может проиграть при условии, что оружие игрока II достигает цели. В случае же промаха игрока II шансы на успех у игрока I возрастают со временем. Математически это выражается тем, что функции $$L(x,y)$$ и $$N(x,y)$$ монотонно убывают по $$y$$ для каждого $$x$$.

Игры с выбором момента времени не обязательно включают по одному действию с каждой стороны, они могут содержать и повторные действия. Кроме того, как и во всех играх, противники могут иметь различную информацию о действиях каждого из них. Решение подобных игр представляет большую сложность, и поэтому рассмотрим только простейший класс, когда каждый из двух противников располагает одним выстрелом, при котором вероятность поражения монотонно возрастает со временем. Кроме того, в этом классе игр действия каждого из игроков, а также их последствия немедленно становятся известными противнику. Поэтому такую игру можно назвать игрой с выбором момента времени в условиях полной информации. Так называемые шумные дуэли являются примером игр этого класса.

В шумной дуэли каждой из двух игроков имеет возможность произвести только один выстрел. По звуку (шуму) каждый игрок знает, что его противник выстрелил. Наличие информации о действиях противника дает возможность считать, что математическое ожидание выигрыша $$L(x,y)$$, является функцией только $$x$$, а $$N(x,y)$$, — функцией только $$y$$.

Пусть вероятность поражения $$P_1(x)$$ игрока II является непрерывной функцией, которая монотонно возрастает по $$x, P_1(0)=0, P_1(1)=1$$. Аналогично вероятность поражения $$P_2(y)$$ игрока I также является непрерывной функцией, которая монотонно возрастает по $$y, P_2(0)=0, P_2(1)=1$$.

Будем считать, что если игрок I поражает игрока II, то выигрыш игрока I

равен 1; если игрок II поражает игрока I, то выигрыш игрока I равен –1; если ни один из игроков не поражен или поражены оба игрока, то выигрыш игрока I равен 0.

В общем виде математическое ожидание выигрыша игрока I, когда игроки используют чистые стратегии $$x$$ и $$y$$, равно (10.10.)

Определим $$K(x,y)$$ следующим образом. При $$x < y$$ первым применяет оружие игрок I, и вероятность того, что он поразит игрока II, равна $$P_1(x)$$, и выигрыш игрока I будет равна $$+1$$. В случае промаха, вероятность которого равна $$1-P_1(x)$$, игрок II применит свое оружие в момент $$y=1$$ и поразит игрока I, выигрыш которого тогда будет равен –1. Следовательно,

$$L(x,y)=P_1(x)+(-1)[1-P_1(x)]=2P_1(x)-1.\\ F(x,y)=P_1(x)+(-1)[1-P_2(x)][1-P_1(x)]=P_1(x)-P_2(x).\\ N(x,y)=(-1)P_2(y)+[1-P_2(y)]=1-2P_2(y)-1$$.

Таким образом, математическое ожидание выигрыша игрока в рассматриваемой игре с выбором момента времени будет

$$K(x,y)= \left< \begin{array}{ccc} 2P_1(x)-1 \text{ если }x < y;\\ P_1(x)-1 \text{ если }x = y;\\ 1-2P_2(y) \text{ если }x > y; \end{array}\right$$

На основании того, что $$P_1(x)$$ и $$P_2(y)$$ увеличиваются с увеличением $$x$$ и $$y$$ соответственно, можно записать:

$$\mathop{max}\limits_x \mathop{min}\limits_y K(x,y) = \mathop{max}\limits_x \mathop{min}\limits_y [2P_1(x)-1,P_1(x)-P_2,1-2P_2(x)]$$

Для x, которые удовлетворяют неравенству

$$P_1(x)+P_2(x)\ge 1$$,

Действительно, на основании 9.12. запишем:

$$P_2(x)\ge 1-P_1(x); -P_2(x)\le P_1(x)-1;\\ P_1(x)-P_2(x)\le 2P_1(x)-1.\\ P_1(x) \ge 1-P_2(x); P_1(x)-P_2(x)\ge 1-2P_2(x)$$.

Следовательно,

$$1-2P_2(x)\le P_1(x)-P_2(x)\le 2P_1(x)-1$$.

Для $$x$$, которые удовлетворяют равенству

$$P_1(x)+P_2(x)=1\\ min[2P_1(x)-1,P_1(x)-P_2(x),1-2P_2(x)]=P_1(x)-P_2(x)$$

так как на основании 9.13.

$$1-2P_2(x)=P_1(x)-P_2(x)=2P_1(x)-1$$.

Для $$x$$, которые удовлетворяют неравенству

$$P_1(x)+P_2(x)\le 1,\\ min[2P_1(x)-1,P_1(x)-P_2(x),1-2P_2(x)]=1P_1(x)-1$$

так как на основании 9.14.

$$P_1(x)-1\le P_1(x)-P_2(x)\le 1-2P_2(x)$$.

Пусть $$x^*$$ определяется уравнением

$$P_1(x^*)+P_2(x^*)=1$$.

Отсюда

$$\mathop{max}\limits_x \mathop{min}\limits_y [2P_1(x)-1,P_1(x)-P_2(x).1-2P_2(x)]=P_1(x^*)1P_2(x^*)$$.

Следовательно,

$$\mathop{max}\limits_x \mathop{min}\limits_y K(x,y)=P_1(x^*)-P_2(x^*)$$,

где $$x^*$$ удовлетворяет уравнению

$$P_1(x^*)+P_2(x^*)=1$$

Аналогично можно показать, что

$$\mathop{max}\limits_xy \mathop{min}\limits_x K(x,y)=P_1(y^*)-P_2(y^*)$$,

где $$y^*$$ удовлетворяет уравнению

$$P_1(y^*)+P_2(y^*)=1$$

Следовательно, функция выигрыша $$K(x,y)$$ имеет седловую точку ( $$x^*,y^*)$$. Отсюда игрок I имеет чистую оптимальную стратегию $$x^*$$, определяемую из уравнения (10.15.) , игрок II — чистую оптимальную стратегию $$y^*$$, определяемую из уравнения (10.16.), а значение игры равно

$$\nu=P_1(x^*)-P_2(x^*)=P_1(y^*)-P_2(y^*)$$

Таким образом, пара $$(x^*,y^*)$$ является решением игры с выбором момента времени и выражает равновесие между желанием задержки и опасностью промедления.

Задача

Распределение атакующих единиц между двумя объектами ( Дрешер М. Стратегические игры. М., "Советское радио" ,1964.).

Предположим, что планируется атака двух населенных пунктов $$T_1$$ и $$T_2$$, имеющих соответственно важности (ценности) $$k_1$$ и $$k_2$$. Пусть противники, один из которых атакует (игрок I), а второй обороняется (игрок II), имеют по $$N$$ боевых единиц и пусть $$N$$ достаточно велико.

Эти единицы могут быть распределены следующим образом. Игрок I может выделить $$n_1$$ единиц для атаки объекта $$T_1$$ и $$N-n_1$$ единиц для атаки объекта $$T_2$$. В свою очередь игрок II может выделить $$n_2$$ единиц для обороны объекта $$T_1$$ и $$N-n_2$$ единиц для обороны объекта $$T_2$$. При этом будем считать, что одна единица игрока II поражает только одну единицу игрока I.

Допустим, что критерий эффективности игрока I пропорционален числу атакующих единиц, достигших объекта, и ценности объекта.

Обозначим

$$x=\frac{n_1}{N}\text{ и }y=\frac{n_2}{N}$$.

Тогда чистыми стратегиями игроков будут числа из интервала $$[0,1]$$ вида (10.18.) Следовательно, необходимо решать матричную игру больших размеров. Однако, если N достаточно велико, можно полагать, что игрок I выбирает любое $$x\in [0,1]$$, а игрок II — любое $$y\in [0,1]$$.

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

$$K(x,y)= \left< \begin{array}{ccc} Nk_1(x-y) \text{ если }x \ge y;\\ Nk_2(y-x) \text{ если }x \le y; \end{array}\right$$

Путем построения графиков функции $$K(x,y)$$ для фиксированных $$x$$ легко убедиться, что эта функция выпукла по $$y$$ (рис. 10.6).

Следовательно,

$$\nu = \mathop{min}\limits_y \mathop{max}\limits_x \left< \begin{array}{ccc} Nk_1(x-y) \text{ если }x \ge y;\\ Nk_2(y-x) \text{ если }x \le y. \end{array}\right $$

Из рассмотрения функции $$K(x,y)$$ для различных фиксированных значений $$y$$

можно убедиться, что если

$$0\le y \le \frac{1}{2}$$, то

$$\mathop{max}\limits_x K(x,y)=Nk_1(1-y)$$,

а если $$\frac{1}{2} < y \le 1$$, то

$$\mathop{max}\limits_x K(x,y)=Nk_2y$$.

Отсюда

$$\mathop{max}\limits_x K(x,y)=max[Nk_1(1-y),Nk_2y]$$.

Итак,

$$\nu=\mathop{min}\limits_y max[Nk_1(1-y),Nk_2y]$$.

Из рассмотрения функции

$$max[Nk_1(1-y),Nk_2y]$$

видно, что она принимает минимальное значение при $$y^*$$, которое удовлетворяет уравнению

$$Nk_1(1-y^*)=Nk_2y^*$$

Из уравнения (10.21.) находим

$$y^*=\frac{k_1}{k_1+k_2}$$.

Тогда на основании (10.20.)

$$\nu=\frac{k_1k_2}{k_1+k_2}N$$.

Следовательно, с учетом (10.18.) оптимальная стратегия игрока II состоит в выделении $$\frac{k_1}{k_1+k_2}N$$ единиц для обороны объекта $$T_1$$ и $$\frac{k_2}{k_1+k_2}N$$ единиц для обороны объекта $$T_2$$.

Для определения оптимальной стратегии игрока I воспользуемся теоремой 1.

Находим

Составляем уравнение

$$K(x,\frac{k_1}{k_1+k_2}N)=\frac{k_1k_2}{k_1+k_2}N$$,

то есть, если x\ge y, то

$$Nk_1(x-\frac{k_1}{k_1+k_2}N)=\frac{k_1k_2}{k_1+k_2}N$$,

если $$x\le y$$, то

$$Nk_2(\frac{k_1}{k_1+k_2}N-x)=\frac{k_1k_2}{k_1+k_2}=\frac{k_1k_2}{k_1+k_2}N$$.

Уравнение (10.22.) имеет решение $$x=1$$, а уравнение (10.23.) имеет решение $$x=0$$.

Так как

$$\frac{\partial k(0,y^*)}{\partial y} >0; x_1=0$$

и

$$\frac{\partial k(1,y^*)}{\partial y} <0; x_2=1$$,

то на основании теоремы(10.1.) игрок I имеет оптимальную стратегию вида

$$F^*(x)=\alpha I_0(x)+(1-\alpha)I_1(x)$$.

Для определения $$\alpha$$ составляем следующее уравнение:

$$\alpha Nk_2+(1-\alpha)(-Nk_1)=0$$

Уравнение (10.24.) имеет решение:

$$\alpha=\frac{k_1}{k_1+k_2}$$.

Таким образом, оптимальная стратегия игрока I заключается в том, чтобы нанести удар всеми силами по объекту $$T_1$$ или $$T_2$$, руководствуясь случайным выбором, то есть выбирая объект $$T_1$$ с вероятностью $$\frac{k_2}{k_1+k_2}$$ и $$T_2$$ с вероятностью $$\frac{k_1}{k_1+k_2}$$.

Итак, на основании решения рассмотренной игры получены рекомендации, согласно которым обороняющаяся сторона может свои силы распределить заранее вполне определенным образом – назначить $$\frac{k_1}{k_1+k_2}$$ часть сил для обороны объекта $$T_1$$ и $$\frac{k_2}{k_1+k_2}$$ часть для обороны объекта $$T_2$$.

Нападающая сторона должна случайным образом сосредоточить все силы для атаки объекта $$T_1$$ или $$T_2$$ соответственно их важности.

Например, если объект $$T_1$$ в два раза важнее объекта $$T_2$$, то объект $$T_1$$ должны оборонять $$\frac{2}{3}$$ всех имеющихся сил. В свою очередь, нападающая сторона должна атаковать этот объект всеми силами с вероятностью $$\frac{1}{3}$$.