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

если Kenney посылает самолеты в сторону неправильного маршрута, то они возвращаются на базу, но число дней, когда возможна бомбежка, уменьшается. Описываемая ситуация моделируется следующей игрой, в которой выигрыши — это число дней, когда возможна бомбежка конвоя (естественно, со знаком «+» для Kenney и «-» для Imamur'bi). Считаем, что Северный маршрут занимает 2 дня, а Южный — 3 (см. рис. 11). Imamura С Ю

Рис. 11.

С

Ю

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

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

Представим себе, что Kenney понимает это и считает, что Imamura выберет Север. В этой новой ситуации Kenney имеет уже доминирующую стратегию — Север.

ВВС США и Австралии атаковали японский конвой, который шел по Северному пути и потопили все транспортные корабли и 4 эсминца: из 7000 чел. до Новой Гвинеи добралась 1000.)

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

Действительно, рассмотрим следующую игру (рис. 12): L R и ( (1,1) (0,0) м (1,1) (2,1) D V (0,0) (2,1) Рис. 12.

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

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

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

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

М С

м П-1,-1) (-10,0) \ с v (0,-ю) (-6,-6)j

Рис. 13.

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

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

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

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

В

К н

К / (46,42) (26,44) \

Л Н \ (52,22) (32,24) ) Рис.

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

Легко видеть, что и здесь у каждого из игроков есть доминирующая стратегия — (Н) — «не кооперироваться». В результате страны получают прибыль 32 и 24 (млн. долларов в день), что гораздо меньше, нежели в ситуации кооперативного поведения. Феномен, с которым мы столкнулись в этом примере, аналогичен «Дилемме Заключенного», и именно поэтому второй пример мы также назвали «Дилеммой Заключенного»: оба игрока играют свои доминирующие стратегии, максимизируя тем самым свои выигрыши, но в то же время исход для каждого из них хуже, нежели в ситуации, когда оба следуют доминируемым стратегиям.

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

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

«Дилемма Заключенного — 3». Предположим, что есть 2 работника, которые могут «работать» (s4- = 1) и «увиливать» (в; = 0) ( Si — уровень усилий, которые прикладывает работник i). Суммарный выпуск «команды» 4(si + S2) делится поровну между работниками. Каждый работник несет издержки, равные 3, если работает (Р), и равные 0, если увиливает (У). Соответствующая матрица изображена на рис. 15.

Р У

Р ( (1,1) (-1,2) \ У V (2,-1) (0,0) )

Рис. 15.

Легко видеть, что «Р» — «Работать» — строго доминируемая стратегия для каждого работника.

Аукцион второй цены. У продавца есть одна единица неделимого товара. Есть п потенциальных покупателей, которые оценивают товар соответственно в 0 < v\ < • • • < vn, и эти оценки являются «общеизвестными». Покупатели одновременно делают свои заявки (назначают цену) G [0, +00) . Назначивший максимальную заявку получает товар и платит вторую цену, т.е. если игрок i выигрывает (> maxj^Sj), то его полезность есть щ = — max^; , а остальные ничего не получают и ничего не платят (т.е. Uj = 0). Если несколько покупателей назначают высшую цену, то товар распределяется случайным образом (например, равновероятно).

Легко убедиться в том, что стратегия назначения своей оценки (Si = Vi) слабо доминирует все остальные. Действительно, пусть ri = maxj^j- Sj . Пусть Si > Vi. Тогда, если r'i > Si, то i-й участник получает 0, что он получил бы и при Si = Vi . Если r'i < Vi, то он получает — гг-, что он опять же получает, назначив . Если теперь < гг- < s; , то его полезность — гг- < 0 , а если бы он назвал , то он бы получил 0. Аналогично и для < : если гг- < s; или гг- > , то он получает ту же полезность, назвав вместо . Если же Si < r'i < , то он упускает возможность получить положительную полезность.

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

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