11], состоит в осуществлении процесса последовательных приближений. Его можно интерпретировать также как экспериментальное нахождение оптимальной стратегии в процессе осуществления матча, отдельные партии которого состоят в проведении матричной игры, причем в каждой партии каждый игрок фиксирует частоты выбора противником чистых стратегий за время, прошедшее от начала матча, и, принимая их за вероятности в смешанной стратегии, выбирает свою чистую стратегию, наиболее благоприятную против этой смешанной.
Оценка сходимости описанного процесса, данная Шапиро [1], показывает, что он сходится весьма медленно: погрешность в определении
1
значения п X етг-игры за t шагов имеет порядок t nm 2.
5. Как пишет Гейл [1], «одним из самых удивительных событий, связанных с появлением современной теории линейных экономических моделей, явилось одновременное, но независимое развитие теории линейного программирования, с одной стороны, и теории игр, с другой, и выявившаяся затем тесная связь между этими двумя предметами». По свидетельству Данцига [1], на связь между линейным программированием и теорией матричных игр указывал еще Дж. фон Нейман в 1947 г. Затем этими вопросами занимались Гейл, Кун и Таккер [1]. В наиболее естественной форме эквивалентность пары двойственных друг другу задач линейного программирования и матричной игры дается теоремой, принадлежащей Данцигу и Брауну и опубликованной Данцигом [2].
Рассмотрим пару двойственных задач линейного программирования
АХТВТУ YAC,
CXT->max, 75r-min
(ХО), (УО).
Для того чтобы векторы Х° и У0 являлись оптимальными решениями этих задач, необходимо и достаточно, чтобы вектор
(tX\ tY°, t)
был оптимальной стратегией одного из игрокоз в игре с матрицей
О -А Вт\ Ат О -Ст\ -В с о /
(поскольку эта матрица кососимметрична, неважно, о каком именно игроке идет речь), причем t > 0.
Эквивалентность решения матричной игры решению задач линейного программирования позволяет применять к решению первых все приемы, разработанные для решения вторых. В частности, оптимальные стратегии в матричных играх можно находить при помощи известного симплекс-метода. Весьма практичный способ решения матричной игры при помощи линейного программирования предложил Таккер [1].
6. При установленном соответствии между матричными играми и парами двойственных задач линейного программирования каждому классу матричных игр соответствует класс задач линейного программирования, и наоборот. При этом может оказаться, что классу игр, естественно очерченному в смысле содержательной интерпретации составляющих его игр, соответствует класс пар задач линейного программирования, также достаточно естественно очерченный, но уже в иной, «линейно-про-
граммной» интерпретации. Примеры такого соответствия между классами могут оказаться весьма полезными потому, что отдельные факты, достаточно запутанные в одном из этих классов, могут быть интуитивно вполне ясными в другом.
Один такой пример был исследован фон Нейманом в статье [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] предложил наилучшее использование ошибок против-