Позиционные игры

Позиционные игры Содержание лекции Позиционные игры Основные понятия Пример позиционной игры Нормализация позиционной игры Дерево решений Пример анализа дерева решений Литература 1. Гадельшина, Г. А. Введение в теорию игр : учебное пособие / Г. А. Гадельшина, А. Е. Упшинская, И. С. Владимирова. — Казань : Казанский национальный исследовательский технологический университет, 2014. — 112 c. — ISBN 978-5-7882-1709-3. — Текст : электронный // Электронно-библиотечная система IPR BOOKS : [сайт]. — URL: http://www.iprbookshop.ru/61829.html (дата обращения: 13.05.2020). — Режим доступа: для авторизир. Пользователей 2. Красс, М. С. Математика в экономике: математические методы и модели : учебник для бакалавров / М. С. Красс, Б. П. Чупрынов ; ответственный редактор М. С. Красс. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2019. — 541 с. — (Высшее образование). — ISBN 978-5-9916-3138-9. — URL : https://urait.ru/bcode/426162 Позиционные игры Часто игроками в процессе принятия решения совершается ряд последовательных во времени шагов. Например, игра в «крестики-нолики» или «шахматы». Позиционные игры Стороны могут совершать последующие шаги в зависимости от складывающейся обстановки, они используют стратегии, отражающие динамику конфликта. Одним из классов игр, описывающих конфликты, динамика которых оказывает влияние на поведение участников, являются так называемые позиционные игры. Позиционные игры Позиционная игра - это бескоалиционная игра, моделирующая процессы последовательного принятия решений игроками в условиях меняющейся во времени информации. Обычно позиционную игру представляют в виде древовидного графа. Позиционные игры Корень дерева - начальный ход игры. В каждом узле указывается, кто из игроков ходит. А дуги соответствуют выбору игроков на очередном ходе. Узлы игры принято называть позициями (отсюда и название - позиционные игры), а возможные выборы в каждой позиции альтернативами Основные понятия О 1 1 В А 1 2 1 2 2 1 А А 2 1 В 2 А 2 1 2 Символами О, А и В обозначены игроки, которые делают ход. При этом символом О обычно обозначается ход в игре, осуществляемый не игроком, а природой, то есть случайным образом. Сначала делает ход игрок О. У него существует две альтернативы: выбрать единицу или двойку. Второй ход делает игрок В, который также может сходить единицей или двойкой, и последним делает ход игрок А. Основные понятия Процесс позиционной игры состоит в переходе от начальной позиции к конечной через ряд промежуточных позиций. В результате образуется цепь (последовательность идущих друг за другом звеньев), связывающую начальную вершину с конечной. Такая цепь называется партией. На рисунке одна из партий выделена жирным шрифтом Основные понятия Число различных партий равно числу окончательных вершин. В каждой окончательной позиции должен быть задан числовой выигрыш игрока А. Также, как и в матричных играх, выигрыш игрока В отличается от выигрыша А только знаком. Если выигрыш отрицателен, это является проигрышем. Основные понятия Различают позиционные игры с полной информацией и позиционные игры с неполной информацией. В позиционных играх с полной информацией (шашки, шахматы) каждый игрок при своем ходе знает ту позицию дерева игры, в которой он находится. Основные понятия В позиционных играх с неполной информацией игрок, делающий ход, не знает точно, в какой именно позиции дерева игры он фактически находится. Этому игроку известно лишь некоторое множество позиций, включающее в себя его фактическую позицию. Основные понятия Такое множество позиций называется информационным множеством. Позиции, принадлежащие одному и тому же информационному множеству, объединяются пунктирными линиями. Пример позиционной игры Рассмотрим игру: игрок А выбирает число 1 или 2, игрок В выбирает число 1 или 2. Первым ходит игрок А. Второй ход делается игроком В. Игра с исходами игрока А имеет вид 1 1 В 2 А 2 В 1 2 -3 -5 2 2 Пусть игрок В знает, какой ход сделал игрок А. Поэтому, если игрок А выберет «1», очевидно, что игрок В выберет «2», и его выигрыш составит «3». Если игрок А выберет «2», то игрок В выберет «1», и его выигрыш составит «5». Когда игроку В известно, какой ход сделал А,он всегда будет выигрывать. Пример позиционной игры Пусть игрок В не знает хода игрока А, поэтому обе его возможные позиции объединены в информационное множество, на рисунке отмеченное пунктиром. В этом случае, если игрок В выбирает «1», то он может проиграть либо «2», либо выиграть «5». Если же игрок В выберет «2», он может выиграть «3» или проиграть «2». Скорее всего, игрок В будет ходить «1». 1 1 В 2 А 1 2 В 2 2 -3 -5 2 Игроку В ход А неизвестен, поэтому проигрывает или выигрывает игрок В зависит от хода игрока А. Нормализация позиционной игры Каждый игрок в ходе игры может использовать различную последовательность ходов. Каждую из заранее определенных последовательностей ходов игрока будем называть чистой стратегией этого игрока. В том случае, если в игре нет случайных ходов (игрок О в игре не участвует), выбор игроком А и игроком В чистых стратегий однозначно определяет исход игры приводит к окончательной позиции, где игроки А и В получают свои выигрыши. Это обстоятельство позволяет сводить позиционную игру к матричной игре. Процесс сведения позиционной игры к матричной называется нормализацией позиционной игры, а соответствующую матричную игру называют стратегической, или нормальной формой позиционной игры Пример нормализации позиционной игры  "Дерево" решений «Дерево» решений применяют тогда, когда нужно принять несколько взаимосвязанных решений в условиях неопределенности в случае принятия решения, зависящего от исхода предыдущего или исходов испытаний "Дерево" решений Составляя дерево решений, рисуют "ствол" и "ветви", отображающие структуру проблемы. Располагают "дерево" решений слева направо. "Ветви" обозначают возможные альтернативные решения, которые могут быть приняты, и возможные исходы, возникающие в результате этих решений. "Дерево" решений На практике результат одного решения приводит к необходимости принятия следующего решения и т.д. Эту последовательность принятия решений нельзя выразить матрицей доходов, поэтому приходится использовать другой алгоритм принятия решений. "Дерево" решений Графически подобные процессы могут быть представлены с помощью "дерева" решений. Такое представление облегчает описание многоэтапного процесса принятия решения в целом. "Дерево" решений Квадратные "узлы" на дереве решений обозначают места, в которых принимаются решения, круглые "узлы" места исходов. Так как не представляется возможным влиять на появление исходов, то в круглых узлах вычисляют вероятности их появления. "Дерево" решений Когда все решения и их исходы указаны на "дереве", оценивается каждый из вариантов и проставляются денежные доходы. Все расходы, вызванные решениями, проставляются на соответствующих "ветвях" Пример анализа дерева решений Фирма может принять решение о строительстве среднего или малого предприятия. Малое предприятие впоследствии можно расширить. Решение определяется будущим спросом на продукцию, которую предполагается выпускать на сооружаемом предприятии. Строительство среднего предприятия экономически оправданно при высоком спросе. С другой стороны, можно построить малое предприятие и через два года его расширить. Пример анализа дерева решений Фирма рассматривает данную задачу на десятилетний период. Анализ рыночной ситуации показывает, что вероятности высокого и низкого уровней спроса равны 0,7 и 0,3 соответственно. Строительство среднего предприятия обойдется в 4 млн р., малого — в 1 млн р. Затраты на расширение через два года малого предприятия оцениваются в 3,5 млн р. Ожидаемые ежегодные доходы для каждой из возможных альтернатив:  среднее предприятие при высоком (низком) спросе дает 0,9 (0,2) млн р.;  малое предприятие при низком спросе дает 0,1 млн р.;  малое предприятие при высоком спросе дает 0,2 млн р. в течение 10 лет;  расширенное предприятие при высоком (низком) спросе дает 0,8 (0,1) млн р.;  малое предприятие без расширения при высоком спросе в течение первых двух лет и последующем низком спросе дает 0,1 млн р. в год за остальные восемь лет. Определить оптимальную стратегию фирмы в строительстве предприятий. Пример анализа дерева решений Данная задача является многоэтапной, так как если фирма решит строить малое предприятие, то через два года она может принять решение о его расширении. В этом случае процесс принятия решения состоит из двух этапов: решение в настоящий момент времени о размере предприятия и решение о необходимости его расширения, принимаемое через два года. Пример анализа дерева решений Предполагается, что спрос может оказаться высоким и низким. Дерево имеет два типа вершин: "решающие" вершины, обозначенные квадратными узлами, и "случайные" вершины, обозначенные круглыми узлами Пример анализа дерева решений Пример анализа дерева решений Начиная с вершины 1, являющейся "решающей", необходимо принять решение относительно размера предприятия. Вершины 2 и 3 являются "случайными". Фирма будет рассматривать возможность расширения малого предприятия только в том случае, если спрос по истечении первых двух лет установится на высоком уровне. Поэтому в вершине 4 принимается решение о расширении или нерасширении предприятия. Вершины 5 и 6 будут "случайными". Пример анализа дерева решений Произведем расчеты для каждой из альтернатив. Вычисления начнем со 2-го этапа. Для последних восьми лет альтернативы, относящиеся к вершине 4, оцениваются так: где ДР — доход с расширением, ДБР — доход без расширения предприятия. В вершине 4 выгоднее не проводить расширение, при этом доход составит l,36 млн р. Пример анализа дерева решений Теперь для дальнейших расчетов оставим одну "ветвь", выходящую из вершины 4, которой соответствует доход 1,36 млн р. за остальные восемь лет. Перейдем к вычислениям 1-го этапа. Для вершины 1 где ДС — доход среднего предприятия, ДМ — доход малого предприятия. Сравнивая получаемые в вершине 1 доходы среднего и малого предприятий, видим, что более предпочтительным является вариант строительства среднего предприятия. Таким образом, фирме целесообразно построить среднее предприятие. Задача о замене оборудования в условиях неопределенности и риска Фирма может принять решение о замене старого оборудования на новое того же вида или его ремонте. Отремонтированное оборудование впоследствии можно частично заменить на новое, более современное, или отремонтировать его заново. Решение определяется продукцию, которую оборудовании. будущим спросом на производят на этом Задача о замене оборудования в условиях неопределенности и риска Полная замена оборудования экономически оправданна при высоком уровне спроса. С другой стороны, можно отремонтированное старое оборудование и через один год, например, заменить на новое, более совершенное, или заново его отремонтировать. В данной задаче процесс принятия решения состоит из двух этапов: решение в настоящий момент времени о замене или ремонте оборудования и решение, принимаемое через один год, относительно частичной его замены и ремонта. Задача о замене оборудования в условиях неопределенности и риска Рассмотрим конкретную задачу о замене оборудования фирмы, представленную в виде "дерева" решений. Предполагается, что спрос может оказаться высоким, средним и низким. Предположим, что фирма рассматривает эту задачу на пятилетний период. Анализ рыночной ситуации показывает, что вероятности высокого, среднего и низкого уровней спроса составляют 0,6, 0,3 и 0,1 соответственно. Замена новым оборудованием того же вида, что и старое, обойдется в 2,5 млн р., а ремонт старого — в 0,8 млн р. Задача о замене оборудования в условиях неопределенности и риска Затраты на частичную замену оборудования на более совершенное, чем старое, оцениваются в 1,5 млн р., а повторный ремонт старого — в 0,8 млн р. Ежегодные доходы для каждой стратегии фирмы следующие. 1. Замена старого оборудования на новое того же вида при высоком, среднем и низком уровнях спроса дает 0,95; 0,7 и 0,45 млн р. соответственно. 2. Ремонт старого оборудования при высоком, среднем и низком уровнях спроса оценивается в 0,3; 0,15 и 0,1 млн р. соответственно. Задача о замене оборудования в условиях неопределенности и риска 3. Частичная замена оборудования на более совершенное при высоком, среднем и низком уровнях спроса составит 0,9; 0,6 и 0,4 млн р. соответственно. 4. Повторный ремонт старого оборудования при высоком, среднем и низком уровнях спроса предполагает 0,3; 0,2 и 0,1 млн р. соответственно. Определить оптимальную стратегию фирмы в замене оборудования. Дерево имеет два типа вершин: "решающие" и «случайные» Задача о замене оборудования в условиях неопределенности и риска Задача о замене оборудования в условиях неопределенности и риска Начиная с "решающей" вершины 1 необходимо принять решение о полной замене оборудования или его ремонте. Вершины 2 и 3 являются "случайными". Фирма будет рассматривать возможность установления более совершенного оборудования или повторного ремонта старого в том случае, если спрос по истечении одного года установится на высоком уровне. Поэтому в вершине 4 принимается решение о частичной замене старого оборудования более совершенным или ремонте старого. Вершины 5 и 6 "случайные". Задача о замене оборудования в условиях неопределенности и риска Оценим результаты каждой стратегии и определим, какие решения следует принимать в "решающих" вершинах 1 и 4. Вычисления начнем с этапа 2. Для последних 4 лет альтернативы, относящиеся к вершине 4, оцениваются так: где ДЧЗ — доход от частичной замены оборудования на более совершенное, ДДР — доход от замены оборудования, прошедшего дважды ремонт. Так как ДЧЗ > ДДР, то в вершине 4 выгоднее произвести частичную замену оборудования на более совершенное, при этом доход составит 1,54 млн р. Задача о замене оборудования в условиях неопределенности и риска Для дальнейших расчетов в вершине 4 можно оставить одну ветвь, которой соответствует доход в 1,54 млн р. за 4 года. Вычислим доходы на 1-м этапе для "решающей" вершины 1: где ДЗН — доход от замены старого оборудования на новое того же вида, ДЗО — доход от отремонтированного оборудования и дальнейшей замены на более совершенное. Так как ДЗН > ДЗО, то оптимальным решением в вершине 1 является полная замена старого оборудования на новое того же вида. Задача о замене оборудования в условиях неопределенности и риска Ответ: Оптимальной стратегией фирмы в замене оборудования является полная замена старого оборудования на новое того же вида, при этом доход составит 1,625 млн р.