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

Решение матричных игр при отсутствии седловой точки

Рассмотрим игру в матричной форме , для которой необходимо найти пару оптимальных смешанных стратегий и цену игры V.

Первый этап решения матричной игры состоит в упрощении матрицы игры — удалении доминируемых и дублируемых стратегий.

На множестве стратегий вводится отношение предпочтения: , т.е. стратегия A_i предпочтительней стратегии A_k, если все выигрыши стратегии A_i не меньше соответствующих выигрышей стратегии A_k.

Аналогично вводится отношение строгого предпочтения:

.

Для стратегий второго игрока отношения предпочтения вводятся так же:

;

.

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

, .

В теории игр доказывается, что если игра представлена матрицей , то число активных стратегий игроков равно min(m, n). Другими словами, один из игроков реально в ходе игры всегда будет использовать лишь min(m, n) стратегий, остальные же будут ему невыгодны при любых возможных ситуациях.

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

Второй этап состоит в проверке на наличие у игры седловой точки (см. выше). Если она есть, то решение – чистые стратегии, если нет – смешанные.

Пример 4

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

	4	7	2	3	4
	3	5	6	8	9
	4	4	2	2	8
	3	6	1	2	4
	3	5	6	8	9

У далим доминируемые и дублируемые стратегии:

В полученной матрице снова проведём удаление доминируемых стратегий ( ). Получим упрощенную матрицу размера , представленную в таблице, и проверим её на наличие седловой точки:

	4	2	2
	3	6	3
	4	6

= 3, = 4, , следовательно, седловой точки не существует и следует искать решение в смешанных стратегиях. Стратегии будут иметь следующий вид:

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

Метод Лагранжа

Метод Лагранжа относится к точным методам решения игр в матричной форме. Считаем, что матрица игры квадратная, размера (либо приведена к квадратной, см. выше).

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

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

Составим функцию Лагранжа: и приравняем к нулю частные производные по всем аргументам: .

Приходим к следующей системе уравнений (2m+2 уравнения, 2m+2 неизвестных):

Решение этой системы и даёт смешанные стратегии для обоих игроков.

Исходная система уравнений разбивается на две подсистемы размера (m+1), а их решение находится за ~O((m+1)!∙(m+1) + m!∙m²) операций.

Пример 5

Рассмотрим игру в общем виде:

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

и цену игры V.

Функция Лагранжа: Приравнивая к 0 частные производные по всем аргументам, получим следующую систему уравнений:

Решая эту систему приходим к следующим выражениям для вероятностей:

.

Подставив полученные значения в выражение для V, получим цену игры.

Для приведённой матрицы из примера 4 получим:

.

Пример 6

Рассмотрим более универсальный способ решения матричных игр методом Лагранжа на примере игры . Рассмотрим игру в общем виде:

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

Эту систему можно представить следующим образом:

Откуда решение системы:

Это в общем виде. Более конкретно: умножение слева на вектор с единичным последним элементом даёт в качестве результата элементы последней строки обратной матрицы. Учитывая то, что обратная матрица вычисляется как транспонированная матрица алгебраических дополнений, делённая на определитель исходной матрицы, можно выразить решение через несколько определителей (при этом также отбрасываем последний элемент, λ; ниже мы вернёмся к нему):

То есть, выражение для p_i содержит определитель матрицы A1 с вычеркнутыми i-й строкой и последним столбцом, умноженный на (-1)ⁱ и делённый на определитель полной матрицы A1. То же самое для q_j, с той разницей, что вычёркивается j-й столбец и последняя строка.

Можно и далее раскрыть эти формулы:

k = – a₁₁·a₂₂ + a₁₁·a₃₂ + a₁₁·a₂₃ – a₁₁·a₃₃ + a₂₁·a₁₂ – a₂₁·a₃₂ –

– a₂₁·a₁₃ + a₂₁·a₃₃ – a₃₁·a₁₂ + a₃₁·a₂₂ + a₃₁·a₁₃ – a₃₁·a₂₃ –

– a₁₂·a₂₃ + a₁₂·a₃₃ + a₂₂·a₁₃ – a₂₂·a₃₃ – a₃₂·a₁₃ + a₃₂·a₂₃

p₁ = (– a₂₁·a₃₂ + a₂₁·a₃₃ + a₃₁·a₂₂ – a₃₁·a₂₃ – a₂₂·a₃₃ + a₃₂·a₂₃) / k

p₂ = ( a₁₁·a₃₂ – a₁₁·a₃₃ – a₃₁·a₁₂ + a₃₁·a₁₃ + a₁₂·a₃₃ – a₃₂·a₁₃) / k

p₃ = (– a₁₁·a₂₂ + a₁₁·a₂₃ + a₂₁·a₁₂ – a₂₁·a₁₃ – a₁₂·a₂₃ + a₂₂·a₁₃) / k

q₁ = (– a₁₂·a₂₃ + a₁₂·a₃₃ + a₂₂·a₁₃ – a₂₂·a₃₃ – a₃₂·a₁₃ + a₃₂·a₂₃) / k

q₂ = ( a₁₁·a₂₃ – a₁₁·a₃₃ – a₂₁·a₁₃ + a₂₁·a₃₃ + a₃₁·a₁₃ – a₃₁·a₂₃) / k

q₃ = (– a₁₁·a₂₂ + a₁₁·a₃₂ + a₂₁·a₁₂ – a₂₁·a₃₂ – a₃₁·a₁₂ + a₃₁·a₂₂) / k

Кстати, из исходных уравнений можно заметить, что –λ₁ = –λ₂ = V, то есть, цена игры легко вычисляется как V = – |A| / |A1|, где А — исходная матрица игры.

На самом деле, данный метод легко применим для произвольной игры : точно так же строится матрица A1, так же через определители можно записать выражения для p_i и q_j, множитель знака для них будет равен (-1)ⁿ⁺ⁱ⁺¹.

Вычисление определителя может быть реализовано многими способами. Один из вариантов – это использование метода QR-разложения, который опирается на следующие факт:

Любая матрица A размера NxN может быть представлена в виде произведения ортонормированной матрицы Q размера NxN (det Q = 1) и верхнетреугольной матрицы R размера NxN.

A = QR

Такое представление позволяет легко находить обратную матрицу A -1, вычислять определитель, решать системы уравнений вида Ax = b. QR-разложение матрицы A строится при помощи преобразований вращения. Обходя матрицу, мы применяем к каждому из элементов, расположенных ниже главной диагонали, преобразование вращения, которое обнуляет этот элемент. Если мы обнуляем элемент ai,j , то осуществляем поворот вокруг i-ой и j-ой координатных осей. За счет поворота элемент ai,j обнуляется, а элемент aj,j изменяет свое значение. Попутно меняются другие элементы i-ой и j-ой строки. Таким образом мы получаем матрицу R. Поскольку матрицы являются треугольными то их определитель равен произведению элементов главной диагонали. Умножая определители получим искомый. Такой вариант реализован в программе.

Метод линейного программирования

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