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

Один такой пример был исследован фон Нейманом в статье [2]. Он состоит в следующем.

Пусть дана т х -матрица А = \\ аи . Игрок I имеет своими стратегиями клетки (ij) этой матрицы, а игрок II -ее строки (i) и столбцы (/). Если игрок I выбирает клетку (ij), то выигрыш его будет равен - при выборе игроком II строки i или столбца / и будет равен нулю в противном случае. В результате мы получаем матричную тп х (т + ?г)-игру.

Все игры такого типа можно интерпретировать следующим образом. Пусть игрок I прячется в одну из клеток матрицы А, а игрок II пытается угадать строку или столбец, на котором лежит эта клетка. Если игрок II угадывает, то он получает от игрока I число, стоящее в выбранной клетке матрицы.

Эта игра эквивалентна задаче линейного программирования, состоящей в максимизации суммы

2 VijXij 1

г, j

при неотрицательных х, подчиненных ограничениям

2 xtjl, 7 = 1, п,

2 хи<: 1, i = 1, ..., т.

Такая задача линейного программирования известна под названием задачи о назначениях : распределить оптимальным образом т лиц по п работам, если эффект, которого добивается лицо i на работе /, равен atj.

7. Если множествами стратегий игроков в антагонистической игре являются выпуклые многогранники (с конечным числом вершин) в конечномерных евклидовых пространствах, а функция выигрыша билинейна, то игра называется полиэдральной. Очевидно, внутренние точки многогранников стратегий, являющиеся как бы физическими смесями вершин, как стратегии приводят ввиду билинейности функции выигрыша к тем же выигрышам, что и соответствующие их вероятностью смеси, т. е. смешанные стратегии. Поэтому в полиэдральных играх можно ограничиться рассмотрением только тех чистых стратегий, которые расположены в вершинах многогранников стратегий. Тем самым полиэдральная игра превращается в конечную.

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

Связь матричных игр с линейным программированием позволяет решить поставленный вопрос, что и было сделано в работах Данцига [31, Чарнса [11 и Вульфа [1].

Пусть определяющая функцию выигрыша игры билинейная форма имеет т х гг-матрицу А (тем самым мы предполагаем, что многогранники стратегий игроков лежат соответственно в m-мерном и га-мерном векторных пространствах), а многогранники стратегий задаются своими гранями, т. е. системами неравенств вида ВХТ rg 6Г, YC с (здесь В есть к х ш-матрица, С - пХ /-матрица, а Ъ и с суть соответственно к- и Z-векторы; к и I, очевидно, означают числа граней в многогранниках стратегий). Тогда оптимальная стратегия игрока I получается как часть X оптимального решения (X, V) задачи линейного программирования

ВХТ г 5&г,

-AXT + CVT = 0,

и аналогично оптимальная стратегия игрока 2 -как часть У оптимального решения (У, U) задачи линейного программирования

YCc,

-YA-j-UB = 0,

£/ >0.

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

В качестве простого, но принципиально важного примера укажем на матричную игру, в которой игрок 1 по тем или иным соображениям, известным противнику, играет в любой своей смешанной стратегии первую чистую стратегию не реже, чем вторую, вторую не реже, чем третью, и т. д. Это значит, что всякая доступная для него смешанная стратегия X = . . ., хп) должна удовлетворять условиям

xt х2 .. . хп.

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

§ 2. БЕСКОНЕЧНЫЕ АНТАГОНИСТИЧЕСКИЕ ИГРЫ

1. Бесконечные антагонистические игры (как и все антагонистические игры) задаются путем указания пространств А и В стратегий двух игроков и функций выигрыша Н на произведении А хВ. Поэтому всякую такую игру естественно записывать как тройку (А, В, Н).

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

ника. По существу, тот же критерий рассматривает Хейбрехтс [1]; она же анализирует принцип, основанный на минимизации некоторой характеристики отклонения функции выигрыша от значения игры.

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

2. Как известно, в стратегических играх целесообразно использовать смешанные стратегии, т. е. вероятностные распределения на множествах чистых стратегий игроков. Однако для того, чтобы рассмотрение смешанных стратегий в игре (А, В, Н) имело смысл, необходимо существование выигрыша в условиях ситуации, образованной любой парой таких стратегий игроков, т. е. существование для любой пары смешанных стратегий F и G интеграла

J j Я (a, b)dF(a)dG(b). (3)

Этот вопрос является содержательным по следующей причине. Дело в том, что уже само рассмотрение вероятностной меры F на множестве А означает предварительное введение на А некоторой а-алгебры Ш подмножеств, измеримых в смысле F. Точно так же рассмотрение меры G связано с о-алгеброй 95 подмножеств В, измеримых в смысле G. Рассмотрение интеграла (3) связано с а-алгеброй подмножеств 6, порожденной всеми декартовыми произведениями вида К х L, где К £ 21 и L £ 93. Если функция выигрыша Н измерима относительно а-алгебры 6, то интеграл (3) существует.

3. Прообразом многочисленных теорем существования в бесконечных антагонистических играх явилась теорема Билля [1] о полной определенности игр на единичном квадрате с непрерывной функцией выигрыша. Фактически при доказательстве этой теоремы используется только то, что сегменты стратегий игроков в своей естественной евклидовой топологии являются условно компактными пространствами *), а функция выигрыша непрерывна в этой же топологии.

Таким образом, оказывается существенным, какая топология (или, в частности, какая метрика) принята на множестве стратегий игроков.

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

Вальд [2] вводит на множествах стратегий естественную метрику (которую можно было бы назвать также равномерной или чебышевской; сам Вальд называет ее иногда также метрикой Хелли), полагая в игре (А, В, Н) для любых а, а £ А

Ра (а\ а ) = sup Н (а, Ъ) - Н (а , Ъ) \

Ь£В

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