теориия игр. Лекции по теории игр вводный уровень
 Скачать 1.71 Mb.
|
|
k=1 ∈ Ω i := {σ i ∈ IR n i + | P n i k=1 σ k i = 1} с которыми данный игрок применяет соответствующие исходные “чистые” стратегии x k i ∈ X i . Опре- делим смешанное расширение игры G m := hI, (Ω i ) I , (U i ) I i, как игру, где допустимые множества есть наборы вероятностей Ω 1 , ..., Ω m , а целевая функция любого игрока есть матожидание выигрыша: U i (σ) := X (x 1 ,x 2 ,...,x m )∈X σ 1 (x 1 ) · σ 2 (x 2 ) · ... · σ m (x m ) · u i (x 1 , x 2 , ..., x m ) (2.5) Нэшевское равновесие в смешанных стратегиях ¯ σ ∈ NE m исходной игры G есть Нэшевское равновесие в ее смешанном расширении G m , то есть набор (¯ σ i ) I , таких, что ни один игрок не может меняя смешанную стратегию улучшить матожида- ние своего выигрыша, при неизменных (смешанных) стратегиях партнеров. (Аналогично можно определить понятие N E m для игры с бесконечным множеством стратегий, только смешанные стратегии σ i оказываются не векторами, а вероятностными мерами, матожидания – из сумм превратятся в интегралы. Переход к смешанному расши- рению (то есть к вероятностному варианту) игры овыпукляет ее множество стратегий и множество достижимых уровней полезности. Это благоприятно сказывается и на существо- вании Нэшевских равновесий (см. теорему Нэша ниже), и на возможности их охарактери- зовать.) 12 Обычно имеют в виду популяционную или повторяющуюся игру. Обозначение m – от англ. “mixed”. 34 Глава 2. Статические или “одновременные” некооперативные игры Итак, пользуясь введенным определением решения, легко для примера "Монет- ки” составить неравенства, которым должны бы удовлетворять вероятности (α L , α R ), применяемые Анной к левому и правому ходу, и аналогичные неравенства для сме- шанных стратегий Виктора (ν L , ν R ). А именно, тот факт, что Анна не хочет ни увели- чивать ни уменьшать частоту применения Левой стртегии за счет правой, означает, что обе приносят одинаковую ожидаемую полезность при заданных вероятностях (смешанных стратегиях (ν L , ν R )) Виктора: U A ((α L = 1, α R = 0), (ν L , ν R )) = −1 ∗ ν L + 1 ∗ ν R = = U A ((α L = 0, α R = 1), (ν L , ν R )) = −1 ∗ ν R + 1 ∗ ν L . Это уравнение укажет, что равенство полезностей возможно лишь при равных веро- ятностях ходов партнера ν L = ν R = 0.5. Аналогичное уравнение относительно равных полезностей Виктора даст искомые равновесные стратегии Анны α L = α R = 0.5. (Упражнение: Найдите аналогично NE m в аналогичной игре герцога де Монмора (см. Мулен 1985): Отец, герцог, желая развить сообразительность сына, каждое утро предлагал ему сыграть в "Монетки”, но не брал с него ничего при не-угадывании (в какой руке у отца монетка), давал золотой за угадывание в левой руке, и два золотых - за угадывание в правой.) Возвращаясь к теории, легко заметить, что к расширенной в вероятностное про- странство игре можно применять все те же приемы, что и к исходной, а обычные равновесия Нэша остаются равновесиями и в вероятностном расширении игры (ведь чистые стратегии – это просто орты в пространстве вероятностных стратегий). Теперь, применяя уже для смешанного расширения игры ранее использованное понятие сильного доминирования, можно сузить множество недоминируемых страте- гий еще одним методом, альтернативным к слабому доминированию и расширяющим множество сильно доминируемых: Определение 2.0.5.5 Стратегию x i назовем смешанно-доминируемой, если суще- ствует смешанная стратегия σ i ∈ Ω i сильно доминирующая над x i . Пример: три стратегии дают игроку выигрыши (4,1), (1,4), и (2,2) соответственно. Ясно, что ни одна из трех не доминирует другую ни сильно ни слабо, но комбинация первых двух с весами 0.5 смешанно-доминирует третью. Полезно - Утверждение. Некоторая чистая стратегия может быть смешанно- недо- минируемой тогда и только тогда, когда является рациональным откликом на некоторую смешанную (возможно, чистую) стратегию партнеров. Этот факт следует из овыпукления игры при ее смешанном расширении (док. см. Myerson 1999, Данилов 2002). Из него можно вывести вложение NE ⊆ INDS (покажите). Наиболее интересно он отражается на антагонистических играх. Для антагонистической игры двух лиц ценой игры u sad называют полезность пер- вого игрока в седловой точке Sad, то есть u sad := sup x 1 ∈X 1 inf x 2 ∈X 2 u 1 (x 1 , x 2 ) = inf x 2 ∈X 2 sup x 1 ∈X 1 u 1 (x 1 , x 2 ) . Если седловой точки, то есть пары стратегий удовлетворяющей этому равенству нет, то игру считают неразрешимой по принципу седла, то есть “не имеющей цены”. 35 Легко заметить, что антагонистическая игра двух лиц (где u 1 (x 1 , x 2 ) = −u 2 (x 1 , x 2 )) имеет цену тогда и только тогда, когда функция u 1 (., .) имеет седловую точку на X 1 × X 2 . Смешанное же расширение игры всегда имеет цену (теорема фон Неймана, см. ниже). Множественность равновесий Нэша, “фокальные точки” и борьба за ли- дерство: равновесие Штакельберга (последовательные ходы) Рассмотрим проблему, возникающую, когда равновесие Нэша не одно. Какое из них считать более вероятным исходом? Это популярная тема "сужения” или "очищения”, рафинирования (refinement) множества равновесий от малоправдоподобных. Мы уже касались одного способа рафинирования. Это пересечение NE с другими решениями: с DE или с максимином, или с итерационно-недоминируемым множеством. Вообще говоря, исход, удовлетворяющий не одной концепции решения, а двум и более - вы- зывает больше доверия, кажется правдоподобнее. Впрочем, в некоторых играх нет никаких оснований предпочитать, в качестве предсказания, одно равновесие другому. Наиболее хорошо это видно в игре коор- динации с односторонними преимуществами типа "Перекресток"(Chicken game). В таких случаях часто можно считать, что выбор из многих возможных равновесий произойдет по принципу "фокальной точки”, то есть не зависит от включенных в рассмотрение данных. Поясним это важное в играх с множеством равновесий понятие. Положив шарик в строго вогнутую чашу, мы единственным образом предскажем равновесие - это “обусловленное” равновесие, а не "фокальное”. Напротив, положив шарик на гори- зонтальную поверхность, мы можем предсказать, что куда его положишь, там он и останется в равновесии. Это и называют эффект "фокальной точки”: зависимость положения равновесия от начальной точки, или даже превращение любой начальной позиции в равновесие. Как уже говорилось, в примере игры координации “семейный спор”, если оба почему-то ожидают от партнера выбор “кино”, (например, известна уступчивость Виктора, или было сделано какое-то намекающее сообщение), то это и случится. Этот довольно распространенный эффект “самоподдерживающихся ожиданий” как раз и является “эффектом фокальной точки”. Так, культурные нормы и традиции часто порождают фокальные равновесные точки в определенных играх с многими потенциальными равновесиями (или поро- ждаются как фокальные точки?). Скажем, левостороннее движение транспорта в Англии и правостороннее на континенте - типичные фокальные точки. Более интересен пример фокальной точки нелегитимного политика. Тут тоже дей- ствет правило самоподдерживающихся ожиданий: “если люди верят, что у тебя есть власть, то у тебя она есть (люди слушаются)”. От дополнительных факторов игра может перескочить в другое равновесие, тоже устойчивое. Аналогично, в игре координации "Перекресток”, если Анна верит, что Боб нико- гда не тормозит, то сама будет тормозить. В результате сложится равновесие более выгодное для Боба. Аналогично можно рассуждать при противоположных ожида- ниях партнеров - Анна в выигрыше. И оба равновесия устойчивы (в смысле строгой невыгодности индивидуальных отклонений). 36 Глава 2. Статические или “одновременные” некооперативные игры Из этих рассуждений следует, что в игре координации с многими разно-выгодными равновесиями выгодно бы сходить первым, и захватить лучшую позицию (в "Пе- рекрестке” – позицию “не торможу”). В некоторых ситуациях такая возможность нарушить одновременность и симметрию есть, и приводит к следующей концепции решения (строго говоря, относящейся уже не к этому разделу, а к последовательным играм). В равновесии Штакельберга (Stackelberg), в отличие от рассмотренных концепций решения “симметричных” относительно игроков, ожидания разных игроков форми- руются по разным принципам. Первый игрок (лидер) ориентируется на индивидуаль- но - оптимальные ответы партнеров зная их предпочтения, а остальные (ведомые) играют, как в NE, близоруко реагируя на его ход и на ходы друг друга. Скажем, на рынке алмазов фирма Де Бирс, контролирующая более 70% продаж, при выбо- ре цен просчитывает отклики на это мелких продавцов, а они играют примитивно подстраиваясь под лидера. Ведь каждый из “мелких” не рассчитывает существенно повлиять на рынок в целом! Эта несимметричная концепция решений годится так- же для случая, когда лидер просто ходит первым, независимо от силы его влияния (последовательная игра). Равновесие Штакельберга с лидером No 1 есть такой профиль (набор) стратегий всех, что первый игрок (лидер) с учетом цедей партнеров адекватно прогнозирует равновесия Нэша, складывающиеся после его хода, и оптимизирует свою стратегию соответственно, а остальные поступают согласно его прогнозу. Более формально: Определение 2.0.5.6 Считая 1-го игрока лидером, обозначим решение Нэша среди последователей при фиксированной стратегии ¯ x 1 лидера – через NE −1 (¯ x 1 ). Равновесие Штакельберга с лидером No 1 (StEP 1 ) есть такой набор ¯ x что ¯ x −1 ∈ NE −1 (¯ x 1 ), (2.6) 6 ∃˜ x 1 ∈ X 1 : u 1 (˜ x 1 , ˜ x −1 ) > u 1 (¯ x 1 , ¯ x −1 ) ∀(˜ x −1 ∈ NE −1 (˜ x), ¯ x −1 ∈ NE −1 (¯ x)). (2.7) В частности, осторожное (пессимистическое) равновесие Штакельберга 13 с ли- дером N 1 есть такой набор ¯ x ∈ StEP 1 , что ¯ x 1 ∈ arg max x 1 ∈X 1 min x −1 ∈N E −1 (x 1 ) u 1 (x 1 , x −1 ), ¯ x −1 ∈ arg min x −1 ∈N E −1 (¯ x 1 ) u 1 (¯ x 1 , x −1 ). Оптимистическое равновесие Штакельберга с лидером N 1 ¯ x ∈ StEO 1 определяет- ся так же, но с заменой min на max. Повторим, равновесие Штакельберга может возникать, например, когда один из игроков (лидер) делает свой выбор раньше других (“ведомых”) и знает их цели. Или когда он один, а однотипных “ведомых” достаточно много, чтобы каждый не пы- тался просчитывать общие последствия своего хода. Концепция StEO 1 предполага- ет доброжелательность партнеров к лидеру при выборе из эквивалентных для себя 13 Наши определения StEO i , StEP i не традиционны. Обычное же StE есть, забегая вперед, просто SPNE в двух-стадийной игре. 37 вариантов (из X ∗ ), а StEP 1 — недоброжелательность; если же выбор “ведомых” од- нозначен, то разницы между StEO и StEP нет. Если не различать оптимистические и пессимистические решения, то можно определить StE = {StEO, StEP} Повторим рассуждения о “борьбе за лидерство”. Смысл борьбы за лидерство, скажем, в игре “Семейный спор” (“Battle of Sexes” - Рис. 2.0.1) таков. Рассмотри- те возможность одному из игроков, например, Виктору, сообщить другому (Анне) свое решение: футбол. Эта возможность ставит его в положение Штакельберговско- го лидера, и позволяет форсировать более выгодное для себя из двух Нэшевских равновесий. Аналогично и для второго игрока. (А есть игры, где выгодно, наоборот, уступить первый ход - “борьбе за не-лидерство”.) То есть, понятие “борьбы” пред- полагает, что рассматриваемая игра вложена в более широкую, где можно выбрать, совершать ли первый ход, попадая в игру с решением Штакельберга. 2.0.6 Кооперативные решения - Парето-оптимум и ядро В заключение обзора наиболее типичных решений статических игр, напомним также основные понятия кооперативных решений, то есть возможных исходов переговоров участников. В данном случае мы планируем применять их для той же некооператив- ной игры, в которой рассматривались Нэш и другие решения. Смысл этого таков: а что если бы участники этой игры вступили в переговоры, к какому соглашению это могло бы вести? Определение 2.0.6.1 Назовем (сильным) множеством Парето (Парето-оптиму- мом, или “сильной Парето-границей”) множество неулучшаемых по Парето точек (исходов), то есть множество исходов неблокируемых-слабо большой коалицией I: P := {ˆ x| 6 ∃x ∈ X : u(x) > u(ˆ x)}, Слабая Парето-граница есть множество исходов неблокируемых-сильно большой коалицией I: P W := {ˆ x| 6 ∃x ∈ X : u(x) À u(ˆ x)}. Итак, Парето-оптимум — это такое состояние, в котором никто из участников не может увеличить своего выигрыша не уменьшив выигрыша кого-то другого, а слабый Парето-оптимум — это состояние, неулучшаемое для всех сразу (т.е., по сильному доминированию большой коалиции). Учитывая также и возможности других коалиций, получим один из вариантов определения ядра: Определение 2.0.6.2 Ядром C = C W (обычным, слабым ядром) называется мно- жество состояний неблокируемых никакой коалицией T ⊂ I, при обычном (силь- ном) определении блокирования: T блокирует вариант x ∈ X если существует альтернатива ˜ x i ∈ X i (i ∈ T ) такая, что все участники из T выигрывают по сравнению с x, т.е. 14 u T (˜ x T , x −T ) À u T (x T , x −T ) — при любых действиях x −T не входящих в коалицию T игроков. 14 Для пар векторов знак > здесь и далее означает ≥6=, а знак À — покомпонентно больше. В сущности, здесь вектор выигрышей коалиции T от альтернативы ˜ x i сильно доминирует (À) над вектором выигрышей от альтернативы x i 38 Глава 2. Статические или “одновременные” некооперативные игры Сильным ядром C S можно назвать множество состояний, неблокируемых ника- кой коалицией при слабом блокировании (что означает u T (˜ x T , x −T ) > u T (x) вместо u T (˜ x T , x −T ) À u T (x) в определении блокирования). Но такое понятие в теории не употребительно. Употребительное (слабое) ядро – это множество вариантов, вне ко- торого соглашений заведомо быть не может, а сильное - менее очевидная концепция. Еще нужно добавить, что ядро в терминах исходных стратегий, а не выигрышей тоже мало употребительно, поскольку во многих играх неочевидно, как описать возможно- сти коалиций, особенно малых. Различные варианты определений ядра, связанного с игрой в нормальной форме: α-ядро, β-ядро, γ-ядро – см. в книгах Мулен, 1985, 1991. Чтобы применить понятие ядра к игре заданной в нормальной форме, нужно договориться, что считать “точкой несогласия”, или иначе, “точкой угрозы” в пере- говорах. Есть несколько естественных вариантов. Иногда, участники считают, что в случае неуспеха их переговоров игра попадет в равновесие Нэша. Если оно един- ственно, то так можно искать соответствующее ядро, иначе нужны дополнительные соображения. Альтернативно, и довольно естественно для случая “угроз”, точкой несогласия для каждого игрока считать уровень его полезности, гарантированной при осторожном поведении. Тогда ядро называют α-ядром, и для игры двух лиц это понятие имеет очевидный смысл. Аналогично, можно расширить это понятие и для произвольного числа игроков, найдя гарантированные выигрыши любой коалиции. Но здесь могут быть тонкости, в которые мы вникать не будем, ограничившись простым случаем 2-х лиц, и не об- суждая других ядер, кроме α-ядра. Упражнение. В рамках обсуждения кооперативных решений, можно сравнить для игры 2-х лиц дележ Нэша и дележ Калаи-Смородинского (известные из других кур- сов) с α-ядром. 2.0.7 Нахождение и сопоставление разных решений Сопоставим все введенные понятия решений на примере единой (би-)матричной иг- ры. Пример 2.0.4 Студент и экзаменатор (Поиск решений матричной игры) Рассмотрим гипотетическую популяцию ленивых студентов и более-менее ста- рательных преподавателей. За точку отсчета возьмем случай, когда студент учит, а преподаватель внимательно смотрит на экзамене за наличием шпаргалок: студент имеет 5, и удовлетворение преподователя оценим в 5 (см. Табл. 2.5). Если при внима- тельном экзамене студент не учит, то имеет оценку 2, но +1 от приятно проведенного в семестре времени, в целом 3, а удовлетворение преподователя 2. Если при невнима- тельном экзамене, но с дополнительными вопросами, студент учит, то имеет оценку 5, но -1 от утомления на экзамене, в целом 4, а удовлетворение преподователя тоже 5, но -1 от утомления, в целом 4. Если же в этом случае студент не учит, то имеет 3 (все же он что-то рассказал) +1 от отдыха в семестре, всего 4. Осталось предполо- жить малое моральное удовлетворение =3 преподавателя от плохого экзамена, еще немного гипотез, и получим игру Табл. 2.9. В подобных (“матричных”) играх с конечными множествами стратегий двух игро- ков легко проверить наличие доминирующих стратегий: достаточно сравнить вектор 39 Студент Стратегии Гарантир. Расчетный и Учить Шпорить выигрыш выигрыш выигрыши (У) (Ш) Препо- Смотреть INDW 5 3 строго (С) 5 SNE 2 2 5 * дава- мягко, но 4 4 с Вопросами (В) 4 3 NE 3 * 4 или 3 тель Мягко, без 5 6 вопросов (М) 3 3 NE 3 * 3 Таблица 2.9: Игра “Экзамен”. выигрышей (5,4,5) при стратегии “Учить” с вектором (3,4,6)- “Шпорить”, чтобы заме- тить, что они несравнимы, следовательно доминирующих стратегий у студента нет, тогда и доминирующего равновесия нет: IDE = ∅. Осторожное равновесие практически ищется так: игрок выбирающий строки в каждой строке находит свой гарантированный выигрыш (то есть минимум в стро- ке), а затем в качестве решения принимает строку или строки с максимальным га- рантированным выигрышем. Аналогично поступает со столбцами игрок выбираю- щий столбцы. В данном случае две нижние клетки - среди осторожных решений MM = {(В,У),(М,У)}. Возможно, при однократной встрече некоторой группы с некоторым (впервые приглашенным в университет) преподавателем такое осторож- ное решение реалистично. Чаще же можно ожидать, что популяция студентов знает по прошлому опыту типичную стратегию преподавателя(-лей), тогда уместнее искать NE. Множество Нэшевских равновесий ищем перебором всех клеток; равнове- сия – это клетки из которых первому участнику не выгодно “уйти вверх или вниз”, а второму - “уйти в сторону” - то есть сменить стратегию при фиксированной чужой; здесь таких три: NE = {(С,У),(В,Ш),(М,Ш)}. Последнее наиболее благоприятно для студентов, но его реалистичность сомнительна, если преподаватели склонны отбра- сывать слабо доминируемые стратегии. Итерационно недоминируемое (слабо) множество IN DW ищем последова- тельным исключением из игры доминируемых строк и столбцов. На первом шаге рассуждений стратегия В=(4,3)>М=(3,3) слабо доминирует нд М, а у студента нет доминирования (иначе бы мы одновременно отбросили и его доминируемые стра- тегии). Таким образом, если об типа игроков действительно отбрасывают слабо до- минируемые стратегии и знают партнера, то стратегия М невозможна, и по сути рассматривается игра 2х2: {(С,У),(С,Ш),(В,У),(В,Ш)}. Тогда для студента страте- гия У=(5,4)>Ш=(3,4), и последняя на втором шаге рассуждений отбрасывается, что понятно преподавателю, остается игра 2х1: {(С,У),(В,У)}. Аналогично, на третьем шаге, по рациональности преподавателя, останется игра 1х1: INDW= {(С,У)}, то есть итерационно-недоминируемое множество свелось к однозначному по выигрышам ис- ходу и является поэтому SoE. Напротив, по сильному доминированию здесь нельзя отбросить ни одной стратегии, поэтому INDS - это вся исходная игра. Решение Штакельберга, если лидер - первый игрок, ищем, приписывая каж- дой стратегии (строке) расчетные оценки его выигрыша, с учетом ответного ход партнера (Нэшевского отклика). Среди них наилучшей для него является С=5, по- 40 Глава 2. Статические или “одновременные” некооперативные игры этому решение StE=(С,У)=(5,5). Если бы вместо (5,5) в клетке (С,У) были выигрыши (3.5,5), то преподаватель, просчитывая варианты, оказался бы в неясном положении. Студенту при (В) безразлично, сыграть (У) или (Ш). При оптимистической позиции преподавателя, он выбрал бы StEO=(В,У)=(4,4), а при пессимистической StEP= (С,У)= (3.5,5). С другой стороны, если бы в правой нижней клетке стояло (М,Ш)=(4,6), то студенты, в слу- чае их организованности и неорганизованности преподавателей, могли бы выступить лидером и форсировать вариант StE 2 =(М,Ш)=(4,6). Равновесие Штакельберга типа StE 1 реалистично, если преподаватель надеется заработать у студентов некоторую личную репутацию (например, “строгого”), и тем самым лидировать в игре. Если же предмет принимает большая группа преподавате- лей, то его личные усилия мало изменят репутацию “популяции преподавателей”, и, соответственно, поведение студентов - тогда лидерство и соответствующее решение StE неправдоподобны. Теперь попробуем представить, что преподаватели за столом переговоров нашли с коллективом студентов общее решение, то есть элемент ядра. Для нахождения ядра, из множества слабо-Паретовских исходов P W = {(С,У),(М,У),(М,Ш)}= {(5,5),(3,5),(3,6)} (то есть из множества неблокируемо- го большой коалицией) нужно отбросить исходы, в которых меньшие коалиции по- лучают менее своего гарантированного выигрыша. В качестве индивидульно- гаран- тированного выигрыша при нахождении ядра довольно реалистичным будет взять ожидаемые (но не фактические) значения полезностей рассматривающиеся в мак- симине; ведь именно их каждый игрок может себе гарантировать независимо от действий партнеров. Здесь преподаватель может гарантировать себе 3, а студент 4, поэтому никакие варианты не отброшены: (3,4)≤(5,5), (3,4)≤(3,5), (3,4)≤(3,6), и C = P W Аналогично из сильной Парето-границы P = C ={(С,У), (М,Ш)}={(5,5), (3,6)} получим сильное ядро, совпадающее здесь с ней. На первый взгляд, если переговоры начинались из ситуации решения Штакель- берга, то реалистичным будет предполагать, что преподаватели в них в качестве альтернативы договоренностям (точки угрозы) станут выдвигать не свой гаранти- рованный выигрыш 3, а выигрыш 5 в точке (С,У). Тогда ядро могло бы сузится до (С,У). Но этот вариант правдоподобен только при “слабой” организации коали- ции студентов, ведь студенты могут ответить контругрозой (Ш). А вводя “силу и слабость” коалиций мы уже отступили бы от стандартной концепции ядра. Для поиска решения Нэша в смешанных стратегиях, обозначим три страте- гии преподавателя 0 ≤ (s, v, m) : s+v+m = 1, и две стратегии студента u, (1−u). Нам нужно найти пару [(s, v, m), u], при которой популяция студентов и преподавателей не изменяет вероятности своих “чистых” ходов. Поскольку решения в чистых ста- тегиях всегда присутствуют среди решений в смешанных, то NE m ⊂ {[(s, v, m) = (1, 0, 0), u = 1], [(s, v, m) = (0, 1, 0), u = 0], [(s, v, m) = (0, 0, 1), u = 0]}. Но будут ли среди NE m еще какие-либо (дробные) решения? В данной здаче - да, только в смеси 0 < v < 1. При любом нетривиальном 0 < u < 1 чистая стратегия препо- давателя (С) оказывается строго выгоднее прочих, а откликом на нее будет (У). Напротив, все смеси (s, v, m) = (0, v, 1 − v) : 0 < v < 1 дают студенту ожидае- мый выигрыш от (Ш) больше, чем от (У), откликом же на (Ш) может быть любое (s, v, m) = (0, v, 1 − v) : 0 < v < 1. Вообще говоря, в подобных задачах поиск NE m ведется перебором гипотез о це- лых (0,1) значениях некоторых переменных и решением уравнений относительно си- 41 стемы прочих (предполагаемых дробными) переменных (здесь - только v). Уравне- ния составляются соответственно гипотезе рациональности выбора: все стратегии с дробным значением должны давать одинаковый выигрыш. Способ нахождения NEm методом перебора базисов таков. Прямое и двойствен- ное решения найденные (однозначно) по базису приравненному к вектору (1,1,. . . ,1) должны давать равновыгодность каждой базисной стратегии и не большую выгод- ность любой не-базисной. Это необходимое и достаточное условие NEm. Сопоставление концепций решений В каких ситуациях логично применять какие из концепций решений? Из примеров мы уже видели, что трудно дать однозначный ответ, выбор решается интуицией, знанием особенностей конкретных участников и ситуации. Вот, скажем, две простые игры (см. Данилов 2001). Ann \ Bob x y Ann \ Bob x y a 7 ,99 1 ,-1000 a 3 ,3 (NE) 0 ,1 b 8 ,99 1 ,100 (NE) b 1 ,0 2 ,2 (NE) В первой у Анны слабо-доминирующая стратегия b, и исход (b, y) является разум- ным решением и по слабому доминированию, и единственным равновесием Нэша. Поэтому, зная цели друг друга, или играя однократную игру в популяции, игроки должны бы остановиться на этом решении. Но если Боб допускает хоть малую ве- роятность того, что Анна из безразличных для нее (при ожидаемой стратегии Боба y) может выбрать a, тогда осторожность требует от него сходить x, а теряет он от этого немного. Поэтому, осторожная стратегия и максиминное решение (b, x) вполне реалистичны. Во второй игре верхнее из Нэшевских равновесий с выигрышами (3,3) выгод- нее нижнего, и в случае переговоров оно может быть точкой соглашения, причем устойчивого. Но при однократной игре втемную каждый может осторожничать, и среди двух Нэшевских решений выбирать то, где выше гарантированный выигрыш, то есть худшее: MM={(b, y)}. Что реалистичнее - трудно сказать. Итак, выбор кон- цепции решения бывает нетривиален, и должен учитывать информационные особен- ности ситуации, дополнительные сведения об игроках. (Мы еще остановимся на идее универсальной концепции с явными ожиданиями.) Теперь – о соотношении кооперативных концепций (P , C W , P W ) с различными некооперативные решениями. Не всегда, но часто результаты некооперативного поведения оказываются не опти- мальными по Парето, как показывают следующие примеры. Пример 2.0.5 Покажем разнообразие возможных ситуаций совпадения или несов- падения некооперативных решений с кооперативными на примерах. В частности, можно разобрать все симметричные игры 2 × 2 с неодинаковыми выигрышами каждого участника. Для этого достаточно посмотреть все различ- ные (с точностью до перестановок) расположения чисел 0,1,2,3 по матрице, и до- полнить их симметрично полезностями второго игрока. Несколько подобных игр и одна игра с частично-совпадающими выигрышами приведены в таблице: 42 Глава 2. Статические или “одновременные” некооперативные игры Игры, где добровольная эффективная кооперация: -гарантирована, симметрична: "Симбиоз" -возможна, симметр.: "Только позови" 0 0 1 2 0 0 3 1 C N E 2 2 0 1 N E 1 1 0 2 2 1 SDE 3 3 C 1 3 C SDE 2 2 C 1 0 N E 3 3 C 2 0 N E 3 3 C -вероятна, несимметрична: "Цыплята" -неправдоподобна: "Дилемма закл." 0 0 N E 3 2 C 0 0 N E 3 1 C DE 1 1 0 3 P SDE 1 1 0 3 N E 2 3 C 1 1 N E 1 3 C 2 2 C 3 0 P N E 3 3 C 3 0 2 2 C Таблица 2.10: Наиболее типичные игры 2х2 и проблема совпадения некооперативных решений с кооперативными. В таблице 2.10 представлены некоторые случаи (не-)совпадения кооперативных и некооперативных решений игр 2х2 (полный их обзор предлагается как упражнение). В первой игре типа "Симбиоз"участникам незачем вступать в переговоры: наилучшее решение из ядра (С) и так сильно доминирующее (SDE). Во второй - аналогично, с той разницей, что есть еще два несимметричных потенциальных соглашения (С), од- но выгодное для одного, а другое для другого. Но несимметричные здесь неустойчи- вы относительно некооперативного поведения. В игре "Цыплята"(кто быстрее клю- нет добычу) два Нэшевских равновесия (N), оба из ядра, но одно выгоднее для од- ного, а другое для другого. Это создает борьбу за лидерство: кто первый займет вы- годную позицию. Это осложняет переговоры. Игра "Только позови"демонстрирует два устойчивых состояния, если она находится не в лучшем, то одному из партнеров достаточно предложить переключиться в лучшее – и партнер согласится. Четвертая пара игр типа "Дилеммы заключенных"представляет ситуацию, где взаимовыгод- ный вариант есть, но устойчивый компромисс маловероятен или даже невозможен, если не принуждать к выполнению соглашения. 2.0.8 Дополнительные примеры решений в непрерывных иг- рах и NE m Связь матричных игр с линейным программированием и нахождение NE m Доказательство Следствия 2.1 для антагонистических конечных (т.е. “матрич- ных”) игр двух лиц можно проводить и независимо от теоремы Нэша, через линейное программирование, которое дает также способ поиска решений NE m для этих игр. Для этого задачу 1-го игрока записывают в форме максимизации (неизвестной игрока заранее) цены игры u s по переменным u s , µ, (где µ := σ 1 ) при ограничениях µ ≥ 0, n 1 X k=1 µ k = 1, µa k ≥ u s (k = 1, ..., n 2 ), где a k ∈ IR n i — столбцы матрицы платежей (a k j ) := (u 1 (x j 1 , x k 2 )). Здесь ограничения ти- па ≥ выражают гипотезу 1-го о неблагоприятном поведении противника (максимин, 43 который совпадает здесь с седлом из-за антагонизма игры). Легко проверить, что за- дача противника есть двойственная к описанной задаче. В обеих двойственных друг другу задачах есть допустимые решения, следовательно симплекс- методом можно найти седловую пару в игре G m . Она является и Нэшевской парой и максимином, по смыслу неравенств – ограничений. Для случая биматричной (то есть не обязательно антагонистической) игры задачи игроков не окажутся двойственными друг к другу, и поиск NE m методом линейного программирования не очевиден. Все же его общая идея - перебор возможных базисов (наборов активных ограничений) сохраняет ценность для поиска решений. В сущно- сти, нужно перебрать все гипотезы о возможных комбинациях стратегий применяе- мых с ненулевой интенсивностью (это не всегда все стратегии!), для обоих игроков. Например, рассмотрим повторяющуюся игру матери с сыном из известного детского стишка. 15 Сыну могут давать чаще или реже карманные деньги, в зависимости от того, часто ли от него пахнет табаком, а если пахнет сигарами - то пороть. Посчи- тайте вероятности (смешанные стратегии) при такой, например, матрице выигрышей (субъективных полезностей) исходов: Сын Мать Давать Не давать Пороть − − −− − − −− − − −− − − −− Не курить | + 0, +0 +1, −2 −5, −5 Курить | + 2, −2 +0, −1 −4, −4 Сигары | + 1, −5 −1, −4 −3, −3 Решение NE m окажется включающим только первые две стратегии и у матери и у сына. Для простого случая биматричной игры 2 × 2 также можно найти NE m графи- чески, строя функции (или отображения) X ∗ i (x −i ) — отклики игроков на действия партнеров; их пересечение окажется равновесием. Эту же идею нахождения решения для неантагонистической игры, даже с большим числом стратегий, можно реализо- вать и в терминах системы равенств и неравенств: все активные (имеющие ненулевой вес) стратегии игрока должны быть равновыгодны, а неактивные менее выгодны. Перебирая все потенциальные базисы (наборы активных стратегий) найдем те, в которых система совместна, то есть NE m Решение NE m можно найти также на компьютере многократными итерациями, опираясь на следующую теорему [см.?? ]. Теорема 1 (Брауна-Джексон) Пусть в повторяющейся матричной (антаго- нистической) игре двух лиц каждый игрок при выборе своего отклика на каждой итерации считает прошлую среднюю частоту, с которой выбиралась конкретная стратегия партнера за вероятность ее будущего появления. Тогда эти итерации асимптотически сходятся к элементу из NE m . Данная теорема служит также идейной опорой понятия NE m , и подводит к понятию устойчивости равновесий. Ее сложное доказательство не приводим. 15 “...сын курил сигары по рублю за штуку. Мать, узнав об этом, дала сыну порку: не кури сигары, а кури махорку.” 44 Глава 2. Статические или “одновременные” некооперативные игры При нахождении равновесия по Нэшу, особенно в играх с непрерывными страте- гиями, можно воспользоваться понятием функции (отображения) отклика F i (x −i ) = X ∗ i (x −i ) определенном в (2.4). Тогда можно переформулировать определение NE так: Точка ¯ x является равновесием по Нэшу т. и т. т., когда ¯ x i ∈ F i (¯ x −i ) или ¯ x i = F i (¯ x −i ) ∀i ∈ I. (2.8) Здесь равенство – если функции F i (.) являются однозначными, тогда нэшевское равновесие задается просто системой уравнений и соответственно вычисляется. Найдем этим путем NE, StE в примере игры с непрерывными стратегиями. Пример 2.0.6 Рэкетиры (или орган налогообложения) выбирают, какую долю τ ∈ [0, 1] валовой выручки y забирать у фирмы. Они при этом максимизируют функ- цию вида T (τ, y) = τ y, то есть желают побольше получить. Фирма имеет функцию π(τ, y) = (1 − τ )y − y 2 , то есть максимизирует прибыль при квадратичной функции затрат выбирая объем продаж y ≥ 0. Найдем решения этой игры при различных гипотезах о поведении: 1)осторожном, 2)“близоруком” (ситуативном), 3)когда рэке- тиры - лидер игры, знающий цели и просчитывающий ответы фирмы. 1) Осторожное равновесие (MM ). Оно не очень правдоподобно в рассматривае- мой ситуации: ведь участники должны бы знать ходы друг друга; но найдем MM для примера. Самое худшее, что может сделать фирма с точки зрения рэкетира – не выпустить ничего: y = 0. При этом рэкетиру все равно, какую долю τ ∈ [0, 1] уста- новить. С другой стороны, самое худшее, что может сделать рэкетир с точки зрения фирмы – установить максимальную τ = 1. При этом фирма максимизирует прибыль π(y) = (1 − τ )y − y 2 . Находим функцию отклика, приравняв производную этой функции по l к нулю: y ∗ (τ ) = (1 − τ )/2, равное нулю при τ = 1. Таким образом, осторожное равновесие MM = [0, 1] × 0 3 (τ, y). 2) Равновесие по Нэшу (NE). При любом ненулевом выпуске y близорукому рэ- кету выгодно установить максимальную долю (τ = 1). Поэтому его (многозначной) функцией отклика будет: τ ∗ (y) = 1 при y > 0; τ ∗ (y) = [0, 1] при y > 0. Функция отклика фирмы y ∗ (τ ) получена выше. Решив систему {τ ∗ (¯ y) 3 ¯ τ , y ∗ (¯ τ ) = ¯ y}, найдем единственное Нэшевское равновесие (¯ τ , ¯ y) = (1, 0), которое совпадает с одним из осторожных, поэтому является и седлом. 3) Равновесие по Штакельбергу (StE) (лидер – рэкет). Рэкет знает функцию от- клика фирмы, и подставляя ее в свою целевую функцию, максимизирует τ (1 − τ )/2. Очевидно, максимум достигается при уровне τ = 1/2, чему соответствует уровень выпуска y = 1/4. 4) Парето-оптимум (P). Если предполагать, что фирма способна передавать рэке- ту не только налог, но и фиксированную сумму r, то Парето-оптимум можно найти как максимум суммы целевых функций. Получим P = {τ = 0, y = 1/2, r ∈ [0, 1/2]} (здесь же и слабый Парето-оптимум). Этот исход достижим, если фирма обещает рэкету некоторую сумму r за нулевой налог (кооперативное поведение). Очевидно, что ни одно из перечисленных некооперативных равновесий не является Парето- оптимальным. 45 5) Ядро (C W ). Какова упомянутая сумма r достижимая в переговорах? Точки ядра не должны блокироваться ни одной коалицией: ни коалицией из обоих участ- ников (т.е. должны принадлежать слабой Парето-границе), ни коалицией из одного участника. Если в качестве индивидуально достижимых выигрышей берем гаран- тированные минимаксные выигрыши T (τ, y) = 0, π(τ, y) = 0, то ядро состоит из всех точек P. Если же считать, что лидирующее положение рэкета известно обо- им участникам, то он считает гарантированным доходом свой доход 1/8 достижи- мый в равновесии Штакельберга, тогда ядро меньше Парето-границы: C = {τ = 0, y = 1/2, r ∈ [0, 1/2]}. Пример 2.0.7 Пусть есть отрасль с функцией цены P от суммарного выпуска Y = P y i (обратной функцией спроса) вида P (Y ) = 40 − 2Y . Пусть есть n > 1 одинаковых конкурентов i = 1, ..., n с линейными издержками, то есть с постоянными предельными издержками, причем ˙ C i = 1. Найдите решение y i каждого об объеме выпуска при разных гипотезах о поведении: 1)MaxMin, 2)StE (один из конкурентов лидирует, например, имея возможность первым объявить выпуск), 3)NE, 4)C-ядро. Приближается ли при росте числа конкурентов n решение по Нэшу (когда каж- дый понимает, что при росте его выпуска цена уменьшится) к решению совершенной конкуренции (когда каждый считает себя несущественно влияющим на общую цену)? Нарисуйте для числа конкурентов n = 2 график кривых безразличия в простран- стве y 1 , y 2 и отметьте на нем все 4 типа решений. 2.0.9 Эволюционная интерпретация NE и NE m , стабильность, “Равновесие дрожащей руки” (THNE) Обычно идея равновесия Нэша в смешанных стратегиях применяется к популяции игроков каждого типа, а не к паре игроков повторяющих игру. Тогда смешение стра- тегий можно понимать так: доля α > 0 игроков типа А выбирает свою первую стра- тегию, а 1 − α > 0 из них выбирают вторую. Аналогично, доля β > 0 игроков типа В выбирают свою первую стратегию, 1 − β > 0 вторую. В этой интерпретации, смена стратегий частью игроков – это эволюционный сдвиг в популяции. А случайные отклонения игроков от обычных стратегий – это мутации. Естественно предполагать, что доля игроков играющих более полезную стратегию растет, причем неважно почему, рациональность поведения не обязательно пред- полагать. Например, неудачники тупо копируют поведение успешных, или просто выбывают из игры. Тем самым, поведение популяции людей или животных иногда хорошо описывается моделью рационального поведения (оптимизации) даже когда они не рациональны. Это подобно тому как вода занимает оптимально-низкое поло- жение в любой впадине не будучи рациональной. 16 Игра "Ястребы и голуби", эволюционное равновесие. ... Идея устойчивости ... Эволюционное равновесие. Ключевая идея эволюционных игр - это идея предыстории нынешнего, рассмат- риваемого, равновесия. Мы увидим, что она разрешает многие недоумения в ди- 16 Эта дарвинистская идея парирует многочисленные нападки на теоретическую гипотезу макси- мизации прибыли со стороны практических анкетных обследований бизнесменов. Ведь если слабые выбывают, то для исхода эволюции почти неважно, что в головах у популяции. 46 Глава 2. Статические или “одновременные” некооперативные игры намических играх, да и в статических играх это основа для очищения множества равновесий от неестественных решений. Определение 2.0.9.1 Равновесие дрожащей руки THNE - это такое равновесие Нэша, что существует сходящаяся к нему вполне смешанная последовательность стратегий всех игроков (где нет неиспользуемых стратегий), ответом на все чле- ны которой и является это равновесие Нэша. Пожалуй, наиболее убедительная трактовка THNE, как и обычного Нэша - именно эволюционная. Подразумевается, что перед данным розыгрышем была предыстория таких же игр, разыгранных подобными же участниками. И ожидания (веры) тепе- решних игроков о намечаемых стратегиях их партнеров взяты именно из предысто- рии. Особенно смешанные стратегии наиболее адекватны эволюционной трактовке: ‘в среднем’ мои партнеры ходят вот так. Требование, чтобы в предыстории они бы- ли вполне смешанными, означает, что у всякого игрока могла “рука дрогнуть”, и он вместо выгодной стратегии иногда ходил случайной. Поэтому, все возможные ситу- ации игры наблюдались, и поэтому мы знаем, как вели себя в них прочие партнеры! Со временем, предполагает концепция, иррациональность поведения уменьшалась, и сейчас сошла на нет, оставив только память о себе в виде ожиданий — память, важную для теперешних ходов. Главное то, что концепция THNE снимает концептуальные проблемы в отноше- нии неприменяемых обычно стратегий (вне пути игры): в предыстории у каждого игрока были моменты (не-рационального) применения любой стратегии, поэтому все пути игры когда-то наблюдались, и теперешние ожидания или веры появились не на пустом месте. 17 Для освоение THNE, вернемся к игре на Таб. 2.4: Victor x y An- a 101, 100 (NE) 1, 100 na b 101, 0 3, 2 (WDE) Таблица 2.11: Оправдание слабого доминирования - через THNE. Здесь, как говорилось, по слабому доминированию образуется невыгодное реше- ние b, y. Оно критиковалось с точки зрения некоторой популяции, где игроки могут не захотеть переходить от хорошего равновесия Нэша на (a, x) на индивидуально- нестрого-более выгодные позиции b и y, основательно опасаясь сползания популяции к малым выигрышам (3, 2) при (b, y). Теперь же, если мы верим в предысторию с 17 Но еще один концептуальный вопрос остается. В предыстории, сформировавшей мои тепереш- ние представления о моих партнерах, вели ли игроки себя хотя бы отчасти рационально? Про- извольность этой предыстории (вполне-смешанной последовательности, сходящейся к нынешнему равновесию) вызывает смутную неудовлетворенность, но не сразу ясно, в каких терминах ее вы- разить. Можно, например, предполагать, что ‘дрожание руки’, то есть иррациональность игроков в ходе предыстории проявлялась специфическим образом. А именно, в силу каких-то причин, воз- можно недостаточного обдумывания, каждый игрок (тип игрока) время от времени ‘не замечал’ часть своих возможностей, и пользовался только оставшимися стратегиями. Но пользовался ими рационально. Эта идея задает самое узкое сужение равновесий Нэша - ‘правильное равновесие’ Майерсона, не рассматриваемое в этом курсе. 47 дрожанием руки, то из двух равновесий Нэша остается только плохое, устойчивое к некоторым мутациям (вот что важно) IN D W 18 Так новая идея сужает множество решений Нэша и оправдывает применение IND W в определенных случаях. (Пока- жите, что всегда T HNE ⊆ IN D W ⊆ IND S .) А вот в игре из Табл. 2.6 принцип вполне-смешанной предыстории (дрожащей ру- ки) исключит три плохих равновесия из четырех SDE сильно- доминирующих (очень бы хотелось, но это может сделать только коалиционное доминирование). Также, во второй игре из Табл. 2.0.7 новый принцип ни одного из двух NE не ис- ключит, а в первой исключит единственное целое равновесие Нэша (сохраняя только смешанное)! 2.0.10 О (не-)совпадении различных решений Приведем утверждения о соотношениях разных некооперативных концепций. Лемма 2.0.10.1 (см. Мулен, 1985 ) Попарно эквивалентны три случая: 1) IDE 6= ∅; 2) Все стратегии в N D эквивалентны; 3) IDE = N D. Теперь соберем вместе несколько фактов. Утверждение 2.0.10.2 1) NE ⊂ NE m ; N D ∩ MM 6= ∅, 2) если IDE 6= ∅, то MM ⊃ IDE = N D = SoE ⊂ NE , IDE ⊂ Sad, причем если доминирующее равновесие сильное, то MM = SIDE = SNE = NE = SoE ⊃ StE O . 19 3) SoE ⊂ NE ⊂ IN DS. 4) SNE ⊂ INDW , причем если SoE 6= ∅, то SNE ⊂ SoE. 5) Обозначая через NE(IND) решение Нэша в редуцированной по доминированию игре, можно утверждать NE(IN DS) =NE, NE(INDW ) = NE∩INDW. То есть, редукция игры по доминированию не образует новых равновесий Нэша, а сильное доминирова- ние вообще не изменяет их. Доказательство. 1) Вложения NE ⊂ NE m , N D ∩ MM 6= ∅ очевидны из определений: среди смешанных стратегий могут быть и чистые, аргмаксимум по векторам пересе- кает аргмаксимум по их минимумам. Доказательсто (2) элементарно, при использо- вании приведенной леммы: поскольку доминирующие стратегии покомпонентно “не хуже” остальных стратегий, то принадлежат и другим некооперативным решениям. Пункт (3): предположим противное: существует равновесие ¯ x : ¯ x ∈ SoE, ¯ x 6∈ NE, то есть для некоторого (например 1-го) участника (∃˜ x 1 : u 1 (˜ x 1 , ¯ x −1 ) > u 1 (¯ x 1 , ¯ x −1 )). Эта альтернативная стратегия ˜ x 1 не может входить в финальное множество INDW = SoE, поскольку в нем все эквивалентны. Тогда, на каком-то этапе итеративного доми- нирования, она была продоминирована какой-либо стратегией ˆ x 1 : u 1 (u 1 (ˆ x 1 , ¯ x −1 ) ≥ ˜ x 1 , ¯ x −1 ) > u 1 (¯ x 1 , ¯ x −1 ). Продолжая аналогичные рассуждения, по индукции получим, что в финальном множестве есть стратегия не хуже, чем ˜ x 1 , - противоречие. (ср. доказательство SoE ⊂ NE в [Мулен, 1985, Теорема 1, стр 74]). 18 Устойчивость ко ВСЕМ мутациям обсуждается ниже в “эволюционном равновесии”. 19 Последнее вложение сравните на игре Табл. 2.6 и Табл. 2.12. 48 Глава 2. Статические или “одновременные” некооперативные игры Вложение NE ⊂ IN DS доказывается аналогично: ¯ x ∈ NE означает [u i (¯ x i , ¯ x −i ) ≥ u i (x i , ¯ x −i )∀i∀x i ]. Но такая стратегия не может строго доминироваться какой-либо другой. (4) доказывается аналогично. (5)- доказывается по определениям (см. Данилов, Лекция 12.) Действительно, строго доминируемая стратегия игрока i не может входить в NE. Поэтому, отбро- сив ее мы не сузим NE. Но и не расширим, так как ни возможности игрока i, ни возможности его партнеров в доминировании стратегий не сузились. Поэтому NE(INDS) = NE. Аналогично, множество NE не расширяется при слабом доминировании. Оно мо- жет сузиться только за счет отбрасывания слабо-доминируемых равновесных стра- тегий, ведь новых стратегий, которые могли бы опровергнуть какое-либо решение Нэша – не возникает. Поэтому NE(INDW ) = NE ∩ INDW . [[[]]]] Относительно соотношения разных решений и равновесия Штакельберга: хотя StE совпадает со строго доминирующим равновесием (если то непусто), но может лежать вне отдельной строго доминирующей стратегии(!), как в Табл. 2.12, и не совпадать ни с итерационно-недоминируемым, ни с Нэшевским решением. Victor x z An- a 101, 0 1, 1 (INDW) na b 100, 100 (StE) 0, 0 Таблица 2.12: Несовпадение INDW и StE. Кооперативные концепции легко сравнить по определениям: Утверждение 2.0.10.3 Ядро принадлежит слабой Парето-границе, а сильное ядро — сильной (обычной) Парето-границе: C W ⊂ P W , C s ⊂ P ⊂ P W . Совпадение или несовпадение кооперативных концепций (P , C W , P W ) с раз- личными некооперативные решениями мы уже обсуждали, и видели что часто ре- зультаты некооперативного поведения оказываются не оптимальными по Парето (см. примеры). 2.0.11 О существовании и компактности множеств решений Утверждение 2.0.11.1 Если все допустимые множества X i компактны, функ- ции u i непрерывны, то 1) P 6= ∅; 2) множества IDE, MM, NE, P W компактны. 3) также непусты множества: осторожных решений (MM 6= ∅), множества итерационно- недоминируемых стратегий (INDS ⊇ INDW 6= ∅), а в игре 2-х лиц и решения Штакельберга: (StE 6= ∅). Доказательство (см. в [Мулен, 1985, с. 79] более подробное доказательство этой теоремы.). Пункт (1) и компактность MM – см. [Мулен, 1985„ стр. 26]. Пункт (2): 49 компактность NE проверена в теореме Нэша (ниже), а компактность IDE доказы- вается опираясь на приведенную лемму (докажите самостоятельно) [Мулен, 1985]. Компактность слабой Парето-границы доказывается рассмотрением пределов. 3) Непустота множеств MM, StE, INDW при конечности X i очевидна из опреде- лений. Для случая компактных множеств доказательство существования MM, StE - по теореме Вейерштрасса, учитывая для StE теорему Нэша. Рассмотрим вложенную последовательность допустимых множеств X = N D 1 ⊃ N D 2 ⊃ ... ⊃ N D k ... заданную определением INDW . На каждом шаге последующее множество N D k задается как вычитание из предыдущего множества N D k−1 друго- го множества D доминируемых стратегий. Замкнутость каждого недоминируемого множества N D k можно доказать от противного по непрерывности u(x i , x −i ): если бы предел последовательности доминировался, то и близкие к нему точки домини- ровались бы. Как известно, пересечение последовательности вложенных компактов непусто. [[[]]]] Теорема 2 (Нэш, 1951) Пусть в игре в нормальной форме все допустимые мно- жества X i (i ∈ I) непусты, компактны и выпуклы, все целевые функции u i (.) (i ∈ I) непрерывны по совокупности переменных и вогнуты по x i , тогда непусто множе- ство Нэшевских равновесий (NE 6= ∅), и оно компактно. Следствие 2.1 Если все X i конечны, то непусто множество равновесий в сме- шанных стратегиях (NE m 6= ∅), и оно компактно. Следствие 2.2 [ср. Мулен, 1985, с. 79] В антагонистической игре удовлетворя- ющей условиям теоремы есть седло (Sad) и, следовательно, цена. Доказательство (для случая, когда множества X i ∈ IR l - в действительном про- странстве). Определим отображение F : IR l 7→ IR l как декартово произведение Нэ- шевских откликов (см. выше) каждого игрока: F(x 1 , ..., x n ) := Q i X ∗ i (x −i ). Каждое отображение X ∗ i (x −i ) выпуклозначно и замкнуто, как аргмаксимум по x i непрерыв- ной вогнутой функции (зависящей непрерывно также от x −i ) на выпуклом компакте X i (док. см. напр. в [В.Гильденбранд “Ядро и равновесие в большой экономике”, стр.26], там же см. теорему Какутани). Тогда к F(.) применима теорема Какутани о неподвижной точке, 20 следовательно имеется неподвижная точка ˜ x : ˜ x ∈ Q i X ∗ i (˜ x −i ), то есть ˜ x ∈ NE, что и требовалось. Для проверки компактности NE можно построить последовательность неподвиж- ных точек {˜ x t } t=1,2,... ∈ NE сходящуюся к некоторой точке ¯ x. Равновесность каждого элемента последовательности ˜ x t ∈ NE, в терминах неравенств (2.3) сохраняется и в пределе, что завершает доказательство. [[[]]]] Для доказательства Следствия 2.1 достаточно проверить, что рассматриваемое в нем смешанное расширение G m исходной конечной игры удовлетворяет условиям те- оремы. Действительно, выпуклая оболочка любого конечного множества стратегий есть выпуклый компакт. Кроме того, матожидание полезности U i (σ 1 , ...σ n ) опреде- ленное в (2.5), есть не только непрерывная, но и линейная (следовательно вогнутая) по переменным σ i функция, что и требовалось для применения Т.Нэша. [[[]]]] 20 Теорема Какутани о неподвижной точке: замкнутое (т.е. имеющее замкнутый график) выпук- лозначное отображение F(.) выпуклого компакта X в себя имеет неподвижную точку x : x ∈ F(x). |