23.2. Теорема. В выпуклой игре Г = < х, у, Я), где у G R, игрок 1 имеет оптимальную стратегию, являющуюся смесью не более чем п-\- 1 чистых.

Доказательство этой теоремы несколько напоминает по своей схеме доказательство теоремы из п. 10.1.

Вьшуклая игра Г является непрерывной, а потому (см. п. 11.2) вполне ограниченной. Следовательно, согласно теореме п. 8.1 она имеет значение Up, а при любом е > О игрок 1 имеет в ней еюптимальную стратегию с конечным спектром.

Пусть - такая стратегия, а ={xq,Xi, ..., } - ее спектр. Очевидно, для любого у GY должно быть

v-eSH{X,,y)=i: XAXi)H(Xi,y)u max Н(х,у).(23.1)

Положим для каждого х G х У€(Х{)={у: H(Xi,y)< v-e}.

В силу выпуклости функции Я(д:, •) каждое из множеств УеО) является

выпуклым (п. 21.3), Кроме того, из (23.1) следует, что П y(Xi) = ф.

1 = 0

Но пересечение конечного семейства выпуклых подмножеств может быть пустым лишь в том случае, когда пусто пересечение некоторого его подсемейства из п + I подмножеств *). Пусть для определенности х = { Xq , Xi, .. ., Хп) - набор стратегий Х( игрока 1, для которых множества у (л-) составляют это подсемейство. Для него должно быть

у-е max H(Xi,y) прилюбом у G у,

и тем боле

max Я(Х, у) для любого j G у,(23.2)

где - совокупность всех смесей стратегий из х.

Рассмотрим вспомогательную игру = (Х, у, Я), где при любых G

G Хе и у G Y

я, (X,,у) = 2 X,(xt)H(x,, у).(23.3)

1 = 0

На основании (23.3) игра Ге является вогнутой (см. п. 13.5).

Следовательно, по п. 13.2 она должна иметь некоторое значение и(Гс), для которого согласно (23.2) будет

i;-6i;(r,) = inf И(XIу), у

где X* - оптимальная стратегия игрока 1 в Г.

*) Это утверждение составляет содержание известной теоремы Хелли о вьшуклых множествах. См., например, Рокафеллар Р. "Вьшуклый анализ", М., "Мир", 1973, с. 203, или Данцер Л., Грюнбаум Б., Кли В. Теорема Хелли", М., "Мир", 1968.

Таким образом,

- е Н{Х*, у) при любом уу,

т.е. согласно п. 3.1 стратегия понимаемая как смешанная стратегия игрока 1 в исходной игре Г, является в ней его 2б-оптимальной стратегией (с (« + 1) -элементным спектром).

Возьмем теперь убывающую последовательность 6i > 62 > .... > >б„ > . .. ->0 и построим для каждого «=1,2,... б„-оптимальную стратегию Хп игрока 1 со спектром, состоящим из « + 1 стратегий. Для каждой такой стратегии мы имеем

Н(Хп,у) длявсех jGy. *(23.2)

Но множество всех таких смешанных стратегий составляет компакт (он является подмножеством компакта Х"). Поэтому из последовательности Xl, Хг, . .. можно вьщелить сходящуюся подпоследовательность с пределом Х©.

Замечая, что функция Я (Х„, >»), будучи суммой « + 1 непрерывных слагаемых, непрерывна по Х„, и переходя в (23.2) к пределу по п, мы получаем Vj. Я(Хо, у) для всех уу, т.е. Хо является искомой оптимальной стратегией игрока 1. □

23.3.Напомним еще раз (см. п. 14.1), что точками спектра оптимальной стратегии игрока I в игре Г могут быть только его существенные стратегии, т.е. решения уравнения

Н(х,у*)(23.3)

(где .у*, как и раньше - оптимальная стратегия игрока 2). Поэтому общая схема нахождения смешанной оптимальной стратегии игрока 1 должна состоять в перечислении корней уравнения (23.3) и нахождении таких их смесей X, которые были бы оптимальными стратегиями игрока 1 (в соответствии с доказанным достаточно рассматривать смеси не более чем п + 1 чистых стратегий).

23.4.Для нахождения "весов", с которыми корни уравнения (23.3) должны входить в оптимальную стратегию X, воспользуемся тем, что необходимым условием оптимальности X, очевидно, является условие приемлемости ситуации (Хд*) для игрока 2, т.е. неравенство

Н(Х,у*) Н(Х,у) привсех уу.(23.4)

Это значит, что на у* достигается наименьшее значение функции Я(Х, •). Как бьшо отмечено в пп. 12.9, 21.2, функция Я(X, •) является выпуклой. Следовательно, если эта функция дифференцируема (в том смысле, что она имеет первые частные производные по всем компонентам стратегии у игрока 2), то, согласно сказанному в п. 21.2, наименьшее ее значение должно быть аналитическим минимумом в той опорной гиперплоскости, в которой лежит стратегия(см. п. 22.4).

Формально это означает, что условиями для определения вероятностей чистых стратегий, составляющих смесь X, должна быть система из уравнений ЭЯ(Х, у)

-Х = 0 для / = а 1,...,г(23.5)

= У*139

и неравенств

----Х>0 для / = /• + !,...,я(23.6)

(здесь X - лагранжев множитель, соответствующий связи Хо + Xi + ... ... + Х„ = 1 между переменными).

Если выбрана такая комбинация ai+1 корней уравнения (23.3), что система соотношений (23.5) -(23.6) разрешима, то соответствующая смешанная стратегия X является оптимальной для игрока 1. В противном случае взятая комбинация корней уравнения (23.3) оптимальной смешанной стратегии игрока 1 составить не может, и следует перейти к другой такой комбинации. При этом теорема п. 23.2 гарантирует, что нужная комбинация из А1 + 1 корней уравнения (23.3) существует.

В следующих двух параграфах действие этого приема будет продемонстрировано на примере задачи, являющейся обобщением рассмотренной в §.§18и19.

§ 24*. ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ОГРАНИЧЕННЫХ РЕСУРСОВ в УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

24.1. Пусть к некоторой системе может быть предъявлено л видов требований, составляющих наборы чисел вида х= (xi, ..., Хп), которые могут быть произвольными элементами компактного множества х С Для удовлетворения таких наборов требований в системе имеются однородные ресурсы, общее количество которых примем равным единице. Долю ресурсов, предназначенных для удовлетворения требования х,-, обозначим через >,.. Таким образом,

У=(у:у=(Ух,...,Уп), У10, Д .!}.(24.1)

Заметим, что фактическая размерность множества у равна л - 1.

Мы будем рассматривать теоретико-игровой вариант задачи, при котором распределение ресурсов у приходится осуществлять, не зная, какой именно набор требований хЕх будет фактически к системе предъявлен.

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

Выполнение требования Xf при выделенных для этого ресурсах у,-достигается при некоторой "напряженности", возрастающей по Xf и убывающей по У/. Мы обозначим ее через /(х/,/). Эту функцию мы будем считать неотрицательной, строго возрастающей по Xf при любом допустимом значении у/ и строго убывающей и строго вьшуклой по у/ при любом

допустимом Х/.

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

Я(х,у)= шах Fi(x,y),(24.2)