ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР

1. МЕТОД БРАУНА-РОБИНСОНА (МЕТОД ФИКТИВНОГО РАЗЫГРЫВАНИЯ)

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

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

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

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

В (k+1)-й партииигрок 1 будет использовать i_k+1-стратегию, а игрок 2 -j_k+1 стратегию. Запишем следующие соотношения:

;

.

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

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

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

Теорема: .

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

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

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

№ партии	Выбор игрока 1	Выбор игрока 2	Выигрыш игрока 1			Проигрыш игрока 2
			α	β	γ	a	b	c
1	α	a	2	3	1	2	1	3
2	β	b	3	3	3	5	1	4
3	β	b	4	3	5	8	1	5
4	γ	b	5	3	7	9	3	6
5	γ	b	6	3	9	10	5	7
6	γ	b	7	3	11	11	7	8
7	γ	b	8	3	13	12	9	9
8	γ	c	11	4	14	13	11	10
9	γ	c	14	5	15	14	13	11
10	γ	c	17	6	16	15	15	12
11	α	c	20	7	17	17	16	15
12	α	c	23	8	18	19	17	18

и

2. МОНОТОННЫЙ АЛГОРИТМ РЕШЕНИЯ МАТРИЧНЫХ ИГР.

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

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

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

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

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

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

              (3)

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

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

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

Далее решаем (2×n)-игру с матрицей: (5)и находим для этой игры оптимальную стратегию 1-го игрока (1-α_N, α_N), значения которых подставляем в уравнения (3), (4) для нахождения x^N, c^N.

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

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

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

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

1. V^N=V^N-1, т.е. последовательность монотонно возрастет с ростом итераций;

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

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

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

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

Решение: шаг 0.В качестве х⁰ выберем первую чистую стратегию 1-го игрока, т.е.
х⁰=(1,0,0) и соответственно в качестве с⁰ выберем первую строку матрицы А:
. Решаем по алгоритму выражение (1): =min(2,1,3)=1= .
Следовательно (2) J⁰={2}, т.е. второй столбец матрицы А.

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

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

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

;

;

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

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

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

Имеем V=V₁= , х*=x²=x¹= Þх*А Þх*Ау*=VÞ

= Þ , а так как Þ

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

где h*Î[0,1].

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

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