Статья: Итерационные методы решения матричных игр

Итерационные методы решения матричных игр

1. Метод Брауна-Робинсона (метод фиктивного разыгрывания)

Идея метода: многократное фиктивное разыгрывание игры, когда одна итерация называется партией.

Рассматривается матричная игра ГА с матрицей А={бij}, где .

В первой партии игроки произвольно выбирают свои чистые стратегии.

В k-й партии каждый игрок выбирает ту чистую стратегию, которая максимизирует его ожидаемый выигрыш против наблюдаемого эмпирического вероятностного распределения противника за (k-1) партию. Пусть за k - партий игрок 1 i-ю стратегию использовал -раз, а игрок 2 свою j-ю стратегию использовал -раз.

В (k+1)-й партии игрок 1 будет использовать ik+1-стратегию, а игрок 2 -jk+1 стратегию.

Запишем следующие соотношения:

;

.

Если рассмотреть как соответственно верхнее и нижнее приближённые значения за k- партий, то приближённые оптимальные смешанные стратегии соответственно 1 и 2 го игроков за k-партий можем записать как:

и .

Значение игры V находится в диапазоне:

.

Сходимость представленного алгоритма подтверждается следующей теоремой:

Теорема:

.

Недостатком данного метода является его медленная и немонотонная сходимость.

Пример. Найти приближённые оптимальные стратегии игроков и значение матричной игры с матрицей . Видим из написанного, что седловой точки нет и значение игры находится в интервале 1<V<2. Стратегии игрока 1 обозначены как б, в, г, стратегии игрока обозначены как a, b, c.

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

Табл. 1

и

2. Монотонный алгоритм решения матричных игр

Алгоритм позволяет находить (точно и приближённо) оптимальную стратегию 1-го игрока и значение матричной игры V.

Рассматривается матричная игра ГА с матрицей размерности mЧn. Обозначим через - приближённое значение оптимальной стратегии 1-го игрока на N-й итерации. Также введём на N-й итерации как важный элемент нашего алгоритма вспомогательный вектор . Пояснения по его получению будет дано по шагам алгоритма.

Шаг 0: игрок 1 выбирает произвольную свою чистую стратегию i0, т.е. , и вспомогательный вектор строка матрицы А. Приближённое значение игры на шаге 0 будем определять, как

(1)

и через

(2)

обозначим множество тех индексов, для которых выполняется равенство (1).

Замечание: на последующих шагах алгоритма соотношения (1) и (2) будем определять аналогично, лишь изменяя верхний индекс 0 на индекс соответствующего шага, т.е. для N шага эти значения будем обозначать соответственно: VN, JN.

Шаг N-1: допустим, что выполнена N-1 итерация и полученыx N-1, cN-1, VN-1.

Шаг N: тогда xN, cN вычисляются по следующим формулам:

(3)

(4),

где , а получение векторов , будем описывать ниже:

Пусть на Nшаге рассматривается игра ГNГАcматрицей АN=, где , т.е. это матрица А только с частью столбцов, определяемых на N-1 шаге по формулам (1) и (2).

Решаем подыгру ГN и находим для этой игры оптимальную стратегию 1-го игрока . Вектор определяем по формуле:

,

где ai строки матрицы А.

Далее решаем (2Чn)-игру с матрицей:

(5)

и находим для этой игры оптимальную стратегию 1-го игрока (1-бN, бN), значения которых подставляем в уравнения (3), (4) для нахождения xN, cN.

Вычислительный процесс продолжается до тех пор, пока не будет выполнено условие бN =0 или не будет достигнута требуемая точность вычисления.

Условие бN =0 говорит о том, что в матрице (5) первая строка доминирует вторую и, следовательно, в качествеоптимальной стратегии 1-го игрока в исходной задаче можно взять х*=xN=xN-1 и V=VN-1.

Сходимость алгоритма гарантируется следующей теоремой:

Теорема: если - итеративные последовательности, значения которых получаются согласно формулам соответственно (1), (3), тогда выполняются следующих 3 условия:

1. VN>VN-1, т.е. последовательность строго монотонно возрастет с ростом итераций;

2. , где V - цена исходной задачи;

3. , х*Х* - оптимальная стратегия первого игрока.

Рассмотрим пример. Дана игра ГА с платёжной матрицей .

Найти ситуацию равновесия в данной игре.

Решение: шаг 0.В качестве х0 выберем первую чистую стратегию 1-го игрока, т.е. х0=(1,0,0) и соответственно в качестве с0 выберем первую строку матрицы А: . Решаем по алгоритму выражение (1):

итеративный игра формула

=min(2,1,3)=1=.

Следовательно (2) J0={2}, т.е. второй столбец матрицы А.

Шаг 1. Для нахождения , и подстановки их значений в формулы (3), (4) рассмотрим подыгру Г1ГА c матрицей А1=, равной второму столбцу матрицы А. Оптимальной стратегией этой игры есть выбор третьей чистой стратегии 1-го игрока, как лучший выигрыш из 1, 0, 2, т.е. =(0,0,1)., т.е. третья строка матрицы А.

Решаем (2Ч3) игру с матрицей. Так как элементы третьего столбца а3 данной матрицы элементов первого столбца а1, то он доминируем первым столбцом, следовательно его можно убрать из решения, не нарушая спектр оптимальных стратегий. Имеем (2Ч2) игру с матрицей. Эта игра вполне смешанная, поэтому решая эту игру по известным формулам прямого счёта, получим оптимальную стратегию 1-го игрока (1-б1, б1)=.

Так как б10, то вычисления продолжаем. Вычислим формулы (3) и (4):

;

;

,

т.е. 1 и 2-й столбцы матрицы А.

Шаг 2. Для нахождения , рассмотрим подыгру Г2ГА c матрицей А2=, равной первому и второму столбцам матрицы А. Так как доминируема и её можно вычеркнуть из спектра оптимальных стратегий. Имеем (2Ч2) игру с матрицей. Эта игра вполне смешанная, поэтому решая эту игру по известным формулам прямого счёта, получим для игры с матрицей оптимальную стратегию 1-го игрока =. Добавлением 0 в качестве первой координаты в получим = оптимальную стратегию 1-го игрока для игры с матрицей А2.

. Решаем (2Ч3) игру с матрицейа2 доминируема а1 матрица 1-б2=1 и б2=0вычисления по алгоритму закончены.

Имеем

V=V1=, х*=x2=x1=х*Ах*Ау*=V

=, а так как

у*=(*,1-*,0),

где *[0,1].

Самостоятельно решить матричные игры с платёжными матрицами:

и итерационными методами Брауна-Робинсона и монотонным методом, когда по первому методу в матрице А на первом шаге выбрать вторые чистые стратегии игроков, а в матрице В - выбрать четвёртую чистую стратегию 1-го игрока и вторую чистую стратегию 2-го игрока и найти приближённые оптимальные стратегии игроков и интервал, в котором находится значение игры, сделав по 20 итераций. Для второго метода на 0-м шаге в качестве чистой стратегии для матрицы А выбрать третью чистую стратегию 1-го игрока, а для матрицы В четвёртую чистую стратегию 1-го игрока.