теориия игр. Лекции по теории игр вводный уровень
 Скачать 1.71 Mb.
|
|
Лекции по теории игр - вводный уровень С. Г. Коковин 5 мая 2010 г. 2 Оглавление Предисловие 5 Введение: классификация игр 6 1 Предпочтения, кооперативные игры, общее равновесие 9 1.1 Предпочтения, их представление и свойства . . . . . . . . . . . . . . . . . . . 9 1.2 Многоцелевой оптимум: сильный и слабый оптимум Парето . . . . . . . . . . 12 1.3 Индивидуальные и коалиционные возможности: “переговорное множество”и ядро 13 1.3.1 Теоремы, характеризующие сильный и слабый Парето-оптимумы . . . 14 1.4 Вальрасовское равновесие и ядро в игре обмена . . . . . . . . . . . . . . . . . 15 1.5 Ядро в играх с трансферабельной полезностью и дележи . . . . . . . . . . . . 18 2 Статические или “одновременные” некооперативные игры 19 2.0.1 Обозначения и термины . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.0.2 Максимин и доминирование . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.0.3 Доминирующее и сильно-доминирующее равновесия 24 2.0.4 Итерационно-недоминируемые решения IN D W , IN D S 28 2.0.5 Игры в популяциях и равновесие Нэша . . . . . . . . . . . . . . . . . . 29 2.0.6 Кооперативные решения - Парето-оптимум и ядро . . . . . . . . . . . . 37 2.0.7 Нахождение и сопоставление разных решений . . . . . . . . . . . . . . 38 2.0.8 Дополнительные примеры решений в непрерывных играх и N E m 42 2.0.9 Эволюционная интерпретация NE и NE m , стабильность, “Равновесие дрожащей руки” (THNE) . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.0.10 О (не-)совпадении различных решений . . . . . . . . . . . . . . . . . . . 47 2.0.11 О существовании и компактности множеств решений . . . . . . . . . . 48 2.0.12 Что общего в разных концепциях решений? . . . . . . . . . . . . . . . . 50 3 Динамические или “последовательные” некооперативные игры 51 3.0.13 Формализация последовательных игр, соответствие развернутой и нор- мальной формы игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.0.14 Стратегии нормальные и пошаговые, мультиперсонная форма игры и SPNE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.0.15 SPNE и обратная индукция . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.0.16 Решение SPNE в непрерывной игре . . . . . . . . . . . . . . . . . . . . . 60 3.0.17 SPNE и SPINDW при равновыгодных исходах или несовершенстве ин- формации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.0.18 Неполная информация о типе партнеров: Байесовское равновесие . . . 63 3.0.19 Неопределенность и динамика: совершенное Байесовское (слабое се- квенциальное) равновесие . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.0.20 Эффект “сигналинг” в игре образования . . . . . . . . . . . . . . . . . . 70 3.0.21 Эффект “блеф” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3 4 Оглавление 3.0.22 Задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.0.23 Дальнейшие уточнения: P BE(ε), секвенциальное равновесие (SeqE), T HP E . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.0.24 Сопоставление решений SPE, SBE, SeqE, THPE, INDW . . . . . . . . . 74 4 Более сложные ситуации: не-общая информация, иррациональность, по- вторения игры 77 4.0.25 Отсутствие “общего знания”, игры с репутацией, блеф . . . . . . . . . . 77 4.0.26 Уточнение понятия рациональности; прямая индукция . . . . . . . . . 78 4.0.27 “Почти-совершенная” информация: повторяющиеся игры с угрозами. . 80 4.0.28 Игры с несовершенной памятью, и другие несовершенства рациональ- ности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.0.29 Игроподобные ситуации без рациональности: псевдооптимизация и эво- люционное равновесие . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.0.30 Содержательное сопоставление различных концепций решений игр . . 85 4.1 Приложение. Основные определения и сокращения . . . . . . . . . . . . . . . 87 Литература 90 Оглавление 5 Предисловие Данное пособие (которое дорабатывается ежегодно) составляет курс лекций “Вве- дение в теорию игр и экономического равновесия” – обязательный курс 2-го года обу- чения экономического факультета Новосибирского государственного университета. Курс опирается на курсы Матанализ, Микроэкономика-1, Оптимизация. Поэтому здесь используются уже изученные студентами понятия целевых функций, предпо- чтений, оптимизации. Курс служит базисом для всех последующих курсов, использу- ющих гипотезу рационального поведения и игровые понятия. В НГУ это “Микроэко- номика-2”, теории отраслевых рынков и общественного сектора (поэтому предпочте- ния и общее экономическое равновесие затронуты больше, чем в типичном учебнике игр). Курс обучает скорее методам и средствам анализа, чем эмпирическим фактам. Какие “практики” или типы реального поведения объяснимы и описываемы какой из гипотез рациональности поведения? Какие ситуации некооперативного поведения (каждый за себя) приводят к кооперативно- неулучшаемым исходам, а какие нет? – это сквозные темы во многих рассматриваемых сюжетах. Вот о них мы и стараем- ся достаточно точно рассуждать, вырабатывать у студентов навыки такого анализа. Кроме этого, студенты должны освоить формализацию и решение конкретных наи- более типичных игр, прежде всего экономических. В соответствии с задачами и учеб- ным планом НГУ, курс организован в виде 2 частей: 1)“Предпочтения, многоцелевой оптимум и кооперативные игры, теория экономического равновесия”; 2)“Некоопера- тивные игры”. Как основа, здесь использованы известные международные учебники по играм и микроэкономике. По предпочтениям и экономическому равновесию – книга Али- прантис, Браун, Бёркиншо: "Существование и оптимальность конкурентного рав- новесия". По играм опорная книга – M.Osborne “An Introduction to Game Theory” (промежуточный уровень), дополнительные: А.Цыплаков "Введение в теорию игр”, R.Gibbons “Game theory for applied economist” (вводный уровень), Gintis “Game the- ory: a lexicon for strategic interaction” (промежуточный уровень), В.И.Данилов "Лек- ции по теории игр” (продвинутый уровень), A.Fudenberg & J.Tirole "Game Theory” (продвинутый уровень). И по экономическому равновесию и по играм использованы также нужные разделы из учебников микроэкономики (где необходимый экономи- стам игровой материал дан более сжато) H.Varian - Microeconomic Analysis., D. Krebs - A Course in Microeconomic Theory, J. Tirole - Industrial Organization,. Дополнитель- но можно рекомендовать также приведенный в конце список литературы, включая пособия изданные в НГУ или размещенные на сети "Эконом”. Характер изложения приспособлен к уровню и характеру восприятия студентов НГУ, к ограничениям учебного плана. Во многих случаях предпочтение отдано не общности формального изложения понятий, а их освоению на примерах, по возмож- ности – содержательных. Важной частью пособия (курса) является задачник (см. econom.nsu.ru/"Система Эконом”), поскольку упор сделан на практическое освоение ключевых идей теории игр и ее приложений. Курс занимает 15 лекций (30 акаде- мических часов), 15 семинаров, с несколькими контрольными и заключительным экзаменом. Автор приносит благодарность акад. В.М.Полтеровичу за советы по выбору мате- риала, А.Савватееву и А.Тонису за сотрудничество в методической разработке пре- подавания теории игр, задачи, и ценные замечания по тексту. 6 Оглавление Введение: классификация игр Математическая “теория игр” есть теория принятия решений или взаимодействий нескольких рациональных субъектов. Итак, она охватывает очень многое: под по- нятие игры подходит любая ситуация с рациональными, то есть целеполагающими, или оптимизирующими субъектами – “игроками”, или “участниками” (и даже неко- торые ситуации с неполной рациональностью). 1 В частности, любая оптимизацион- ная задача – это, по сути дела, просто игра с одним участником. Напротив, зада- чу поиска многоцелевого оптимума (Парето-оптимума) игрой назвать еще нельзя. Недостает описания индивидуальных прав или возможностей участников, и описа- ния информационно-поведенческих особенностей ситуации. Структура любой игры описывается тремя блоками данных: 1)физические воз- можности, то есть допустимые множества ходов или стратегий участников; 2)цели участников; 3)тип поведения и информированности участников, включая характер взаимодействия друг с другом, рациональность мышления, способ рассуждений и др. Для данных типа (1) и (2) выработаны достаточно удобные описывающие модели – допустимые множества или графы игры, целевые функции. Но трудно придумать единый для всех игр формальный способ описать тип поведения; часто это описание формализуют “концепцией решения” игры. Задача анализа игры — по заданным возможностям, целям и информации игроков уметь прогнозировать “решение” игры, то есть множество возможных ходов и их результатов (множество исходов): 1. Возможности ходов участников (допустимые множества) 2. Цели участников (предпочтения, целевые функции) 3. Информация и тип поведения (информационные множества, “ожидания”, тип рассуждений, контекст игры, ...) ⇒ Ход игры (решение) По этим и другим признакам огромное разнообразие игр можно классифициро- вать. Например, по характеру доступных стратегий игры разделяют: — на конеч- ные или бесконечные (в частности, бесконечные во времени), — на дискретные или непрерывные, — на “статические” (с одновременными ходами), или динамические. По соотношению целей участников игры разделяют на антагонистические или неанта- гонистические (с непротивоположными интересами). По типу поведения — на коопе- ративные (где участники ищут компромисс в переговорах), и некооперативные (где договоры неосуществимы или невыполнимы). По информационной структуре игры можно делить на игры с совершенной или несовершенной рациональностью, с общим или не-общим знанием данных, и др.. А также, учитывая внешний контекст игры, на 1)уникальные, 2)популяционные (где игроки пользуются знанием о происходивших ранее аналогичных играх подобных игроков, но с данными конкретными партнерами больше не встретятся), 3)повторяющиеся в том же коллективе (где игроки накапли- вают информацию о партнерах и могут пользоваться угрозами). 1 Напротив, в психологии и в быту под игрой понимают лишь деятельность, непосредственные цели которой условны, не связанны с жизненными интересами участников. Оглавление 7 Для анализа условия игры обычно формализуют в одной из трех форм: в харак- теристической (описываются значения выигрышей каждой коалиции, только для кооперативных игр), в развернутой (описываются последовательности возможных ходов), или в стратегической (описываются цельные стратегии). Последняя под- разделяется на нормальную стратегическую форму и мультиперсонную. В каком-то смысле, разные формы одной игры – это разные модели одного явления. Сначала мы рассмотрим многоцелевой оптимум и кооперативные игры и рынки. Затем, во второй части курса, сначала наиболее простую – нормальную форму некооперативной игры, потом развернутую. И сопоставим все эти формы и понятия. 8 Оглавление Глава 1 Предпочтения, кооперативные игры, общее равновесие (Материал этой части дан в лекционном пособии А.В.Сидорова, см. "Система Эко- ном". Здесь же дается только перечень тем и некоторые примеры.) 1.1 Предпочтения, их представление и свойства (см. лекции Сидорова, Тема 1, учебник Алипрантис стр. 12-35) В осеннем семестре изучалась оптимизация. Цели задавались целевыми функци- ями. Теперь рассмотрим и другие способы. Предпочтения. Пусть есть допустимое множество X альтернатив и некто, де- лающий выбор на этом допустимом множестве. Простой способ описывать чей-то выбор или предпочтение - это бинарным отношением, например, Apple  Ivan Banan означает, что агент i = Ivan строго предпочитает Apple по сравнению с Banan, а Apple º Ivan Banan означает аналогичное нестрогое предпочтение Ивана. То же са- мое можно выразить символом (Apple, Banan) ∈ R Ivan , где R Ivan обозначает мно- жество тех упорядоченных пар, про которые справедливо, что первая компонента не хуже второй для Ивана (в лекциях Сидорова чаще такая символика с R i ). Мы берем за основу нестрогое отношение предпочтения º i , и по нему определим строгое отношение предпочтения и эквивалентность: x  i y ⇔ [x º i y, y 6º i x], x ∼ i y ⇔ [x º i y, y º i x]. Высказанное отношение называется полным, если про любую пару альтер- натив x, y указано определенно одно из трех отношений: x  i y или x ∼ i y или x ≺ i y (нет неопределенности) . Оно называется транзитивным, если для любых альтернатив выполнено (x º y º z ⇒ x º z) и (x º y  z ⇒ x  z). Та- кие, полные и транзитивные, отношения выбора мы будем называть рациональными отношениями предпочтениями (по Мас-Коллелу), (Алипрантис называет их линей- ными, или просто отношениями предпочтения). Только ими и будем заниматься. Другой путь выразить предпочтения: записать точечно-множественное отобра- жение, то есть описать для каждого элемента x множество L + (x) вариантов не хуже чем x и множество строго лучших вариантов L ++ (x): L + i (¯ x) = {x ∈ X| x º ¯ x} = {x ∈ X| (x, ¯ x) ∈ R}, 9 10 Глава 1. Предпочтения, кооперативные игры, общее равновесие L ++ i (¯ x) = {x ∈ X| x  ¯ x}}. Также можно рассматривать множество “не лучших” чем x элементов L − (x) := {z | x º z} (его называют “нижнее Лебегово множество” если предпочтение описа- но некоторой функцией, а L + (x) – верхнее Лебегово множество точки x при этом предпочтении). Полнота предпочтений в векторных пространствах R n Пример 2. Я (i) могу сообщить отношение выбора, что предпочитаю набор то- варов x ∈ R 2 товару наборов y ∈ R 2 если вектор x по всем компонентам больше, то есть x À y ⇒ x  i y, x ≥ y ⇒ x º i y. (?)Рационально ли оно? Высказанное мной предпочтение, очевидно, транзитивно, но неполно: я ничего не сообщил о том, каковы мои предпочтения среди несравнимых покомпонентно векто- ров (где одни компоненты больше, другие меньше). Пример 3. Пусть, я добавлю к тому же, что несравнимые вектора для меня эк- вивалентны. Высказанное мной теперь предпочтение станет полным, но, легко про- верить, нетранзитивным. Пример 4. Или, я могу заявить, что вектор x ∈ R 2 лучше для меня, чем вектор y ∈ R 2 , если его первая компонента больше: x  y если x 1 > y 1 . (?) Высказал ли я полное и транзитивное предпочтение? Транзитивность очевидна, но полнота будет достигнута только если я до-определю, эквивалентны ли для меня все вектора с равной первой компонентой. Предположим, я сообщил, что при равных первых компонентах я сравниваю вторые, и у которого компонента больше – тот вектор для меня строго лучше: x  y если x 1 > y 1 ∨ (x 1 = y 1 ∧ x 2 > y 2 ). А эквивалентен вектор только сам себе. Так упорядочивают слова в словарях, поэтому такое предпочтение называют лексикографическим (Lexgraph). Представление предпочтений целевыми функциями и обратно Третий путь формулировки отношения предпочтения, Вами уже изученный в других курсах – отражать его некоторой целевой функцией. Между этими способами есть связь. Говорят, что функция u i (·) соответствует отношению предпочтения { i } на множестве альтернатив X или “является его индикатором”, когда [u i (x) ≥ u i (y) ⇔ x º i y , u i (x) > u i (y) ⇔ x  i y ∀x, y ∈ X]. Очевидно, заданное функцией предпочтение окажется полным и транзитивным: функция везде определена, и соответствующие разным наборам товаров ее значения транзитивны на прямой. По заданной функции u : R n 7→ R n можно для любого x ∈ R n найти соответствующую линию безразличия L 0 (x) := {y ∈ R n |y ∼ x} и соответствующее множество не-менее желательных чем x векторов L + (x) := {y ∈ R n |y º x}. Повторим, функцию u(.) называют индикатором предпочтения  если [u(x) ≥ u(y) ⇔ x º y ∀x, y ∈ X]. Пример 6. (?)Постройте линии уровня (карту предпочтения) для функции по- лезности Кобба-Дугласа, заданной в виде u(x, y) = √ y ∗ x или в виде u(x, y) = y ∗ x или в виде u(x, y) = ln(y) + ln(x). Одинаковы ли полученные карты предпочтений, в чем разница? (только в нумерации линий уровня, т.е., масштабе) Оправдана и обратная задача: как по высказанной карте предпочтений (напри- мер, линий уровня или предпочитаемых множеств) построить соответствующую ей функцию - индикатор? 1.1. Предпочтения, их представление и свойства 11 Какую действительную функцию предложить, так, чтобы она “была индикато- ром” отношения предпочтения вышеупомянутого Ивана? Например, можно взять оценки полезности u i (Apple) = 20, u i (Banan) = 14, но можно и многие другие функ- ции, сохраняющие тот же порядок; выбор функции неоднозначен. Предпочтение опи- сывает лишь порядок: что предпочитается чему. Напротив, функция описывает и масштаб: насколько альтернатива А, или во сколько раз предпочтитается альтерна- тиве Б. Обычно индивид при опросе затруднится ответить на такой вопрос, и вы- скажет лишь предпочтение. По нему мы можем подобрать много непротиворечащих этому предпочтению целевых функций, но в выборе масштаба допустим произвол исследователя. Для многих предпочтений подбор индикатора легок, например, для гиперболи- ческих линий уровня x 2 = a/x 1 Вы легко подберете индикатор - функцию Кобба- Дугласа. |