Упрощение матричных игр

Тема 1 Решение матричных игр в чистых стратегиях

Понятие об играх и стратегиях

Определение. "Игра (в математике) - это идеализированная математическая модель коллективного поведения: несколько игроков влияют на исход игры, причем их интересы различны". [7].

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

Запись матричной игры в виде платёжной матрицы

В общем виде матричная игра может быть записана следующей платёжной матрицей [1, 2, 7] (рис. 1.1.),

	B1	B2	…	Bn
A1	A11	A12	...	A1n
A2	A21	A22	...	A2n
…	...	...	...	...
Am	am1	am2	...	amn

Рис. 1.1. Общий вид платёжной матрицы матричной игры

где A_i – названия стратегий игрока 1, B_j – названия стратегий игрока 2, a_ij – значения выигрышей игрока 1 при выборе им i – й стратегии, а игроком 2 – j – й стратегии. Поскольку данная игра является игрой с нулевой суммой, значение выигрыша для игрока 2 является величиной, противоположенной по знаку значению выигрыша игрока 1.

Понятие о нижней и верхней цене игры. Решение игры в чистых стратегиях

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

V_н = max_i min_j a_ij ,

или найти минимальные значения по каждой из строк платёжной матрицы, а затем определить максимальное из этих значений. Величина V_н называется максимином матрицы или нижней ценой игры.

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

V_в = min_j max_i a_ij .

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

В случае, если значения V_н и V_в не совпадают, при сохранении правил игры (коэффициентов a_ij ) в длительной перспективе, выбор стратегий каждым из игроков оказывается неустойчивым. Устойчивость он приобретает лишь при равенстве V_н = V_в = V. В этом случае говорят, что игра имеет решение в чистых стратегиях, а стратегии, в которых достигается V - оптимальными чистыми стратегиями. Величина V называется чистой ценой игры. [8].

Например, в матрице (рис. 1.2)

	B1	B2	B3	B4	Minj
A1
A2
A3
Maxi

Рис. 1.2. Платёжная матрица, в которой существует решение в чистых стратегиях

существует решение в чистых стратегиях. При этом для игрока 1 оптимальной чистой стратегией будет стратегия A1, а для игрока 2 – стратегия B4.

В матрице (рис. 1.3)

	B1	B2	B3	B4	Minj
A1
A2
A3
Maxi

Рис. 1.3. Платёжная матрица, в которой не существует решения в чистых стратегиях

решения в чистых стратегиях не существует, так как нижняя цена игры достигается в стратегии A1 и её значение равно 2, в то время как верхняя цена игры достигается в стратегии B4 и её значение равно 3.

ассмотрим несколько методов упрощения платёжных матриц.

Упрощение матричных игр

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

Определение 1. Если в платежной матрице игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующее этим строкам (столбцам) стратегии называются дублирующими.

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

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

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

Пример. Упростить матричную игру, платежная матрица которой имеет вид:

Bj   Ai	B1	B2	B3	B4	B5
A1
A2
A3
A4
A5

Из платежной матрицы видно, что стратегия А₂ дублирует стратегию А₅, потому любую из них можно отбросить (отбросим стратегию А₅). Сравнивая почленно стратегии А₁ и А₄, видим, что каждый элемент строки А₄ не больше соответствующего элемента строки А₁. Поэтому применение игроком А доминирующей над А₄ стратегии А₁ всегда обеспечивает выигрыш, не меньший того, который был бы получен при применении стратегии А₄. Следовательно, стратегию А₄ можно отбросить. Таким образом, имеем упрощенную матричную игру с платежной матрицей вида:

Bj   Ai	B1	B2	B3	B4	B5
A1
A2
A3

Из этой матрицы видно, что в ней некоторые стратегии игрока В доминируют над другими: В₃ над В₂, В₄ и В₅. Отбрасывая доминируемые стратегии В₂, В₄ и В₅ получаем игру 3x2, имеющей платежную матрицу, вида:

Bj   Ai	B1	B3
A1
A2
A3

В этой матрице стратегия А₃ доминирует как над стратегией А₁, так и стратегией А₂. Отбрасывая стратегию А₃, окончательно получаем игру 2x2 с платежной матрицей

Bj   Ai	B1	B3
A1
A2

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

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

Свойство 1. Если ко всем элементам платежной матрицы прибавить (вычесть) одно и тоже число С, то оптимальные смешанные стратегии не изменятся, а только цена игры увеличится (уменьшится) на это число С.

Свойство 2. Если каждый элемент платежной матрицы умножить на положительное число k, то оптимальные смешанные стратегии не изменятся, а цена игры умножится на k.

Отметим, что эти свойства верны и для игр, имеющих седловую точку. Эти два свойства матричных игр применяются в следующих случаях:

1) если матрица игры наряду с положительными имеет и отрицательные элементы, то ко всем ее элементам прибавляют такое число, чтобы исключить отрицательные числа в матрице;

2) если матрица игры имеет дробные числа, то для удобства вычислений элементы этой матрицы следует умножить на такое число, чтобы все выигрыши были целыми числами.