теориия игр. Лекции по теории игр вводный уровень
 Скачать 1.71 Mb.
|
|
Что общего в разных концепциях решений? Завершая раздел статических (одновременных) игр, в качестве упражнения интуи- ции в применимости той или иной концепции, попробуем сформулировать универ- сальную, достаточно широкую концепцию решения, охватывающую многие некоопе- ративные решения как частные случаи. Она выдвигает на первый план понятие ожи- даний, которое затем пригодится в последовательных играх. Определение 2.0.12.1 Набор ¯ x ∈ (X × X × ... × X) ожидаемых стратегий (гипотез о всех партнерах, включая себя, причем ожидания любого игрока о себе совпадают с реально выбранной его стратегией) ¯ x i∗ = (¯ x i1 , ..., ¯ x in ) ∈ X (i = 1, ..., n) можно назвать равновесием с правилом ожиданий – отображением E : (X × X × ... × X) ⇒ (X × X × ... × X) если 1) выбор ¯ x ii ∈ X i каждого игрока i является одним из наилучших для него от- ветов на ожидаемые стратегии x ij ∈ X j прочих игроков j 6= i, то есть: u i (¯ x ii , ¯ x ij ) = max x ii ∈X i u i (x ii , ¯ x ij ); 2) ожидания любого игрока i о всех игроках соответствуют заданному правилу согласования ожиданий: (¯ x 1∗ , ..., ¯ x n∗ ) ∈ E(¯ x 1∗ , ..., ¯ x n∗ ). В частности, для Нэшевской концепции решения, правило соответствия ожиданий очень простое E(x) = (x 11 , x 22 , ..., x nn )×(x 11 , x 22 , ..., x nn )×...×(x 11 , x 22 , ..., x nn ), то есть ожидания должны соответствать действительно выбранным стратегиям. Напротив, для концепции осторожного решения (MaxMin) ожидания соответствуют наихудшим гипотезам о партнерах. 21 Возможно записать в форме отображения предположений E(.) и другие правила, в том числе, соответствующие равновесию Штакельберга и итерационному домини- рованию, но это громоздко, и мы этого не коснемся. Итак, в этом параграфе выражен взгляд на различные концепции решений, как на ситуации, различающиеся именно ожиданиями о партнерах, но не типами рацио- нальности поведения (методами рассуждений игроков). Противоположный взгляд - что рациональность бывает разная - теоретически менее последователен, но практи- чески тоже часто бывает удобен. 21 Как уже отмечено, в ситуации антагонистической игры это достаточно реалистично, но в других случаях одновременные решения игроков при таком правиле ожиданий могут приводить к исходу, неожиданному для них: пессимизм не всегда оправдается. В этом смысле MaxMin, в отличие от NE, не во всех играх можно назвать равновесием, ведь трудно представить себе популяционную игру, где одни и те же ожидания нарушаются из раунда в раунд. Глава 3 Динамические или “последовательные” некооперативные игры Перейдем к рассмотрению игр, заданных в развернутой форме, то есть в виде описа- ния не стратегий, а отдельных ходов и их последовательностей. Для этой цели часто применяются сетевые структуры – графы, причем преимущественно — “исходящие” деревья. 3.0.13 Формализация последовательных игр, соответствие раз- вернутой и нормальной формы игры Исходящим деревом (out-tree) называют связный направленный (ориентированный) граф с единственным истоком (“корнем”), если в графе нет циклов, и каждый узел имеет единственного непосредственного предшественника. Часто полезно отражать игры и графами более общего вида, но, как прави- ло, "фундированными". Фундированным называют связный направленный граф с одним истоком (корнем) и без циклов. Упражнение. Чтобы понять, что дерево - не всегда самое экономное представление игры из возможных, представьте девятиклеточные “Крестики-нолики” фундированным гра- фом, не являющимся деревом (в некоторые позиции можно попадать из разных предше- ственников). Для упрощения можно считать первый ход “Х - в центр” уже сделанным, и идентифицировать ходы именами типа “0 - в угол”, “Х - в противоположный угол”, отожде- ствляя тем самым эквивалентные ситуации. Докажите, что цена игры - “ничья”. Граф игры мы будем обозначать Γ(G), точки выбора участников будут “узлами”, а ходы – “дугами” графа. Каждому конечному узлу, то есть (финальной) “вершине”, или “исходу” игры, приписываются некоторые выигрыши всех участников. Тем са- мым, граф игры задает физическую и целевую структуры игры, а информационная структура игры отражается “информационными множествами”, а также отдельно от графа, например, в той или иной концепции решения. Определение 3.0.13.1 Информационное множество или информационная пози- ция игры есть несколько узлов (физических позиций) графа игры, соответствующих 51 52 Глава 3. Динамические или “последовательные” некооперативные игры определенному ходу одного участника, который не может различать между ними (не знает, в котором узле он находится). Очевидно, одновременная игра есть частный случай последовательной, где у каж- дого игрока просто всего одно информационное множество. Чтобы подойти к концепции решения последовательных игр, рассмотрим приме- ры. Пример 3.0.8 (“Террорист”, см. Мулен, 1987) Предположим, в самолете ле- тящем из Майами в Нью-Йорк обнаруживается террорист, обещающий взорвать бом- бу, если самолет не повернет на Кубу. Допустим, пилот, от которого зависит реше- ние, считает свою смерть (неважно где) хуже посадки на Кубе, которая, в свою очередь, хуже посадки в Нью-Йорке. Это можно отразить, например, такими вы- игрышами пилота: U P ilot (...) := (Bomb → 0, Cuba → 1, New-Y ork → 2). Предпо- ложим, данный террорист также жизнелюбив и не хочет умирать, и это видно по его лицу, только он Кубу предпочитает Нью-Йорку. То есть его цели можно за- дать в виде U T errorist (...) := (Bomb → 0, Cuba → 2, New-Y ork → 1). Пилот дол- жен выбрать, поворачивать ли на Кубу, а затем террорист – взрывать ли бом- бу, как обещал. Что произойдет, если летчик почему-то, например, по жизнелю- бивому виду террориста, вполне уверен в своем (истинном) предположении о це- лях террориста, то есть его ожидания о целях партнера истинны: β pilot (u terr ) = (Bomb → 0, Cuba → 2, N − Y → 1)? Для ответа формализуем игру. Можно представить варианты этой игры с после- довательными ходами двумя деревьями: Рис. 3.2 отражает случай, когда террорист НАБЛЮДАЕТ ход пилота, а Рис. 3.1 - противоположный случай (довольно глупый: что ж тогда угрожать? Но нам важно сравнить их.). То есть, в случае “Б” терро- рист не способен глядя в иллюминатор определить, куда ведут самолет. Это игра с несовершенной (неполной) информацией о сделанных ходах. Это отражается на дере- ве игры объединением пунктиром узлов, неразличимых для игрока принимающего здесь решение, объединенные так узлы составляют информационное множество, или “историческую позицию” игры. В этом случае игрок вынужден принимать решение вслепую, и то, что он хо- дит вторым, а не первым – не имеет значения, равно как и его объявленная в духе cheap-talk (пустые слова) стратегия [N-Y → bomb, Cuba → peace]. Тогда мы можем представить соответствующее дерево “Б” (Рис. 3.1) в уже известной нам нормальной стратегической форме следующей матрицей стратегий и выигрышей: Если пилот знает цели партнера, то легко предсказать, что он определит его стратегию “peace” как строго доминирующую, и выберет для себя “New-York”. Это произойдет и в том случае когда он рассуждает как Штакельберговский лидер, и по концепции “сложного равновесия”, и просто по доминированию – независимо от зна- ния целей партнера. По сути, подобная игра без наблюдаемости хода эквивалентна одновременным играм, изученным выше, и новых понятий не требует. Интереснее случай “Н” с наблюдаемостью курса самолета. Для прояснения со- отношения развернутой и нормальной форм игры на Рис. 3.2 она переведена и в нормальную форму. Здесь стратегия (b, b) означает намерение бомбить и в случае поворота на Нью- Йорк (первая компонента вектора (b, b)), и в противоположном случае. Все страте- гии террориста, кроме последней (p, p), выглядят глупо с точки зрения его целей, 53 Pilot Terr-st Terr-st * j * z 1 q 0, 0 2, 1 0, 0 1, 2 N-York Cuba bomb peace peace bomb 0, 0 0, 0 1, 2* 2, 1 bomb peace New-YorkCuba Pilot Terrorist j ¼ 1 j Рис. 3.1: Игра “Террорист”-Б — без наблюдаемости хода. Развернутая (слева) и нор- мальная (справа) формы. Pilot Terr-st Terr-st * j * z 1 q 0, 0 2, 1 0, 0 1, 2 N-York Cuba bomb peace peace bomb 0, 0 0, 0 0, 0 2, 1* N-York Cuba Pilot: Ter-st: j ¼ 1, 2* 0, 0 1, 2* 2, 1 (b,b) (b,p) (p,b) (p,p) (N,C) 6 6 Рис. 3.2: Игра “Террорист-Н” — с наблюдаемостью хода. Развернутая (слева) и нор- мальная (справа) формы. но они физически возможны, поэтому вносятся в матрицу. Важно заметить: стра- тегией является не ход, а полная инструкция себе — как ходить в ответ на каждый ход противника, то есть в каждом информационном множестве (исторической по- зиции). Поэтому, в отличие от случая “Б” с несовершенной информации о сделанных ходах (который можно интерпретировать и как игру с одновременными ходами) мат- рица нормальной формы соответствующая новому дереву оказывается размером не 2 × 2, а 2 × 4 — матрица стратегий уже обширнее матрицы выигрышей (возможных исходов). Более того, в отличие от случая “Б”, по ней уже нельзя однозначно восста- новить дерево из которого она построена, часть информации утеряна. В этом смысле развернутая форма записи игр более информативна, чем нормальная. Итак, каждая последовательная игра, заданная графом, одно- значно может быть представлена и в нормальной форме (свер- нута). Но обратное действие - восстановление развернутой формы по нормальной - может быть неоднозначно, поскольку свертывание теряет информацию о последовательности ходов. 54 Глава 3. Динамические или “последовательные” некооперативные игры 3.0.14 Стратегии нормальные и пошаговые, мультиперсонная форма игры и SPNE Что есть стратегия? Абстрактно, "полная” или нормальная стратегия — это план-предписание своего поведения в любой ситуации. В данном же контек- сте, в терминах графа, можно сказать, что полная стратегия есть вектор, описыва- ющий избранные ходы в каждой возможной информационной позиции. Формально, если мы обозначим последовательные исторические позиции (historical nodes) игро- ка А символами h 1A , h 2A , h 3A , ..., а переменные ходов в этих позициях x 1A , x 2A , x 3A , ... (каждая переменная может принимать столько значений, сколько выходов из этой позиции), то нормальная стратегия s A есть набор s A = (x 1A , x 2A , x 3A , ...) описываю- щий поведение в каждой позиции. Соответственно, выписав по ходам все возможные стратегии и приписав выигрыши всем профилям стратегий, развернутую игру можно свести к нормальной. Достаточно ли этого свернутого ("нормального”) представления динамической иг- ры и введенных ранее концепция решений (NE, IND), чтобы предсказывать ее исхо- ды, или нужно пользоваться графом и вводить новые идеи? Несколько последующих разделов убеждают во втором мнении. Например, в матрице стратегий примера “Террорист-Н” можно заметить целых три Нэшевских равновесия, и одно из них ((b, p),(Cuba)) соответствует простой по- слушной реакции пилота на объявленную на словах стратегию террориста (b, p). Но это равновесие и еще одно ((p, b),(N-York)) – кажутся неправдоподобными с точки зрения содержательного описания игры, и с точки зрения дерева игры. Разве мож- но поверить, что жизнелюбивый террорист действительно взорвет бомбу после того как увидит, что его не послушались? Эти стратегии слабо доминируются стратегией “peace” в любой ситуации: (p, p). Кроме того, и это важнее, они сильно доминируют- ся стратегией “peace” как в подыгре исходящей из узла N-York, так и в “подыгре” исходящей из узла Cuba. Определение 3.0.14.1 Подыгрой называют подграф исходной игры, связ- ный от некоторого узла — корня подграфа — до его финальных вершин, и изолированный, то есть не имеющий ни физических ни информацион- ных (через информационные множества) связей с другими подграфами игры, кроме дуги входящей в его корень. В нашем примере правдоподобным в смысле рациональности поведения в поды- грах представляется только одно из трех Нэшевских равновесий ((N-York),(p, p)). То есть, террорист, если он рационален, остановится на стратегии “не бомбить ни в ка- ком случае”, как в подыгре, возинкающей после хода (N-York), так и в другой. А пилот, понимая это, полетит в Нью-Йорк. Итак, в примере “Террорист” мы выделили среди нескольких NE равновесий од- но правдоподобное, с учетом складывающихся по ходу игры ситуаций. Эту идею сужения множества потенциальных исходов благодаря рациональности поведения не только в начальной точке, но и позже, можно задать так. Определение 3.0.14.2 Назовем совершенными в подыграх (Нэшевскими) равновесиями (SPNE = SPNE= Subgame Perfect (Nash) Equilibrium) Нэ- 55 шевские равновесия, являющиеся Нэшевскими равновесиями во всех поды- грах (в том смысле, что сужения равновесных стратегий на подыгры являются равновесиями в них). Заметим, что эту общую идею рациональности поведения "по ситауции"можно отразить и через другую форму стратегического представления исходной игры, на- зываемую мультиперсонной. Это означает, что один и тот же игрок, в разных си- туациях (узлах дерева) представлен разными (“условно-ситуационными”) игроками. У каждого условного игрока стратегия тогда не вектор, а скаляр – один ход. Эти стратегии иногда называют поведенческими (behavioral) или пошаговыми, ситуатив- ными. В этой форме игра "Террорист” представлена в Таблице 3.1. Pilot↓ \ N-Y-Terr-st→ bomb peace N-Y 0, 0, 0 2, 1, 1 Cuba 0, 0, 0 1, 2, 2 Pilot↓ \ Cuba-Terr-st→ bomb peace N-Y 0, 0, 0 2, 1, 1 Cuba 0, 0, 0 1, 2, 2 Таблица 3.1: Мультиперсонное представление игры “Террорист”. В данном примере, при мультиперсонном представлении Террорист превратит- ся в двух лиц – Террориста в Нью-Йорке, и Террориста на Кубе. Естественно, вы- игрыши обоих Террористов в образующейся при этом игре трех лиц (Пилота и двух разных террористов) совпадают, но действуют они каждый за себя. Это соответ- ствует гипотезе действия “по ситуации”, в противоположность действию по заранее объявленному плану. Тем самым, при мультиперсонном представлении используется гипотеза отсутствия возможности “creadible commitment”, то есть “обязательства, вызывающего доверие”. Обозначим через NE mult множество Нэшевских равновесий в мультиперсонном стратегическом представлении игры. В этом примере единственное NE mult , а именно, (x P = N − Y, x T N = p, x T C = p). Это же, по сути, решение является и единственным SPNE: (x P = N −Y, x T N = (p, p)). Мы предполагаем, что пилот верит в поведение партнера “по ситуации”, а не в обя- зательство бомбить в Нью-Йорке. Выражая это в мультиперсонных терминах, он просто выбирает, с кем из “условно-ситуационных” Террористов столкнуться. (Ес- ли бы летчик верил в обещание Террориста бомбить в Нью-Йорке, игру следовало бы представлять другим деревом, или вместо SPNE применять другую концепцию решения.) На первый взгляд, правдоподобно следующее утверждение: “Некоторый профиль стратегия является совершенным в подыграх решением (SPE) тогда и только тогда, когда это есть Нэшевское равновесие, являющееся Нэшевским равновесием и в мультиперсонном (пошаговом) представлении игры.” Однако, оно опровергается примером “решения с дискоординацией” ниже. Пока мы всюду старались вести рассуждения в общей форме, пригодной для при- менения и к исходной, конечной или бесконечной игре, и к расширенной (смешанной) игре (правда, смешивания стратегий бесконечных игр мы не касаемся). Теперь заме- тим, что стратегии или ходы в динамические игры могут быть не только целыми, но и смешанными, как и в статических (одновременных) играх. Здесь отличие пошаговых стратегий от "полных” становится важным: 56 Глава 3. Динамические или “последовательные” некооперативные игры Выгодно ли для игрока смешивать полные стратегии вида s A = (x 1A , x 2A , x 3A , ...), или выгоднее сначала смешивать отдельные ходы, а потом объединять их в полную смешанную стратегию, или это все равно? Одинаково ли множество NE m в том и другом случае? Условия эквивалентности того и другого типа поведения определяются теоремой Куна (см. В.И.Данилов, 2001, или Fudenberg & Tirole 1991 p.89): Теорема (Кун 1953). Для игры с совершенной памятью (полной рацио- нальностью) оба способа смешивания эквивалентны: все равно, смешивать полные или пошаговые стратегии. Контрпример, показывающий, что при неполной памяти смешивание полных и пошаговых неэквивалентно - "забывчивый водитель”. 3.0.15 SPNE и обратная индукция Во многих динамических играх, довольно естественно решения типа SPNE (=SP- NE) искать алгоритмом обратной индукции, то есть “алгоритмом Куна”, по сути эквивалентным определению SPNE (проверьте это самостоятельно). При полной ин- формации о сделанных ходах, он описывается так: 1. Отбрасываем (вычеркиваем) сильно доминируемые стратегии во всех финальных подыграх (содержащих только вершины и предвершинные узлы). 2. Невычеркнутые значения выигрышей переносим на предвершинные узлы. Если невычеркнутых значений несколько – то переносим все эти варианты, или, что то же, создаем несколько вариантов дерева игры. 3. Редуцируем каждую игру (каждый из вариантов дерева), удаляя уже рассмот- ренные вершины, то есть считаем бывшие предвершинные узлы новыми фи- нальными вершинами. Если остался не только корневой узел, то повторяем операции 1–3, уже над редуцированной игрой. END: В конце останутся возможные значения выигрышей в корневом узле и цепоч- ки, которые их породили — каждая из них означает одно из равновесий SPE, и включает нереализовавшиеся, но подразумеваемые ветви дерева (ожидания). В случаях со скрытой информацией, нужно рассматривать соответствующие поды- гры как одновременные игры. Их NE считать исходом этих подыгр и использовать далее в редукции дерева игры. Проще всего этот алгоритм срабатывает, когда (в отличие от примера “Терро- рист”) информация полная и каждый игрок имеет различные выигрыши в различ- ных вершинах. 1 Тогда результат алгоритма (то есть SPE) единственен. По сути дела, понятие SP E включает идею оставить итерационно-сильно-недоминируемые страте- гии, только порядок отбрасывания доминируемых стратегий изменяется. Оно про- водится по подыграм и порядок определен деревом игры Γ, а не требованием одно- временности как в INDS. Если отображать эти операции с игрой на "шахматке” ее 1 К однозначности выигрышей игру иногда можно привести, объединяя вполне эквивалентные вершины графа в одну. Тогда, скажем, шахматы имеют всего три финальные вершины, только достигаемые многими путями: выигрыш, проигрыш, или ничья белых. 57 нормальной формы, то на любом примере можно заметить, что отбрасывание одной ветви дерева по сильному доминированию соответствует отбрасыванию соответству- ющей СЛАБО доминируемой стратегии шахматки, или нескольких таких стратегий (отбрасываются не все доминируемые). Эта разница может иметь значение: напри- мер, в игре “Террорист” IN DS Γ не совпадает с INDS игры в нормальной форме, а только с IN DS мультиперсонной формы игры. Итак, пользуясь обратной индукцией и отбрасывая СИЛЬНО доминируемые в подыграх стратегии, мы по сути отбрасываем некоторые (возможно, не все!) СЛАБО доминируемые стратегии нормального представления этой игры, причем в опреде- ленном порядке, заданном графом. Из этого следует некоторые соображения. Во первых SPNE ⊂ NE не только по определению, но и опираясь на выше-доказанное утверждение, о том, что отбрасы- вание доминируемых стратегий не расширяет множество NE. Второе - что любое INDW Γ окажется SPE, т.е. INDW Γ ⊂ SP NE = INDS Γ 6= INDS (под IND Γ имея в виду итеративно-недоминируемое решение нормальной фор- мы этой игры, образованное по порядку отбрасывания графа). Третье, менее тривиальное - это выделение случаев, когда порядок не важен, и SPNE можно находить через INDW произвольного порядка отбрасывания в нормаль- ной форме, не обращаясь к графу (см. теорему Куна ниже). “Дискоординация” в мультиперсонном представлении игры и “обязатель- ство” (commitment) На первый взгляд, можно определить SPNE через пересечение NE в нормальной форме и NE в мультиперсонной. Но отметим, что решение Нэша в мультиперсонном представлении может быть шире чем NE в нормальном. Рассмотрим соответствую- щий пример “дискоординации”. Пример "Голосование за свою гибель.” Предположим, Анна, Боб и Костя мо- гут проголосовать, выжить ли вместе или умереть, простым большинством голосов (например, они плывут в корабле с пробоиной, и заткнуть ее можно только вдво- ем или втроем, но не в одиночку, они сидят молча по своим каютам и независимо решают выйти ли). Каждый решает Life или нет, и если хотя бы двое "за” то все живы. Тут при одновременном принятии решений 5 Нэшевских равновесий, при- чем некоторые, особенно последнее, весьма "странные”: NE = {(Lif e, Lif e, Lif e), (Lif e, Lif e, Death), (Lif e, Death, Lif e), (Death, Lif e, Lif e), (Death, Death, Death)}. Формально, все 4 из приведенных голосований за свою смерть (включая последнее, единодушное) являются Нэшевскими, потому что переголосовав за Life участник- меньшинство не может изменить ситуацию, уже определенную большинством, так что не имеет стимула изменить голос. Очистка множества Нэшевских равновесий по осторожному принципу или по слабому доминированию улучшила бы моделирова- ние этой ситуации, удалив странность, но мы сейчас сосредоточиваемся на анализе самих понятий NE, SPNE. Теперь посмотрим на динамический вариант этой игры, когда решение принима- ется последовательно: сначала Анна голосует, потом, не видя ее хода голосует Боб, потом Костя. И Костя не видит сделанных партнерами ходов, поэтому решает втем- ную Life или нет, имея лишь ожидания о партнерах, сформированные прошлыми розыгрышами подобных партнеров (возможно, ныне мертвых :)). Если он слышал, 58 Глава 3. Динамические или “последовательные” некооперативные игры что игроки No 1 и No 2 всегда пасовали на Death, то и ему все равно, спасовать или нет, возможно он пасует. Аналогично и каждый из его партнеров пасует по той же причине, так что (Death, Death, Death) - опять одно из SPNE. Важно, что в поня- тии NE никто не надеется изменить поведение партнеров, принимая их стратегии за данность. Теперь рассмотрим этот динамический вариант, но с усложнением: за Константи- на третий голос может подать Анна, уже подавшая свой первый (или вынудить его к нужному ей ходу). Но она-то знает свой первый ход, и к тому же может маневриро- вать парами ходов (первый, третий), поэтому странное решение (Death, Death, Death) в NE исчезнет. А в мультиперсонном представлении игры оно бы осталось. Оно и есть "дискоординация"первого и третьего хода, являющаяся недостатком мультиперсон- ного представления игры, создающего иногда лишние NE. Суть “дискоординации” в том, что в решении NE mul благодаря неадекватным и несогласованным верам, я завтрашний поступаю несогласованно со мной сегодняш- ним, возможно упуская часть выгоды от координации этапов моей стратегии. По- этому NE mul неадекватно для описания полной рациональности. Напротив, SPNE свободно от этого недостатка поскольку включает требование NE. Но в некоторых играх оно обладает другим недостатком этого типа, называемом проблемой “невоз- можности обязательств” (lack of credible commitment). Скажем, в разобранной игре “Террорист”, если бы Террорист на предварительной стадии, до игры, мог связать себя обещанием автоматически взорвать бомбу при посадке в Нью-Йорке, то он вы- играл бы больше! Это парадоксальное на первый взгляд связывание себя 2 , то есть ограничение своих последующих возможностей, часто приносит выгоду. А обратное – невозможность связать себя обязательством – воспринимается как обидная неэф- фективность, препятствующая взаимовыгодным сделкам. (См. также в задачнике примеры: Мосты Цезаря, Веревки Одиссея, Цена репутации при кредите.) С точки зрения моделирования всех таких ситуаций, появление возможности обя- зательства (commitment) должна изображаться на дереве игры дополнительной вет- кой, не имеющей последующих разветвлений для игрока, дающего обязательство. В примере Террорист это выглядело бы так: Таким образом, возможность связать себя есть дополнительная возможность, это новая игра, и получение большего выигрыша в равновесии при возможности обязательств (commitment) не так уж парадоксально. О существовании решений SPE, единственности и совпадении концепций Утверждение 3.0.15.1 В развернутой форме конечной игры с совершенной ин- формацией (о ходах) сущестование и обычных и совершенных решений Нэша гаран- тировано: SP NE 6= ∅ (следовательно и NE 6= ∅). Действительно, существование решений очевидно из алгоритма Куна. Он по суще- ству лишь задает (конечный) алгоритм отбрасывания сильно доминируемых в по- диграх стратегий; но отбрасывая одну стратегию, мы всегда сохраняем в множестве 2 Сравн. пример “веревки Одиссея” в задачнике. 59 допустимых стратегий ту, что ее продоминировала, так что множество SP E не мо- жет остаться пустым. Включение NE ⊃ SP E следует из определения SP E и влечет NE 6= ∅. [[[]]]] Существование же решений для игр с несовершенной информацией (нетривиаль- ными информационными множествами) не гарантировано, как мы видели в разделе статических (одновременных) игр. В динамической игре (на дереве Γ) можно рассматривать и итерационное слабое доминирование. Чтобы ярче сравнить разные понятия, мы введем нетипичное для других учебников игр понятие SP INDW - Совершенное в подыграх равновесие при слабом доминировании. Отличие от SPNE только в том, что если игрок в левой стра- тегии ожидает получить X или меньший выигрыш, а в правой гарантированный Х, то левая стратегия отвергается. Здесь порядок отбрасывания стратегий задается дере- вом игры Г по подыграм, а не одновременен, как в обычном INDW рассматриваемом на шахматке. Это иногда существенно, а иногда - нет для решения. Скажем, в игре “Террорист” порядок слабого доминирования не важен: решение IN DW = SP INDW оказалось одно и то же. Это не всегда так, как мы увидим в примере (Табл. 4.1). Итак, в общем случае совпадение SP INDW = SP E или SP INDW = INDW не обязательно, можно гарантировать только SP INDW ⊂ SP E, и вообще, вложение итерационно-слабо-недоминируемых решений в сильные при совпадении порядка от- брасывания. Это вложение можно доказать (проверьте это самостоятельно), посколь- ку “слабое” доминирование вычеркивает больше стратегий, чем “сильное”, принятое для SP E. Частное достаточное условие единственности и, следовательно, совпадения ре- шений SP INDW =SP E есть “отсутствие неполного совпадения выигрышей в исхо- дах”. Здесь это утверждение распространено на фундированные графы, что упроща- ет формулировку (это позволяет пару вполне эквивалентных по выигрышам вершин объединить в графе, и считать одной вершиной). Заодно мы сформулируем теорему Куна: Теорема 3 Пусть в динамической конечной игре с совершенной информацией, описанной фундированным графом, каждый игрок имеет различные выигрыши в раз- ных финальных вершинах (нет пары вершин с одинаковыми для него выигрышами). 3 Тогда 1) Решения SP E = SP IN DW совпадают между собой и с результатом алго- ритма обратной индукции, причем результат существует и единственен по вы- игрышам. 2) [ Кун ] Эти решения совпадают с решением IN DW (с исходом при одно- временном порядке слабого итерационного доминированию в стратегическом пред- ставлении игры). Доказательство пункта (1) о существовании и единственности (см. Мулен-1985) — довольно очевидно из алгоритма. Действительно, каждый шаг отсечения вершин в алгоритме Куна даст при принятых гипотезах единственный вектор выигрышей. 3 Здесь подразумевается, что в исследуемой игре любые вершины, совпадающие по выигрышам для всех игроков, можно объединить в одну вершину, и применить эту теорему к этой новой игре. Тем самым, приведенный здесь вариант эквивалентен другому варианту теоремы, где разрешается совпадение выигрышей в некоторых вершинах, но тогда уж выигрыши должны совпадать для всех участников. 60 Глава 3. Динамические или “последовательные” некооперативные игры По индукции получаем единственное решение алгоритма. Легко проверить, что это и есть SP E= SP IN DW , и что других равновесий SP E, SP INDW нет. Доказательство пункта (2) – теоремы Куна – нетривиально и опускается (см. Мулен, 1985). [[[]]]] Отсюда следует, что если игра в стратегической форме представима фундирован- ным графом с различными в указанном смысле исходами, то INDW существует и единственно по выигрышам. Отсюда следует, в частности, существование решения SoE в шахматах (теорема Цермело), в шашках, и всех конечных настольных иг- рах с совершенной информацией. Но этого нельзя сказать о карточных играх, где информация о текущем положении игры обычно скрыта (несовершенна), и решение в чистых стратегиях может отсутствовать. Упражнения: Пример 3.0.9 “Пираты”. (Мулен, 1985). Пираты. (Мулен, 1985,p.-85). Пусть на пиратском корабле 50 пиратов разного старшинства делят 100 кусков золота по следующему обычаю. Старший предлагает дележ – кому сколько. Если хотя бы по- ловина команды (включая его) согласна, то так и будет, иначе его выбросят за борт. Оставшийся старшим предложит дележ, и так далее. Пираты не сговариваются (иг- рают каждый за себя), жадны к золоту и испытывают удовольствие от выбрасывания кого-либо за борт в размере 0.000001 от куска золота. Предскажите, кто сколько получит, вплоть до младшего юнги (Найти хоть одно решение SPE, или INDW Γ ). Пример 3.0.10 “Камешки”. Пусть Андрей и Борис договорились, что из лежа- щих перед ними n=10 камешков Андрей возьмет 1 или 2, по желанию. Потом Борис 1 или 2, и так далее, а взявший последний камень проиграл. Кто выиграет при идеальной игре обоих, первый или второй? Сохранится ли результат, если можно брать 1 или 2 или 3? Каков общий метод решения всех таких задач ∀n? (SPNE = INDW Γ ?) 3.0.16 Решение SPNE в непрерывной игре В непрерывных (по стратегиям и/или времени) играх применение тех же идей и ал- горитма обратной индукции аналогично. Только вместо дерева нужно представлять себе (даже если не удается нарисовать) некоторый граф с бесконечными разветвле- ниями (типа секторов круга). Пример 3.0.11 (“Последовательный торг по Рубинштейну”) (Дележ убы- вающего пирога= дележ выгоды при инфляции). (A.Rubinstein, 1959, see also H.Varian “Microec.Analysis”) Уезжая из дома, мать оставила двум жадным детям пирог, с таким условием. Сна- чала Анна предложит дележ ¯a 1 ∈ [0, 1] (свою долю), если Виктор согласен, то так и будет, иначе через час Виктор предложит дележ ¯ v 2 ∈ [0, 1] (свою долю). Если Анна не согласна, она через час сделает третье предложение дележа ¯a 3 ∈ [0, 1], и так далее. С каждым часом полезность пирога убывает некоторым темпом (возможно, от нетерпе- ния, или от засыхания пирога, когда α = β). Конкретнее, через час остается α ∈ (0, 1) исходной полезности для Анны и β ∈ (0, 1) полезности Виктора. Если, скажем, на k-й 61 итерации они согласились на дележ (¯a k , ¯ v k ); ¯a k + ¯ v k = 1, то полезность Анны от него будет A(¯ v k ) = a k = α k ¯a k , полезность Виктора — V (¯ v k ) = v k = β k ¯ v k . Зная конечный период T , в течение которого пирог остается съедобен, нужно предсказать, на какой итерации и как (рациональные и жадные) дети поделятся (подобная игра очень ти- пична в ситуации, когда две фирмы способны осуществить взаимовыгодный проект, но надо договориться о разделе прибыли, а время переговоров означает упущенную прибыль). Анализируя эту игру торга, для простоты будем считать α = β = 1/2, Т=4, и нарисуем дерево (если можно так выразиться) этой непрерывной по стратегиям игры: 6 - 1 8 1 4 1 1 a t v t * q ) * q ) * q ) * q ) a 1 v 2 a 3 v 4 0 0 0 0 1 1 2 1 2 1/4 1/8 ^ ^ 6 ^ ^ - ref use A5 agree V 2 a 1 1 − a 1 1 − v 2 v 2 a 3 1 − a 3 1 − v 4 v 4 0, 0 A 1 agree A5 agree A3 agree V 4 SP E ( 3 8 , 5 8 ) Рис. 3.3: Игра: дележ убывающего пирога по Рубинштейну (последовательный торг). Решение игры в изображенном простом случае (общий случай, и бесконечный вариант игры рассмотрите самостоятельно) легко найти с помощью ступенчатой ди- граммы уровней полезностей, алгоритмом обратной индукции. Действительно, ре- шим игру с конца: предположим она дошла до последнего, четвертого периода, где Виктор предлагает дележ. Если Анна откажется, то оба получат 0, поэтому она со- гласится на дележ a 4 > 0 сколь угодно близкий к нулю, что изображено нижним концом пунктира. Виктор же тогда получит почти все от оставшегося пирога, то есть почти 1/8. Зная это, на третьем шаге Анна должна предложить партнеру по- лезность не менее v 3 = 1/8, тогда пунктирная линия дает точку 2, где оба имеют примерно по 1/8. Зная это, Виктор на втором шаге предложит партнеру примерно a 2 = 1/8, а сам получит остальные 3/8. Аналогично мы получаем SPE: дележ пер- вого шага a 1 = 5/8, v 1 = 3/8, который и случится, при принятой гипотезе полной рациональности. Упражнение. Предположите, что дисконты (“кофициенты терпения”) Анны α и Виктора β разные, как и в чью пользу (терпеливого ли) изменится решение? Обоб- щите решение для произвольного числа периодов Т, и для бесконечного T = ∞, на- пример, переходом к пределу. (Проверьте A = (1−β)/(1−αβ), V = (1−α)β/(1−αβ).) Пример 3.0.12 Упражнение: Игра входа в отрасль. Пусть есть отрасль с функцией обратного спроса (ценой от суммарного объема) вида p(Y ) = 9 − Y и монополистом - старожилом в этой отрасли, с постоянными предельными издержками ˙c 1 (y 1 ) = 1 (проверьте, будет ли монопольная цена p M = 5 или 4). Пусть потенциальный новичок, входя в отрасль, должен сделать невозврат- ные начальные капиталовложения K = 1 и ожидает предельные издержки ˙c 2 (y 2 ) = 2. 62 Глава 3. Динамические или “последовательные” некооперативные игры Пусть отрасль может просуществовать два периода (можно обобщить на n) и дискон- та нет: прибыли сегодня и завтра равноценны, альтернативное вложение капитала K - с нулевым процентом. Старожил обещает новичку в случае входа добиться (повы- шением выпуска) снижения цены достаточно низко (< 2), чтобы заставить новичка прекратить производство, предполагая, что после этого новичок банкрот и во вто- ром периоде можно сохранять монополию. Если же новичок войдет, то ожидается решение Штакельберга (т.е. SP E Old,N ew ): лидер- старожил установит выпуск рань- ше). Стоит ли верить этой угрозе или он блефует и можно входить? Обобщите задачу для различных данных ˙c 2 (y 2 ) 6= 2, K 6= 1. 3.0.17 SPNE и SPINDW при равновыгодных исходах или несо- вершенстве информации Теперь рассмотрим SPNE и SPINDW в более сложном случае: при совпадении неко- торых значений выигрышей и/или при неполной информации о сделанных ходах. Легко увидеть, что здесь, в отличие от случая предыдущей теоремы, решений может быть множество. Но с существованием решений проблемы могут возникать только при несовершенстве информации. Пример 3.0.13 Случай “С” описанной на (Рис. 3.4) игры возможен, если терро- рист — психически особенный человек (это с ними бывает): ему все равно, жить или нет, но приятнее умереть или жить на Кубе. Летчику же смерть в Нью-Йорке предпочтительнее смерти на Кубе, а где быть живым - все равно. Тогда возника- ет много равновесий SP E (3 исхода, исключая (Cuba,Bomb)). Но вектор выигры- шей пилота при курсе Нью-Йорк (2,1) слабо доминирует над альтернативным, и множество SP IN DW итерационно (слабо) недоминируемых по подыграм страте- гий состоит из двух неэквивалентных исходов: SP INDW = {(N − Y, P eace) ⇒ (2, 1); (N − Y, Bomb) ⇒ (0, 1)}. Итак, здесь INDW 6= SP INDW 6= SP NE. Pilot Terr-st Terr-st * j * z 1 q 1, 1 2, 1 0, 2 2, 2 N-York Cuba Bomb Peace Peace Bomb Pilot Terr-st Terr-st * j * z 1 q 1, 1 2, 1/2 0, 0 2, 2 N-York Cuba Bomb Peace Peace Bomb Case C: full information, but equal payoffs Case D: imperfect information Рис. 3.4: Игра “Террорист - камикадзе”: часть решений SPNE 6= SPINDW. В варианте “D” игры “Террорист” похожее несовпадение. Здесь выигрыши раз- личны, но неинформированность террориста о ходе летчика (не видно, куда летим) 63 позволяет ожидать от него любых ходов. В результате опять неединственно равно- весие SP E (поскольку собственных подыгр нету, то оно равно NE={ (N-Y,Bomb), (Cuba,Peace)} ), но одно SP IN DW . В подобной игре, которая эквивалентна одновременной, иногда ни Нэшевского, ни тем более совершенного в подыграх решения не существует (мы видели это при неко- торых вариантах выигрышей, скажем, в игре "Монетки": ((1,0),(0,1),(0,1),(0,1)) ). Тогда нужно искать равновесие в смешанных стратегиях. Упражнение. Пример “Масти и Картинки”. Формализуйте графом игру “Выбери масть и силу карты” (см. Таблицу 3.0.17) и сравните SPNE и INDW. Масти: Крас- ные Чер- ные Черви ↓ Бубны ↓ Крести ↓ Пики ↓ 8 0 2 0 Старшие: Туз→ 1 3 5 1 6 0 4 2 Старшие: Король 7 1 5 3 2 6 8 0 Младшие: Дама 3 9 3 1 0 4 4 0 Младшие: Валет 3 7 9 1 Таблица 3.2: Пример “Масти и Картинки”. Здесь, в Таблице 3.0.17, предполагается, что строчный игрок – Анна – выберет: Старшие или Младшие, потом столбцовый – Боб – выберет: Красные или Черные, потом строчный - конкретную картинку из уже названной группы (из Старших или из Младших), потом столбцовый - конкретную масть из уже названного цвета. Найти SPE, SPINDW. Вариант 2: Усложнение задачи - найти SPE, SPINDW если последний ход реша- ется жребием - подбрасыванием монетки. Вариант 3: То же, но результат подбрасывания монетки известен до всех ходов второму игроку, и только ему. Вариант 4: Найти SPE, SPINDW если второй ход решается жребием - подбрасы- ванием монетки, и никто не видит его. Вариант 5: Найти SPE, если предпоследний ход делается (Анной) втемную, и Боб не видит его результат делая последний ход. 3.0.18 Неполная информация о типе партнеров: Байесовское равновесие Ранее мы предполагали, что игроки либо ничего не знают о целях партнеров (концеп- ции MM, DE), либо знают цели точно (IND), или не интересуются целями, зная ходы партнеров: NE, SPNE. Теперь рассмотрим случай, когда игрок имеет представление о нескольких типах возможных партнеров – каждый с известными целями, и гипо- тезу о вероятности встретить каждого из них. Это Байесовское равновесие, частный 64 Глава 3. Динамические или “последовательные” некооперативные игры случай SPNE. Для этого мы используем общее представление о поведении в усло- виях риска, разработанное Нейманом и Моргенштерном - максимизацию ожидаемой полезности (см. учебники по микроэкономике). Чтобы ввести понятие Байесовского равновесия, рассмотрим пример “Инспекция”. По сути, это описание равновесия в некоторой популяции инспекторов и нарушите- лей, но каждый отдельный эпизод встречи пары игроков – есть двухшаговая игра. Сначала ходит природа (случай), выбирая типы, которые встретились, а затем одно- временно, не видя типа партнера, ходят эти реализовавшиеся инкарнации игроков. Пример 3.0.14 Нарушитель и инспектор. Рассмотрим игру, где две роли: по- тенциальный нарушитель и инспектор. Например, нарушение состоит в том, чтобы выпить садясь за руль, а инспектор — сотрудник ГАИ. Предположим, в первой ро- ли бывает по два подтипа: “наглый” водитель, который не очень боится штрафов, или “робкий” водитель. Также и инспектор может быть “старательный”, или “лени- вый” — то есть сильно недовольный, когда проверит зря. Эти гипотезы отражены в следующей матрице - Таблице 3.3. Таблица 3.3: Инспекторы: 1 − λ λ Стара- тельный Лени- вый Контр-ть Лениться Контр-ть Лениться Наглый: Пить 3 0 1 0 -1 2 -1 2 Наглый: Не пить -1 0 -4 0 1 0 1 0 Робкий: Пить 3 0 1 0 -3 1 -3 1 Робкий: Не пить -1 0 -4 0 1 0 1 0 Чтобы предсказать, какая обстановка сложится на этом посту ГАИ: часто ли во- дители станут проезжать его с нарушением, и часто ли их будут проверять (что, очевидно, связано), нужно задать гипотезы о частоте, с которой встречаются в при- роде типы. Пусть “наглым” водитель бывает с частотой ν ∈ [0, 1] (соответственно, робким — (1 − ν)), а инспектор бывает ленивым с частотой λ ∈ [0, 1]. Зададим кон- цепцию решения. Рассмотрим игру, где имеется n ролей игроков i = 1, .., n и в каждой из них мо- жет оказаться несколько (T ) типов t = 1, .., T , (для простоты записи, пусть число T одинаково во всех ролях). Типы различаются целевыми функциями, но не возможно- стями ходов. Пусть каждая инкарнация, то есть игрок/тип (jt) знает “объективные”, известные всем, вероятности (µ i1 , .., µ iT ) ∀i появления типов и максимизирует мато- жидание своей полезности U jt (¯ x), зависящее от матрицы ¯ x := (x it ) t=1,..,T i=1,..,n текущих стратегий выбранных всеми игроками/типами. 4 4 Зависимость моей полезности от ходов игроков моей роли практически не наблюдается, но формально удобнее аргументом полезности считать всю матрицу стратегий. 65 Определение 3.0.18.1 Байесовское равновесие BE есть такой набор ¯ x стратегий (возможно, смешанных) что ни одному игроку/типу нет выгоды отступать от текущей стратегии при знании частоты типов и гипотезе, что все остальные не отступают от своих стратегии. Тем самым, это Нэшевское равновесие SPNE в соответствующей игре, где скрыт ход природы задающей типы. Равновесие называют “вполне разделяющим” (separating equilibrium) относитель- но некоторой роли, если разные типы этой роли действуют в нем по-разному и раз- личимы по наблюдаемому действию. Равновесие называют “вполне объединяющим” (pooling equilibrium), если разные типы действуют в нем одинаково и неразличимы. В промежуточных случаях говорят о частично разделяющем (частично объединя- ющем) решении. Легко заметить, что по определению BE есть (смешанное) SPNE в двухшаго- вой игре, или просто Нэшевское равновесие в подходящим образом заданной игре, а именно в такой, где дополнительный игрок – природа – задал раз и навсегда свои смешанные стратегии µ i1 , .., µ iT ∀i. 5 Чтобы найти BE в примере “инспектор/нарушитель”, будем проверять все вари- анты для параметров вероятностей (µ driver,1 , µ inspector,2 ) = (ν, λ). Проверим сначала “разделяющее” равновесие вида (N nagl , N robk , I star , I leni = (Пить,Непить, Проверять, Непр.). Запишем условие, необходимое, чтобы “Наглый” не отступил в этой ситуа- ции от стратегии Пить: U nagl (Пить, Непить, Контроль, Лень)= −1(1 − λ) + 2(λ) ≥ U nagl (Непить, Непить, Контр., Лень)= 1(1 − λ) + 0(λ) ⇔ 2 ≤ 4λ ⇔ 1/2 ≤ λ. Аналогично, чтобы “Робкий” не отступил в этой ситуации от стратегии Непить: U robk (Непить, Непить, Контр., Лень)= 1(1 − λ) + 0(λ) ≥ U robk (Пить, Непить, Контр., Лень)= −3(1 − λ) + 1(λ) ⇔ λ ≤ 4/5. Так же проверяя совместимость стратегий Проверять для Старательного и Непро- верять для Ленивого с текущими стратегиями Наглого и Робкого, найдем, что огра- ничения на вероятность ν наглых, при которой обсуждаемое “вполне разделяющее” равновесие возможно, должна лежать в пределах 1/4 ≤ ν ≤ 4/5. Могут ли в этой игре быть “объединяющие” или “частично объединяющие” рав- новесия, то есть такие, где типы в одной из ролей ведут себя одинаково? Рассмотрев матрицу выинрышей, легко установить, что это невозможно. Например, если оба инспектора “Ленятся”, тогда оба водителя начинают “Пить”. После этого оба инспек- тора начнут проверять, и так далее, так или иначе, игра не стабилизируется в этом “объединяющем” состоянии. Аналогично проверяется и неравновесность остальных объединяющих состояний. Поэтому решения могут быть только среди “вполне раз- деляющих” вариантов. Что же произойдет, когда ν, λ не попадают в пределы, при которых возможно “разделяющее” равновесие? Очевидно, Байесовского равновесия в чистых стратеги- ях тогда нет. Игра раскачивается, и нужно обсуждать Байесовское равновесие в смешанных стратегиях, подобное NE m (легко догадаться, что это и есть NE m в подходящим образом сформулированной игре описанных игроков; игре между собой и с природой). А именно, нужно использовать найденные нами границы природ- ных вероятностей 1/2 ≤ λ ≤ 4/5, 1/4 ≤ ν ≤ 4/5 как условные вероятности “на- блюдаемых типов поведения”. Скажем, если ленивых инспекторов в природе менее 5 Подобного игрока с фиксированной стратегией называют “болваном” (“dummy”). 66 Глава 3. Динамические или “последовательные” некооперативные игры половины, то их нехватку для формирования равновесия восполнят часть стара- тельных, которые иногда ленятся, то есть по поведению примыкают к другому типу (частично-разделяющее равновесие). А именно, мы должны искать такую пару ча- стот 1/2 ≤ ˜ λ ≤ 4/5, 1/4 ≤ ˜ ν ≤ 4/5, чтоб наглым было все равно по матожиданию выигрыша нарушать правила или нет. А старательным инспекторам чтоб было все равно, проверять или нет: U s t(P r, ˜ ν) = U s t(Nepr, ˜ ν). Тем самым, мы найдем и доли нарушающих и доли проверяющих в смешанном равновесии. Упражнение: найти такое решение. 3.0.19 Неопределенность и динамика: совершенное Байесов- ское (слабое секвенциальное) равновесие Теперь рассмотрим более сложную концепцию, совмещающую вероятностный под- ход Байесовского равновесия и смешанные стратегии с развернутой (динамической) формой игры. Дадим определение, а затем мотивируем это очередное усложнение (утончение, refinement) концепции решения динамических игр, утончение введенное Зелтеном (Selten, 1975??). Определение 3.0.19.1 Веры ¯ µ ih игрока i в информационном множестве h i есть век- тор вероятностей, которые он приписывает возможности нахождения в каждом из физических узлов этого множества если в нем находится, в сумме они составляют 1. Определение 3.0.19.2 Пошагово-смешанная (поведенческая, behavioral) стратегия σ i игрока i называется секвенциально-рациональной при верах ¯ µ и при заданных смешанных стратегиях партнеров ¯ σ j , если в каждом информационном множестве она является лучшим ответом-откликом на эти веры и стратегии (и на ходы этого же участника в предыдущих позициях), то есть максимизирует по σ ih его матожида- ние выигрыша E{u i (σ ih , ¯ σ ik , ¯ σ j , ¯ µ)}. Тем самым, начиная от любого множества h(i) мат-ожидание полезности E{u i (σ i , ¯ σ −i )} не может быть улучшено изменением оставшихся до конца игры ходов, при доступной игроку информации и фиксирован- ных ходах партнеров. Определение 3.0.19.3 (Сильное) Совершенное Байесовское равновесие ((Subgame) Perfect Bayesian Equilibrium, PBE = SPBE), или, иначе, слабое секвенциальное рав- новесие в игре n лиц есть профиль (¯ σ, µ) смешанных пошагово (поведенческих) стра- тегий ¯ σ = (¯ σ 1 , ..., ¯ σ n ) ∈ ∆X и вер µ = (µ 1 , ..., µ n ) ∈ ∆M всех игроков, 6 таких что 1) Для каждого игрока i его стратегия ¯ σ i является секвенциально-рациональной при данных стратегиях партнеров ¯ σ −i и верах µ i ; 2) веры µ слабо (на пути игры) согласованы со стратегиям σ, в смысле Байесовского правила условных вероятностей. 7 6 Вероятностная пошаговая стратегия есть вектор смешанного расширения ходов, в отличие от смешанного расширения полных (многоходовых) стратегий. 7 В частности, если все ходы из некоторого узла оканчиваются в одном последующем информа- ционном множестве, то веры в нем должны совпадать с вероятностями ходов: µ h = σ h−1 , а в других случаях используются более сложные условные вероятности. Иной вариант концепции решения – сильное согласование вер – ниже введен в понятии SeqE. 67 Поясняя и мотивируя понятие SPBE, рассмотрим пример, где обычной концеп- ции SPNE недостаточно, поскольку таких равновесий многовато и не все выглядят разумным поведением. Точнее, SPNE включает наряду с осмысленными и довольно неправдоподобные исходы, которые хотелось бы исключить из решений. A B B 3 ° N ° ° N N 0, 2 Simple representation 0 u A = 1 -.5 -1 1/2, 1/2 0, 2 NE -1, -1 Up Left Right l r r l 1, 1 NE -1/2, -1 r l Up Right Left .5 -1 .5 -1 A B B 3 ° N ° ° N N 0, 2 0, 2 1 -.5 -1 1/2, 1/2 0, 2 NE -1, -1 Up Left Right Sophisticated representation l r r 1, 1 NE -1/2, -1 r l Up, [R] u B = 1 Down, L l .5 -1 .5 A 0, 2 0, 2 2 -1 1 ? 6 Down Up, [L] Down, R Рис. 3.5: Пример "Жирафа” мотивирующий недостаточность концепции SPNE, пре- имущество PBE. Пример 3.0.15 В примере "Жирафа” (назван по силуэту дерева) 8 простое изображение игры (слева) сравнивается с более сложным допустимым отображением той же игры (спра- ва) и оказывается, что у них разные множества равновесий SPNE, что является недостатком этой концепции. Действительно, слева нет собственных подыгр, есть только сама игра. Поэтому оба решения NE являются совершенными, т.е. SPNE: (A = Up, B = [r]) → (0, 2), (A = Lef t, B = l) → (1, 1). Но по сути, в первом из них игрок B объявляет свой ход "r” бездумно (точнее, это обещание хода на слу- чай стратегии Down, формирующее ожидания партнера). Он демонстрирует “пустую болтовню” поскольку к нему ход никогда не попадает, так что улучшить выигрыш перейдя к своей доминирующей стратегии "l” он не надеется и безразличен. Но это "r” кажется глупым поведением на случай если ход к нему может попасть хотя бы с очень маленькой вероятностью: тогда лучше запланировать хотя бы недоминируе- мую стратегию, а еще лучше – оптимальный отклик на действия партнера. 8 Можно придумать и сказку под это название: в зоопарке жирафа Ann может выбрать, кормить- ся ли по утрам вытягивая голову вверх к веткам деревьев (Up) или вниз – в левую кормушку или в правую. Если она не высунула голову над крышей, мальчик Bob, не зная, куда она пошла, может положить ей корм либо в левую кормушку (l=left), либо в правую (r=right) и полюбоваться жира- фой. Итак, возможно наблюдать жирафу либо над крышей, либо слева, либо справа. Слева светлее, и наблюдение там радует Боба больше, чем справа, но и наверху видно хорошо, что отражено в выигрышах. 68 Глава 3. Динамические или “последовательные” некооперативные игры В более сложным же отображении той игры, показанном справа, оказывается, что первое из этих равновесий не остается решением SPNE, так как не является равновесием NE в подыгре возникающей после хода Down (и сверх того, состоит из строго доминируемых стратегий, причем для обоих!). Сложное представление игры здесь более удовлетворительно чем простое, оно исключило "глупое” решение. 9 Чтобы исключить неестественные решения в любом представлении игры, можно потребовать, чтобы любой игрок в любой ситуации обещал действовать рационально (или, чтоб от него ожидали только рациональных действий), основываясь на некото- рых вероятностях, которые он приписывает своему истинному положению в рамках информационного множества. Эти вероятности и называют "верами”. Они связаны с ожиданиями о партнерах, то есть их истинными стратегиями по правилу услов- ных вероятностей. Скажем, в левом варианте игры "Жирафа”, предположим, игрок A планирует вероятности своих трех ходов как Up=0.7, Left=0.1, Right=0.2. Тогда веры игрока B о вероятности нахождения в левом или правом узле своего множества (если уж ему попал ход) должны быть Left=1/3, Right=2/3. Если же A планирует вероятности ходов Up=1.0, Left=0.0, Right=0.0, то веры в узлах B 2 , B 3 все равно должны быть ненулевые. Тогда, при любых верах µ 2 , µ 3 равновесие NE=(Up,[r]) не выглядит рациональным поведением игрока B, он не должен играть сильно доми- нируемую стратегию. Концепция SPBE отсекает глупости. Преимущество сложного представления этой игры – что оно тоже обеспечивает ненулевые веры даже для концепции SPNE, то есть приближает SPNE к идее Совершенного Байесовского рав- новесия PBE. В предыдущем примере, понятие PBE очистило множество решений от неразум- ных использованием “вер”, чего мы и добивались усложнением концепции. В следу- ющем, такое очищение достигается за счет самого понятия секвенциальной рацио- нальности. Пример 3.0.16 (“Ослик” Зелтена, вариант) . Интерпретация игры не обсу- ждается, игра названа “Ослик” за форму графа: 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 Рис. 3.6: Игра “Ослик” (Selten, 198..?). Здесь два SPNE в чистых стратегиях. Решение SPE 1 =(a,L,[B]). Игрок Bob объ- являет стратегию B поскольку ему все равно что объявлять, ход к нему никогда 9 Несколько подобное, но не строго доминируемое “глупое” NE в примере "дырявая лодка” раз- бираемом выше в связи с дилеммой заключенных. 69 не попадает. Казалось бы, оно поддерживается соответствующими по Байесовско- му правилу верами (1,0) и могло бы быть PBE. Но этот ход Боба не является секвенциально-рациональным, потому эта рациональность требует обещать в каж- дой ситуации где получил бы ход действовать лучшим образом, а здесь это не так. Переходив вниз Боб выигрывает 5 вместо 3-х при текущих намерениях Константи- на. Итак, секвенциальная рациональность тоньше Нэшевской, выбирает более узкое множество оптимумов. Второе решение SPE 2 =(A,B,[R]) подтверждается как SPBE при верах a, b третьего игрока, наблюдающего, что ему дали ход (вероятностях, что дали из позиции a или из b) типа a > 2b (оно является и сильным секвенциальным равноыесием). Чтобы подробнее обыграть понятие PBE, разберем также следующую игру. Thief µ Ss µ Sa * j > - - R 7 1, -2, 0 0, 0, 0 1, -1, 0 stole stole armed silence cry silence cry Policemen µ P s * : s z ignore 1, -2, 0 -2, 1, 2 -5, 1, -3 not stole 1, -1, 0 catch catch µ P s Seller ignore (u T , u S , u P ) = (u T , u S , u P ) = σ T a σ Ss σ P i σ P i σ Ss σ T s Рис. 3.7: Игра “Базар”: решения SBE. Пример 3.0.17 (“Вор на базаре”) На Рис.3.7 представлена игра с несовершен- ной информация о ходах: второй и третий игроки не способны различать, какой ход сделан первым. Подразумевается популяция трех ролей: Воров, Торговок, Полисме- нов. Базарный вор может или отдыхать (быть честным), или воровать просто, или воровать с оружием. Торговка может кричать или молчать, когда у нее с лотка тя- нут товар. Полисмен может или бежать на крик и ловить, или лениться (отдыхать). Записанные на рисунке выигрыши берут за точку отсчета (0,0,0) вариант, когда Вор отдыхает, и остальные - тоже. Когда торговка что-то теряет, ей неприятно (-1), но неприятно вдвойне, если она еще и кричит при этом зря (это отражает выигрыш -2 в этом варианте). Если же ее врага-вора поймают - она довольна (+1). О Полисмене, предполагается, что он любит премии за поимку воров, но не любит риска с воору- женным вором, хотя справится и с таким. О Воре известно, что он больше отсидит, если пойман с оружием (5 лет против 2-х). Будем рассматривать смешанные стратегии игроков (σ thief ∈ [0, 1] 3 , σ seller ∈ [0, 1] 2 , σ police ∈ [0, 1] 2 ) как вероятности, с которыми эти хо- ды в среднем встречаются на описанном базаре. Разыскивая равновесие (то есть стабильное поведение каждого типа), предположим, что ОЖИДАНИЯ всех игроков (предполагаемые вероятности ходов партнеров), а именно: ожидания вора, ожидания торговки, ожидания полисмена — соответствуют наблюдаемым частотам делаемых ходов. Но этого мало, поскольку нужно еще и вне пути игры задать так называемые 70 Глава 3. Динамические или “последовательные” некооперативные игры ВЕРЫ, то есть ожидаемые вероятности нахождения в том или ином узле информа- ционного множества, если игра вдруг, каким-нибудь чудом, туда попадет. Скажем, если все Воры обычно отдыхают, то Торговке, а еще более - Полисмену, все же любо- пытно знать, с ножом ли тот, кто стащил у нее вещь с лотка, если это случится. Это и есть их (Торговки и Полисмена) априорные, не проверенные жизнью, веры, которые между собой могут не совпадать. Например, Торговка может предполагать частоты верхнего и нижнего узлов графа типа (0.2, 0.8), а Полисмен - (0.9, 0.1), и каждый объявлять свою (возможно, ненаблюдаемую, но известную партнерам) стратегию, исходя из этих априорных вер. Проверим, может ли быть решением (Отдыхать,[Кричать,Ловить]) (в квадратных скобках, как обычно, ходы вне пути игры) хоть при каких-либо верах. Заметим, что стратегия торговки КРИЧАТЬ лучше противоположной при ее ожидании от Полис- мена хода "Ловить". Полисмен же может продолжать объявлять (только на словах, пока Вор не ворует) стратегию Ловить, только если он верит, что если уж Вор сво- рует, то без оружия. Если же с вероятностью более 2/5 он верит в противоположное, то отступит от Ловить. Иначе, проверяемое решение может оставаться SBE (а также SPE, NE) при вере более 3/5 в безоружность, и при любых верах Торговки, возможно и отличающихся от вер Полисмена! Анализируя эту игру, можно найти, что в ней есть и другие Совершенные Бай- есовские равновесия, но несовпадение вер торговки и Полисмена становится невоз- можным, если Вор хоть иногда ворует: определение PBE не позволяет несоответствие вер практике на пути игры. 3.0.20 Эффект “сигналинг” в игре образования С содержательной стороны, важным эффектом возникающим в Байесовских играх является "сигналинг”, то есть ходы, часто связанные с дополнительными затратами, предпринятые специально для того, чтобы выявить для партнера по игре свой тип. Естественно, это проявляется только в разделяющих равновесиях. Продемонстриру- ем это на важном с мировоззренческой стороны примере, построенном на упрощении знаменитой модели Спенса объясняющей самовыявление способностей через универ- ситеты. Пример 3.0.18 (Рынок образования по Спенсу, упрошенный вариант). 10 Пусть, в популяции тинейджеры бывают двух типов: с вероятностью λ ∈ (0, 1) возникают тинейджеры “Low” (с низкими способностями или трудолюбием) и с веро- ятностью 1 − λ тинейджеры “High” (с высокими способностями). Те и другие в стар- ших классах школы и после нее могут выбрать одну из двух стратегий: “Educate” или “Leisure”, а могут и смешивать ту и другую с вероятностями (1 − l i ) > 0 и l i > 0 когда стратегии равновыгодны (подразумевается, что часть суб-популяции поступа- ет по-одному а часть по-другому). Первая стратегия означает пойти учиться дальше в университете, а вторая – полениться и окончив школу сразу идти работать. Пусть, 10 Более развитые варианты модели Спенса включают много типов или даже континуум типов способностей учеников, много вариантов учебы, включая выбор числа лет образования и др. услож- нения. 71 Nature 6 ? High Low student - - ¾ ¾ Study= 1 − l H Study= 1 − l L leisure = l H leisure = l L λ 1 − λ Employer Employer Y ) i ) * z * j 4(1 − µ L1 ) + 2µ L1 µ L1 = l H ∗(1−λ) µ L1 +µ L2 4(1 − µ L2 ) + 2µ L2 µ L2 = l L ∗λ µ L1 +µ L2 4(1 − µ L3 ) + 2µ L3 µ L3 = (1−l H )∗(1−λ) µ L3 +µ L4 4(1 − µ L4 ) + 2µ L4 µ L4 = (1−l L )∗λ µ L3 +µ L4 Education as signalling Рис. 3.8: Игра “Образование как сигнал”: решения PBE. для типа High учиться не трудно, и издержки подготовки к поступлению и дальней- шей четырехлетней учебы в университете они оценивают для себя в 1 (скажем, одну сотню тысяч дисконтированного до уровня Net-Present-Value дохода), а тип Low оце- нивает эти издержки в c > 1, несколько дороже. Пусть, на стороне работодателей тип High обычно приносит 8 единиц выручки (Net-Present-Value на момент решения об учебе), а тип Low только 4. При этом рынок труда будем предполагать совершенным, поэтому совокупный работодатель играет как болван (“dummy”), выплачивая любо- му работнику в точности размер ожидаемой от него выручки за вычетом налогов и нормальной прибыли, составляющих половину выручки. А именно, работодатель выплачивает 4 если он уверен, что это High, либо 2 если уверен в Low. В смешанном случае он выплачивает 2µ l + 4(1 − µ l )0 – когда ожидает с вероятностью µ l > 0 что нанял Low и с вероятностью (1 − µ l ) что нанял High. (Здесь не очень реалистично предположено, что образование само по себе не улучшает качество работника, а оно важно только как сигнал. Это сделано нарочно, чтобы подчеркнуть, что уже этой роли образования достаточно, чтобы оно существовало. И что вообще, не-бесплатные сигналы нередко образуются в равновесиях.) Итак, при верах µ l > 0 дерево игры и ожидаемые выигрыши примут такой вид как на Рис.?? (выигрыши болвана роли не играют и заменены пробелом). Таким образом, первой играет природа, сообщив каждому из популяции учащихся его тип, неразличимый для работодателя. Затем играет ученик каждого типа выби- рая стратегию учебы. Причем возможно, какой-либо тип учеников выбирает смешан- ную стратегию, например, часть l H ≥ 0 хороших учеников ленится, или часть l L ≥ 0 плохих учеников ленится. В равновесии работодателя настраивают свои ожидания при найме по средним наблюдаемым обычно после найма производительностям вида 2µ l + 4(1 − µ l )0. Например, предположим достаточно высокие издержки c = 3 неспособных, чтобы они никогда не учились и проверим, что возможно вполне разделяющее равновесие: сильные учатся, а слабые нет. Тогда ожидания выручки работодателя от человека с дипломом равны 8, он платит ему 4, и за вычетом издержек способный получает 3, поэтому не переключится на стратегию не учится, где выигрыш только 2. Аналогич- но, неспособный из зарплаты 4 за вычетом издержек получил бы удовольствие только 72 Глава 3. Динамические или “последовательные” некооперативные игры 1, что меньше 2-х получаемых если не учится. Пожтому он тоже не отклоняется от текущей стратегии, это равновесие. Более сложное, частично-разделяющее неспособных равновесие (l H = 0, l L > 0), возможно при меньших издержках неспособных, скажем 1.5. Посчитав, мы найдем нетривиальную долю l L > 0 тех из них, кто ленится. Найдем, при какой доле λ > 0 ленивых среди рождающихся такое равновесие возможно. ... 3.0.21 Эффект “блеф” Пример Упрощенный покер (trivial quiz). Анна имеет карту “Дама” и это обоим известно, карта открыта. А Боб тянет одну из 2-х карт простой колоды: Король и Валет. Смотрит и не показывает. Если он говорит “Пасую, Валет”, то проигрывает, получая -$1, а Анна выигрывает $1. Если он говорит “Играю, Король”, то ставка повышается до $2, и Анна ходит. Если она говорит “Верю что Король”, Пасую, то проигрывает $2, отдавая их Бобу. Иначе (“Не верю”), карты открываются, и если карта Боба старше, он выигрывает $4 за счет Анны. Оба нейтральны к риску. Формализуем игру, построив дерево, найдем решение SPNE в смешанных страте- гиях β < 1, α < 1, то есть вероятность блефа Боба, “проверяю” Анны, и веры Анны. |