Теория игр. Оуэн (1971) (Теория игр. Оуэн (1971).djvu), страница 11

Применение (2.5.23) к этой матрице дает также у = = (О, а/и а/т, 0); легко проверить, 2 х что это действительно оптимальные стратегии и значение игры. Этим исчерпывается простей- 0 .0 ший тип игр; обобзцения указан- ных методов на другие игры, если Рис. П.бп. и возможны, то слишком трудоемки, чтобы принести какую-то практическую пользу. Для более общих игр используются некоторые другие схемы. Самая простая для обьяснения схема приводится ниже. Мы не даем доказательства сходимости этой схемы; его можно найти в соответствующей литературе. П5!О. Решение при помощи фиктивного разыгр ы в а ни я '), Предположим, что два игрока, возможно, не знающие теории игр, решают разыграть игру много раз. Не зная теории игр, они тем не менее склонны к статистике и потому следят за чистыми стратегиями, которые использует противник в отдельных разыгрываниях игры. При каждом разыгрывании каждый игрок действует так, чтобы максимизировать свой ожидаемый выигрыш против наблюдаемого эмпирического вероятностного распределения противника: если игрок П использовал свою 1-ю стратегию д1 раз, то игрок ! выберет 1 так, чтобы максимизировать ~ а,)д1.

Аналогично, если игрок 1 использовал Бю стратегию ре раз, то игрок П выберет / так, чтобы минимизировать ~ а,)ри Сколь ни наивным кажется этот метод, поразительным является то, что такие эмпирические распределения сходятся к оптимальным стратегиям. Точнее, пусть р", — число использований игроком ! 1-й стратегии в течение первых Ф разыгрываний игры. Если положить х",= р",/М, то очевидно, что хм является смешан- ') Этот метод часто называется итеративным методом (Брауна — Робин. сов).

— Прим. иерее. П. В. Симметричные игры ной стратегией. Эта последовательность стратегий не обязанасходиться; однако, поскольку она находится в компактном множестве смешанных стратегий, она должна содержать сходяшуюся подпоследовательность. Справедливо утверждение, что предел любой скодяи(ейся подпоследовательности является оптимальной стратегией. Мы опускаем доказательство атой теоремы, поскольку оно слишком сложно. Коротко говоря, оно основано на том факте, что если хн и ун — полученные указанным выше способом стратегии игроков 1 и П соответственно, то будет выполнено равенство )пп (о (ун) — о («н)) = О.

(2.5.25г Этот метод, между прочим, наиболее полезен в случае очень больших игр (т. е. игр с большим числом чистых стратегий), к которым довольно трудно применить какой-либо другой метод вследствие их объема. (Набросок доказательства втой теоремы см. в задаче П.9.) Н.

б. СИММЕТРИЧНЫЕ ИГРЫ Мы закончим эту главу кратким рассмотрением одного частного класса игр. П.6.1. Определение. Квадратная матрица А = (ан) называется кососимметрической, если аи = — ан для всех 1, !. Матричная игра называется симметричной, если ее матрица кососимметрическая. 1!.6.2. Т ео р е м а.

Значение симметричной игры равно нулю. Кроме того, если х есть оптимальная стратегия для игрока 1, то х есть также оптимальная стратегия для игрока П. Доказате,льство. Пусть А — матрица игры и х — произвольная стратегия. Легко видеть, что А = — Ат, Следовательно, «Ахт «Аткт («А«т)т «А«т Поэтому хАхт = О. Отсюда следует, что для любого х ппп хАут ~ О, е так что значение игры неположительно; в то же время шах уАкт = О У так что значение игры неотрицательно. Следовательно, значение игры равно нулю. Далее, если х — оптимальная стратегия игрока1, то хА~ О. Га !!, Антагонистические игры Но отсюда х(- Ат) ~ О, хАт ~ 0 Акт~ О так что или Значит, стратегия х оптимальна также н для игрока П.

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

Пример. Рассмотрим игру с матрицей Ее можно считать обобщением хорошо известной детской игры «камень, мешок и ножницы». Так как матрица кососимметрическая, значение игры должно быть равно нулю, Очевидно, эта игра не имеет седловой точки. Кроме того, оптимальная стратегия не может использовать только две чистые стратегии; действительно, если, например, х, > О, хт 0 и хг = О, то легко видеть, что такая смешанная стратегия для игрока 1 дает отрицательный ожидаемый выигрыш против первой чистой стратегии игрока П. Поэтому все компоненты оптимальной стратегии х будут положительными. Эта стратегия оптимальна также и для игрока П, и рассуждение, подобное проведенному в п.

П.5.5, показывает, что компоненты х должны удовлетворять системе линейных уравнений — х,+2хг=О, х, — Зх =О, — 2х1+Зхт =О, х,+ х,+ х,=-1. Решение этих уравнений (')т, т/г, '!е) нетрудно найти. Для обоих игроков это единственная оптимальная стратегия. Задачи Задачи 3.

Показать, что если представить матричную (т Х а)-игру как точку в тл-мерном евклидовом пространстве, то значение такой игры оказывается не. нрерывной функцией игры, 4. Показать, что отображение матрицы игры на множество ее оптимальных стратегий является полунепрерывным сннзу. 5, Показать, что множество матричных (т Х н)-игр с единственным ревеиием всюду плотно и открыто. б. Пусть х и у — крайние точки множеств оптимальных стратегий игры с матрицей М и ненулевым значением.

Показать, что М имеет такую квадратнуи» невырожденную подматрнцу М, что ум УМ !У ! уМ-!у г где У вЂ” вектор нужной размерности, все компоненты которого рваны 1. а) Произведение х на любой столбец из М, принадлежащий М, должно равняться а, б) Произведение у на любую строку из М, принадлежащую М. должно рввнятьси ц в) У-я строка и у-й столбец из М должны принадлежать М, если х; > О и у, > О.

г) К матрице М можно добавлять строки и столбцы (при этом должны выполняться свойства а) и б)) до тех пор, пока онн остаются линейно независимыми. д) Если построенная таким способом матрица имеет линейно зависимые строки, то точка х не является крайней. Если столбцы линейно зависимы, то точка у не является крайней. 7. Пусть А = (а!!) — кососимметрическая матрица игры. Пусть х (хь..., х ) — смешанная стратегия. Введем обозначения: и! ~~'~ адху, !р (и!) шах (О, и!) у ! Ф(х) ~', ф (и!), «р (х) ~~~ф'(и!). ! ! ! ! Показать, что для любой «начальной» стратегии хз решение системы дифференциальных уравнений — ф(и!) — кгФ (х), х (О) хз «!х! «(у 1, Показать, что если С вЂ” любое выпуклое множество и х — любая точка границы С, то существует такой вектор рчЬО, что ~ х р! О и ~ у,.р! 3-О для всех у щ С.

(Это несколько более сильный вариант теоремы об опорной гиперплоскости. Воспользуйтесь этой теоремой и тем обстоятельством, что если к находится на гравице С, то существует последовательность точек х" ф С, которая сходится к х.) 2, Показатзь что множество оптимальных стратегий всегда замкнуто, выпукло и ограничено и, следовательно, является выпуклой оболочкой своих крайних точек. Гл. П. Антагонистические игры сходится к оптимальной стратегии в том смысле, что оно должно иметь предельные точки и любая предельная точка является оптимальной стратегией.

а) Если кг — стратегия, то к(Г) будет стратегией прн всех Г. б) Функция ф удовлетворяет уравнению — — 2Ф(к) ф(к). г!ф г(! в) ф(к) ~ Ф'(к), г) Из б) н в) должно следовать неравенство ф (") О+ рфю)' 8. Пусть А (а!г) — произвольная (и Х л) -матрица. Рассмотрим, палец (огн Х тн)-матрицу В (Ьрч), определяемую следующим образом: Ьы„вн+Ь,<а Пн+, аи — аиГ. Показать, что матрица В кососнмметрнчесиая; следовательно, она представляет симметрнчную игру.

Кроме того, показать, что если й (Хь ..., ),~ч) — опти. мальная стратегия для В, то векторы х н у, определяемые равенствами кт ~~г~ аы 1 и+! /-1 У! Х йн-!! н+Р г ! являются оптимальными стратегнямн в А для игроков ! и П соответственно. 9. (Решение нгр прн помощи фиктивного разыгрывания). Рассмотрнм следующий процесс для матричной игры А (аы). Два нгрока разыгрывают зту игру много раз. Прн первом разыгрывании они могут использовать любые стратегия.