Методы решения конечных игр

Перед тем, как решать игру т×п, нужно, прежде всего, попытаться ее упростить, избавившись от лиш­них стратегий. Введем понятие «доминирования».

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

Первая стратегия “слабо доминирует” вторую (то есть первая стратегия “заведомо не хуже”, чем вторая) – когда первая стратегия при любых действиях партнеров не хуже второй стратегии и, по крайней мере, для одного варианта действий партнеров строго лучше.

Первая стратегия “сильно доминирует” вторую (то есть первая стратегия “заведомо лучше”, чем вторая) – когда первая стратегия при любых действиях партнеров лучше второй стратегии.

Если две стратегии доставляют одинаковые выигрыши при любых действиях партнеров, то они эквивалентны для игрока.

Если же из пары стратегий ни одна не слабо доминирует другую и они не эквивалентны, то они несравнимы.

Поясним сказанное примером. Пусть игра 5×5 за­дана матрицей таблицы 5.

Таблица 5

Прежде всего заметим, что в ней стратегия А₅ дубли­рует стратегию А₂, поэтому любую из них можно от­бросить. Отбрасывая А₅, замечаем, что в строке А₁ все выигрыши больше (или равны) соответствующим выигрышам строки А₄, значит А₁ доминирует над А₄. Отбросим А₄ и получим матрицу 3×5.

Перейдя к стратегиям игрока В замечаем, что в ней некоторые стратегии игрока В доми­нируют над другими: например, В₃ над В₄ и В₅, a В₁ - над стратегией В₂ , поскольку игрок В стремится отдать поменьше. Отбрасывая названные столбцы, получим игру 2×2.

В руководствах по теории игр обычно останавливаются на решении простейших игр 2×2, 2×х_п и m×2, которое допускает геометрическую интерпрета­цию, но мы этого делать не будем - рассмотрим решение в общем виде.

Пусть имеется игра т×п без седловой точки с мат­рицей (a,j) (см. таблицу 27.5).

Таблица 6

Допустим, что все выигрыши а_ij положительны (этого всегда можно добиться, прибавляя ко всем членам матрицы достаточно большое число М; от этого цена игры увеличится на М, а решение S^*_A, S^*_B не изменится). Если все а_ij положительны, то конечно, и цена игры, т. е. средний выигрыш при оптимальной стратегии, тоже положителен: v > 0.

Мы хотим найти решение игры, т. е. две оптималь­ные смешанные стратегии S*_A = (p₁, р₂, …, р_т), S*_B = (q₁, q₂,..., q_n), дающие каждой стороне максимально возможный для нее средний выигрыш (минимальный проигрыш).

Найдем сначала S*_A. Мы знаем, что если один из игроков (в данном случае это А) применяет свою оп­тимальную стратегию, то другой (B) не может улуч­шить свое положение, отступая от своей. Заставим противника (В) отступать от своей оптимальной стра­тегии, пользуясь чистыми стратегиями В₁, В₂, ..., В_п (а мы тем временем упорно держимся стратегии S_A). В любом случае наш выигрыш будет не меньше, чем v:

a₁₁ p₁ + a₂₁ p₂ +…+ a_m1 p_m ≥ v

a₁₂ p₁ + a₂₂p₂ +…+ a_m2 p_m ≥ v

………………………………..

a_1n p₁ + a_2n p₂ +…+ a_mn p_m ≥ v

Разделим полученные неравенства на положительную ве­личину v и введем обозначения

.

Тогда система условий примет вид

a ₁₁ х₁ + a₂₁ х₂ +…+ a_m1 х_m ≥ 1

a₁₂ х₁ + a₂₂х₂ +…+ a_m2 х_m ≥ 1

………………………………..

a_1n х₁ + a_2n х₂ +…+ a_mn х_m ≥ 1

где х₁, х₂,..., х_т - неотрицательные переменные.

В си­лу того, что p₁ + р₂ + … + p_m = 1, переменные x₁, х₂,..., х_т удовлетворяют условию

х₁ + х₂+ … + х_т = 1/v .

Но v есть не что иное, как наш гарантирован­ный выигрыш; естественно, мы хотим сделать его максимальным, а значит, величину 1/v - минимальной.

Таким образом, задача решения игры свелась мате­матической задаче линейного программирования: найти неотрицательные значения переменных х₁, х₂, ..., х_т такие, чтобы они удовлетворяли линейным ограничениям-неравенствам и обращали в минимум линейную функции этих пере­менных:

L = х₁ + х₂+ … + х_т → min

Оптимальная стратегия игрока В находится совершенно аналогично, с той разницей, что В стремится минимизировать, а не максимизировать выигрыш, а значит обратить в максимум величину - 1/v , а в ограничениях-неравенствах вместо знаков ≥ будут сто­ять знаки ≤.

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

Наиболее простым и наглядным является так называемый метод итераций (иначе - метод Брауна-Робинсон). Идея его в сле­дующем. Разыгрывается «мысленный эксперимент», в котором стороны А и В поочередно применяют друг про­тив друга свои стратегии, стремясь выиграть побольше (проиграть поменьше). Эксперимент состоит из ряда «партий» игры. Начинается он с того, что один из иг­роков (скажем, А) выбирает произвольно одну из своих стратегий A_i. Противник (B) отвечает ему той из своих стратегий B_j, которая хуже всего для А, т. е. обращает его выигрыш при стратегии A_i в минимум. Дальше сно­ва очередь А — он отвечает В той своей стратегией которая дает максимальный выигрыш при стратегии В противника. Дальше — снова очередь противника. Он отвечает нам той своей стратегией A_k, которая является наихудшей не для последней, примененной нами, стра­тегии А_к, а для смешанной стратегии, в которой до сих пор примененные стратегии А_i, А_к встречаются с равными вероятностями. И так далее: на каждом ша­ге итерационного процесса каждый игрок отвечает на очередной ход другого той своей стратегией, которая яв­ляется оптимальной для него относительно смешанной стратегии другого, в которую все примененные до cux пор стратегии входят пропорционально частотам их применения.

Вместо того чтобы вычислять каждый раз средний выигрыш, можно пользоваться просто «накоп­ленным» за предыдущие ходы выигрышем и выбирать ту свою стратегию, при которой этот накопленный вы­игрыш максимален (минимален). Доказано, что такой метод сходится: при увеличении числа «партий» сред­ний выигрыш на одну партию будет стремиться к цене игры, а частоты применения стратегий — к их вероят­ностям в оптимальных смешанных стратегиях игроков.

Рассмотрим применение итерационного метода на конкретном примере. Продемонстрируем его на примере игры 3×3 предыдущего параграфа (табли­ца 4). Чтобы не иметь дела с отрицательными чис­лами, прибавим к элементам матрицы таблицы 4 число 5 (см. таблицу 7); при этом цена игры увели­чится на 5, а решение. S*_A , S*_В не изменится.

Таблица 7

Начнем с произвольно выбранной стратегии игрока А,— например, со стратегии А₃. В таблице 8 приведе­ны первые 15 шагов итерационного процесса по методу Брауна — Робинсон. В первом столбце дан номер пар­тии (пары выборов) k, во втором — номер i выбранной в данной партии стратегии игрока А. В последующих трех столбцах — «накопленный выигрыш» за первые k партий при тех стратегиях, которые применяли игроки в предыдущих пар­тиях и при стратегиях В₁, В₂, Вз игрока В в данной партии (получается при­бавлением элементов соот­ветствующей строки к то­му, что было строкой вы­ше). Из этих накопленных выигрышей в таблице 8 подчеркнут минимальный (если их несколько, подчеркиваются все). Под­черкнутое число определяет ответный выбор иг­рока В в данной партии — он выбирает ту страте­гию, которая соответствует подчеркнутому числу (если их несколько, берется любая). Таким образом определя­ется номер j оптимальной (в данной партии) стратегии В (ставится в следующем столбце).

Таблица 8

В последующих трех столбцах дается накопленный выигрыш за k партий соответственно при стратегиях A₁, А₂, А₃ игрока А (получается прибавлением элементов столбца Bj к тому, что было строкой выше). В последних трех столбцах таблицы 8 даны: — нижняя оценка цены игры, равная минимальному накопленному выигрышу, деленному на число партий k; — верхняя оценка цены игры, равная максимальному накопленному выигрышу, деленному на k; v* — сред­нее арифметическое между ними (оно служит лучшей, чем нижняя и верхняя, приближенной оценкой цены игры).

График, построенный по результатам последнего столбца и представленный на рисунке 10 показывает, что величина v* незначительно колеблется около цены игры v = 5 (цена исходной игры была 0, но мы прибавили к элементам матрицы по 5).

Рисунок 10. График зависимости v* от номера итерации

Подсчитаем по таблице 8 частоты стратегий игроков. Получим:

р₁ = 4/15 = 0,266, р₂ = 7/15 = 0,468; р₃ = 4/15 = 0,266,

q₁ = 2/15 = 0,133, q₂ = 8/15 = 0,534, q₃ = 5/15 = 0,333,

что не так уж сильно отличается от вероятностей, вычисленных аналитически.

Очень важным преимуществом итерационного мето­да решения игр является то, что его трудоемкость сравнительно медленно возрастает с увеличением раз­мерности игры т× п, тогда как трудоемкость метода линейного программирования растет при увеличении размерности задачи гораздо быстрее.

Замечание: в теории игр счи­тается, что каждому игроку известны все возможные стратегии противника, неизвестно лишь то, какой именно из них он воспользуется в данной партии игры. В реальном конфликте это обычно не так: перечень возможных стратегий противника как раз неизвестен, и наилучшим решением в конфликтной ситуации неред­ко будет именно выйти за пределы известных против­нику стратегий, «ошарашить» его чем-то совершенно новым, непредвиденным!