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

Учитывая, что цена игры нам неизвестна, перейдём к новым переменным: . Система неравенств теперь выглядит так:

Учитывая, что задача первого игрока — максимизация цены игры V, получаем задачу линейного программирования: при указанных выше ограничениях.

Решение этой задачи позволяет найти цену игры и вектор смешанной стратегии первого игрока: .

Аналогично такая задача записывается и относительно второго игрока:

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

Программа использует табличный симплекс-метод для поиска экстремальных точек таких задач.

Метод Брауна-Робинсона

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

Для компактной записи хода метода вводится таблица следующего вида:

k	i	B1	…	Bn	j	A1	…	Am	V		V*

В каждой строке таблицы записывается:

в столбце k — номер итерации (партии);

i — номер стратегии, выбранной первым игроком (игроком A);

B_1, …, B_n — накопленный за k партий выигрыш первого игрока при выборе им стратегии i и соответствующем названию столбца выбору стратегии второго игрока;

j — выбор стратегии второго игрока (игрока B);

A_1, …, A_m — накопленный за k партий выигрыш первого игрока при выборе им соответствующей стратегии и выборе вторым игроком стратегии j;

V — средний минимальный выигрыш за k партий;

— средний максимальный выигрыш за k партий;

.

Суть метода состоит в следующем. В первой партии стратегия первого игрока, i, выбирается случайным образом (либо, например, максимином). Далее, в столбцах B_1, …, B_n выписываются элементы i-й строки матрицы игры (выплаты при всех возможных ответах второго игрока), и среди них выбирается минимальный – это определяет выбор стратегии второго игрока, j. После этого в столбцах A_1, …, A_m выписываются элементы j-го столбца матрицы игры, и среди них выбирается максимальный, что определяет выбор первого игрока в следующей партии.

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

На каждой итерации также вычисляются средние минимальный и максимальный выигрыши за последние k партий, V и — они равны делённым на k соответственно минимальному и максимальному элементам столбцов B_1, …, B_n и A_1, …, A_m в текущей партии.

Доказано, что при устремлении k к бесконечности, метод даёт сходимость к точному решению: , где M_i и N_j — количество выборов соответственно стратегий A_i и B_j за k партий.

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

Трудоёмкость этого метода приблизительно определяется как ~O(k∙(m+n)).

Пример 7

Рассмотрим первые несколько итераций алгоритма на примере расчёта игры со следующей матрицей:

	7	2	9
	2	9	0
	9	0	11

Будем искать пару смешанных стратегий

и цену игры V.

Выполним описанные выше шаги метода:

1. k=1,

2. случайным образом выбираем стратегию игрока A (например, i=3),

3. к накопленным в столбцах значениям прибавляем значения i-й строки матрицы игры,

4. среди значений в столбцах выбираем наименьшее ( , в таблице помечено индексом «-») и фиксируем соответствующее значение j (j=2, т.к. =0),

5. к накопленным в столбцах значениям прибавляем значения j-го столбца матрицы игры,

6. среди значений в столбцах выбираем наибольшее ( , в таблице помечено индексом «+») и фиксируем соответствующее значение i (i=2, т.к. =9),

7. вычисляем и ( )

8. k=k+1 и возвращаемся к пункту 3

Первые 4 итерации метода представлены в таблице:

k	i	B1	…	Bn	j	A1	…	Am	V		V*
1	3	9		11	2	2		0	0	9	4.5
2	2	11		11	2	4		0	4.5	9	6.75
3	2	13	18		3	13		11	3.67	6	4.84
4	2	15	27		4		18	22	2.75	5.5	4.13
5	1

Для данного примера и .

Программа MatrixGames.

Данная программа предназначена для решения матричных игр методами Лагранжа, Брауна-Робинсона и с использованием симплекс-метода.

рис.1

Главное окно программы представлено на рис.1 и содержит следующие компоненты:

1) Выбор метода поиска оптимальной стратегии;

2) Параметры выбранного метода;

3) Окно ввода и отображения платежной матрицы;

4) Выбор количества стратегий игроков;

5) Окно отображения хода решения и найденных решений;

6) Кнопка начала поиска решения;

7) Кнопка выхода из программы;

8) Очистка записи о ходе работы программы;

9) Сохранение записи о ходе работы программы в текстовый файл;

10) Меню программы (включает в себя пункты сохранения, загрузки и сброса матрицы игры, а также вызов помощи программы);

Параметры метода Брауна-Робинсона:

1. «Приводить матрицу к квадратной» - запускает алгоритм удаления доминируемых и дублируемых стратегий;

2. «Показывать значения для итераций» - Позволяет просмотреть выбранное количество итераций метода

3. «Показывать p,q» - Выводит в окне со значениями итераций вместо накопленного выигрыша значения p,q для смешанных стратегий, что позволяет наблюдать их сходимость к результату.

Пример работы программы:

1)

Матрица игры:

	7	2	9
	2	9	0
	9	0	11

Поиск решения методом Лагранжа:

Поиск и удаление доминируемых и дублирующих стратегий:

Поиск седловой точки:

Седловая точка не найдена.

Поиск решения в смешаных стратегиях...

Методом Лагранжа найдено решение в смешаных стратегиях:

p=(0,250000; 0,500000;0,250000)

q=(0,250000; 0,500000;0,250000)

Цена игры: V=5,00000041749901

Поиск решения симплекс-методом:

Поиск седловой точки:

Седловая точка не найдена.

Поиск решения в смешаных стратегиях...

Симплекс методом найдено решение в смешаных стратегиях: