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

Проанализируем возможное поведение сторон на примере платежной матрицы без седловой точки (табл. 6.6). Если игра проводится однократно и нет обоснованных предположений о действиях другой стороны, то логично использовать нам максиминную стратегию , а оппоненту – минимаксную стратегию . Но при многократном повторении игры оппонент, убедившись в предсказуемости нашего поведения, может уменьшить свой проигрыш с 5 до 4, применив стратегию . Мы можем в ответ увеличить свой выигрыш до 7, применив стратегию , которой оппонент может противопоставить , и т. д.

Таблица 6.6

				-3			-3
					-6		-6

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

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

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

.

Для оптимальных смешанных стратегий и значение платежной функции – это цена игры и справедливы неравенства

.

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

Таблица 6.7

				-3		-1

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

Таблица 6.8

			-3	-1

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

Таблица 6.9

			-3
Линейная комбинация и

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

Таблица 6.10

				Линейная комбинация и
			-3

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

Таблица 6.11

		-3

Тогда платежная функция запишется как

и искомые экстремумы – максимальный выигрыш для нас и минимальный проигрыш для оппонента можно найти, приравнивая нулю ее частные производные:

;

.

Далее

;

и оптимальные стратегии сторон будут

и .

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