Лекция 8. Исключение доминируемых стратегий

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

В общем случае поведение игрока зависит от его информации о других игроках, в частности, об их полезностях. Пусть, для простоты, два игрока. Если первый знает полезности второго и знает, что второй не знает его по­лезности, ОН будет уверен, ЧТО ВТОрОЙ ПрИМеНИТ ОСТОрОЖНуЮ СТратеГИЮ 5*2,

и тогда сам применит свой наилучший ответ на 5*2- А как быть, если первый знает полезности второго, но не знает, знает ли второй его полезности? В дальнейшем мы сосредоточим внимание на частном, можно сказать - выро­жденном - случае, которым только и занималась ортодоксальная теория игр, на случае полной информации. Под этим понимается, что все игроки знают полезности друг друга, знают, что все это знают и т.д.

Метод исключения. На предыдущей лекции мы показали, что рацио­нальный игрок не использует доминируемые стратегии. Рассмотрим игру

 

п

 

 

 

4,3

2,7

0,4

52

5,5

5,-1

-4,-2

Видно, что стратегия £3 явно плохая для второго игрока; более точно, она доминируется (сильно) стратегией VI. Поэтому 2-й игрок ее применять не будет. У 1-го игрока доминируемых стратегий нет. Однако если он знает полезности 2-го, то он понимает, что 2-й не будет применять £3. Но тогда игра редуцируется к

 

п

 

51

4,3

2,7

52

5,5

5,-1

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

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

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

= 5^ 13 5^ 13 ... 13 5^ 13 ...

для каждого игрока /. где состоит из недоминируемых стратегий в игре (Ы, (б^), щ\Бк). Ясно, что (в силу конечности множеств 5^) эта последова­тельность стабилизируется на множествах, которые мы условно обозначим 5?°. Игра разрешима по доминированию, если все 5?° состоят из единствен­ной стратегии (или из эквивалентных стратегий для игрока г).

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

А именно, рассмотрим предфинальную вершину у. В ней делает ход игрок г. И совершенно ясно, какой он сделает ход - тот который дает максималь­ное значение щ. (Может, правда, оказаться, что есть несколько ходов с мак­симальным щ. Это источник неоднозначности процедуры, однако если вы­игрыши всех игроков во всех финальных вершинах разные, то процедура уже однозначна, т.е. является алгоритмом.) В этом случае мы можем сде­лать нашу предфинальную вершину у финальной, поместив туда платежитой финальной вершины х, в которую пойдет игрок г. И так шаг за шагом мы редуцируем всю игру в начальную вершину. Все это называются алго­ритмом Цермело-Куна.

Покажем это на примере игры

(2,2)

и

• 1

В

(3,1)—^02-^—(0,0)

Игрок 2, поставленный перед выбором ходов / иг, несомненно выберет I. Поэтому мы можем редуцировать исходную игру к виду

(2,2)

и

• 1

В

(3,1)

После этого ясно, что 1-й выберет В7 и мы приходим к решению (В,1).

Видно, что эти аргументы близки к аргументам исключения доминируе­мых стратегий, и это действительно так. Те стратегии, которые получаются алгоритмом Куна, выживают при исключении по (слабому) доминированию, а остальные исключаются. Это утверждение известно как теорема Куна. До­казательство см. в книге Мулена, гл. 2.

Общее знание. Заметим, что разрешение по доминированию существен­но опирается на знание всеми предпочтений всех, а также на рациональность всех игроков. Но не только. Вернемся к первому примеру. Игрок 2 исключа­ет стратегию £3, потому что рационален, но откуда первый игрок знает, что второй ее исключит? Для этого нужно предположить, что 1-й игрок знает, что второй рационален. А второй применяет стратегию И потому, что знает, что первый знает, что второй рационален, а также, что первый рационален (чтобы исключить в1).

Одним словом, не только каждый игрок рационален, но этот факт яв­ляется, как говорится, общим знанием (common knowledge). Некий факт Л является общим знанием, если все знают Л, все знают, что все знают Л, все знают, что все знают, что все знают Л, и т.д. Чтобы лучше прочувствовать это, приведем одну (быть может, не самую лучшую, но простую) байку про общее знание.

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

В это время в купе заглядывает Проводник и объявляет, что в вагоне находится человек с грязным лицом. После этого Алиса покраснела. Она по­няла, что ее лицо испачкано. Но почему она поняла это? Разве проводник не сообщил то, что она уже знала!

Проследим цепочку рассуждений Алисы.

Алиса: Предположим, мое лицо чистое. Тогда Боб, зная, что кто-то из нас грязный, должен сделать вывод, что грязный он, и покраснеть. Раз он не краснеет, значит, моя посылка про мое чистое лицо ложная, мое лицо грязное, и я должна покраснеть.

Проводник добавил к информации, известной Алисе, информацию о зна­ниях Боба. До этого она не знала, что Боб знает, что кто-то из них испачкан. Короче, сообщение проводника превратило знание о том, что в кабине есть

человек с грязным лицом, в общее знание.

Фактически, это упрощенный вариант байки про мудрецов в красных колпаках. Обыч­но ее преподносят в более сложном варианте с тремя мудрецами. Сидят три умника, на каждом надет колпак красного цвета. Каждый видит колпаки других, но не видит, ка­кой колпак на нем. И каждому, чтобы показать свою проницательность, нужно угадать цвет своего колпака. Прохожий (или экзаменатор) объявляет всем, что один из колпаков красный. Тогда один из мудрецов понимает, что на нем красный колпак. Рассуждает он так: допустим, на мне надет белый колпак. Тогда два оставшихся умника, узнав подсказку прохожего, быстро сообразили бы (смотри предыдущий рассказ про Боба и Алису), что на ком-то из них красный колпак, и объявили бы об этом. А раз они молчат, значит на мне красный колпак.

Конечно, тут можно поставить любое число мудрецов.

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

Сороконожка. Рассмотрим вариант сороконожки Розенталя, Один эксцентричный филантроп готов подарить университету миллиард долларов. Он приглашает президентов университетов Иелбриджа и Харфорда и объясняет, что они должны разыграть следую­щую игру. Дерево ее имеет вид

12        12 2 12

•--О--О--О----- —О--О--О-- (0,0)

1,0    0,10   100,0 0,1000        о,ю7   108,0 0,109

На первом ходе филантроп предлагает президенту Иелбриджа 1 доллар, который тот может принять или отказаться. Если он отказывается, филантроп предлагает президенту Харфорда 10 долларов и т.д., повышая ставки каждый раз в 10 раз.

Применяя алгоритм Цермело, мы видим, что каждому из президентов надо принимать предложение. Поэтому игра должна закончится на первом же ходу - президент Иелбриджа схватит 1 доллар! Чувствуется, что здесь что-то не так.

Рассмотрим, например, ситуацию в вершине 4, когда президент Харфорда решает -взять 1000 долларов или отказаться. Обратная индукция (алгоритм Цермело) говорит, что надо соглашаться. Почему? Потому что президент Иелбриджа рациональный и т.д. и поэтому на следующем шаге хапнет 10000. Но если он такой рациональный, то что же он на предыдущем шаге отказался от 100 долларов? А как бы вы сами играли в этой игре1?

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

Ослабления. Иногда процедура исключения приводит к единственному исходу, но чаще - нет.

Можно было бы исключать и слабо доминируемые стратегии, как это по существу и делается в алгоритме Цермело-Куна. Однако исключение слабо доминируемых стратегий уже не столь несомненно (и не выводится из ги­потез о рациональности игроков). Во-первых, начинает играть роль порядок исключения. Но это полбеды. Хуже, что слабо доминируемые стратегии мо­гут входить в равновесия. Рассмотрим игру

 

п

Г2

 

 

100,0

52

0,100

100,100

1 Здесь можно увидеть аналогию с рассказом о "неожиданной проверке". Учительница говорит ученикам, что она устроит им проверку в один из дней будущей недели. Когда? - спросили уче­ники. Когда вы не ожидаете этого, ответила учительница. Они решили, что это не может быть пятница, но тогда и не четверг, и т.д. Так они решили, что проверки не будет, и не готовились. Но в понедельник учительница устроила проверку, и для всех это оказалось неожиданным!

Здесь первый столбец слабо доминирует второй, как и первая строка слабо доминирует вторую. Исключение таких "слабых"стратегий дает выигрыши (1,1). Но есть более хорошее решение (в2,£2).

Доминируемые стратегии. Выше мы исключали те стратегии 8, которые сильно доминировались некоторой более лучшей стратегией з'. На самом деле можно немного расширить список исключаемых стратегий. Такие "плохие" стратегии будут называться доминируемыми. Мы приведем два определения доминируемости и затем покажем, что они эквивалентны. Здесь мы фиксируем одного игрока и пишем 5 вместо Б{. Множество стратегий остальных игроков обозначим как О.

Первое определение. Стратегия 5 доминируется, если для любой "смешанной" точки [л е Д(О) найдется стратегия ,з' е Б, такая что в (/л) < в'(/л).

Конечно, если некоторая стратегия з' доминирует 8, ее можно использовать в первом определении. Однако в общем случае "победитель" стратегии 5 зависит от ситуации (то есть от /л).

Второе определение. Стратегия 5 доминируется, если найдется "смешанная" стратегия о е Д(Б), которая сильно доминирует 5.

Видно, что второе понятие посильнее. Замечательно, что на самом деле они совпада­ют. Это следствие теоремы о разделении выпуклых множеств и фактически уже выло установлено в Лекции 6. Однако не мешает и повторить.

Предложение. Оба предыдущих понятия доминируемости совпадают.

Доказательство. Снова будем стратегии из 5 мы изображать векторами в пространстве К°. Так что 5 реализуется как конечное подмножество в К°. Если теперь А - "внутренняя оболочка" 5 в смысле Лекции 6, то стратегия 5 доминируется во втором смысле, если она попала во внутренность А.

Предположим теперь, что стратегия 5 не доминируется во втором смысле, то есть не попадает внутрь А. Тогда она лежит на границе А (и даже на той части границы, которая попадает в выпуклую оболочку 5). Но тогда по теореме об отделении выпуклых множеств существует линейный функционал р на К°, который (нестрого) отделяет 5 от А. Это значит, что р(з) > ткхрА. Очевидно, что р положительный; если отнормировать его, мы получим смесь /л С Д(О) такую что 8(р) > а(р) для любого а е А. В частности, 8(р>) > 8'(р>) Для любого 81 (г Б. Но это означает, стратегия 5 не доминируется в первом смысле. □