Бесконечно повторяющиеся ИРФ с несовершенной информацией. СПРН в Бесконечно повторяющихся ИРФ.

Лекция 11 Тема 12. Бесконечно повторяющиеся ИРФ с несовершенной информацией. СПРН в Бесконечно повторяющихся ИРФ. ( [1] Главы 15, 16; [2] Глава 2 , разделы 2.2; 2.2.2; [7], Лекции 7, 8) Все условия те же, что и в конечно повторяемых Играх, только теперь базовая Игра G играется бесконечное число раз. Обозначим эту бесконечно повторяющуюся игру: G(). ** Интересно отметить , что Подыгра G(t, ), как поддерево, начинающееся с любого момента t , совпадает с самой Игрой G() !!! ** Хотя на эти одинаковых поддеревьях могут разыгрываться разные стратегии!!! **Но нас интересуют "хорошие " стратегии, т.е. совершенные по подыграм равновесия Нэша (СПРН)! Имеем Фрактальность структуры дерева игры!!! 1 Поэтому, СПРН s* должно порождать своё СПРН в каждой G(t, ) при любом развитии событий (по сценарию СПРН) до любого момента t ! (1) Как оценивать результаты (выигрыши) Игроков в G()? 1. Суммировать выигрыши нельзя! (Почему?) 2. Средний выигрыш на одно повторение - не очень подходит, т.к. могут быть проблемы. ** Наиболее удобно и принято рассчитывать выигрыш игрока во всей игре как, как дисконтированную сумму выигрышей в отдельных повторениях. Обозначим эту бесконечно повторяющуюся игру c коэффициентом дисконтирования  G(,  ). Через Коэффициент дисконтирования 0   ˂ 1 аналогичен (в обратном смысле) банковскому проценту. Он позволяет оценить текущую стоимость выигрыша в произвольном повторении. Пусть { , ...} бесконечная последовательность выигрышей Игрока i во всех повторениях базовой Игры G. , ..., Тогда текущая стоимость выигрыша Игрока i в игре G(, ) определяется по формуле : Vi = ∑  = ∑  (2) 2 Иногда желательно как то сравнить выигрыши в игре G(, ) с выигрышами в базовой игре G. Для этого удобно ввести условную нормировку выигрышей в G(, ) положив: = (1 - )Vi , исходя из равенства ∑  =  (3) si игрока i в бесконечно повторяющейся игре G(, ) есть бесконечная последовательность функций : si = { , ..., , ...}, *** Стратегия где каждая - правило, по которому Игрок i выбирает ход в t – повторении Игры G в зависимости от всех ходов , сделанных игроками в предыдущих повторениях. Заметим, что число (чистых) стратегий в G(, ) не просто бесконечно, но континуально ! **Нас интересуют "хорошие " стратегии и профили, т.е. равновесия Нэша (РН), и совершенные по подыграм равновесия Нэша (СПРН)! 3 Пример 3. Бесконечно повторяющаяся базовая игра G "Дилемма заключённых". C Знаем, что РН (С, С) не эффективное! Хочется заменить его на повторение эффективного кооперативного исхода (N, N) в игре C N G(, ) , но так, чтобы в результате получилось СПРН. 1; 1 5; 0 Для этого используем т.н. называемые релейные (или тригерные) N 0; 5 4; 4 Таблица 4 стратегии . **Рассмотрим пример релейной 1. 2. стратегии ={ , .., = N , если все игроки во всех предыдущих повторениях выбирали N. = С в противном случае. , ...} (4) ** Каждый игрок придерживается кооперативного поведения N пока все тоже действуют кооперативно. Как только первый раз произошло отклонение от кооперативного поведения, все игроки переходят на индивидуально - рациональное поведение С . Релейные стратегии - это стратегии с одним переключением и без возврата!. (Это - Жёсткие Релейные стратегии ) 4 ** Заметим, что если произошло переключение на повторение (С, С), то это соответствует требованию СПРН, как и в конечно повторяющихся играх. *** Исследуем, когда (Жёсткая) релейная стратегия будет СПРН? Для этого рассмотрим отклонение от равновесной релейной стратегии . Отклонившийся Игрок получит максимальный выигрыш 5 в момент отклонения, но потом выигрыши 1 во все остальные моменты времени! Этот вариант в СПРН должен быть не лучше, чем, получения выигрыша 4 в каждом повторении! ...  .... , или …………… , ** Если   или   (5) , то повторение кооперативного профиля (N, N) становится РН и даже СПРН! Этот способ построения СПРН на основе подобных релейных стратегий переносится на любые бесконечно повторяющаяся игры G(, ) ! 5 Пример 4. Базовая игра G "Дилемма заключённых". Знаем, что РН (С, С) не эффективное! Заменим его на повторение более эффективного кооперативного поведения, т.е. на C N соответствующие стратегии вG(, ) , но так, чтобы в результате 0; 0 7; -2 получилось СПРН (или РН). -2;7 5; 5 Для этого используем ещё один вариант жёстких релейных Таблица 4 C N (тригерных) стратегий. Профиль ={ 1. Правило 1: на шагах с нечётными номерами чётными номерами , .., игроки разыгрывают (C, N), с - разыгрывают (N, С). 2. Как только кто либо отклонился от Правила 1 на шаге и до , ...} , со следующего шага + 1 все играют РН (С, С). (6) Когда никому не выгодно отклоняться? Игрок 2 (на чётном шаге): если выберет С вместо N, получит 0 вместо -2. ……. + …… = ⟹    2 (7)  6 Пример 5. Базовая игра G "Дилемма заключённых" (та же). Вид наказания: «наказание с прощением», или «тригер с забыванием», «forgiving trigger». Профиль ={ , .., , ...} 1. Действовать по Правилу 1: а. на всех шагах все играют (N, N ). б. Как только кто либо отклонился от (N, N ) на шаге со следующего шага + 1 все играют (С, С) Т раз. 2. После реализации б. снова играть по Правилу 1. , (8) Когда никому не выгодно отклоняться? Пусть Игрок вместо N сыграл С. ……………………………………..   Тогда: 7 …………………. Обсуждение ………. 7 Возможности использования релейных стратегий понимали многие исследователи и потому следующий результат называется в литературе "Народной" теоремой (Folk Theorem). "Народная" теорема (Folk Theorem) («простая» версия). Пусть G - базовая конечная статическая игра. G = { =( , ) - РН в игре G. вектор выигрышей при Пусть =( , , ; u1( p ), u2 (p)} (р*) выигрыш игрока i в этом РН, ̅ = ( = , )- . ) - произвольный профиль стратегий в G и такой, что выигрыши ( )  ( ) = , i = 1, 2. Тогда существует коэффициент дисконтирования  , достаточно близкий к 1, такой, что игроков при нём больше , чем при , = в повторяющейся игре G(, ) существует СПРН, в котором каждый игрок получает средний нормированный выигрыш = , ̅=( , ) *** Смысл Релейных стратегий в том, что они устойчивым образом реализуют совместный план эффективных действий, с помощью взаимного стимулирования и угроз. 8 Схема и метод доказательства "Народной" теоремы : Пусть каждый Игрок i использует релейную стратегию 1. 2. ={ , .., , ...} , если все игроки во всех предыдущих повторениях выбирали = = . в противном случае. При отклонении от Игрок i может получить не больше, чем = ui ( , )= ui ( , ) , Условие невыгодности отклонения: ⟹  При таких ⟹   профиль +  max { =( ,   (6) } ) является СПРН. 9 Оказывается, с помощью обобщённых релейных стратегий можно строить профили с векторами выигрышей из множества векторов G ( ). G ( ) из Примера 3, G - "Дилемма заключённых". ̃ - Заштрихованная часть на множестве возможных векторов нормированных выигрышей соответствует таким векторам, где выигрыши больше, чем в РН (С. С) и при этом могут быть получены с помощью обобщённых релейных стратегий как СПРН в G(, ). U - (Ромб ) – выпуклая оболочка векторов выигрышей в чистых стратегиях. (̅). ̅=( , ) = (1, 1). =( , ) = (С, С) Тогда ̃= U (̅) (7) 10 *** Для построения СПРН в G(, ) существуют различные интересные и полезные обобщения Релейных стратегий, как специально сконструированные планы совместных (кооперативных) действий с более сложными правилами переключения. Рассмотрим некоторые из этих обобщений (на примере G из Примера 4). *** Определим понятие базового динамического Цикла. Это последовательность действий Игроков: Т1 раз они играют (N, N), затем Т2 раза (С, С), Т3 - (N , С) и Т4 раза (С, N) (возможно Тi = 0). После этих Т = Т1 + Т2 + Т3 + Т4 игр цикл повторяется. Назовём цикл "индивидуально рациональным" или просто "хорошим", если суммарный выигрыш каждого Игрока i за Т игр в цикле - положительный. Обозначим этот выигрыш Pi (T). Рассмотрим Обобщённую релейную стратегию 1. 2. ={ , .., , ...} Игрока i = { ходить в соответствии с выбранным Циклом, если все делают также}. = С в противном случае, (6) 11 Тогда "Народная Теорема" (обобщённая версия) утверждает, фактически, следующее: *** Для любого заданного "хорошего" динамического Цикла последовательность Циклов в G(, ) реализуются как РН и СПРН с помощью обобщённых релейных стратегий при достаточно большом (близком к единице)  !!! **** Потери Игрока при отклонении от последовательности Циклов - это наказание ему за это отклонение. В Обобщённых релейных стратегиях существуют различные механизмы наказаний, отличные от рассмотренного выше. Могут быть мягкие варианты, когда Игроки через некоторое время (в течении которого они "исправились") снова возвращаются к "хорошим" Циклам. В расчётах, при решении задач можно считать , что дисконтированный выигрыш Игрока i , реализующего – совместно с другими игроками – «хороший» базовый динамический Цикл всю игру c самого начла, равен, приблизительно, 12 Pi (G(, ))  (8) Пояснения…… Некоторые выводы и следствия из Народной теоремы. (На примере G из Примера 4) 1. Все профили с базовыми циклами и положительными выигрышами могут быть равновесными при  близком к 1. 2. Стратегий с базовыми циклами достаточно, что бы получить любой вектор с положительными выигрышами. 3. Будущие выигрыши значимы! 4. Существует  Равновесий (РН и СПРН). 5. Из недостатков: мгновенное обнаружение нарушений и мгновенное наказание. …….. 13 Бесконечно повторяющиеся ИРФ с несовершенной детекцией нарушений и не мгновенным тригером. Мы можем рассматривать выигрыши как средние (усреднённые). Таблица 4 C N C 0; 0 7; -2 N -2;7 5; 5 Обычно: действия фиксируются не сразу, а выигрыши – сразу. Например, выигрыши в РН (С, С) как (x, y). Если видим (x, y), то … …разные вероятности …………. Поэтому, если видим (x, y), нужно решать : тригер или пока нет? ⟹ Пороговая тригерная стратегия: определяется пороговым числом М следующим образом: П1. Все играют (N, N) пока выигрыши у каждого выше, чем М в каждой игре G. Как только у кого – либо станет меньше М, все играют (С, С) Т раз. П2. Затем все возвращаются к П1. Когда пороговая стратегия будет равновесием – РН или СПРН ? Как влияют на это М и Т ? Обсуждение …………….. 14 1. Чем больше Т, тем вероятнее, что профиль будет РН (СПРН) …. 2. Чем более строже (больше) М, и чем больше Т, тем менее выигрышная стратегия. Т.е. противоречие: чем строже мониторинг, тем меньше выигрыш. Пусть – вероятность тригера, т.е. вероятность …….. (15) ………………………………….. …………………………………… Обсуждение …… 15 Всегда ли Тригерные РН являются СПРН ??? Нет! Равновесие, полученное при использовании триггерных стратегий, часто не является совершенным по подыграм!! Пример. ([2] Глава 2 , раздел 2.2.2, стр. 125) Пусть при некотором  в повторяющейся дилемме заключенного Таблица 4 H 1; 1 5; 0 существует равновесие в триггерных стратегиях, обеспечивающее ходы (D,D) в каждый момент времени. Предположим, что в момент t=1 игрок 2 в повторяющейся дилемме заключенного выбрал следующую D 0;5 стратегию: играть H в этот момент и играть триггерную стратегию во все H D 3; 3 последующие периоды. …………………………… ……………………………………………… 16 Рассмотрим пример совершенного равновесия в следующей игре, повторяемой бесконечное число раз: Пример: [2] Глава 2 , раздел 2.2.2, стр. 127) На рис. показано совершенное по подыграм равновесие, в котором Выигрыш игроков будет u=(4; 4), что соответствует действиям a = (A; A) в каждом периоде. 17 Обсуждение этого вопроса… 18 Некоторые популярные игровые модели в литературе, где используются бесконечно повторяющиеся игры G(, ) и специальные релейные стратегии: 1. Сговор в повторяющихся олигополиях Курно; 2. Модели эффективной зарплаты (повторяющиеся переговоры фирмы и работника); 3. Модель денежной политики и управления инфляцией; 4. Модель функционирования фондового рынка, (NASDAQ), Гл. 16, [1]; 5. Модель ценообразования на нефтяном рынке Гл. 17, [1]; 6. Модель анализа проблемы Трагедии Общин Гл. 18, [1]; и другие. 19