§ 19. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ 2Х/2-ИГР
19.1 Рассуждения предыдущего параграфа показывают, что полный, перечисляющий всевозможные случаи анализ даже для такого простого класса игр, как 2 X 2-игры, оказывается достаточно нетривиальным. Пере&ход к играм большего формата существенно увеличил бы его громозд&кость. Естественно поэтому, что большинство алгорифмов решения игр должно иметь достаточно сокращенный вид и опираться на те или иные соображения, основанные на наглядности.
Кроме того, оказывается, что для перечисления всех ситуаций равнове&сия игры основную трудность составляет нахождение спектров оптималь&ных стратегий игроков, после чего остается сравнительно несложная и традиционная работа.
Для некоторых классов матричных игр представляет практический ин&терес графоанал итический метод решения, названный так пото&му, что в нем графически определяются качественные особенности решения (спектры оптимальных стратегий игроков, форма множеств оптимальных стратегий и т.д.), после чего, пользуясь знанием этих особенностей, полную характеристику решения игры можно найти уже чисто аналитически.
19.2. В основе описываемых далее графоаналитических методов лежит следующее соображение, основанное на том, что согласно теореме п. 15.1 в матричной игре ГА должно быть
Опишем способ нахождения оптимальных стратегий игрока 1 в тХп- игре. Рассмотрим для этого ш-мерную призму, основанием которой являет&ся (іт— 1)-мерный симплекс X стратегий игрока 1 в ГА, а вдоль образую&щей откладываются значения функции выигрыша Я (рис.
1.16). Графиком каждой из функции ХА./ является гиперплоскость, а графиком функции minXA.j — "минимальная" огибающая всех таких гиперплоскостей. Эта /
огибающая ограничивает сверху некоторое "обелискообразное" тело (см. рис. 1.17). Наибольшая Я-координата точек этого тела есть согласно (19.1) vA, а проекции этих точек на основание призмы — оптимальные стратегии игрока 1.
Разумеется, при больших значениях т такой способ неприменим, но при т = 2 он представляется достаточно практичным. Воспроизведем в деталях рассуждения в этом случае.
19.3. Рассмотрим игру, в которой игрок 1 имеет две чистые стратегии, а игрок 2 — произвольное число п чистых стратегий. Матрица выигрышей этой игры имеет вид
Фундаментальный симплекс смешанных стратегий игрока I представляет собой в рассматриваемом случае сегмент [0, 1 ], в котором координата точки, описывающей смешанную стратегию игрока 1, есть вероятность ис&пользования им первой чистой стратегии.
Пусть игрок 2 выбирает свою чистую стратегию/. Тогда выигрыш игро&ка 1 будет зависеть от выбранной им смешанной стратегии X, т.е. фактичес&ки от вероятности J выбора им первой чистой стратегии: XA.j + + 0-1) a2j.
Графически зависимость этого выигрыша от ? изображается прямой линией. Каждой чистой стратегии / игрока 2 соответствует своя прямая (рис. 1.18). Ясно, что если матрица (19.1) имеет одинаковые столбцы, то прямые, соответствующие таким стратегиям игрока 2, будут совпадать. Ради простоты будем все совпадающие столбцы считать одной стратегией. Графиком функции
minX47- = min + (1 - і і
будет нижняя огибающая всех прямых, соответствующих стратегиям игрока 2 (на рис. 1.18 она выделена жирной линией). Очевидно, этот гра&фик представляет собой ломаную, обращенную выпуклостью вверх.
Наи&высшая точка этой ломаной будет соответствовать тому значению, на котором достигается
max min XA.j = maxmingtf + (1 — ?) a2j).
X і
Абсцисса этой точки является, таким образом, оптимальной смешанной стратегией игрока 1, а ее ордината — значением игры. Если же таких выс&ших точек будет более одной, то, очевидно, огибающая ломаная будет иметь горизонтальный участок (рис. 1.19). Множество оптимальных стра&тегий игрока 1 будет состоять из всех абсцисс этих точек.
19.4. Описанное построение позволяет находить также оптимальные стратегии игрока 2. Здесь может представиться несколько различных случаев.
Пусть сначала огибающая ломаная имеет верхний горизонтальный учас&ток, соответствующий чистой стртегии /о игрока 2. Очевидно, это может быть лишь при alJ'o = а2/ . В этом случае игрок 2 имеет единственную оптимальную стратегию, которая является чистой.
Предположим теперь, что огибающая ломаная завершается "пиком".
Если абсциссой "пиковой" точки является 0 или 1 (рис. 1.20), то опти&мальная стратегия первого игрока — чистая (в случае, изображенном на рис. 1.20, это точка 0), а оптимальными стратегиями игрока 2 будут те его чистые стратегии, которые соответствуют прямым, подходящим к
пиковой точке с положительным наклоном. Разумеется, все их смеси также будут оптимальными стратегиями игрока 2.
Аналогичная картина наблюдается в том случае, когда "пик" имеет абсциссу 1.
Пусть, наконец, абсцисса пика отлична как от нуля, так и от единицы. Это значит, что в верхней „ее точке пересекается не менее двух прямых, из которых одна имеет положительный наклон, а другая — отрицательный (рис. 1.21). Пусть
H = a2jl +?(01/, H = a2ji + /2 я2/2)
— эти прямые. Если игрок 2 откажется от использования всех своих осталь&ных стратегий, то в получившейся 2 X 2-игре как значение, так и единст&венная оптимальная стратегия игрока 1 будут теми же, что и в первоначаль&ной игре. Это значит, что, пользуясь только двумя стратегиями j\ и /2, игрок 2 может воспрепятствовать игроку 1 получить больше, чем vA. Следовательно, оптимальная стратегия игрока 2 в исходной игре может быть получена путем смешивания только двух его чистых стратегий j\ и /2. Таким образом, оптимальная стратегия игрока 2 в новой 2 X 2-игре является оптимальной его стратегией и в исходной 2 X «-игре. Для ее вычис&ления можно воспользоваться формулой (18.12), которая в данном случае приобретает вид
ахіі-аІІ2 ~a2ji + а2к
Еще по теме § 19. ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ 2Х/2-ИГР: