теориия игр. Лекции по теории игр вводный уровень
 Скачать 1.71 Mb.
|
|
b, c), и сходила (c) а не (d). Тогда ему разумно ходить (u), другой ответ на (b) нерационален. Зная это, Анна пойдет (b) а не (a), и получит 5. Так дополнительные сообржения о рациональности по “прямой индукции” сузили множество ожидаемых исходов игры. 79 > µ - 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 Рис. 4.2: Прямая индукция при неполной рациональности. Однако в другой подобной игре (Рис. 4.2) подобные соображения могут быть обоснованы только неполной рациональностью; множества решений по прямой и по обратной индукции не пересекаются! На Рис. 4.2 игроки ходят по очереди, и Виктор также на последнем ходе не зна- ет предыдущего хода Анны. Но это ему и не нужно, ведь в любом случае он схо- дил бы вниз: (z), этот ход строго доминирует над (u). Поэтому единственное SPNE =(a, [y, d, z]). Если же мы переведем эту игру в нормальную форму (Табл. 4.1), то окажется, что стратегия Анны (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 Таблица 4.1: Прямая индукция. После хода (b), Виктору надо решить что это: взятие на пушку, глупость или по- дозрение партнера в глупости. В последних случаях надо ходить вверх! При гипотезе же полной рациональности обоих (известной обоим), нужно не покупаться на блеф, ходить вниз (y, z) и иметь 8. С другой стороны, если бы Анна имела возможность объявить, владея “creadible commitment”, стратегию (b, c) и не отступать от нее, то реализовала бы выигрыш 3. Тогда, при “creadible commitment”, Виктор вынужден отступить на (x). 1 Этот термин в играх означает “выполнимое обещание”. 80Глава 4. Усложнения: манипуляции с информацией, повторения игры, иррациональность Мораль из этого примера: в ситуациях однократной игры, в том числе при непол- ной рациональности игрок может стараться сделанным ходом сигнализировать о сво- их гипотезах (истинных или блефовых) относительно партнера, к своей выгоде. Это практически эквивалентно сигнализированию о своем типе в Байесовских играх. Аналогично, применение стратегий, а не ходов, резонно в повторяемой игре, где игрок способен завоевать репутацию. Тогда прямая индукция правдоподобна. Упражнение. В примере “футбол или кино” (Рис. 2.0.1), рассмотрите следующую модификацию. Пусть, Виктор общается с Михаилом, который наверняка увидится с Анной до вечера, до выбора футбол/кино, но стесняется прямо попросить Михаила передать Анне просьбу прийти на футбол или в кино. Он сжигает 1 рубль на глазах Михаила, никак не объясняя своего поступка, но надеясь, что тот расскажет Анне об этом странном случае, и та сделает выводы. Покажите прямой индукцией, что это сжигание – разумный ход Виктора. 4.0.27 “Почти-совершенная” информация: повторяющиеся иг- ры с угрозами. “Почти-совершенной” называют информацию о всех сделанных ходах, кроме послед- него или текущего. Подобная ситуация возникает в весьма распространенном классе “повторяющихся” игр. Это такие игры, где участники ходят одновременно, затем од- новременно наблюдают результат действий партнеров, еще раз разыгрывают эту же игру, и т.д. Например, игра “Монетки”, “Перекресток”, “Футбол или кино” – могут быть разыграны в повторяющемся режиме. Что тогда изменится в типе решения? Строго говоря, при анализе такой игры уже нельзя обойтись просто матрицей нормальной формы игры. Правильный подход – рассматривать дерево игры с повто- ряющимися элементами, конечное или бесконечное. Оказывается, что решения при этом могут существенно отличаться от решений однократной аналогичной игры. Пример 4.0.21 (“Камень в огород” ) (или повторяющаяся “Дилемма заклю- ченных”) Предположим, два недолюбливающих друг друга соседа имеют выбор: бро- сить соседу камень в огород, уходя утром на работу, или воздержаться. 2 Выигрыши заданы следующей игрой в нормальной форме.. Очевидно, структура игры та же, что в “дилемме заключенных”. Поэтому един- ственное строго доминирующее равноесие SDE (и одновременно единственный не- Парето-эффективный исход!) есть (Агрессия,Агрессия). Теперь рассмотрим дерево этой игры на конечном интрвале времени, предполагая цели игроков в виде дискон- тированной суммы выигрышей по периодам. Окажется, что совершенное в подыграх равновесие (SPE) то же, что и DE: (Agress., Agress.) 4 = ((Agr., Agr., Agr., Agr., ), (Agr., Agr., Agr., Agr., )). Теперь отметим, что “нормальной стратегией” является не просто ход, а последовательность ходов. А стратегией в более общем смысле является объявляемая функция отклика: это последовательность реакций на каждом этапе на каждую из возможных наблюдаемых ситуаций. Поэтому точнее приведенное решение будет записать так: SP E = {((Agr., Agr., Agr., Agr., ) anyway , (Agr., Agr., Agr., Agr., ) anyway )}. 2 Аналогичная игра возникает во многих практических ситуациях. Например, между двумя оли- гополистами, каждый из которых может снизить цену продукта в некотором периоде, и отнять у конкурента долю рынка, зная, что тот может тоже ответить “агрессией”. 81 -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. Рис. 4.3: Повторяющаяся игра “Камень в огород”. Кроме этого, теоретически, можно рассмотреть и такие стратегии “максимального наказания”: {(P eace, P eace, P eace, P eace, ) f or peacef ul partner , (P eace, ...., Agr., Agr., ) f or agress. partner }, 82Глава 4. Усложнения: манипуляции с информацией, повторения игры, иррациональность то сеть, обещание быть мирным, пока партнер мирный, иначе переключаться на агрессию до конца веков. Однако эти стратегии “максимальной угрозы” (обещание мстить за агрессию максимально, иначе сохранять мир) не рациональны в смысле SPNE в конечной игре, рациональна только чистая агрессия. В бесконечной же игре они могут быть рациональны! (Считают, что целевые цункции бесконечной игры есть взвешенные с некоторым дисконтом выигрыши моментов игр.) Проверьте, что при дисконте близком к 1 (слабое убывание полезности) кроме “максимальной угрозы” много и других решений: скажем, когда оба партнера агрессивны только по понедель- никам, а мстят за отступления от этого объявленного правила ограниченное число периодов, Обобщим эту идею. Теорема 5 (“Народная теорема” (Folk Theorem):) В бесконечной повторя- ющейся игре, если дисконт стремится к единице, множество возможных средних выигрышей стремится к множеству всех выигрышей выше гарантированных. Доказательство мы опускаем. Иллюстрацией смысла теоремы служит Рис.4.3. Множество возможных выигрышей - четырехугольник, помеченный (1,1). ..... 4.0.28 Игры с несовершенной памятью, и другие несовершен- ства рациональности До сих пор мы предполагали, что каждый игрок помнит все, что он знал ранее, в том числе собственные предыдущие ходы. Иногда это не так: в картах слабые игроки нередко не помнят вышедших карт, даже своих. Как моделировать подобные ситуации? Очевидный ответ – с помощью мультиперсонного представления игры: одного и того же игрока нужно считать другим (хотя с теми же целями), после того, как он забыл часть информации. Пример 4.0.22 (“Бабушка и очки”.) Бабушка снимает очки, и идет умывать- ся, а очки кладет на видное место у выхода из ванной. Она знает, что не вспомнит, куда их положила, и проектирует ситуацию, чтобы на них наткнуться. В данном случае, она смоделировала себя как другого игрока, чей ход (искать очки) состоится после умывания первого игрока, и приняла адекватное решение (постройте дерево игры и SPE). Аналогично, мультиперсонное представление игры помогает моделировать ситуа- ции, когда иррациональность участников заключается в изменении их целей по ходу игры. Пример 4.0.23 (“Курильщик” (D.Kahneman, A.Tversky, 1982).) Бывший ку- рильщик наиболее предпочитал бы выкуривать 2 сигареты в день, менее приятно для него совсем не курить, а совсем нехорошо (врачи запрещают) курить пачку в день. Он бы и выбрал 2 сигареты, но знает, что тогда предпочтения его изменятся, он не удержится, и будет курить пачку. Поэтому он останавливается на полном воздержа- нии (постройте дерево игры и SPE). В противоположность двум приведенным примерам иррациональности, рассмот- рим ситуацию, которая кажется иррациональной, но ей не является. Пример 4.0.24 (“Честный дележ”) (см. J.Tirole 2001), A.Rubinstein 2002 - до- клад в РЭШ) Паре игроков ведущий обещает $ 100 если дележ, предложенный пер- вым будет принят с первого раза вторым. С точки зрения кооперативных игр, воз- можными дележами является все ядро, от 0 до 100. С точки зрения же Штакельбер- говского решения первого игрока (то же SPE), можно предлагать всего 1 второму и 99 себе, второй вынужден согласиться. Практически же, многочисленные опыты этой игры с неподготовленной аудиторией дают около 95% случаев дележа 50:50, около 2% других принятых дележей, около 3% отвергнутых дележей, когда оба получили 0! Тем не менее, это наблюдение не позволяет говорить о средней иррациональности лю- дей. Просто нужно считать их целевые функции заданными не только на денежном выигрыше, но и на сопоставлении выигрыша своего и партнера. Практически люди чаще максимизируют самоуважение, чем непосредственный результат: им важно “не остаться в дураках”. Кроме того, многие придерживаются некоторых концепций “справедливости” при дележе. Если внести определенный вариант подобных гипотез в конструируемую модель их целевых функций, то окажется, что обидеть “наглеца”, предлагающего не равный дележ прибыли – рациональная стратегия, максимизиру- ющая самоуважение, а первый игрок, зная это, предлагает дележ 50:50 (постройте целевые функции, дерево игры и SPE). Аналогично “самоуважению”, альтруизм – это не иррациональность, а нетриви- альные цели. Современная “психологическая экономика”, “экспериментальная эконо- мика” накопила достаточно фактов такого характера, демонстрирующих системати- ческое отклонение поведения от тривиально понимаемой рациональности (и немало фактов истинной иррациональности). 83 Истинная иррациональность может иметь разные причины: - несовершенный рас- чет игры; - несовершенная память; - изменение целей в ходе игры; - иррациональные предпочтения (неполные или нетранзитивные). Мы видели, что модели теории игр, с некоторыми модификациями, оказываются пригодны и к этим ситуациям. Теперь мы покажем, что они пригодны и к некоторым ситуациям совсем без рациональности. 4.0.29 Игроподобные ситуации без рациональности: псевдооп- тимизация и эволюционное равновесие Биологи, исследуя популяции животных, построили различные модели динамиче- ских систем их взаимодействия. Системы могут иметь равновесия или не иметь (рас- качиваться). В частности, хорошо известны модели Вольтерра “хищники и жертвы”, описывающие динамику совместных колебаний численности популяций, например, волков и оленей, связанных в экосистеме. Нас будут интересовать те ситуации, где переменными являются различные ва- рианты поведения. Окажется, что даже если особи совсем иррациональны (болваны), результирующие равновесия чем-то похожи на рациональное (оптимизирующее) по- ведение. Это не удивительно, поскольку даже в неживой природе некоторые явления хорошо описываются оптимизационной моделью, например, расположение воды на- литой в емкость минимизирует высоту ее центра тяжести. Такие явления можно на- звать “псевдооптимизацией”: оптимальный, в некотором смысле, исход в отсутствии оптимизирующего субъекта. Это феномен, волновавший религиозных мыслителей и Дарвина, в связи с естественным отбором. Когда игрок не один, то (Парето) опти- мальность не гарантирована естественным отбором. Рассмотрим подобную ситуацию - равновесие типа Нэшэвского, но без рациональных субъектов. Пример 4.0.25 (“Голуби и ястребы” (см. Ordeshook, p.183)) Пусть популя- ция воробьев (пример можно применить и к другим животным, или к популяции ти- пов поведения людей) состоит из 2 типов птиц: “Агрессивный” (как ястреб) или “Мир- ный” (как голубь), причем ни один не меняет своего типа поведения (они “болваны”). Но тот тип, который в среднем имеет лучшее благосостояние, обильнее и размножа- ется (либо особи перенимают образ поведения субъектов, выглядящих успешными). Так или иначе, доля агрессивных воробьев в популяции со временем будет возрас- тать, если они “обыгрывают” более мирных, и наоборот. Предположим, тип поведения проявляется возле куска корма: двое мирных осо- бей встретившись — вместе его клюют, мирный отступает перед агрессивным, а двое агрессивных деруться, с обоюдными потерями. Эти гипотезы о выигрышах в каж- дой из 4-х возможных комбинаций (кто с кем окажется возле корки хлеба) отразим матрицей выигрышей: Обозначим α(t) ∈ [0, 1] текущую долю агрессивных птиц в популяции, тогда µ = (1 − α(t)) ∈ [0, 1] есть доля мирных. Найдем равновесие Нэша в смешанных стратегиях NE m , понимая его как стаци- онарное состояние ¯ α доли агрессивных птиц, то есть решение уравнения: U(¯ α, (1 − ¯ α)) = −1¯ α + 2(1 − ¯ α) = 2 − 3¯ α = U(1 − ¯ α, ¯ α) = 0¯ α + 1(1 − ¯ α) = 1 − ¯ α, ⇒ ¯ α = 0.5. При такой доле агрессивных эта пропорция могла бы не меняться. 84Глава 4. Усложнения: манипуляции с информацией, повторения игры, иррациональность Второй воробей агресс. мирный -1 0 Первый агрессивный -1 2 SNE воробей 2 1 мирный 0 SNE 1 Таблица 4.2: “Голуби” и “ястребы”. Заметим, что кроме найденного симметричного равновесия NE m ¯ α = 0.5 в систе- ме есть и два крайних равновесия Нэша в чистых стратегиях: (Агр.,Мирн.), (Мирн.,Агр.), однако они не отвечают содержательной формулировке “игры”: нельзя придумать долю α отвечающую этим ситуациям. Напротив, содержательно возможны крайние ситуации, когда какого-то типа просто нет: ˜ α = 0, ˆ α = 1. Однако, как легко про- верить, в отличие от первого, они неустойчивы к возможным мутациям, то есть к ненулевой вероятности случайного появления особей любого типа (аналог случайных ходов в ситуациях с рациональностью). Понятие локальной устойчивости эволюционных равновесий в системах такого типа можно сформулировать так. Пусть есть n типов игроков i = 1, ..., n с одина- ковыми целевыми функциями u 1 (.) = ... = u n (.) = u(.), доли их в популяции есть α 1 , ...α n : α i ∈ [0, 1], P i α i = 1 (в иной интерпретации, это одинаковые игроки, а α 1 , ...α n есть частоты применения чистых стратегий). Определение 4.0.29.1 В описанной ситуации набор стратегий (типов поведения) (¯ α 1 , ..., ¯ α n ) называется “эволюционным равновесием” EvE, если для любого типа по- ведения i выполняется u i (¯ α i , ¯ α −i ) > u i (α i , ¯ α −i ) ∀α i (стратегия ¯ α i строго предпочти- тельна при равновесных стратегиях партнеров ¯ α −i ), либо u i (¯ α i , ¯ α −i ) ≥ u i (α i , ¯ α −i ), u i (¯ α i , α −i ) > u i (α i , α −i ) ∀(α i , α −i ) (стратегия ¯ α i нестрого предпочтительна, но начи- нает строго предпочитаться при отклонении партнеров от Нэшевского решения). Итак, эволюционно- устойчивые cтратегии - это Нэшевские cтратегии от кото- рых к тому же строго вредно отклоняться при сохранении позиций партнеров, или при отклонении партнеров. Эволюционное равновесие - профиль таких стратегий. Очевидно, SNE ⊂ EvE ⊂ NE. Заметим, что показанный эволюционный подход применим и к случаям частичной рациональности такого типа: участники популяции (особи) — это не люди или живот- ные, а бытующие типы поведения. А игроки — люди или животные — поступают тем или иным образом случайно, с некоторой текущей частотой α(t), не занимаясь насто- ящей оптимизацией, но несколько увеличивая частоту тех ходов, где они в среднем, по опыту, больше выигрывают. Мутации есть случайные ходы. Концепция равнове- сия и результат в таких ситуациях те же, что в популяциях с реальными особями типа “болванов” (dummy). |