Лекции по теории игр и политологии
 Скачать 1.03 Mb.
|
|
в конечной и бесконечной играх? Достаточно ли его также и в бесконечной игре? Но гипотеза о некотором ε > 0 кажется произвольной: какое именно ε реально? Можно предполагать “очень малую” вероятность случайных ходов, тогда формируя концепцию решения приходится переходить в предел ε− > 0. Этим путем мы и пой- дем, только предполагая неодинаковые частоты случайных ходов (ε 1 , ..., ε n ) у разных игроков, и будем идти в предел по "определенному направлению”. Содержательно, идея секвенциального равновесия, вытекающего из этой идеи, описывается так. В по- пуляции игроков (типов), которую мы рассматриваем, была некоторая предыстория нынешнего состояния. Все игроки ошибались, делая случайные ходы, и все предполо- жения и веры о том, что обычно происходит в каждой информационной позиции или узле игры - обоснованы этой предысторией. При этом частоты случайностей умень- шались, возможно неравномерно, и сейчас оказались практически нулевые. Но наши теперешние веры у всех одинаковы и обоснованы предысторией, что формально кон- цепцию можно выразить так. Определение 2.8.2 (Сильное) секвенциальное равновесие SeqE в игре n лиц есть набор (¯ σ, ¯ µ) смешанных пошаговых (поведенческих) стратегий ¯ σ = (¯ σ 1 , ..., ¯ σ n ) ∈ ∆X и вер ¯ µ = (¯ µ 1 , ..., ¯ µ n ) ∈ ∆M всех игроков, таких что 1) стратегии ¯ σ i являются секвенциально-рациональными, при данных верах ¯ µ и стра- тегиях партнеров ¯ σ j ; 2) веры ¯ µ сильно согласованы с наблюдаемым стратегиям ¯ σ, в том смысле, что су- ществует последовательность вполне смешанных стратегий σ (k) → ¯ σ сходящаяся к равновесной, по которой (однозначно) строится последовательность вер µ (k) → ¯ µ, схо- дящихся к ¯ µ. 28 Если к тому же стратегии ¯ σ секвенциально-рациональны не только при финальных верах ¯ µ, но и при всех поздних (начиная с некоторого номера) членах построенной последовательности вер σ (k) , то это равновесие SeqE называют (Совершенным) Рав- новесием дрожащей руки THPE (Trembling Hand Perfect Equlibrium). 29 Теперь сопоставим различные концепции решений. 2.9 Сопоставление решений SPE, SBE, SeqE, THPE, INDW Введенные понятия SeqE, T HP E, и идеи случайных ходов оправдывают выделение равновесий со слабым доминированием типа INDW (или SoE) среди равновесий типа SPE. Действительно, все слабо доминируемые стратегии отбрасываются, если есть вероятность (даже если она близка к нулю) любого исхода. Поэтому, во многих играх окажется T HP E = INDW , и в любом случае T HP E ⊂ INDW (проверьте это). 28 В частности, если все ходы из некоторого узла оканчиваются в одном (последующем) информа- ционном множестве, то веры в нем должны совпадать с вероятностями ходов: ¯ µ h = ¯ σ h−1 29 Вообще-то, определение ‘дрожащей руки’ обычно дают в терминах нормального представления игры, без понятия вер, и получается формально другой объект - (Trembling Hand Nash Equlibrium). Он в играх с полной рациональностью (условия Куна) совпадает по множеству стратегий и выигры- шам с THPE, которое нам удобнее для сопоставления с секвенциальным. 51 Традиционно решения SeqE и THPE определяют только для смешанных страте- гий, так что можно обозначать SeqE ≡ SeqE m и THPE ≡ T HP E m . Однако нам далее удобно ввести обозначения и определение этих концепций и для чистых стратегий (pure strategies), а именно — это те чистые стратегии, которые входят в соответству- ющее множество секвенциальных или "дрожащих"равновесий (s как интенсивности применения чистых стратегий, состоят из нулей и единиц): T HP E p := {s ∈ T HP E m | s − integer }, SeqE p := {s ∈ SeqE m | s − integer }. Сопоставляя концепциии, понятия T HP E и NE m можно считать полюсами (самое узкое и самое широкое множества среди введенных здесь), между которыми вмеща- ется большинство остальных некооперативных концепций как частный случай сме- шанных Нэшевских решений. Действительно, SPE в чистых стратегиях обобщается до смешанного SP E m . Аналогично, каждую концепцию можно рассматривать и в чи- стой и в смешанной форме. Соответственно, можно составить следующий важный граф вложений (его левый и правый края смыкаются, что отражено повторами обо- значений SP E i ): 30 SP E mul SP E m ⊃ P BE m ⊃ SeqE m ⊃ THPE m ⊂ INDW mΓ ⊂ SP E m ⊂ NE m ∪ ∪ ∪ ∪ ∪ ∪ ∪ ∪ (9) SP E ≡ SP E p ⊃ P BE p ⊃ SeqE p ⊃ T HP E p ⊂ INDW pΓ ⊂ SP E p ⊂ NE p ≡ NE. В этом графе центральное положение занимает наиболее узкая, наиболее рафини- рованная концепция из верхней цепочки с еще гарантированным существованием (см. теорему ниже) – это THPEm. Из приведенных вложений следует, что если T HP E m существует, то существуют и все охватывающие THPEm решения. Для существования же всех “целых” концепций, то есть нижней цепочки, нужны дополнительные условия. Иначе, есть примеры несуществования, даже для наиболее широкой из них концепции NE. Какие условия? Например, INDW pΓ , SeqE p и более широкие концепции развер- нутой формы существуют при совершенстве информации (отсутствии нетривиальных информационных множеств). Благодаря приведенным выше цепочкам вложений, существование всех названных (смешанных) решений можно вывести из существования THPE. Сформулируем его условия (доказательство этой непростой теоремы мы опускаем). Теорема 4 В конечной игре с полной рациональностью (хотя, возможно, и несо- вершенной информацией о ходах) смешанное Равновесие дрожащей руки существует (T HP E m 6= ∅). Следствие: NE m 6= ∅, P BE m 6= ∅, INDW Γ 6= ∅, SP E m 6= ∅, SeqE m 6= ∅. Сложное доказательство опускаем. 30 Под SP E mul подразумевается решение SPE в мультиперсонном представлении игры, которое бывет шире обычного. 52 Сопоставим концепции далее: решение T HP E p в большинстве случаев совпадает с IN DW Γ , расхождение мне (С.К.) неизвестно. Равновесие Нэша – это SP E в одношаго- вой игре с одновременными ходами. Пара равновесие Штакельберга – это просто SP E двухшаговой игры, когда лидер ходит первым (а по сравнению с "оптимистическим Штакельбергом” SP E может включать еще какие-то исходы). Максимин может быть аппроксимирован P BE(ε)-равновесиями модифицированной игры, при элементарных функциях полезности участников с очень большим неприятием риска. С другой стороны, полезно продемонстрировать, что понятия SPE, SBE, SeqE не тождественны, и понять, почему. Пример 2.10 (“Ослик” Зелтена, вариант-2) . Интерпретация игры не обсу- ждается, игра названа “Ослик” за форму графа: Ann Bob Cons Cons ? ? - - U U (1,1,1) (3,3,3) (2,2,2) (5,5,0) (4,4,4) L L R R A a b B Рис. 8: Игра “Ослик” (Selten, 198..?). Здесь два SPE в чистых стратегиях: SPE1=(aL[B]) при соответствующих по Байесу верах, и SPE2=(AB[R]) при верах a, b третьего игрока, наблюдающего, что ему дали ход (вероятностях, что дали из позиции a или из b) типа a > 2b. Первое, то есть SPE1, есть также и SPBE, но не может быть секвенциальным равновесием (SeqE), а SPE2 является секвенциальным. Итак, мы представили широкий арсенал концепций решений, применимых в раз- ных ситуациях игр и их связи. Подбор адекватной модели (графа) и концепции игро- вого решения под жизненную ситуацию – творческое дело исследователя, требующее знания содержательной стороны дела. Ничем, кроме примеров, учебник здесь не по- может. 53 Это завершает рассмотрение “популяционных” или “эволюционных” игр, характе- ризующихся полной рациональностью. Теперь мы займемся играми с более сложной информационной структурой, чем “популяционные”. В принципе, все введенные кон- цепции решений применимы и в них, в том числе в играх с несовершенной рациональ- ностью или необщим знанием, в повторяющихся играх одной пары партнеров. Но в них есть и специфика, и другие решения. 2.10 Отсутствие “общего знания”, игры с репутацией, блеф Изменим гипотезы игры “сороконожка” (“Бери или оставь”), добавив к возможности иррациональных ходов неопределенность знаний о степени иррациональности парт- нера (это уже не “общее знание”). Окажется, что концепция решения P BE(ε) должна модифицироваться, и включать характеристику информации. Пример 2.11 (Продолжение игры “Бери или оставь”) (“Сороконожка”) Пусть, в разобранной выше игре “сороконожка” ситуация изменилась: игрок Victor слышал, что Анна в подобной игре из 10-ти ходов сделала 1 иррациональный (невыгод- ный, ошибочный), и ожидает, соответственно, вероятность иррациональности около α = 1/10. Аналогично, Анна слышала, что Виктор в подобной игре из 30-ти ходов сделал 2 иррациональных хода, она ожидает вероятность иррациональности β = 2/30 (это окажется не то же, что 1/15!). Предположим, игроки считают рациональным брать банк, когда вероятность ошибки партнера больше 1/7 и ожидают от партнера такого же мнения. Очевидно, при такой “простоватой” рациональности, Анна на пер- вом ходу ВОЗЬМЕТ (если не ошибется). Но если он ошибется, возьмет ли Виктор? Он может интерпретировать оставление Анной как ошибку, и тогда подправить свою субъективную вероятность ошибок А до величины (1+1)/(10+1)=2/11. Либо считать случившееся оставление рациональным ходом, и сделать отсюда вывод о текущих гипотезах (β =?) Анны относительно себя (Виктора). Независимо от того, верны ли эти гипотезы, выгодно ли теперь Виктору оставлять и пойдет ли игра до узла V 3 ? 1)По сравнению с предыдущей ситуацией, оставим Виктора “простым”, а первого игрока предположим способным рассчитать предыдущую ситуацию. Станет ли он на первом шаге ОСТАВЛЯТЬ, независимо от своих гипотез о партнере (БЛЕФОВАТЬ)? Пойдет ли игра до 6-го хода? 54 2)Что если теперь оба игрока “сложные”, и В просчитывает возможность блефа первого (считающего второго простым), изменит ли это результат? 2.11 Уточнение понятия рациональности; прямая индукция Кольберг и Мертенс (1986) предложили возможность сужения множества совершен- ных или других равновесий основанных на обратной индукции с помощью “прямой индукции”. По сути дела она означает решение игры по доминированию и в развер- нутой и в нормальной форме (по определенному порядку), и пересечение множеств ответов. Это затрагивает фундаментальный вопрос о “creadible commitment”, 31 подня- тый Нейманом и Моргенштерном: всегда ли игроки могут до игры рассчитать свои оптимальные стратегии (планируемые реакции на возможные ходы/информацию), а затем только придерживаться их? Часто это не так, и игроку было бы выгодно с само- го начала объявить свою стратегию, и лишить себя возможности передумать затем в ходе игры (см. игру “Цезарь сжигает мосты” в задачнике). В следующем же примере (Рис. 9) противоречия не возникает, и прямая индукция выглядит обоснованно. µ - q 3 - 7 j A 1 A 2 V 1 V 1 4, 0 5, 1 0, 0 0, 0 3, 4 a b c d u u z z Рис. 9: Прямая индукция. В этой игре Виктор в ситуации V 1 не знает, сходила ли Анна c или d. Здесь два последовательных равновесия SPE в чистых стратегиях (и еще одно в смешанных): (a, [d, z]), (b, c, u). Однако, только последнее остается, если рассматривать прямую ин- дукцию, определяемую так. Приведя эту игру к нормальной форме заметим, что стра- тегия Анны (b, d), сильно доминируется ее стратегией (a). Зная это, Виктор, в случае наблюдаемого хода (b), должен решить, что Анна имела в виду стратегию (b, c), и сходила (c) а не (d). Тогда ему разумно ходить (u), другой ответ на (b) нерационален. Зная это, Анна пойдет (b) а не (a), и получит 5. Так дополнительные сообржения о рациональности по “прямой индукции” сузили множество ожидаемых исходов игры. 55 > µ - q 3 - 7 j V 1 0, 8 A 2 0, 8 V 2 V 2 1, 0 3, 6 9, 0 0, 2 1, 0 0, 8 A 1 a b x y c d u u z z Рис. 10: Прямая индукция при неполной рациональности. Однако в другой подобной игре (Рис. 10) подобные соображения могут быть обос- нованы только неполной рациональностью; множества решений по прямой и по обрат- ной индукции не пересекаются! На Рис. 10 игроки ходят по очереди, и Виктор также на последнем ходе не знает предыдущего хода Анны. Но это ему и не нужно, ведь в любом случае он сходил бы вниз: (z), этот ход строго доминирует над (u). Поэтому единственное SPE =(a, [y, d, z]). Если же мы переведем эту игру в нормальную форму (Табл. 16), то окажется, что стратегия Анны (bc) слабо доминирует над (bd). Одновременно стратегия Виктора (x) слабо доминирует над (yu). Затем (bc) сильно доминирует над (a) и единственное SoE=(b, x, [, z]) 6= SPE. Поэтому SoE не кажется рациональным: как можно верить, что в ситуации A 2 Анна пойдет вверх на (c) ожидая на это рациональный отклик (z)? Но, с другой стороны, в ситуации V 1 Виктор может рассуждать и так: а почему же она вообще пошла сюда, в этот узел, если предполагает меня рациональным? Это невозможно. Тогда она может ожидать от меня иррационального хода: (u). И ожидая его, планировать ход (c). Тогда Виктор ходит (x) и SoE действительно реализуется. При этом, возможно, Анна блефовала, демонстрируя ходом (b) свое неверие в рацио- нальность Виктора, и получила 3 от блефа вместо 1 по тривиальной стратегии a. Anna\ Victor x yu yz a 1, 0 (SP E, SoE Γ ) 1, 0 1, 0 bc 3, 6 (SoE f orward ) 9, 0 0, 2 bd 3, 6 1, 0 0, 8 Таблица 16: Прямая индукция. После хода (b), Виктору надо решить что это: взятие на пушку, глупость или по- дозрение партнера в глупости. В последних случаях надо ходить вверх! При гипотезе же полной рациональности обоих (известной обоим), нужно не покупаться на блеф, ходить вниз (y, z) и иметь 8. С другой стороны, если бы Анна имела возможность объявить, владея “creadible commitment”, стратегию (b, c) и не отступать от нее, то реализовала бы выигрыш 3. Тогда, при “creadible commitment”, Виктор вынужден отступить на (x). Мораль из этого примера: в ситуациях однократной игры, в том числе при непол- ной рациональности игрок может стараться сделанным ходом сигнализировать о сво- их гипотезах (истинных или блефовых) относительно партнера, к своей выгоде. Это практически эквивалентно сигнализированию о своем типе в Байесовских играх. 31 Этот термин в играх означает “выполнимое обещание”. 56 Аналогично, применение стратегий, а не ходов, резонно в повторяемой игре, где игрок способен завоевать репутацию. Тогда прямая индукция правдоподобна. Упражнение. В примере “футбол или кино” (Рис. 1.1), рассмотрите следующую модификацию. Пусть, Виктор общается с Михаилом, который наверняка увидится с Анной до вечера, до выбора футбол/кино, но стесняется прямо попросить Михаила передать Анне просьбу прийти на футбол или в кино. Он сжигает 1 рубль на глазах Михаила, никак не объясняя своего поступка, но надеясь, что тот расскажет Анне об этом странном случае, и та сделает выводы. Покажите прямой индукцией, что это сжигание – разумный ход Виктора. 2.12 “Почти-совершенная” информация: повторяющиеся игры с угрозами. “Почти-совершенной” называют информацию о всех сделанных ходах, кроме послед- него или текущего. Подобная ситуация возникает в весьма распространенном классе “повторяющихся” игр. Это такие игры, где участники ходят одновременно, затем од- новременно наблюдают результат действий партнеров, еще раз разыгрывают эту же игру, и т.д. Например, игра “Монетки”, “Перекресток”, “Футбол или кино” – могут быть разыграны в повторяющемся режиме. Что тогда изменится в типе решения? 57 Строго говоря, при анализе такой игры уже нельзя обойтись просто матрицей нормальной формы игры. Правильный подход – рассматривать дерево игры с повто- ряющимися элементами, конечное или бесконечное. Оказывается, что решения при этом могут существенно отличаться от решений однократной аналогичной игры. Пример 2.12 (“Камень в огород” ) (или повторяющаяся “Дилемма заключен- ных”) Предположим, два недолюбливающих друг друга соседа имеют выбор: бросить соседу камень в огород, уходя утром на работу, или воздержаться. 32 Выигрыши зада- ны следующей игрой в нормальной форме.. -1, 2 0, 0 2, -1 1, 1 Victor - s Anna - 3 Victor - s Agress.Peace Anna - 3 - Period t-1 Period t Period t+1 6 - 1 1 2 2 A V Average payoff Ag. Pe. Ag. Ag. Pe. Pe. Рис. 11: Повторяющаяся игра “Камень в огород”. Очевидно, структура игры та же, что в “дилемме заключенных”. Поэтому един- ственное строго доминирующее равноесие SDE (и одновременно единственный не- Парето-эффективный исход!) есть (Агрессия,Агрессия). Теперь рассмотрим дерево этой игры на конечном интрвале времени, предполагая цели игроков в виде дискон- тированной суммы выигрышей по периодам. Окажется, что совершенное в подыграх равновесие (SPE) то же, что и DE: ( |