Лекции по теории игр и политологии
 Скачать 1.03 Mb.
|
|
.5, 0.5)). бор) вероятностей применения чистых стратегий, такой, что ни один иг- рок не может меняя свою смешанную (вероятностную) стратегию улуч- шить матожидание своего выигрыша, при неизменных смешанных стра- тегиях партнеров. То же самое в более формальных терминах: Определение 1.4.4 Для игры G, где у каждого игрока i ∈ I есть конечное число (n i ≥ 1) стратегий X i = {x i1 , ..., x in i }, определим смешанную стратегию каждого иг- рока i как набор вероятностей 11 σ i = (σ k i ) n i k=1 = (σ k i (x k i )) n i 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 ) (5) Нэшевское равновесие в смешанных стратегиях ¯ σ ∈ NE m исходной игры G есть Нэшевское равновесие в ее смешанном расширении G m , то есть набор (¯ σ i ) I , таких, что ни один игрок не может меняя смешанную стратегию улучшить матожидание своего выигрыша, при неизменных (смешанных) стратегиях партнеров. (Аналогично можно определить понятие N E m для игры с бесконечным множеством стра- тегий, только смешанные стратегии σ i оказываются не векторами, а вероятностными мера- ми, матожидания – из сумм превратятся в интегралы. Переход к смешанному расширению (то есть к вероятностному варианту) игры овыпукляет ее множество стратегий и множе- ство достижимых уровней полезности. Это благоприятно сказывается и на существовании Нэшевских равновесий (см. теорему Нэша ниже), и на возможности их охарактеризовать.) Итак, пользуясь введенным определением решения, легко для примера "Монетки” составить неравенства, которым должны бы удовлетворять вероятности (α L , α R ), при- меняемые Анной к левому и правому ходу, и аналогичные неравенства для смешанных стратегий Виктора (ν L , ν R ). А именно, тот факт, что Анна не хочет ни увеличивать ни уменьшать частоту применения Левой стртегии за счет правой, означает, что обе приносят одинаковую ожидаемую полезность при заданных вероятностях (смешанных стратегиях (ν L , ν R )) Виктора: U A ((α L = 1, α R = 0), (ν L , ν R )) = −1 ∗ ν L + 1 ∗ ν R = 11 Обычно имеют в виду популяционную или повторяющуюся игру. Обозначение m – от англ. “mixed”. 18 = U A ((α L = 0, α R = 1), (ν L , ν R )) = −1 ∗ ν R + 1 ∗ ν L . Это уравнение укажет, что равенство полезностей возможно лишь при равных веро- ятностях ходов партнера ν L = ν R = 0.5. Аналогичное уравнение относительно равных полезностей Виктора даст искомые равновесные стратегии Анны α L = α R = 0.5. (Упражнение: Найдите аналогично NE m в аналогичной игре герцога де Монмора (см. Мулен 1985): Отец, герцог, желая развить сообразительность сына, каждое утро предлагал ему сыграть в "Монетки”, но не брал с него ничего при не-угадывании (в какой руке у отца монетка), давал золотой за угадывание в левой руке, и два золотых - за угадывание в правой.) Возвращаясь к теории, легко заметить, что к расширенной в вероятностное про- странство игре можно применять все те же приемы, что и к исходной, а обычные равновесия Нэша остаются равновесиями и в вероятностном расширении игры (ведь чистые стратегии – это просто орты в пространстве вероятностных стратегий). Теперь, применяя уже для смешанного расширения игры ранее использованное понятие сильного доминирования, можно сузить множество недоминируемых страте- гий еще одним методом, альтернативным к слабому доминированию и расширяющим множество сильно доминируемых: Определение 1.4.5 Стратегию x i назовем смешанно-доминируемой, если существу- ет смешанная стратегия σ i ∈ Ω i сильно доминирующая над x i Пример: три стратегии дают игроку выигрыши (4,1), (1,4), и (2,2) соответственно. Ясно, что ни одна из трех не доминирует другую ни сильно ни слабо, но комбинация первых двух с весами 0.5 смешанно-доминирует третью. Полезно - Утверждение. Некоторая чистая стратегия может быть смешанно- недоми- нируемой тогда и только тогда, когда является рациональным откликом на некото- рую смешанную стратегию партнеров (в частности, возможно, на чистую стра- тегию). Этот факт следует из овыпукления игры при ее смешанном расширении (док. см. Myerson 1999, Данилов 2002). Из него можно вывести вложение NE ⊆ IN DS (покажите). Наиболее интересно он отражается на антагонистических играх. Для антагонистической игры двух лиц ценой игры 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 ) . Если седловой точки, то есть пары стратегий удовлетворяющей этому равенству нет, то игру считают неразрешимой по принципу седла, то есть “не имеющей цены”. Легко заметить, что антагонистическая игра двух лиц (где u 1 (x 1 , x 2 ) = −u 2 (x 1 , x 2 )) имеет цену тогда и только тогда, когда функция u 1 (., .) имеет седловую точку на X 1 × X 2 . Смешанное же расширение игры всегда имеет цену (теорема фон Неймана, см. ниже). 19 1.4.2 Множественность равновесий Нэша, “фокальные точки” и борьба за лидерство: равновесие Штакельберга (последовательные ходы) Рассмотрим проблему, возникающую, когда равновесие Нэша не одно. Какое из них считать более вероятным исходом? Это популярная тема "сужения” или "очищения”, рафинирования (refinement) множества равновесий от малоправдоподобных. Мы уже касались одного способа рафинирования. Это пересечение NE с другими решениями: с DE или с максимином, или с итерационно-недоминируемым множеством. Вообще говоря, исход, удовлетворяющий не одной концепции решения, а двум и более - вы- зывает больше доверия, кажется правдоподобнее. Впрочем, в некоторых играх нет никаких оснований предпочитать, в качестве пред- сказания, одно равновесие другому. Наиболее хорошо это видно в игре координации с односторонними преимуществами типа "Перекресток"(Chicken game). В таких слу- чаях часто можно считать, что выбор из многих возможных равновесий произойдет по принципу "фокальной точки”, то есть не зависит от включенных в рассмотрение данных. Поясним это важное в играх с множеством равновесий понятие. Положив шарик в строго вогнутую чашу, мы единственным образом предскажем равновесие - это “обу- словленное” равновесие, а не "фокальное”. Напротив, положив шарик на горизонталь- ную поверхность, мы можем предсказать, что куда его положишь, там он и останется в равновесии. Это и называют эффект "фокальной точки”: зависимость положения равновесия от начальной точки, или даже превращение любой начальной позиции в равновесие. Как уже говорилось, в примере игры координации “семейный спор”, если оба почему- то ожидают от партнера выбор “кино”, (например, известна уступчивость Виктора, или было сделано какое-то намекающее сообщение), то это и случится. Этот довольно распространенный эффект “самоподдерживающихся ожиданий” как раз и является “эффектом фокальной точки”. Так, культурные нормы и традиции часто порождают фокальные равновесные точ- ки в определенных играх с многими потенциальными равновесиями (или порождают- ся как фокальные точки?). Скажем, левостороннее движение транспорта в Англии и правостороннее на континенте - типичные фокальные точки. Более интересен пример фокальной точки нелегитимного политика. Тут тоже дей- ствет правило самоподдерживающихся ожиданий: “если люди верят, что у тебя есть власть, то у тебя она есть (люди слушаются)”. От дополнительных факторов игра может перескочить в другое равновесие, тоже устойчивое. Аналогично, в игре координации "Перекресток”, если Анна верит, что Боб нико- гда не тормозит, то сама будет тормозить. В результате сложится равновесие более выгодное для Боба. Аналогично можно рассуждать при противоположных ожидани- ях партнеров - Анна в выигрыше. И оба равновесия устойчивы (в смысле строгой невыгодности индивидуальных отклонений). Из этих рассуждений следует, что в игре координации с многими разно-выгодными равновесиями выгодно бы сходить первым, и захватить лучшую позицию (в "Пере- крестке” – позицию “не торможу”). В некоторых ситуациях такая возможность на- рушить одновременность и симметрию есть, и приводит к следующей концепции ре- шения (строго говоря, относящейся уже не к этому разделу, а к последовательным играм). В равновесии Штакельберга (Stackelberg), в отличие от рассмотренных концепций 20 решения “симметричных” относительно игроков, ожидания разных игроков формиру- ются по разным принципам. Первый игрок (лидер) ориентируется на индивидуально - оптимальные ответы партнеров зная их предпочтения, а остальные (ведомые) иг- рают, как в NE, близоруко реагируя на его ход и на ходы друг друга. Скажем, на рынке алмазов фирма Де Бирс, контролирующая более 70% продаж, при выборе цен просчитывает отклики на это мелких продавцов, а они играют примитивно подстра- иваясь под лидера. Ведь каждый из “мелких” не рассчитывает существенно повлиять на рынок в целом! Эта несимметричная концепция решений годится также для случая, когда лидер просто ходит первым, независимо от силы его влияния (последовательная игра). Равновесие Штакельберга с лидером No 1 есть такой профиль (набор) стратегий всех, что первый игрок (лидер) с учетом цедей партнеров адекватно прогнозирует равновесия Нэша, складывающиеся после его хода, и оптимизирует свою стратегию соответственно, а остальные поступают согласно его прогнозу. Более формально: Определение 1.4.6 Считая 1-го игрока лидером, обозначим решение Нэша среди последователей при фиксированной стратегии ¯ x 1 лидера – через NE −1 (¯ x 1 ). Равновесие Штакельберга с лидером No 1 (StEP 1 ) есть такой набор ¯ x что ¯ x −1 ∈ NE −1 (¯ x 1 ), (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)). (7) В частности, осторожное (пессимистическое) равновесие Штакельберга 12 с ли- дером 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 предполагает добро- желательность партнеров к лидеру при выборе из эквивалентных для себя вариантов (из X ∗ ), а StEP 1 — недоброжелательность; если же выбор “ведомых” однозначен, то разницы между StEO и StEP нет. Если не различать оптимистические и пессимисти- ческие решения, то можно определить StE = {StEO, StEP} Повторим рассуждения о “борьбе за лидерство”. Смысл борьбы за лидерство, ска- жем, в игре “Семейный спор” (“Battle of Sexes” - Рис. 1.1) таков. Рассмотрите возмож- ность одному из игроков, например, Виктору, сообщить другому (Анне) свое реше- ние: футбол. Эта возможность ставит его в положение Штакельберговского лидера, и 12 Наши определения StEO i , StEP i не традиционны. Обычное же StE есть, забегая вперед, просто SPE в двух-стадийной игре. 21 позволяет форсировать более выгодное для себя из двух Нэшевских равновесий. Ана- логично и для второго игрока. (А есть игры, где выгодно, наоборот, уступить первый ход - “борьбе за не-лидерство”.) То есть, понятие “борьбы” предполагает, что рассмат- риваемая игра вложена в более широкую, где можно выбрать, совершать ли первый ход, попадая в игру с решением Штакельберга. 1.5 Кооперативные решения - Парето-оптимум и ядро В заключение обзора наиболее типичных решений статических игр, напомним также основные понятия кооперативных решений, то есть возможных исходов переговоров участников. В данном случае мы планируем применять их для той же некооператив- ной игры, в которой рассматривались Нэш и другие решения. Смысл этого таков: а что если бы участники этой игры вступили в переговоры, к какому соглашению это могло бы вести? Определение 1.5.1 Назовем (сильным) множеством Парето (Парето-оптимумом, или “сильной Парето-границей”) множество неулучшаемых по Парето точек (исходов), то есть множество исходов неблокируемых-слабо большой коалицией I: P := {ˆ x| 6 ∃x ∈ X : u(x) > u(ˆ x)}, Слабая Парето-граница есть множество исходов неблокируемых-сильно большой ко- алицией I: P W := {ˆ x| 6 ∃x ∈ X : u(x) À u(ˆ x)}. Итак, Парето-оптимум — это такое состояние, в котором никто из участников не может увеличить своего выигрыша не уменьшив выигрыша кого-то другого, а слабый Парето-оптимум — это состояние, неулучшаемое для всех сразу (т.е., по сильному доминированию большой коалиции). Учитывая также и возможности других коалиций, получим один из вариантов определения ядра: Определение 1.5.2 Ядром C = C W (обычным, слабым ядром) называется множе- ство состояний неблокируемых никакой коалицией T ⊂ I, при обычном (сильном) определении блокирования: T блокирует вариант x ∈ X если существует альтернати- ва ˜ x i ∈ X i (i ∈ T ) такая, что все участники из T выигрывают по сравнению с x, т.е. 13 u T (˜ x T , x −T ) À u T (x T , x −T ) — при любых действиях x −T не входящих в коалицию T игроков. Сильным ядром C S можно назвать множество состояний, неблокируемых ника- кой коалицией при слабом блокировании (что означает u T (˜ x T , x −T ) > u T (x) вместо u T (˜ x T , x −T ) À u T (x) в определении блокирования). Но такое понятие в теории не употребительно. Употребительное (слабое) ядро – это множество вариантов, вне ко- торого соглашений заведомо быть не может, а сильное - менее очевидная концепция. Еще нужно добавить, что ядро в терминах исходных стратегий, а не выигрышей тоже мало употребительно, поскольку во многих играх неочевидно, как описать возможно- сти коалиций, особенно малых. Различные варианты определений ядра, связанного с игрой в нормальной форме: α-ядро, β-ядро, γ-ядро – см. в книгах Мулен, 1985, 1991. 13 Для пар векторов знак > здесь и далее означает ≥6=, а знак À — покомпонентно больше. В сущности, здесь вектор выигрышей коалиции T от альтернативы ˜ x i сильно доминирует (À) над вектором выигрышей от альтернативы x i 22 Чтобы применить понятие ядра к игре заданной в нормальной форме, нужно дого- вориться, что считать “точкой несогласия”, или иначе, “точкой угрозы” в переговорах. Есть несколько естественных вариантов. Иногда, участники считают, что в случае неуспеха их переговоров игра попадет в равновесие Нэша. Если оно единственно, то так можно искать соответствующее ядро, иначе нужны дополнительные соображения. Альтернативно, и довольно естественно для случая “угроз”, точкой несогласия для каждого игрока считать уровень его полезности, гарантированной при осторожном поведении. Тогда ядро называют α-ядром, и для игры двух лиц это понятие имеет очевидный смысл. Аналогично, можно расширить это понятие и для произвольного числа игроков, найдя гарантированные выигрыши любой коалиции. Но здесь могут быть тонкости, в которые мы вникать не будем, ограничившись простым случаем 2-х лиц, и не обсу- ждая других ядер, кроме α-ядра. Упражнение. В рамках обсуждения кооперативных решений, можно сравнить для игры 2-х лиц дележ Нэша и дележ Калаи-Смородинского (известные из других кур- сов) с α-ядром. 1.6 Нахождение и сопоставление разных решений Сопоставим все введенные понятия решений на примере единой (би-)матричной игры. Пример 1.4 Студент и экзаменатор (Поиск решений матричной игры) Рассмотрим гипотетическую популяцию ленивых студентов и более-менее стара- тельных преподавателей. За точку отсчета возьмем случай, когда студент учит, а пре- подаватель внимательно смотрит на экзамене за наличием шпаргалок: студент имеет 5, и удовлетворение преподователя оценим в 5 (см. Табл. 5). Если при внимательном экзамене студент не учит, то имеет оценку 2, но +1 от приятно проведенного в семе- стре времени, в целом 3, а удовлетворение преподователя 2. Если при невнимательном экзамене, но с дополнительными вопросами, студент учит, то имеет оценку 5, но -1 от утомления на экзамене, в целом 4, а удовлетворение преподователя тоже 5, но -1 от утомления, в целом 4. Если же в этом случае студент не учит, то имеет 3 (все же он что-то рассказал) +1 от отдыха в семестре, всего 4. Осталось предположить ма- лое моральное удовлетворение =3 преподавателя от плохого экзамена, еще немного гипотез, и получим игру Табл. 9. Студент Стратегии Гарантир. Расчетный и Учить Шпорить выигрыш выигрыш выигрыши (У) (Ш) Препо- Смотреть SoE 5 3 строго (С) 5 SNE 2 2 5 * дава- мягко, но 4 4 с Вопросами (В) 4 3 NE 3 * 4 или 3 тель Мягко, без 5 6 вопросов (М) 3 3 NE 3 * 3 Таблица 9: Игра “Экзамен”. В подобных (“матричных”) играх с конечными множествами стратегий двух игро- ков легко проверить наличие доминирующих стратегий: достаточно сравнить вектор 23 выигрышей (5,4,5) при стратегии “Учить” с вектором (3,4,6)- “Шпорить”, чтобы заме- тить, что они несравнимы, следовательно доминирующих стратегий у студента нет, тогда и доминирующего равновесия нет: IDE = ∅. Осторожное равновесие практически ищется так: игрок выбирающий строки в каждой строке находит свой гарантированный выигрыш (то есть минимум в стро- ке), а затем в качестве решения принимает строку или строки с максимальным га- рантированным выигрышем. Аналогично поступает со столбцами игрок выбираю- щий столбцы. В данном случае две нижние клетки - среди осторожных решений MM = {(В,У),(М,У)}. Возможно, при однократной встрече некоторой группы с неко- торым (впервые приглашенным в университет) преподавателем такое осторожное ре- шение реалистично. Чаще же можно ожидать, что популяция студентов знает по про- шлому опыту типичную стратегию преподавателя(-лей), тогда уместнее искать NE. Множество Нэшевских равновесий ищем перебором всех клеток; равновесия – это клетки из которых первому участнику не выгодно “уйти вверх или вниз”, а второму - “уйти в сторону” - то есть сменить стратегию при фиксированной чужой; здесь таких три: NE = {(С,У),(В,Ш),(М,Ш)}. Последнее наиболее благоприятно для студентов, но его реалистичность сомнительна, если преподаватели склонны отбрасывать слабо доминируемые стратегии. Итерационно недоминируемое (слабо) множество INDW ищем последователь- ным исключением из игры доминируемых строк и столбцов. На первом шаге рассу- ждений стратегия В=(4,3)>М=(3,3) слабо доминирует нд М, а у студента нет домини- рования (иначе бы мы одновременно отбросили и его доминируемые стратегии). Таким образом, если об типа игроков действительно отбрасывают слабо доминируемые стра- тегии и знают партнера, то стратегия М невозможна, и по сути рассматривается иг- ра 2х2: {(С,У),(С,Ш),(В,У),(В,Ш)}. Тогда для студента стратегия У=(5,4)>Ш=(3,4), и последняя на втором шаге рассуждений отбрасывается, что понятно преподавате- лю, остается игра 2х1: {(С,У),(В,У)}. Аналогично, на третьем шаге, по рационально- сти преподавателя, останется игра 1х1: INDW=SoE= {(С,У)}, то есть итерационно- недоминируемое множество свелось к однозначному по выигрышам исходу и является поэтому SoE. Напротив, по сильному доминированию здесь нельзя отбросить ни одной стратегии, поэтому INDS - это вся исходная игра. Решение Штакельберга, если лидер - первый игрок, ищем, приписывая каждой стратегии (строке) расчетные оценки его выигрыша, с учетом ответного ход партнера (Нэшевского отклика). Среди них наилучшей для него является С=5, поэтому реше- ние StE=(С,У)=(5,5). Если бы вместо (5,5) в клетке (С,У) были выигрыши (3.5,5), то преподава- тель, просчитывая варианты, оказался бы в неясном положении. Студенту при (В) безразлично, сы- грать (У) или (Ш). При оптимистической позиции преподавателя, он выбрал бы StEO=(В,У)=(4,4), а при пессимистической StEP= (С,У)= (3.5,5). С другой стороны, если бы в правой нижней клетке стояло (М,Ш)=(4,6), то студенты, в случае их организованности и неорганизованности преподавателей, могли бы выступить лидером и форси- ровать вариант StE 2 =(М,Ш)=(4,6). Равновесие Штакельберга типа StE 1 реалистично, если преподаватель надеется заработать у студентов некоторую личную репутацию (например, “строгого”), и тем самым лидировать в игре. Если же предмет принимает большая группа преподавате- лей, то его личные усилия мало изменят репутацию “популяции преподавателей”, и, соответственно, поведение студентов - тогда лидерство и соответствующее решение StE неправдоподобны. Теперь попробуем представить, что преподаватели за столом переговоров нашли с коллективом студентов общее решение, то есть элемент ядра. Для нахождения ядра, из множества слабо-Паретовских исходов 24 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) значениях некоторых переменных и решением уравнений относительно системы прочих (предполагаемых дробными) переменных (здесь - только 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) 25 В первой у Анны слабо-доминирующая стратегия b, и исход (b, y) является ра- зумным решением и по слабому доминированию, и единственным равновесием Нэша. Поэтому, зная цели друг друга, или играя однократную игру в популяции, игроки должны бы остановиться на этом решении. Но если Боб допускает хоть малую ве- роятность того, что Анна из безразличных для нее (при ожидаемой стратегии Боба y) может выбрать a, тогда осторожность требует от него сходить x, а теряет он от этого немного. Поэтому, осторожная стратегия и максиминное решение (b, x) вполне реалистичны. Во второй игре верхнее из Нэшевских равновесий с выигрышами (3,3) выгоднее нижнего, и в случае переговоров оно может быть точкой соглашения, причем устой- чивого. Но при однократной игре втемную каждый может осторожничать, и среди двух Нэшевских решений выбирать то, где выше гарантированный выигрыш, то есть худшее: MM={(b, y)}. Что реалистичнее - трудно сказать. Итак, выбор концепции решения бывает нетривиален, и должен учитывать информационные особенности си- туации, дополнительные сведения об игроках. (Мы еще остановимся на идее универ- сальной концепции с явными ожиданиями.) Теперь – о соотношении кооперативных концепций (P , C W , P W ) с различными некооперативные решениями. Не всегда, но часто результаты некооперативного поведения оказываются не оптималь- ными по Парето, как показывают следующие примеры. Пример 1.5 Покажем разнообразие возможных ситуаций совпадения или несов- падения некооперативных решений с кооперативными на примерах. В частности, можно разобрать все симметричные игры 2 × 2 с неодинаковыми выигрышами каждого участника. Для этого достаточно посмотреть все различные (с точностью до перестановок) расположения чисел 0,1,2,3 по матрице, и дополнить их симметрично полезностями второго игрока. Несколько подобных игр и одна игра с частично-совпадающими выигрышами приведены в таблице: Игры, где добровольная эффективная кооперация: -гарантирована, симметрична: "Симбиоз" -возможна, симметр.: "Только позови" 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 Таблица 10: Наиболее типичные игры 2х2 и проблема совпадения некооперативных решений с кооперативными. В таблице 10 представлены некоторые случаи (не-)совпадения кооперативных и некооперативных решений игр 2х2 (полный их обзор предлагается как упражнение). 26 В первой игре типа "Симбиоз"участникам незачем вступать в переговоры: наилучшее решение из ядра (С) и так сильно доминирующее (SDE). Во второй - аналогично, с той разницей, что есть еще два несимметричных потенциальных соглашения (С), одно выгодное для одного, а другое для другого. Но несимметричные здесь неустойчивы относительно некооперативного поведения. В игре "Цыплята"(кто быстрее клюнет добычу) два Нэшевских равновесия (N), оба из ядра, но одно выгоднее для одного, а другое для другого. Это создает борьбу за лидерство: кто первый займет выгодную позицию. Это осложняет переговоры. Игра "Только позови"демонстрирует два устой- чивых состояния, если она находится не в лучшем, то одному из партнеров достаточно предложить переключиться в лучшее – и партнер согласится. Четвертая пара игр типа "Дилеммы заключенных"представляет ситуацию, где взаимовыгодный вариант есть, но устойчивый компромисс маловероятен или даже невозможен, если не принуждать к выполнению соглашения. 1.7 Дополнительные примеры решений в непрерывных играх и 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-го о неблагоприятном поведении противника (максимин, который совпадает здесь с седлом из-за антагонизма игры). Легко проверить, что задача противника есть двойственная к описанной задаче. В обеих двойственных друг другу задачах есть допустимые решения, следовательно симплекс- методом можно найти седловую пару в игре G m . Она является и Нэшевской парой и максимином, по смыслу неравенств – ограничений. Для случая биматричной (то есть не обязательно антагонистической) игры задачи игроков не окажутся двойственными друг к другу, и поиск NE m методом линейного программирования не очевиден. Все же его общая идея - перебор возможных базисов (наборов активных ограничений) сохраняет ценность для поиска решений. В сущно- сти, нужно перебрать все гипотезы о возможных комбинациях стратегий применяе- мых с ненулевой интенсивностью (это не всегда все стратегии!), для обоих игроков. Например, рассмотрим повторяющуюся игру матери с сыном из известного детского стишка. 14 Сыну могут давать чаще или реже карманные деньги, в зависимости от того, часто ли от него пахнет табаком, а если пахнет сигарами - то пороть. Посчи- тайте вероятности (смешанные стратегии) при такой, например, матрице выигрышей 14 “...сын курил сигары по рублю за штуку. Мать, узнав об этом, дала сыну порку: не кури сигары, а кури махорку.” 27 (субъективных полезностей) исходов: Сын Мать Давать Не давать Пороть − − −− − − −− − − −− − − −− Не курить | + 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 . Ее сложное доказатель- ство не приводим. При нахождении равновесия по Нэшу, особенно в играх с непрерывными страте- гиями, можно воспользоваться понятием функции (отображения) отклика F i (x −i ) = X ∗ i (x −i ) определенном в (4). Тогда можно переформулировать определение NE так: Точка ¯ x является равновесием по Нэшу т. и т. т., когда ¯ x i ∈ F i (¯ x −i ) или ¯ x i = F i (¯ x −i ) ∀i ∈ I. (8) Здесь равенство – если функции F i (.) являются однозначными, тогда нэшевское равновесие задается просто системой уравнений и соответственно вычисляется. Найдем этим путем NE, StE в примере игры с непрерывными стратегиями. Пример 1.6 Рэкетиры (или орган налогообложения) выбирают, какую долю τ ∈ [0, 1] валовой выручки y забирать у фирмы. Они при этом максимизируют функцию вида T (τ, y) = τ y, то есть желают побольше получить. Фирма имеет функцию π(τ, y) = (1 − τ )y − y 2 , то есть максимизирует прибыль при квадратичной функции затрат выбирая объем продаж y ≥ 0. Найдем решения этой игры при различных гипотезах о поведении: 1)осторожном, 2)“близоруком” (ситуативном), 3)когда рэкетиры - лидер игры, знающий цели и просчитывающий ответы фирмы. 1) Осторожное равновесие (MM ). Оно не очень правдоподобно в рассматривае- мой ситуации: ведь участники должны бы знать ходы друг друга; но найдем MM для 28 примера. Самое худшее, что может сделать фирма с точки зрения рэкетира – не вы- пустить ничего: 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 за нулевой налог (кооперативное поведение). Очевидно, что ни од- но из перечисленных некооперативных равновесий не является Парето-оптимальным. 5) Ядро (C W ). Какова упомянутая сумма r достижимая в переговорах? Точки ядра не должны блокироваться ни одной коалицией: ни коалицией из обоих участников (т.е. должны принадлежать слабой Парето-границе), ни коалицией из одного участника. Если в качестве индивидуально достижимых выигрышей берем гарантированные ми- нимаксные выигрыши T (τ, y) = 0, π(τ, y) = 0, то ядро состоит из всех точек P. Если же считать, что лидирующее положение рэкета известно обоим участникам, то он считает гарантированным доходом свой доход 1/8 достижимый в равновесии Штакельберга, тогда ядро меньше Парето-границы: C = {τ = 0, y = 1/2, r ∈ [0, 1/2]}. Пример 1.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 типа решений. 29 1.8 “Равновесие дрожащей руки” (THNE) для нормальной фор- мы Ключевая идея эволюционных игр - это идея предыстории нынешнего, рассматривае- мого, равновесия. Мы увидим, что она разрешает многие недоумения в динамических играх, но и здесь, в статических она приносит важные плоды для сужения, очищения множества равновесий от неестественных. Определение 1.8.1 Равновесие дрожащей руки THNE - это такое равновесие Нэ- ша, что существует сходящаяся к нему вполне смешанная последовательность стратегий всех игроков (где нет неиспользуемых стратегий), ответом на все члены которой и является это равновесие Нэша. Пожалуй, наиболее убедительная трактовка THNE, как и обычного Нэша - именно эволюционная. Подразумевается, что перед данным розыгрышем была предыстория таких же игр, разыгранных подобными же участниками. И ожидания (веры) тепереш- них игроков о намечаемых стратегиях их партнеров взяты именно из предыстории. Особенно смешанные стратегии наиболее адекватны эволюционной трактовке: ‘в сред- нем’ мои партнеры ходят вот так. Требование, чтобы в предыстории они были вполне смешанными, означает, что у всякого игрока могла “рука дрогнуть”, и он вместо вы- годной стратегии иногда ходил случайной. Поэтому, все возможные ситуации игры наблюдались, и поэтому мы знаем, как вели себя в них прочие партнеры! Со вре- менем, предполагает концепция, иррациональность поведения уменьшалась, и сейчас сошла на нет, оставив только память о себе в виде ожиданий — память, важную для теперешних ходов. Главное то, что конецепция THNE снимает концептуальные проблемы в отношении неприменяемых обычно стратегий (вне пути игры): в предыстории у каждого игрока были моменты (не-рационального) применения любой стратегии, поэтому все пути игры когда-то наблюдались, и теперешние ожидания или веры появились не на пустом месте. 15 Для освоение THNE, вернемся к игре на Таб. 4: Victor x y An- a 101, 100 (NE) 1, 100 na b 101, 0 3, 2 (WDE) Таблица 11: Оправдание слабого доминирования - через THNE. Здесь, как говорилось, по слабому доминированию образуется невыгодное реше- ние b, y. Оно критиковалось с точки зрения некоторой популяции, где игроки могут 15 Но еще один концептуальный вопрос остается. В предыстории, сформировавшей мои теперешние представления о моих партнерах, вели ли игроки себя хотя бы отчасти рационально? Произвольность этой предыстории (вполне-смешанной последовательности, сходящейся к нынешнему равновесию) вызывает смутную неудовлетворенность, но не сразу ясно, в каких терминах ее выразить. Мы сде- лаем это так. Можно предполагать, что ‘дрожание руки’, то есть иррациональность игроков в ходе предыстории проявлялась специфическим образом. А именно, в силу каких-то причин, возможно недостаточного обдумывания, каждый игрок (тип игрока) время от времени ‘не замечал’ часть сво- их возможностей, и пользовался только оставшимися стратегиями. Но пользовался ими рационально! Это задает самое узкое сужение равновесий Нэша - ‘абсолютное равновесие’, не рассматриваемое в этом курсе. 30 не захотеть переходить от хорошего равновесия Нэша на (a, x) на индивидуально- нестрого-более выгодные позиции b и y, основательно опасаясь сползания популяции к малым выигрышам (3, 2) при (b, y). Теперь же, если мы верим в предысторию с дрожанием руки, то из двух равновесий Нэша остается только плохое, устойчивое к некоторым мутациям (вот что важно) IN D W 16 Так новая идея сужает множество решений Нэша и оправдывает применение IND W в определенных случаях. (Покажи- те, что всегда T HNE ⊇ IN D W ⊇ IND S .) А вот в игре из Табл. 6 принцип вполне-смешанной предыстории (дрожащей руки) исключит три плохих равновесия из четырех SDE сильно- доминирующих (очень бы хотелось, но это может сделать только коалиционное доминирование). Также, во второй игре из Табл. 1.6 новый принцип ни одного из двух NE не ис- ключит, а в первой исключит единственное целое равновесие НЭША (сохраняя только смешанное)! 1.9 О (не-)совпадении различных решений Приведем утверждения о соотношениях разных некооперативных концепций. Лемма 1.9.1 (см. Мулен, 1985 ) Попарно эквивалентны три случая: 1) IDE 6= ∅; 2) Все стратегии в N D эквивалентны; 3) IDE = N D. Теперь соберем вместе несколько фактов. Утверждение 1.9.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 . 17 3) SoE ⊂ NE ⊂ IN DS. 4) SNE ⊂ INDW , причем если SoE 6= ∅, то SNE ⊂ SoE. 5) Обозначая через NE( I ND) решение Нэша в редуцированной по доминированию игре, можно утверждать NE( I NDS) =NE, NE( I NDW ) = 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 ). Продолжая аналогичные рассуждения, по индукции получим, 16 Устойчивость ко ВСЕМ мутациям обсуждается ниже в “эволюционном равновесии”. 17 Последнее вложение сравните на игре Табл. 6 и Табл. 12. 31 что в финальном множестве есть стратегия не хуже, чем ˜ x 1 , - противоречие. (ср. доказательство SoE ⊂ NE в [Мулен, 1985, Теорема 1, стр 74]). Вложение 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 совпадает со строго доминирующим равновесием (если то непусто), но может лежать вне отдельной строго доминирующей стратегии(!), как в Табл. 12, и не совпадать ни с итерационно-недоминируемым, ни с Нэшевским решением. Victor x z An- a 101, 0 1, 1 (SoE) na b 100, 100 (StE) 0, 0 Таблица 12: Несовпадение SoE и StE. Утверждение 1.9.3 В конечной антагонистической игре двух лиц SoE ⊂ Sad. Следствие: если SoE 6= ∅ (игра разрешима по доминированию), то у игры есть цена (игра разрешима и по принципу седла). Доказательство см. в [Мулен, 1985, Лемма 4, с. 49]. Кооперативные концепции легко сравнить по определениям: Утверждение 1.9.4 Ядро принадлежит слабой Парето-границе, а сильное ядро — сильной (обычной) Парето-границе: C W ⊂ P W , C s ⊂ P ⊂ P W . Совпадение или несовпадение кооперативных концепций (P , C W , P W ) с различ- ными некооперативные решениями мы уже обсуждали, и видели что часто результаты некооперативного поведения оказываются не оптимальными по Парето (см. примеры). 1.10 О существовании и компактности множеств решений Утверждение 1.10.1 Если все допустимые множества X i компактны, функ- ции u i непрерывны, то 1) P 6= ∅; 2) множества IDE, MM, NE, P W компактны. 3) также непусты множества: осторожных решений (MM 6= ∅), решений Шта- кельберга, (StE 6= ∅), множества итерационно- недоминируемых стратегий (IN DS ⊇ INDW 6= ∅). 32 Доказательство (см. в [Мулен, 1985, с. 79] более подробное доказательство этой теоремы.). Пункт (1) и компактность MM – см. [Мулен, 1985„ стр. 26]. Пункт (2): компактность NE проверена в теореме Нэша (ниже), а компактность IDE доказы- вается опираясь на приведенную лемму (докажите самостоятельно) [Мулен, 1985]. Компактность слабой Парето-границы доказывается рассмотрением пределов. 3) Непустота множеств MM, StE, INDW при конечности X i очевидна из опреде- лений. Для случая компактных множеств доказательство существования MM, StE - по теореме Вейерштрасса, учитывая для StE теорему Нэша. Рассмотрим вложенную последовательность допустимых множеств X = N D 1 ⊃ N D 2 ⊃ ... ⊃ N D k ... заданную определением IN DW . На каждом шаге последующее множество 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(.) применима теорема Какутани о неподвижной точке, 18 следовательно имеется неподвижная точка ˜ x : ˜ x ∈ Q i X ∗ i (˜ x −i ), то есть ˜ x ∈ NE, что и требовалось. Для проверки компактности NE можно построить последовательность неподвиж- ных точек {˜ x t } t=1,2,... ∈ NE сходящуюся к некоторой точке ¯ x. Равновесность каждого элемента последовательности ˜ x t ∈ NE, в терминах неравенств (3) сохраняется и в пределе, что завершает доказательство. [[[]]]] Для доказательства Следствия 2.1 достаточно проверить, что рассматриваемое в нем смешанное расширение G m исходной конечной игры удовлетворяет условиям те- оремы. Действительно, выпуклая оболочка любого конечного множества стратегий есть выпуклый компакт. Кроме того, матожидание полезности U i (σ 1 , ...σ n ) определен- ное в (5), есть не только непрерывная, но и линейная (следовательно вогнутая) по переменным σ i функция, что и требовалось для применения Т.Нэша. [[[]]]] 18 Теорема Какутани о неподвижной точке: замкнутое (т.е. имеющее замкнутый график) выпукло- значное отображение F(.) выпуклого компакта X в себя имеет неподвижную точку x : x ∈ F(x). 33 |