ИРФ с несовершенной информацией. СПРН и модификация метода обратной индукции.

Лекция 9 Тема 10. ИРФ с несовершенной информацией. СПРН и модификация метода обратной индукции. ( [1] Главы (Chapter) 13; [2] Глава 2, 2.1.5! ) ИРФ с полной но не совершенной информацией. Подыгры. Рассмотрим дерево ИРФ G с полной но не совершенной информацией. Дерево (игра) содержит информационные множества, состоящие из более чем одного узла. Рассмотрим информационные множества, состоящие из одного узла. Пусть У такой узел. ** Поддеревом G(У), с вершиной У, называется совокупность всех дуг и узлов на всех путях, идущих из У в терминальные узлы (т.е. с началом в У и концом в терминальных узлах). Игра, определяемая поддеревом с корнем в узле У, состоящим из всех путей, выходящих из узла У и заканчивающихся в каком либо терминальном узле дерева G Уточним определение подыгры. Говорим, что поддерево G(У) определяет подыгру G(У), если выполняются дополнительные условия. 1 *** Пусть дана ИРФ G. Подыгра G(У) игры G— это поддерево дерева игры G с вершиной У, удовлетворяющее следующим свойствам: 1. У — единственный элемент в своем информационном множестве. 2. Информационные множества, содержащие вершины из Подыгры G(У) не содержат вершин, лежащих вне Подыгры G(У). (1) Из определения самого информационного множества (ИМ) следует, что * Из всех вершин информационного множества (ИМ) выходит одинаковый комплект дуг (ходов) с одинаковыми альтернативами ! (2) Важность свойств (1) и (2) : обсуждение……………… Примеры неправильного изображения дерева Игры с несовершенной информацией: ……………………… 2 V1: A N B, V2: B A N, V3: N A B 3 Модификация метода обратной индукции для ИРФ с несовершенной информацией. Метод Обратной Индукции в том виде, в каком он применяется для ИРФ с совершенной информацией может быть неприменим для ИРФ с не совершенной информацией из-за неоднозначности в больших информационных множествах! Но используется его немного «модернизированный» вариант, который позволяет находить Совершенные по Подиграм Равновесия Нэша (СПРН)! Пример 3. [2], стр. 98. Вариация игры «Сжигание мостов». Генерал должен защищать город на берегу реки. До того как враг нападает, генерал принимает решение, сжигать мост, соединяющий город с другим берегом (B) или нет (N). (Враг нападает в любом случае). Далее командиры двух отрядов (подчиненные генерала) принимают решение: бежать с поля боя (R) или нет (F). Их выигрыши в двух случаях различны. Выигрыш генерала равен 1, если город остался защищать хотя бы один отряд, и 0, если оба отряда бежали. Дерево этой игры : 4 Игру можно решить «модернизированным» методом ОИ. Лекция ….. 2. Совершенные по Подиграм Равновесия Нэша (СПРН)! 5 Опишем Алгоритм «Модернизированного» метода Обратной Индукции (М-ОИ метода) подробнее. Подыгра G(У) игры G называется простой, если не содержит в себе другой подыгры, отличной от самой G(У). (Аналог финальной вершины в ИРФ с совершенной информацией.) Описание Итерации в Алгоритме ОИ. Имеем начальную (или текущую) Игру G. Шаг 1.  Выделим в Игре G множество (G) простых Подыгр в игре G.  Для каждой простой Подыгры G(У) из (G) осуществляем следующее: Находим все РН в G(У), возможно и в смешанных стратегиях. Каждому найденному РН будет соответствовать свой вариант решения игры G. Для каждого РН: фиксируем стратегии и соответствующий исход закрепляем за узлом У. 6 Шаг 2. Рассматриваем и фиксируем каждый из найденных вариантов.  Запоминаем, что записали и закрепили на предыдущем Шаге 1.  Удаляем (временно) из дерева Игры G все рассмотренные подыгры.  Вершины У «удалённых» Подыгр вместе с ранее закреплёнными за ними исходами (списками выигрышей) объявляем "новыми" терминальными узлами.  Получаем новую, "укороченную", Игру ̆, в которой множество ̆0 терминальных узлов состоит из оставшихся старых и объявленных "новых" терминальных узлов: Переходим к следующей Итерации (где вместо G рассматривается уже Игра ̆ ). Итерации осуществляем до тех пор, пока не получим простейшую Игру (Дерево) с множеством ( ̆) , состоящим из одного узла - корня Начальной Игры (Дерева) G. 7 После последней Итерации, восстанавливая в обратном порядке Дерево начальной Игры и соответствующие записанные ходы Игроков, получаем для каждого Игрока i соответствующую Стратегию =( , ... ,... , и М-ОИ-профиль ). Теорема ( ОИ и СПРН в играх ИРФ с не совершенной информацией). Профили стратегий, получаемые в ИРФ с не совершенной информацией «модернизированным» методом Обратной Индукции являются СПРН. Рассмотрим подробнее насыщенный пример «Голосование». 8 V1: A V1: A N N B, B, V2: B V2: B A A N, N, V3: N V3: N A A B B 1; 0; -1 9 Лекция Разбор: …… !!!! Д/З Почему это будет тоже СПРН ??? !!!! Д/З Найти ещё другие СПРН, и объяснить !!!! (На хор. Бонус!!!) ……………………… 10 Пример 4. [2], стр. 98 Подробный разбор: Лекция ………….. 11 …………………. 1) Таким образом, понятие совершенства по подыграм предполагает не только то, что все игроки ожидают, что во всех подыграх будут реализовываться равновесия Нэша, но и то, что игроки во всех подыграх ожидают реализации одних и тех же равновесий Нэша !. 2) Концепция СПРН также требует следующее очень сильное свойство рациональности: с какой бы подыгры не началась Игра, игроки всегда играют в этой подыгре РН. И вне зависимости от «прошлого» играют сами и верят, что и другие будут играть РН. Обсуждение …. 12