1.3. Доминируемые стратегии
не будет играть М, то игрок 2 знает, что 1 будет играть и, а тогда 2 должен играть L . Этот процесс — последовательное удаление строго доминируемых стратегий (мы дадим позднее строгое определение и соответствующий экономический пример). Вопрос, естественно возникающий здесь: «А не зависит ли множество стратегий, выдерживающих такое исключение доминируемых стратегий, от порядка исключения?» К счастью, нет, и дело здесь в том, что если стратегия строго хуже, чем s' для всех стратегий оппонента из множества D , то она хуже, чем s'- и для любого подмножества множества D.
Посмотрим теперь на следующую игру (рис.8): L R и ( (2,0) ("1,0) м (0,0) (0,0) D V (-1,0) (2,0) Рис. 8. Здесь М не доминируется строго стратегией U, и М не доминируется строго стратегией D. Однако, если игрок 1 играет U с вероятностью 1/2 и D — с вероятностью 1/2, он обеспечивает себе выигрыш 1/2 независимо от того, как играет игрок 2. Следовательно, чистая стратегия может строго доминироваться смешанной стратегией, даже если она не доминируется строго никакой чистой стратегией.
Введем следующие обозначения: пусть i ? /, тогда через s_i ? S-i будем обозначать набор стратегий игроков из I \ {г}, (s',s_8) обозначает набор стратегий (si, • • •, s'-, ..., sn). Аналогично, для смешанных стратегий (а'г, ст_г) — это (сть ..., стг_1, а'г, аг+1,..., ап) . (Заметим, что в этих обозначениях s = (s4-, s_8) .) Определение 1.3.1.
Чистая стратегия Si игрока г в игре Г строго доминируема (строго доминируется), если существует другая чистая стратегия s'- такая, чтоut(s't,s_t) > Ui(si,s-i) (3.1)
для всех s_i ? S-i .
В этом случае говорят, что стратегия s' доминирует стратегию Si. Стратегия Si слабо доминируется, если существует такая s'- , что (3.1) выполняется как нестрогое неравенство, но хотя бы для одного набора — неравенство строгое. Аналогично определение и для смешанных стратегий:
Определение 1.3.2. Смешанная стратегия строго доминируется в игре Г, если существует другая стратегия а[ такая, что для всех cr_i ?
иг(а[, ст_г) > щ(аг, ст_г).
Стратегия аг- называется строго доминирующей стратегией для игрока i в игре Г, если она строго доминирует любую другую стратегию из ^ - .
Заметим, что для проверки строгой доминируемости аг- стратегией <т', нам нужно посмотреть на «поведение» этих двух стратегий против чистых стратегий оппонентов игрока i.
Формально:
(А) щ(а'г, ст_г) > щ(аг, ст_г) Уст_г тогда и только тогда, когда
{В) ut( щ((т'г, а-г)-щ((тг, (Т_г) = (]^[(Tfc(sfc))[M8((T',s_8)-M8((T8,s_8)].
S — t(zS—t кфг
Тогда если (В), то (А), т.к. все [щ(сг'-, — > 0.
(В) следует из (А), т.к. — вырожденный случай .
Задача. Докажите, что если чистая стратегия является строго доминируемой, то таковой же является и любая стратегия, использующая с положительной вероятностью.
Однако смешанная стратегия может быть строго доминируемой, даже если она использует с положительной вероятностью чистые стратегии, которые даже не слабо доминируемы. Действительно, рассмотрим следующую игру (рис.9):
L
R
и
( (1,3)
("2,0)
м
("2,0)
(1,3)
D
V (ОД)
(ОД)
Рис. 9.
Стратегия первого игрока дает ожидаемый вы
игрыш — ^ вне зависимости от того, что играет игрок 2, а следовательно, строго доминируется стратегией D .
Естественно, что строго доминируемые стратегии надо удалять. Вернемся к игре, изображенной на рис. 7. Нетрудно убедиться в том, что здесь в результате последовательного удаления строго доминируемых стратегий остается пара стратегий (и, L) . На первом шаге удаляется стратегия М (она доминируется стратегией R). Затем удаляется стратегия тп (доминируемая стратегией и). На третьем шаге удаляется стратегия d (доминируется стратегией и). Наконец, на последнем шаге удаляется R.
Но даже если такие ситуации представляют собой хорошие кандидатуры, все не обязательно произойдет в соответствии с их «предписанием», особенно если выигрыши могут принимать «экстремальные» значения.
Рассмотрим, например, следующую игру (рис. 10):
L R и ( (20,10) (15,20) \ D V (-100,20) (40,30) J
Рис. 10.
Очевидно, что здесь стратегия L доминируется стратегией R , а потому ситуация (D, R) является хорошим кандидатом. Но ...Проигрыш игрока 1 в ситуации (D,L) слишком велик, поэтому вполне можно допустить, что игрок 1 может не рискнуть сыграть стратегию d (допуская, например, возможность случайной ошибки игрока 2).
Все, конечно, изменится, если игроки могут договориться до принятия решения. В этом случае все уже будет зависеть от «силы» договоренности.