1.4. Последовательное удаление слабо доминируемых стратегий

Рассмотрим следующую известную игру "Море Бисмарка". Предыстория события такова: 1943г. Адмирал Imamura получил приказ доставить подкрепление по морю Бисмарка на Новую Гвинею. В свою очередь адмирал Кеnnеу должен был воспрепятствовать этому. Imamura должен был выбрать между Северным (более коротким) и Южным маршрутами, а Кеnnеу — решить куда посылать самолеты, чтобы разбомбить конвой. Причем в течение одного дня самолеты могут бомбить лишь на одном из двух направлений — либо на Северном, либо на Южном маршрутах (но не на двух). Поэтому, если Кеnnеу посылает самолеты в сторону неправильного маршрута, то они могут вернуться, но число дней, когда возможна бомбежка, уменьшается. Описываемая ситуация моделируется следующей игрой. Считаем, что Северный маршрут займет 2 дня, а Южный — 3. (См. рис. 11).

Рис. 11.

Вообще говоря — это матричная игра, т. е. антагонистическая игра с конечным множеством стратегий у каждого игрока. Ни один игрок не имеет доминирующей стратегии. Но здесь можно говорить о слабом доминировании: для Imamur'ы стратегия Юг слабо доминируема, так как для любой стратегии Кеппеу проигрыш Imamur'ы (число дней, когда конвой будет подвергаться бомбордировкам) не меньше для Ю, чем для С, но для стратегии Кеnnеу Ю — проигрыш при С строго меньше, чем при Ю.

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

Представим себе, что Кеnnеу понимает это и считает, что Imamura выберет Север. В этой новой ситуации Кеnnеу имеет уже доминирующую стратегию — Север. Это и дает нам равновесие при последовательном удалении доминируемых стратегий. (В действительности, так и случилось: 2-5марта 1943 г. ВВС США и Австралии атаковали японский конвой, который шел по Северному пути и потопили все транспортные корабли и 4 эсминца: из 7000 чел. до Новой Гвинеи добрались 1000.)

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

Действительно, рассмотрим следующую игру (рис. 12).

Рис. 12.

Если вначале удаляется u (слабо доминируется М), а затем L (слабо доминируется R), то мы приходим к исходу (2,1) (второй игрок выбирает R). Если же вначале удаляется D (слабо доминируется М), а затем R (слабо доминируется L), то мы приходим к исходу (1,1).

Рассмотрим несколько примеров. Мы начнем со знаменитой Дилеммы Заключенного — в некотором смысле чрезвычайно простой игры, которая в разных формулировках встречается в большинстве учебников по теории игр, которая приводится едва ли не в самом начале каждого курса и которую многие сразу же вспоминают, когда слышат словосочетание "теория игр".

Дилемма Заключенного. Ставший почти хрестоматийным сюжет этой стилизованной истории таков. Двое подозреваемых в совершении тяжкого преступления арестованы и помещены в одиночные камеры, причем они не имеют возможности передавать друг другу какие-либо сообщения. Их допрашивают поодиночке. Если оба признаются в совершении преступления, то им грозит, с учетом их признания, тюремное заключение сроком по 6 лет каждому. Если оба будут молчать, то они будут наказаны за совершение какого-то незначительного преступления и получат в этом случае по 1 году тюремного заключения. Если же один из них сознается, а другой — нет, то первый, за содействие следствию, будет вовсе освобожден от наказания, тогда как второй будет приговорен к максимально возможному за данное преступление наказанию — 10-летнему тюремному заключению.

Описанная история может быть представлена следующей игрой (рис. 13).

Рис. 13.

Здесь нетрудно убедиться в том, что стратегия "молчать" является строго доминируемой для каждого игрока (еще раз напомним, что они рациональны), поэтому каждый игрок выберет стратегию "сознаться". В результате оба заключенных получат по 6 лет тюремного заключения.

Как мы увидим ниже ситуация ("сознаться", "сознаться"), естественно, является ситуацией равновесия по Нэшу. При этом мы сразу же сталкиваемся с бросающейся в глаза проблемой: получающийся исход очень плохой — он дает максимальный суммарный срок заключения (разумеется, мы подчеркиваем это еще раз, не следует забывать предположение о рациональности игроков, поскольку здесь исключаются из рассмотрения проблемы предательства, и т. д.). Это послужило толчком к многочисленным исследованиям этой игры, поскольку, например, естественным желанием было бы получить в качестве исхода этой игры (или ее модификаций) ситуацию ("молчать", "молчать"), дающую каждому заключенному лишь по одному году заключения.

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

"Дилемма заключенного - 2". Рассмотрим две страны добывающие нефть, которые мы назовем, скажем, А и В. Эти две страны могут кооперироваться, договариваясь об объемах ежедневной добычи нефти, ограничиваясь, к примеру, добычей 2 млн. баррелей нефти в день для каждой страны. С другой стороны, страны могут действовать некооперативно, добывая, скажем, по 4 млн. баррелей в день. Такая ситуация может быть представлена следующей игрой, в которой указаны прибыли стран, в зависимости от их объемов добычи нефти (рис. 14).

Рис. 14.

Эта картина достаточно типична для картеля, когда у каждого из членов картеля есть стимул отклониться от договора, чтобы за счет увеличения объемов продаж получить дополнительную прибыль.

Легко видеть, что и здесь у каждого из игроков есть доминирующая стратегия — "не кооперироваться". В результате страны получают прибыль 32 и 24 (млн. долларов в день), что гораздо меньше, нежели в ситуации кооперативного поведения.

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

Можно ли достичь "кооперативного поведения" в дилемме заключенного? Как мы увидим в следующей главе — да.

Здесь мы ограничимся лишь еще одним примером на эту же тему.

"Дилемма заключенного - 3". Предположим, что есть 2 работника, которые могут "работать" (s_i = 1) и "увиливать" (s_i = 0) (s_i — уровень усилий, которые прикладывает работник i). Суммарный выпуск "команды" 4(s₁+s₂) делится поровну между работниками. Каждый работник несет издержки равные 3, если работает, и равные 0, если увиливает. Соответствующая матрица изображена на рис. 15.

Рис. 15.

"Работать" — строго доминируемая стратегия для каждого работника.

Аукцион второй цены. У продавца есть одна единица неделимого товара. Есть п потенциальных покупателей, которые оценивают товар, соответственно, в 0 < v₁ < … < v_n и эти оценки являются "общеизвестными". Покупатели одновременно делают свои заявки (назначают цену) s_i[0, +). Назначивший максимальную заявку получает товар и платит вторую цену, т. е. если игрок i выигрывает (s_i > ), то его полезность есть u_i = v_i — , а остальные ничего не получают и ничего не платят (т. е. u_j = 0). Если несколько покупателей назначают высшую цену, то товар распределяется случайным образом (например, равновероятно).

Легко убедиться в том, что стратегия назначения своей оценки (s_i = v_i) слабо доминирует все остальные. Действительно, пусть r_i = . Пусть s_i > v_i. Тогда, если r_i  s_i, то r -ый участник получает 0, что он получил бы и при s_i = v_i. Если r_i  v_i, то он получает v_i  r_i, что он опять же получает, назначив v_i. Если теперь v_i < r_i < s_i, то его полезность v_i  r_i < 0, а если бы он назвал v_i, то он бы получил 0. Аналогично и для s_i < v_i: если r_is_i или r_i  v_i, то он получает ту же полезность, назвав v_i вместо s_i. Если же s_i < r_i < v_i, то он упускает возможность получить положительную полезность.

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

Мы вернемся к аукциону второй цены в п. 1.6.