Решение игр в чистых стратегиях.

Рассмотрим конечную матричную игру двух лиц, представленную матрицей выигрышей (mxn), где число стратегий игрока А совпадает с числом строк i=1,…,m, а число стратегий игрока В совпадает с числом столбцов j=1,…,n.

Игрок А придерживается максиминной стратегии. Онхочет получить гарантированный выигрыш. Это значит, что для каждойi-ой стратегии он определяет наименьшее значениесвоего выигрыша, а затем выбирает максимальное из них. Математически максиминную стратегию можно записать в виде

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

Если выполняется равенство α = β, то игра имеет оптимальное решение в чистых стратегиях и чистая цена игры ν равна

ν = α = β.

В этом случае игра называется игрой с седловой точкой.

Если имеет место неравенство α <β, то игра не имеет решения в чистых стратегиях, а цена игры удовлетворяет неравенству

α < ν < β

В этом случае игра не имеет седловой точки, но имеет решение в смешанных стратегиях.

Задача.

Дана платежная матрица игры. Определить верхнюю и нижнюю цены игры, также минимаксную и максиминную стратегии игроков.

	B1	B2	B3	αi
A1
A2
βj

Решение.

1) Нижняя цена игры.

, следовательно, максиминная стратегия А₂

2) Верхняя цена игры.

, следовательно, максиминная стратегия В₁

Имеем, ν = α = β = 4 – чистая цена игры при стратегиях А₂ и В₁

Следовательно, это игра с седловой точкой и есть решение в чистых стратегиях.

Решение игры: оптимальные чистые стратегии (А₂, В₁), цена игры ν = 4.

Редукция матричной игры.

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

Пусть А=(а_ij) платежная матрица размерности (mxn). Говорят, что стратегия A_i доминирует (дублирует) стратегию A_k , если справедливы неравенства

a_ij ≥ a_kj , где j=1,…,n.

В этом случае из платежной матрицы можно убрать k-ю строку.

Аналогично, стратегия B_j доминирует (дублирует) стратегию B_p, если справедливы неравенства

a_{ij ≤} a_ip , гдеi=1,…,m.

В этом случае из платежной матрицы можно убрать p-ый столбец.

Редукция не изменяет значения игры (цены игры) в чистых стратегиях.

Задача.

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

	0,4	0,9	0,5	0,5	0,6
	0,6	0,5	0,7	0,8	0,9
	0,6	0,3	0,8	0,6	0,7
	0,3	0,8	0,5	0,4	0,3
	0,1	0,3	0,5	0,4	0,3
	0,4	0,8	0,5	0,4	0,5

С позиции коммерческого предприятия (выигрыши игрока А) стратегия доминирует над стратегией , а стратегия доминирует над стратегией . Следовательно, исключаем 5-ю и 6-ю строки матрицы.

	0,4	0,9	0,5	0,5	0,6
	0,6	0,5	0,7	0,8	0,9
	0,6	0,3	0,8	0,6	0,7
	0,3	0,8	0,5	0,4	0,3

С позиций спроса на товары (проигрыши игрока В) стратегия B₁ доминирует над стратегиями B₃,B₄,B₅, поэтому эти столбцы исключаем.

	0,4	0,9
	0,6	0,5
	0,6	0,3
	0,3	0,8

С позиций игрока А стратегия A₁ доминирует над стратегией A₄, а стратегия A₂ доминирует над стратегией A₃. Поэтому исключим 3-ю и 4-ю строки и в результате получим сокращенную платежную матрицу

	0,4	0,9
	0,6	0,5

Получили платежную матрицу меньшей размерности, которую исследуем по принципу максимина и минимакса.

			αi
	0,4	0,9	0,4
	0,6	0,5	0,5
βj	0,6	0,9

Имеем, , . Следовательно, игра не имеет решения в чистых стратегиях так как α < β, седловой точки нет, а цена игры заключена в интервале 0,5 < ν < 0,6. Решать эту задачу можно только в смешанных стратегиях.

Аффинное правило.

Пусть задана исходная платежная матрица А=(a_ij) размерностиmxn.Аффинное преобразование -это линейное преобразование всех элементов матрицы А по формуле

где k ≠ 0 иb –любые константы.

Решение матричной игры для платежной матрицы А^'=(a^'_ij) совпадает с решением для исходной платежной матрицы. Цену игры ν для исходной платежной матрицы можно найти из цены игры для преобразованной платежной матрицы ν^’, опираясь на аффинное правило по формуле

Задача. Задана платёжная матрица игры:

A =

Необходимо упростить матрицу игры.

1. Умножим каждый из элементов матрицы Aна k = 0.001, получим:

2. К каждому элементу матрицы прибавим b = 5, получим матрицу:

=

Таким образом, мы получили платёжную матрицу с положительными элементами и небольшими по абсолютной величине. Искать решение для платежной матрицы А^" проще, чем для исходной А.