Игры двух лиц с нулевой суммой

Существуют два способа описания игр: позиционный и нормаль­ный. Позиционный способ дает развернутую форму игры в виде дереза игры. Нормальный способ явно представляет совокупность стратегий игро­ков и платежную функцию в матричном виде.

Пусть задана антагонистическая игра двух лиц с нулевой сум­мой в нормальной форме:

G = (X, Y, L),

где Х={x₁,..,x_m} - множество стратегий игрока А (1-й игрок), Y={у₁,..,у_n} -множество стратегий игрока Б (2-й игрок), L(х,у) - ограниченная числовая функция одного из игроков, определенная на декартовом произведении множеств Х на У и равная математическому ожиданию выигрыша. Функцию L обычно задают в виде платежной матрицы Q=||q_ij||_nxm. где q_ij=L(x_i,y_j). Цели у игроков противоположны: игрок А максимизиру­ет выигрыш, а игрок Б минимизирует проигрыш (или наоборот). Трудность состоит в том, что один из игроков не контролирует платежную функцию L(x,у). Существо рекомендаций теории игр к состоит в преодолении этой трудности (впрочем, это справедливо лишь для рассматриваемых игр, так как если игроков больше двух, то возникает возможность образования коалиций с договорным распределением выигрыша!).

Следующие примеры показывают, каким образом строится модель игры.

Игра полковника Блотто.

Полковник Блотто и его противник пытаются занять две позиции, распределив надлежащим образом свои силы. Допустим, что Блотто имеет 4 полка, а его противник – 3 полка, которые следует распределить между двумя позициями. Платеж полковнику Блотто определяется следующим образом. Если у Блотто на данной позиции полков больше, чем у его противника, то он получает все полки противника на данной позиции плюс еще один его полк, так как ус­ловно считается, что занятие позиции эквивалентно захвату одного полка. Если на данной позиции у Блотто меньше полков, чем у его противника, то он теряет все свои полки на данной позиции плюс еще один полк. Общий платеж равен сумме платежей на обеих позициях. У полковника Блотто есть пять стратегий для распределениядения четырех полков на двух позициях. У его противника имеется четыре стратегии. Матрица платежей Q полковник Блотто имеет следующий вид:

|(3,0) (0,3) (2,1) (1,2)

_____|__________________

(4,0) | 4 0 2 1

Q = (0,4) | О 4 1 2

(3,1) | 1 -1 3 О

(1,3) | -1 1 0 3

(2,2) | -2 -2 2 2

 

Двухпальцевая игра Морра.

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

Решение. Вначале необходимо определить, сколько стратегий у каждого игрока. Очевидно, четыре: (1, 1), (1, 2), (2, 1), (2, 2), - где первое число указывает на то, сколько пальцев показывает игрок, а второе – сколько пальцев называется. Игра состоит из 4х4 = 16 партий, а платежная матрица игры имеет вид:

	2-й игрок
(1,1)	(1,2)	(2,1)	(2,2)
1-й игрок	(1,1)			-3
(1,2)	-2
(2,1)				-4
(2,2)		-3

Для поиска оптимальной стратегии в теории игр используется «пессимистический» критерий, называемый критерием максимина/минимакса и основанный на выборе наилучшей из наихудших возможностей. Почему? - В ТИ предполагается, что оба игрока одинаково сильны, не прощают ошибок. Предполагается, что оптимальное решение достигнуто, если ни одному из игроков невыгодно изменить свою стратегию (точка равновесия или седловая точка), т.е. достижение компромисса в реальном конфликте сторон, имеющих противоположные интересы, является выгодным для каждого из противников. Любопытно отметить, что всякая игра с полной информацией (крестики/нолики, шашки, шахматы и т.п.) обязательно имеет седловую точку. Рассмотрим пример. Пусть задана платежная матрица вида:

Q =		y1	y2	y3	y4
x1
х2					3
х3			-6		-6
		3

Тогда максимин или нижняя чистая цена игры равна: ,

Минимакс или верхняя чистая цена игры равна:

Можно доказать, что всегда α≤β. Для данной матрицы , т.е. игра имеет седловую точку (точка равновесия или точка Нэша). Здесь – чистая цена игры, а сама игра называется игрой с седловой точкой.

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

К сожалению, подавляющее большинство игр не имеют седловой точки. Возникает вопрос: если , то чему равна цена игры и какие стратегии рекомендовать игрокам в качестве оптимальных стратегий? – Оказалось, что если допускать в игре не только чистые стратегии, но и их смешивание, т.е. чередование выбора чистых стратегий случайным образом с некоторыми вероятностями, то можно найти решение, т.е. цену игры и оптимальные стратегии игроков. Так в игре Морра α = -2, β = 2, т.е. интервал [-2, 2] является как бы ничейным и каждый из игроков может попытаться улучшить свой результат на этом интервале.

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

В общем случае, обозначим через смешанные стратегии 1-го и 2-го игроков, в которых – вероятность применения 1-м игроком своей чистой стратегии , – вероятность применения 2-м игроком своей чистой стратегии .

Обязательно выполнение следующего условия:

.

Возможность нахождения каждым игроком своей оптимальной стратегии базируется на основной теореме теории игр. Она является доказательством существования решения для каждой конечной антагонистической игры двух лиц с нулевой суммой. В 1927г. Э. Борель сформулировал основную теорему теории игр, а в 1928г. Дж. Фон Нейман доказал эту теорему. Приведем без доказательства формулировку теоремы.

Основная теорема теории игр. Всякая конечная антагонистическая игра 2-х лиц с нулевой суммой имеет цену и у каждого игрока имеется, по меньшей мере, одна оптимальная стратегия.

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

Начнем с первого вопроса: как определить, является ли некоторая стратегия оптимальной или нет? Доказано, что оптимальные стратегии игроков обладают следующим свойством:

, причем цена игры .

Удалось также доказать следующее. Чтобы стратегии и были оптимальными необходимо и достаточно выполнение следующих неравенств:

для всех .

 

Определим на примере для игры Морра, являются ли оптимальными следующие смешанные стратегии:

 

(1,1)	(1,2)	(2,1)	(2,2)
	(1,1)			-3		-3
	(1,2)	-2				-2
	(2,1)				-4	-4
	(2,2)		-3			-3
		2

 

Вначале вычислим

Далее, приступим к проверке приведенных выше неравенств. Если для некоторого значения i или j неравенства не выполняются, то стратегии ξ или η будут неоптимальными и проверку на оптимальность можно останавливать. Итак, вычисляем и :

=0, =0, =0, =1/5.

Видно, что неравенства справедливы для всех индексов , следовательно, стратегии и являются оптимальными, а цена игры L(ξ,η)= .

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

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

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

· Если седловая точка отсутствует, то нельзя ли упростить игру?

Только после этого приступают к поиску решения.

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

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

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

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

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

1.2. Аналитическое решение игры (2×2)

Рассмотрим вначале простейший случай – игру, которая описывается матрицей (2×2), в общем случае имеющей следующий вид:

Q =

Необходимо найти решение игры, т.е. найти: цену игры и оптимальные стратегии

игроков и .

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

Воспользуемся ранее приведенным утверждением. Для игры (2×2) оно означает следующее.

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

Кроме того, справедливо уравнение .

Решая данную систему из трех уравнений с тремя неизвестными, получим, что

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

Получим