теориия игр. Лекции по теории игр вводный уровень
 Скачать 1.71 Mb.
|
|
Какова “цена игры” то есть сумма за которую Анна согласится сыграть? Nature Bob+King Bob+Junior Ann * 1 : (u B , u A )=(-1, 1) j 3 - Ann j - > z (-4, 4) (4, -4) (2, -2) (2, -2) α =“rise” α =“rise” probabilty 1 − α 1 − α β J 1 − β K β K 1 − β J 1/2 1/2 µ J 1 − µ J =rise if J Рис. 3.9: Игра “Блеф”: решения PBE = SPNE. На дереве (которое не совсем дерево, поскольку совпадающие исходы изображены объединенно, что допустимо) видно, что Анна имеет информационное множество, не зная, при сильной или слабой карте Боб поднял ставки. Переменная µ bluf f отражает ее веру что он блефует, то есть поднял на слабой карте. При вполне смешанных стратегиях она должна быть вычислена по стратегиям по Байесовскому правилу условных вероятностей. Наример, если Боб всегда поднимает на сильной карте, и выберет вероятность блефа β J = 1/3, то веры окажутся µ J = 1/2∗1/3 1/2∗1/3+1/2 , 1 − µ J = 1−1/2∗1/3 1/2∗1/3+1/2 (то есть сумма вер должна быть равна 1, а пропорция меду ними равна пропорции в полном перечне возможных исходов игры). Можно проверить, что Анна будет пасовать или проверять с равной вероятностью (α = 1/2), а Боб действительно всегда на сильной карте повышает, а на слабой блефует с вероятностью 1/3. 73 3.0.22 Задачи. Упражнение. В примере “Масти и Картинки” приведенном выше в секции ... . найти PBE в вариантах со скрытой информацией, совпадет ли оно с SPNE? Вариант примера “Trivial quiz”: Анна имеет карту “Дама” а в колоде 10, Валет, Дама, Король, Туз. Боб тянет карту из колоды, и не показывая или удваивает ставку, или пасует, тогда имеет -1, а Анна 1. Если удвоено, то Анна или пасует (тогда имеет -2, а Боб 2), или удваивает = “проверяю”, и карта открывется. Если карта Боба больше, чем Дама (т.е. Король, Туз), то Боб выиграл 4 у Анны, иначе (если равна или меньше) проигрывает, получая -4. Найти SBE: частоты “пасов” при каждой карте и веры, цену игры. 3.0.23 Дальнейшие сужения решений: P BE(ε), секвенциаль- ное равновесие (SeqE), T HP E, их существование Удовлетворительная ли концепция P BE? В примере “Базар” проявилась логическая неясность понятия P BE: в нем разные игроки могут иметь разные ожидания об одном и том же партнере вне пути игры. Реалистично ли это? И вообще, как обос- новать ожидания игроков о тех ветках игры, которые никогда не реализуются? Это важно, поскольку от этих ожиданий зависят решения, и они могут оказаться логиче- ски сомнительными. Устранению этой неясности и сужению множество возможных решений служат понятие ε-равновесия P BE(ε) и понятие (сильного) секвенциально- го равновесия SeqE. Определение 3.0.23.1 Для заданного малого ε > 0 назовем ε-совершенным равно- весием (P BE(ε)) - такой набор смешанных мультиперсонных стратегий (σ 1 , ..., σ n ) и вер (µ 1 , ..., µ n ), что веры слабо согласованы со стратегиями, а все стратегии секвенциально- рациональны при дополнительном ограничении: ни один ход не мо- жет иметь вероятность применения меньше ε. По сути, это определение модифицирует PBE, вводя возможность не-рациональных ходов игроков: у любого может "рука дрогнуть", можно ошибиться. То есть, предпо- лагается, что есть случайности, и вероятность всякого хода не менее ε > 0. Важность этой гипотезы видна из примера. Пример 3.0.19 Игра “Возьми или оставь” (“сороконожка”): V 1 s A 2 A 1 V 2 A 3 V 3 s s s s s - - - - - - 4, 1 2, 8 16, 4 8, 32 64, 16 32, 128 256, 64 l A1 l V 1 l A2 l V 2 l A3 l V 3 t A1 t V 1 t A2 t V 2 t A3 t V 3 Рис. 3.10: Игра “Возьми или оставь” (Rosental, 1956?). Пусть первый из двух игроков (Анна) может взять 4/5 общей прибыли (то есть $4 из $5 на ветви take A1 ) на шаге 1, тогда игра закончится, а второму - Виктору 74 Глава 3. Динамические или “последовательные” некооперативные игры - останется $1. Либо можно оставить банк на столе (leave A1 ). На шаге 2 прибыль удваивается (например, ведущим), и черед 2-го выбирать: взять ли 4/5 прибыли (то есть $8 из $10-и) и закончить тем самым игру, или оставить, и т.д. Предсказывая исход для конечной (скажем, по 3 хода каждого) игры по принципу SP E, P BE, или T HP E (определено ниже) мы увидим, что игра тривиально закончится на 1-м шаге take A1 с выигрышами (4,1). А по принципу решения P BE(ε) она может дойти до конца с большой суммой прибыли. (Здесь ε– вероятность не ниже которой ожидается от любого хода, благодаря случайному поведению – иррациональности). Покажите, что ε > 1/7 достаточно для ходов типа leave i и продолжения игры до счастливого конца (или хотя бы для продолжения рациональных ходов до узла V 3 ). Какое ε необходимо для рациональности ходов типа leave i в конечной и бесконечной играх? Достаточно ли его также и в бесконечной игре? Но гипотеза о некотором ε > 0 кажется произвольной: какое именно ε реально? Можно предполагать “очень малую” вероятность случайных ходов, тогда формируя концепцию решения приходится переходить в предел ε− > 0. Этим путем мы и пой- дем, только предполагая неодинаковые частоты случайных ходов (ε 1 , ..., ε n ) у разных игроков, и будем идти в предел по "определенному направлению”. Содержательно, идея секвенциального равновесия, вытекающего из этой идеи, описывается так. В по- пуляции игроков (типов), которую мы рассматриваем, была некоторая предыстория нынешнего состояния. Все игроки ошибались, делая случайные ходы, и все предпо- ложения и веры о том, что обычно происходит в каждой информационной позиции или узле игры - обоснованы этой предысторией. При этом частоты случайностей уменьшались, возможно неравномерно, и сейчас оказались практически нулевые. Но наши теперешние веры у всех одинаковы и обоснованы предысторией, что формально концепцию можно выразить так. Определение 3.0.23.2 (Сильное) секвенциальное равновесие SeqE в игре n лиц есть набор (¯ σ, ¯ µ) смешанных пошаговых (поведенческих) стратегий ¯ σ = (¯ σ 1 , ..., ¯ σ n ) ∈ ∆X и вер ¯ µ = (¯ µ 1 , ..., ¯ µ n ) ∈ ∆M всех игроков, таких что 1) стратегии ¯ σ i являются секвенциально-рациональными, при данных верах ¯ µ и стра- тегиях партнеров ¯ σ j ; 2) веры ¯ µ сильно согласованы с наблюдаемым стратегиям ¯ σ, в том смысле, что су- ществует последовательность вполне смешанных стратегий σ (k) → ¯ σ сходящаяся к равновесной, по которой (однозначно) строится последовательность вер µ (k) → ¯ µ, сходящихся к ¯ µ. 11 Если к тому же стратегии ¯ σ секвенциально-рациональны не только при финаль- ных верах ¯ µ, но и при всех поздних (начиная с некоторого номера) членах построен- ной последовательности вер σ (k) , то это равновесие SeqE называют (Совершенным) Равновесием дрожащей руки THPE (Trembling Hand Perfect Equlibrium). 12 Теперь сопоставим различные концепции решений. 11 В частности, если все ходы из некоторого узла оканчиваются в одном (последующем) инфор- мационном множестве, то веры в нем должны совпадать с вероятностями ходов: ¯ µ h = ¯ σ h−1 12 Вообще-то, определение ‘дрожащей руки’ обычно дают в терминах нормального представления игры, без понятия вер, и получается формально другой объект - (Trembling Hand Nash Equlib- rium). Он в играх с полной рациональностью (условия Куна) совпадает по множеству стратегий и выигрышам с THPE, которое нам удобнее для сопоставления с секвенциальным. 75 3.0.24 Сопоставление решений SPE, SBE, SeqE, THPE, INDW Введенные понятия SeqE, T HP E, и идеи случайных ходов оправдывают выделение равновесий со слабым доминированием типа INDW (или SoE) среди равновесий типа SPE. Действительно, все слабо доминируемые стратегии отбрасываются, если есть вероятность (даже если она близка к нулю) любого исхода. Поэтому, во многих играх окажется T HP E = INDW , и в любом случае T HP E ⊂ INDW (проверьте это). Традиционно решения 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 можно считать полюсами (са- мое узкое и самое широкое множества среди введенных здесь), между которыми вмещается большинство остальных некооперативных концепций как частный случай смешанных Нэшевских решений. Действительно, SPNE в чистых стратегиях обобща- ется до смешанного SP E m . Аналогично, каждую концепцию можно рассматривать и в чистой и в смешанной форме. Соответственно, можно составить следующий важ- ный граф вложений (его левый и правый края смыкаются, что отражено повторами обозначений SP E i ): 13 SP E mul SP E m ⊃ P BE m ⊃ SeqE m ⊃ THPE m ⊂ INDW mΓ ⊂ SP E m ⊂ NE m ∪ ∪ ∪ ∪ ∪ ∪ ∪ ∪ (3.1) SP E ≡ SP E p ⊃ P BE p ⊃ SeqE p ⊃ T HP E p ⊂ IN DW pΓ ⊂ SP E p ⊂ NE p ≡ NE. В этом графе центральное положение занимает наиболее узкая, наиболее рафини- рованная концепция из верхней цепочки с еще гарантированным существованием (см. теорему ниже) – это THPEm. Из приведенных вложений следует, что если T HP E m существует, то существуют и все охватывающие THPEm решения. Для существова- ния же всех “целых” концепций, то есть нижней цепочки, нужны дополнительные условия. Иначе, есть примеры несуществования, даже для наиболее широкой из них концепции NE. Какие условия? Например, INDW pΓ , SeqE p и более широкие кон- цепции развернутой формы существуют при совершенстве информации (отсутствии нетривиальных информационных множеств). 13 Под SP E mul подразумевается решение SPNE в мультиперсонном представлении игры, которое бывет шире обычного. 76 Глава 3. Динамические или “последовательные” некооперативные игры Благодаря приведенным выше цепочкам вложений, существование всех назван- ных (смешанных) решений можно вывести из существования THPE. Сформулируем его условия (доказательство этой непростой теоремы мы опускаем). Теорема 4 В конечной игре с полной рациональностью (хотя, возможно, и несо- вершенной информацией о ходах) смешанное Равновесие дрожащей руки существу- ет (T HP E m 6= ∅). Следствие: NE m 6= ∅, P BE m 6= ∅, SP INDW 6= ∅, SP E m 6= ∅, SeqE m 6= ∅. Сложное доказательство опускаем. Сопоставим концепции далее: решение T HP E p в большинстве случаев совпада- ет с SP INDW , расхождение мне (С.К.) неизвестно. Равновесие Нэша – это SP E в одношаговой игре с одновременными ходами. Пара равновесие Штакельберга – это просто SP E двухшаговой игры, когда лидер ходит первым (а по сравнению с "опти- мистическим Штакельбергом” SP E может включать еще какие-то исходы). Макси- мин может быть аппроксимирован P BE(ε)-равновесиями модифицированной игры, при элементарных функциях полезности участников с очень большим неприятием риска. С другой стороны, мы продемонстрировали, что понятия SPE, SBE, SeqE не тож- дественны, и почему. Итак, мы представили широкий арсенал концепций решений, применимых в раз- ных ситуациях игр и их связи. Подбор адекватной модели (графа) и концепции игро- вого решения под жизненную ситуацию – творческое дело исследователя, требующее знания содержательной стороны дела. Ничем, кроме примеров, учебник здесь не по- может. Это завершает рассмотрение “популяционных” или “эволюционных” игр, харак- теризующихся полной рациональностью. Теперь мы займемся играми с более слож- ной информационной структурой, чем “популяционные”. В принципе, все введенные концепции решений применимы и в них, в том числе в играх с несовершенной раци- ональностью или необщим знанием, в повторяющихся играх одной пары партнеров. Но в них есть и специфика, и другие решения. Глава 4 Усложнения: манипуляции с информацией, повторения игры, иррациональность 4.0.25 Отсутствие “общего знания”, игры с репутацией, блеф Изменим гипотезы игры “сороконожка” (“Бери или оставь”), добавив к возможности иррациональных ходов неопределенность знаний о степени иррациональности парт- нера (это уже не “общее знание”). Окажется, что концепция решения P BE(ε) должна модифицироваться, и включать характеристику информации. Пример 4.0.20 (Продолжение игры “Бери или оставь”) (“Сороконожка”) Пусть, в разобранной выше игре “сороконожка” ситуация изменилась: игрок Vic- tor слышал, что Анна в подобной игре из 10-ти ходов сделала 1 иррациональный (невыгодный, ошибочный), и ожидает, соответственно, вероятность иррационально- сти около α = 1/10. Аналогично, Анна слышала, что Виктор в подобной игре из 30-ти ходов сделал 2 иррациональных хода, она ожидает вероятность иррациональности β = 2/30 (это окажется не то же, что 1/15!). Предположим, игроки считают раци- ональным брать банк, когда вероятность ошибки партнера больше 1/7 и ожидают от партнера такого же мнения. Очевидно, при такой “простоватой” рациональности, Анна на первом ходу ВОЗЬМЕТ (если не ошибется). Но если он ошибется, возьмет ли Виктор? Он может интерпретировать оставление Анной как ошибку, и тогда под- править свою субъективную вероятность ошибок А до величины (1+1)/(10+1)=2/11. Либо считать случившееся оставление рациональным ходом, и сделать отсюда вы- вод о текущих гипотезах (β =?) Анны относительно себя (Виктора). Независимо от того, верны ли эти гипотезы, выгодно ли теперь Виктору оставлять и пойдет ли игра до узла V 3 ? 1)По сравнению с предыдущей ситуацией, оставим Виктора “простым”, а первого игрока предположим способным рассчитать предыдущую ситуацию. Станет ли он на первом шаге ОСТАВЛЯТЬ, независимо от своих гипотез о партнере (БЛЕФО- ВАТЬ)? Пойдет ли игра до 6-го хода? 77 78Глава 4. Усложнения: манипуляции с информацией, повторения игры, иррациональность 2)Что если теперь оба игрока “сложные”, и В просчитывает возможность блефа первого (считающего второго простым), изменит ли это результат? 4.0.26 Уточнение понятия рациональности; прямая индукция Кольберг и Мертенс (1986) предложили возможность сужения множества совершен- ных или других равновесий основанных на обратной индукции с помощью “прямой индукции”. По сути дела она означает решение игры по доминированию и в развер- нутой и в нормальной форме (по определенному порядку), и пересечение множеств ответов. Это затрагивает фундаментальный вопрос о “creadible commitment”, 1 подня- тый Нейманом и Моргенштерном: всегда ли игроки могут до игры рассчитать свои оптимальные стратегии (планируемые реакции на возможные ходы/информацию), а затем только придерживаться их? Часто это не так, и игроку было бы выгодно с самого начала объявить свою стратегию, и лишить себя возможности передумать затем в ходе игры (см. игру “Цезарь сжигает мосты” в задачнике). В следующем же примере (Рис. 4.1) противоречия не возникает, и прямая индукция выглядит обосно- ванно. µ - 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 Рис. 4.1: Прямая индукция. В этой игре Виктор в ситуации V 1 не знает, сходила ли Анна c или d. Здесь два последовательных равновесия SPNE в чистых стратегиях (и еще одно в смешанных): (a, [d, z]), (b, c, u). Однако, только последнее остается, если рассматривать прямую индукцию, определяемую так. Приведя эту игру к нормальной форме заметим, что стратегия Анны (b, d), сильно доминируется ее стратегией (a). Зная это, Виктор, в случае наблюдаемого хода (b), должен решить, что Анна имела в виду стратегию ( |