Итеративный метод приближенного решения матричных игр

Решение сравнительно сложных матричных игр вручную (без компьютерных программ) путем приведения их к задачам линейного программирования в большинстве случаев представляет собой достаточно трудоемкий и громоздкий процесс. Но даже при компьютерном решении задачи линейного программирования могут возникнуть сложности для матриц больших размерностей. Поэтому при развитии теории игр возникла потребность в разработке методов приближенного решения матричных игр. Разработка этих методов была оправдана также тем, что часто в практических задачах нет необходимости находить точное решение матричной игры. Достаточно найти приближенное решение, которое дает средний платеж, близкий к цене игры, и приближенные оптимальные стратегии игроков [7].

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

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

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

В теории игр разработано несколько таких методов, из которых самым известным и весьма простым является итеративный метод Брауна — Робинсон, известный также как метод фиктивного разыгрывания. Метод назван в честь американских математиков Джорджа Брауна (1917—2005) и Джулии Робинсон (1919—1985), предложивших подходы к решению матричных игр на основе их фиктивного разыгрывания.

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

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

При решении игры с матрицей А_тХп = {а-} в каждой партии каждый игрок выбирает ту стратегию, при которой он может получить максимальный платеж при стратегии, выбранной противником. Для определенности принимают, что первый ход делает первый игрок (что не влияет на дальнейшую логику решения). Второй игрок выбирает стратегию, которая максимизирует его собственный накопленный выигрыш (минимизирует его накопленный проигрыш) при выбранной стратегии первого игрока, и т. д. С ростом числа партий смешанные стратегии, которые приписываются игрокам, приближаются к их оптимальным стратегиям.

В итоге если игра останавливается на /е-м шаге, и за k разыгрываний первый игрок использовал г-ю чистую стратегию раз, i = 1,…, т, а второй игрок —7−10 чистую стратегию rf раз, j = 1,…, п, то приближенными оптимальными смешанными стратегиями игроков будут векторы х* = …, %*"/?),.

y^k = (л*А •••> п1Д);

На каждом шаге определяются минимальный средний проигрыш второго игрока (of) и максимальный средний выигрыш игрока (of). Приближенное значение цены игры о* лежит в диапазоне | of; of] и определяется как среднеарифметическое of и of: (of + of)/2.

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

На практике результаты итераций данного метода обычно представляются в виде таблицы (табл. 4.6).

Таблица 4.6

Представление итераций метода Брауна — Робинсон.

Проиллюстрируем использование этого метода на примере.

Пример 4.8. Пусть игра задана следующей платежной матрицей':

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

Результаты 10 итераций представлены в табл. 4.7. Опишем подробнее последовательность действий.

Таблица 4.7

Результаты решения игры методом Брауна — Робинсон.

' При описании метода использованы материалы книг [7, 22].

Предположим, что начинает первый игрок и, следуя принципу максимина, выбирает первую стратегию. В этом случае проигрыши второго игрока составят (2; 0; 3). Второй игрок выбирает стратегию так, чтобы его проигрыш оказался минимальным, что обеспечивается второй стратегией. Тогда выигрыши первого игрока составят (0; 3). При этом и] = min{2; 0; 3}/1 = 0, Uj = max{0; 3}/1 = 3, о^[1] = = (0 + 3)/2 = 1,5 (см. табл. 4.7).

В ответ на эту стратегию первый игрок должен выбрать свою вторую чистую стратегию. В этом случае накопленные платежи определяются как (2 + 1; 0 + 3; 3 — 3), т. е. (3; 3; 0). Эти платежи соответствуют накопленным проигрышам второго игрока и записываются в соответствующие ячейки табл. 4.7. Стараясь минимизировать свой проигрыш, второй игрок выбирает свою третью чистую стратегию. Тогда накопленные выигрыши первого игрока составят (0 + 3; 3 — 3), т. е. (3; 0). При этом и, = min{3; 3; 0}/2 = 0; = шах{3; 0}/2 = 1,5; х2 = (0 + 1,5)/2 =.

= 0,75 (см. табл. 4.7).

В третьей партии первый игрок выбирает первую чистую стратегию, чтобы максимизировать свой накопленный платеж. При этом накопленные проигрыши второго игрока составят (3 + 2; 3 + 0; 0 + 3), т. е. (5; 3; 3). Здесь мы сталкиваемся с ситуацией неоднозначного выбора стратегии второго игрока, которая будет минимизировать его накопленный проигрыш: и вторая, и третья стратегии обеспечивают минимальный проигрыш (3). В этом случае одна из двух этих стратегий выбирается произвольно (случайно) либо используются дополнительные критерии, определяющие более предпочтительную стратегию (например, выбирается менее рискованная стратегия), но подобные критерии нс всегда очевидны и однозначны. В таких случаях из двух равнозначных стратегий для определенности выбирается стратегия с наименьшим номером (в данном случае это стратегия 2). В итоге накопленные платежи первого игрока составят (3 + 0; 0 + 3), т. е. (3; 3) (см. табл. 4.7).

Таким образом, в четвертой партии при выборе стратегии первого игрока вновь сталкиваемся с ситуацией равенства накопленных платежей, т. е. равнозначностью стратегий. Из двух стратегий, обеспечивающих максимальный накопленный выигрыш первого игрока, выбираем стратегию с меньшим номером (стратегия 1). Тогда в четвертой партии накопленные проигрыши второго игрока составят (7; 3; 6), и он, минимизируя свой проигрыш, выберет вторую стратегию, обеспечив первому игроку накопленные выигрыши (3; 6), что, в свою очередь, обусловливает выбор первым игроком в пятой партии его второй чистой стратегии и т. д.

Следуя такой логике, можно получить приближенное решение игры.

Субоптимальные (приближенные к оптимальным) смешанные стратегии игроков определяются частотами выбора чистых стратегий. В данном случае после 10 итераций получаем лг¹⁰ = (7/10, 3/10), г/¹⁰ = (0, 7/10, 3/10), а приближенное значение цены игры о¹⁰ = 1,05. Читатель может проверить, что точное решение этой игры х = (2/3,1/3), у = (0, 2/3,1/3), и = 1, т. е. с помощью данного метода в рассматриваемом примере получено достаточно хорошее приближение к точному решению.

Рассмотренный в примере процесс сходится, т. е. после достаточного числа итераций можно получить решение с заданной точностью'. В качестве простейшего ориентира для оценки сходимости процесса и точности получаемого решения может быть принято абсолютное значение разности значений и* в данной и предыдущей партиях игры: lu*- Однако его сходимость немонотонна, поэтому часто для получения приемлемого решения необходимо выполнить большое число (десятки или даже сотни) итераций. При этом скорость сходимости заметно уменьшается с ростом числа стратегий игроков. Это также является следствием немонотонности последовательностей of и of.

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

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

• [1] Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. М.: Высшая школа, 1998.