Лекции по теории игр и политологии
 Скачать 1.03 Mb.
|
|
Содержание Предисловие 3 Введение: классификация игр 4 1 Глава. Игры в нормальной форме (“статические” или “одновременные”) 5 1.1 Максимин и доминирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Доминирующее равновесие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Итерационно-недоминируемые решения IN D W , IN D S . . . . . . . . . . . . . . . 13 1.4 Игры в популяциях и равновесие Нэша . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.1 Смешанные стратегии и смешанное равновесие N E m . . . . . . . . . . . 17 1.4.2 Множественность равновесий Нэша, “фокальные точки” и борьба за ли- дерство: равновесие Штакельберга (последовательные ходы) . . . . . . . 20 1.5 Кооперативные решения - Парето-оптимум и ядро . . . . . . . . . . . . . . . . . 22 1.6 Нахождение и сопоставление разных решений . . . . . . . . . . . . . . . . . . . 23 1.7 Дополнительные примеры решений в непрерывных играх и N E m . . . . . . . . 27 1.8 “Равновесие дрожащей руки” (THNE) для нормальной формы . . . . . . . . . . 30 1.9 О (не-)совпадении различных решений . . . . . . . . . . . . . . . . . . . . . . . . 31 1.10 О существовании и компактности множеств решений . . . . . . . . . . . . . . . 32 1.11 Что общего в разных концепциях решений? . . . . . . . . . . . . . . . . . . . . . 34 2 Глава. Игры в развернутой форме (“динамические” или “последователь- ные”) 35 2.1 Формализация последовательных игр, соответствие развернутой и нормальной формы игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2 Стратегии нормальные и пошаговые, мультиперсонная форма игры и SPNE . . 37 2.3 SPNE и обратная индукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.3.1 “Дискоординация” в мультиперсонном представлении игры и “обяза- тельство” (commitment) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.3.2 О существовании решений SPE, единственности и совпадении концепций 41 2.4 Решение SPE в непрерывной игре . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5 SPE и INDW Γ при равновыгодных исходах или несовершенстве информации . 44 2.6 Неполная информация о типе партнеров: Байесовское равновесие . . . . . . . . 45 2.7 Совершенное Байесовское или слабое секвенциальное равновесие . . . . . . . . 47 2.8 P BE(ε), секвенциальное равновесие (SeqE), T HP E . . . . . . . . . . . . . . . . 50 2.9 Сопоставление решений SPE, SBE, SeqE, THPE, INDW . . . . . . . . . . . . . . 51 2.10 Отсутствие “общего знания”, игры с репутацией, блеф . . . . . . . . . . . . . . . 54 2.11 Уточнение понятия рациональности; прямая индукция . . . . . . . . . . . . . . 55 2.12 “Почти-совершенная” информация: повторяющиеся игры с угрозами. . . . . . . 57 2.13 Игры с несовершенной памятью, и другие несовершенства рациональности . . 59 2.14 Игроподобные ситуации без рациональности: псевдооптимизация и эволюци- онное равновесие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.15 Содержательное сопоставление различных концепций решений игр . . . . . . . 62 3 Приложение: Наиболее употребительные определения 64 Литература 65 2 Предисловие Данное пособие (которое дорабатывается) составляет курс лекций “Элементы те- ории игр и политологии” – обязательный курс 3-го года обучения экономического факультета Новосибирского государственного университета. Курс опирается на курсы Микроэкономика-1, Оптимизация, и Теория экономиче- ского равновесия. Поэтому здесь уже изученные студентами понятия предпочтений, оптимизации, кооперативная теория игр – затрагиваются минимально. Курс служит базисом для всех последующих курсов, использующих гипотезу рационального по- ведения и игровые понятия, включая “Микроэкономику-2”, теории отраслевых рын- ков и общественного сектора. Он обучает скорее методам и средствам анализа, чем эмпирическим фактам. Какие "практики"или типы поведения логически объяснимы гипотезой индивидуальной рациональности, а какие нет - вот главный вопрос во всех рассматриваемых ситуациях, и умение точно рассуждать об этом является главным вырабатываемым навыком. Студенты должны освоить формализацию и решение наи- более типичных игр, прежде всего экономических и политических. В соответствии с задачами, курс организован в виде 2 частей: первая часть - “Теория Игр” сфокусиро- вана на общих понятиях игр и методах решения, а вторая - “Политическая Теория” - на моделях политических объектов и процессов. Как основа подхода, здесь использованы известные международные учебники по играм и моделям политики, прежде всего: R.B.Myerson - Game Theory (Analysis of Conflict) (продвинутый уровень), P.C. Ordeshook- Political Theory Primer, (вводный уровень). Использованы нужные разделы из учебников микроэкономики (где необ- ходимый экономистам игровой материал дан более сжато) H.Varian - Microeconomic Analysis., D. Krebs - A Course in Microeconomic Theory, J. Tirole - Industrial Organiza- tion,. Дополнительно использована литература из приведенного списка литературы, и пособия изданные в НГУ: В.Бусыгин, С.Коковин, Е.Желободько, А.Цыплаков (1999) - Микроэкономический анализ несовершенных рынков (вводный уровень игр, основные концепции), продвинутое пособие В.И.Данилова Лекции по теории игр, изданное в РЭШ. К этим материалам рекомендуется обращаться. Характер изложения практически приспособлен к типу и возможностям восприя- тия студентов НГУ, к ограничениям учебного плана. Во многих случаях предпочтение отдано не общности формального изложения понятий, а их освоению на примерах, по возможности – содержательных. Важной частью пособия (курса) является задачник, поскольку упор сделан на практическое освоение ключевых идей теории игр и поли- тической теории. Курс занимает 18 лекций (36 академических часов), без семинаров, с несколькими контрольными и заключительным дифференцированным зачетом. Раздел 1 пособия является базовым; он вводит необходимые понятия теории игр. Раздел 2 применяет их к моделям политики. Задачи собраны в задачнике - см. www.math.nsc.ru/ mathecon. Автор приносит благодарность В.М.Полтеровичу за советы по выбору политиче- ского материала, А.Савватееву и А.Тонису за сотрудничество в методической разра- ботке преподавания теории игр и ценные замечания по тексту. 3 Введение: классификация игр Математическая “теория игр” есть теория принятия решений группой участников. В ней под понятие игры подходит любая ситуация с рациональными, то есть целепо- лагающими, оптимизирующими субъектами (“участниками”), а также некоторые си- туации с неполной рациональностью. 1 В частности, любая оптимизационная задача - это, по сути дела, просто игра с одним участником. Напротив, задачу поиска мно- гоцелевого оптимума (Парето-оптимума) игрой назвать еще нельзя. Недостает описа- ния индивидуальных прав или возможностей участников, и описания информационно- поведенческих особенностей ситуации. Структура любой игры описывается тремя блоками: 1)физические возможно- сти, то есть допустимые множества ходов или стратегий участников; 2)цели участни- ков; 3)тип поведения и информированности участников, включая характер взаимо- действия друг с другом, рациональность мышления, способ рассуждений и др. Для структур (1) и (2) выработаны достаточно удобные описывающие модели – допусти- мые множества или графы, целевые функции. Но трудно указать единый для всех игр формальный способ описать тип поведения; часто это описание формализуют “концепцией решения” игры. Задача анализа игры — по заданным возможностям, целям и информации иг- роков уметь прогнозировать “решение” игры, то есть множество возможных ходов и их результатов (исходов): 1. Возможности ходов участников (допустимые множества) 2. Цели участников (предпочтения, целевые функции) 3. Информация и тип поведения (информационные множества, “ожидания”, рациональность, контекст игры, ...) ⇒ Ход игры (решение) По этим и другим признакам огромное разнообразие игр можно классифициро- вать. Например, по характеру доступных стратегий игры разделяют: — на конеч- ные или бесконечные (в частности, бесконечные во времени), — на дискретные или непрерывные, — на “статические” (с одновременными ходами), или динамические. По соотношению целей участников игры разделяют на антагонистические или неантаго- нистические (с непротивоположными интересами). По типу поведения — на коопе- ративные (где участники ищут компромисс в переговорах), и некооперативные (где договоры неосуществимы или невыполнимы). По информационной структуре игры можно делить на игры с совершенной или несовершенной рациональностью, с общим или не-общим знанием данных, и др.. А также, учитывая внешний контекст игры, на 1)уникальные, 2)популяционные (где игроки пользуются знанием о происходивших ранее аналогичных играх), 3)повторяющиеся в том же коллективе (где игроки поль- зуются угрозами). Для анализа условия игры обычно формализуют в одной из трех форм: в характе- ристической (описываются значения выигрышей каждой коалиции, только для коопе- ративных игр), в развернутой (описываются последовательности возможных ходов), 1 Напротив, в психологии и в быту под игрой понимают лишь деятельность, непосредственные цели которой условны, не связанны с жизненными интересами участников. 4 или в стратегической (описываются цельные стратегии). Последняя подразделяется на нормальную стратегическую форму и мультиперсонную. В каком-то смысле, раз- ные формы одной игры – это разные модели одного явления. Сначала мы рассмотрим более простую – нормальную форму, потом развернутую, затем сопоставим их. 1 Глава. Игры в нормальной форме (“статические” или “одновременные”) “Нормальную” форму игры часто соотносят со случаем “статической” или одновре- менной игры (однократные одновременные ходы участников), а развернутую форму — с “динамическими” играми (последовательные ходы), хотя мы увидим, что возмож- ны и другие трактовки. Нормальная форма задает исходную физическую и целевую структура игры как объект G := hI, X, u(.)i = hI, {X i } i∈I , {u i (.)} i∈I i , где I := {1, ..., m} — множество участников i, X := (X i ) i∈I := Q i X i = (X 1 ×X 2 ×...×X m ) — набор (профиль) допустимых множеств стратегий (x i ) i∈I участников, u := (u i ) I = (u i ) i∈I — набор (профиль) целевых функций участников (заметим: каж- дая целевая функция u i : X i 7→ IR зависит, вообще говоря, от всех (x j ) j∈I ). 2 Состоянием игры в нормальной форме будем называть или профиль x = (x i ) i∈I выбранных стратегий, или, более полно, пару (x, β) выбранных стратегий и ожиданий всех участников. Ожидание β i ∈ X каждого участника о ходах всех партнеров может совпадать с настоящими, намеченными к исполнению, стратегиями, или не совпадать. Проиллюстрируем используемые далее принципы обозначений и простейшее понятие решения на примере. Пример 1.1 “Игра координации”, (известная в одном из вариантов как “семейный спор” = “Battle of Sexes”: Luce and Raiffa, 1953). Далее, как и здесь, мы будем большими буквами обозначать участников (или мно- жества), малыми латинскими буквами – переменные стратегий. Греческие буквы ис- пользуются для ожиданий или вероятностей, в данном случае β V – это ожидание Виктора о ходе Анны. Играют Анна (персонаж, который далее во всех обсуждаемых динамических иг- рах ходит первым и обозначается А) и Виктор (персонаж, который в других играх, не как здесь, ходит позже Анны и, соответственно, обозначается буквой V стоящей позже в латинском алфавите). Здесь Анна и Виктор ходят одновременно, после хода "Природы", сформировавшей у них какие-то "ожидания"(beliefs) о поведении парт- нера. Они не имеют возможности переговариваться (возможно, это период симпатии до знакомства, или это супруги, уставшие спорить :-) ). Каждый выбирает, пойти 2 Возможно также более общее представление игр (оно соответствует, в частности, Вальрасовско- му равновесию игр обмена): не только выигрыши, но и текущее допустимое множество стратегий каждого участника может зависеть от текущих действий других участников. 5 ли вечером на футбол или в кино. Оба предпочли бы оказаться где-нибудь вме- сте, что отражено в таблице выигрышей на Рис. 1.1. А именно, совместное попа- дание в кино ( x = (x A , x V ) := (c A , c V ) ) дало бы вектор полезностей (выигрышей) (u A (c A , c V ), u V (c A , c V )) := (3, 2), а совместное попадание на футбол дает выигрыши (u A (f A , f V ), u V (f A , f V )) := (1, 4). U q Nature Victor Anna * j j N 3, 2 0, 0 0, 0 1, 4 cinema (c A ) cinema (c V ) football (f V ) footb. (f A ) Ann’s belief (β A ) Vic.’s belief (β V ) Payoff matrix Рис. 1: “Игра слепой координации” (или “Семейный спор”, “Battle of Sexes”). (При- ношу извинения, английские надписи на рисунках вынуждены программным обеспе- чением.) В каждой клетке, соответствующей одному из 4-х возможных исходов, помещен сначала субъективный выигрыш строчного игрока – Анны (измеренный в некото- рых единицах полезности), затем - выигрыш Виктора. (Таким образом, две матрицы выигрышей совмещены в одной диаграмме, каждая клетка отражает один из исхо- дов. Это типичный способ представления игр с конечным множеством стратегий — “матричных” или “биматричных”, по другой терминологии, не поддерживаемой на- ми.) Стрелки отражают последовательность ходов, в данном случае - то, что игроки вынуждены принять решения одновременно, не зная выбора другого, а только имея какие-то “ожидания” (beliefs) об этом выборе, предопределенные природой (случаем). Что может произойти? Очевидно, если оба ожидают от партнера выбор “футбол”, то есть β A = f ootb V , β V = f ootb A , тогда рациональный выбор каждого — присо- единиться к выбору партнера, и исходом будет счастливая (более счастливая для Виктора) встреча на футболе: x A = f ootb A , x V = f ootb V . Аналогично, совпадающие ожидания о кино привели бы к счастливой, особенно для Анны, встрече в кино, а несовпадающие гипотезы – к развлечениям порознь. 3 Итак, мы описали простейший вариант множества решений игры – “решения с заданными извне (несогласованными с реальностью) ожиданиями”. Далее будем рассматривать другие типы решений, в том числе, этой же игры. О понятиях решения. Вообще говоря, найти решение игры означает, предска- зать множество ее возможных состояний, соответствующих нашим (наблюдателя) гипотезам о принципах поведения и информации участников. Совокупность наших гипотез задает некоторое “согласование” стратегий и ожиданий. Обычно оно фор- 3 Заметим, что здесь независимое не-кооперативное принятие решений может приводить к не- Парето-эффективному исходу, что вообще типично. 6 мализуется в “концепции решения” или “равновесия”, то есть состояния, от которых участники не станут переходить к другим состояниям, если игра повторится. В приведенном примере для предсказания исхода мы использовали простейшую концепцию – решение с заданными заранее необоснованными ожиданиями ходов, из- вестными откуда-то предсказывающему наблюдателю. Ожидания не предполагались “согласованными”, или “обоснованными” истинными намерениями партнера. Перечис- лим более сложные решения игр, изучаемые в этом разделе. (Табл.1): Информация, на которую Тип возникающих решений ориентируется участник j ∈ I : (равновесий), т.е., поведения: - только на знание множеств (X i ) I ⇒ MM — “осторожное” (максимин), IDE, SIDE — “доминирующее”, - еще и на чужие цели (u i ) I\{j} ⇒ IND S , IND W , SoE — “сложное”, - на текущий чужой ход (x i ) I\{j} ⇒ NE — “Нэшевское” - на текущую вероятность ходов ⇒ NEm — “Нэшевское в смешанных стратегиях” - лидер знает цели, ведомые - теку- ⇒ StE — щий ход “Штакельберговское” - на соглашение с партнерами ⇒ C — ядро — “кооперативное” Таблица 1: Разные типы решений игр в нормальной форме, в зависимости от инфор- мации о партнерах (это не значит, что решение Нэша нельзя применять в ситуации знания чужих целей или в ситуации переговоров, таблица говорит только о типич- ности применения понятий). Всюду в таблице подразумевается знание собственных целей, и “общее знание” множества возможных стратегий всех участников. Обсудим последовательно каждую из концепций решения, начав с простых. 1.1 Максимин и доминирование Будем обозначать через x −i := ( |