[МУЗЫКА] [МУЗЫКА] Здравствуйте. Темой сегодняшнего занятия будут кооперативные многошаговые игры. Первая часть занятия посвящена кооперативным многошаговым играм в форме характеристической функции, а вторая часть посвящена кооперативным многошаговым играм с нетрансферабельным выигрышем. Первая часть может быть использована для описания оптимальных параметров кооперативного соглашения, описывающего способ распределения прибыли между инвесторами в небольшой компании. Вторая часть может быть использована для определения параметров стратегического соглашения, в котором определяются стратегии или поведения игроков в рамках этого соглашения. Допустим, такие соглашения, как ограничения выбросов вредных газов в атмосферу. Начнем с многошаговых игр в форме характеристической функции и рассмотрим следующий пример — это утверждение некоторого пакета документов. Предположим, что есть компания, которая хочет утвердить пакет документов в трех ведомствах последовательно. Предполагается, что если в каком-то из ведомств пакет документов не подписывается, то тогда игра заканчивается. Если пакет документов подписывается в трех ведомствах, то считается, что результат является хорошим, и пакет документов утверждается. Предполагается, что фирма платит некоторую госпошлину всем трем ведомствам за подписание документов. Для того чтобы построить математическую модель подобного процесса, можно использовать многошаговые игры с полной информацией, которые мы с вами изучили в предыдущем разделе. Для этого необходимо определить множество игроков N = {1,...,n}. Необходимо задать граф, который будет определять очередность ходов игроков. И необходимо задать множество позиций на графе, как X. И определить множество очередностей игроков и множество окончательных позиций. Напомню, что множество очередностей игроков — это Хi, это множество позиций, в которые игрок i делает ход. Множество окончательных позиций — это множество позиций, на которых заданы выигрыши, по крайней мере так мы определяли это множество в предыдущем разделе. В нынешней постановке мы предположим, что в каждой позиции на графе или в каждом состоянии игры определены некоторые выплаты. То есть каждый из игроков на каждом шаге получает какую-то прибыль. Потом можно рассчитать суммарную прибыль, которую получают игроки вдоль некоторой траектории, которая реализуется. Вернемся к примеру подписания пакета документов. На слайде представлен граф данной игры. Здесь у нас есть три шага и три игрока. Предполагается, что игроки — это ведомства. В каждый момент времени, на каждом шаге ведомство может выбрать одну из двух стратегий: подписать пакет документов или не подписать пакет документов. Если оно использует альтернативу B, это означает, что пакет документов не подписывается, и тогда фирма выплачивает всем ведомствам выигрыш, равный единице. Если первое ведомство подписывает пакет документов, то пакет документов переходит во второе ведомство. И у второго ведомство тоже есть две чистые стратегии или две альтернативы: подписать пакет документов или не подписать пакет документов. В случае неподписания всем ведомствам выплачивается выигрыш, равный 1/2. В случае подписания игра продолжается. После этого третье ведомство тоже имеет две альтернативы: подписание пакета документов и неподписание. В случае подписания каждое ведомство получает выигрыш, равный 2. В случае неподписания каждое ведомство получает выигрыш, равный 1/3. Что же такое кооперативная игра? Для того, чтобы определить кооперативную многошаговую игру, необходимо определить набор стратегий игроков или в данном случае ведомств, которые максимизируют суммарный выигрыш. Конечно, подобная постановка и ее физическая интерпретация может показаться странной, но здесь мы хотим определить набор стратегий ведомств, чтобы максимизировать суммарную прибыль. То есть как действовать ведомствам, чтобы заработать больше денег от компании? В нашем случае это означает, что нам нужно найти решение оптимизационной задачи, представленной на слайде, то есть найти такой путь, который максимизирует суммарный выигрыш. Или найти такой набор стратегий, который максимизирует выплаты от компании. Решение данной оптимизационной задачи, а именно путь и соответствующий набор стратегий, мы будем называть кооперативной траекторией и кооперативной стратегией соответственно. Напомню, что hi(xk) — это выплаты i-му игроку на шаге или в позиции xk. Вернемся к примеру подписания пакета документов. Также хочется отметить, что в нашем примере выплаты, определенные в позициях x0, x1, x2, равны нулю. То есть мы считаем, что фирма выплачивает, допустим, госпошлину только в случае окончания процесса, то есть если пакет документов был не подписан на какой-то из итераций или если он был подписан. Итак, как же нам определить кооперативные стратегии и соответствующую кооперативную траекторию? Для этого нам необходимо выбрать один из четырех возможных путей. Или нам необходимо выбрать максимум из следующих выигрышей: 3, 1.5, 1 и 6. То есть нам нужно определить, на каком пути суммарный выигрыш всех игроков максимальный. В данном случае, очевидно, это путь x0, x1, x2, x3, на котором выигрыш равняется шести. Далее, для того чтобы понять, каким образом мы можем распределить этот суммарный выигрыш между игроками, нам необходимо определить понятие характеристической функции коалиции S. Заметим, что при рассмотрении кооперативных игр и нахождении некоторого пути, который максимизирует суммарный выигрыш, некоторым игрокам данный путь или данный набор стратегий может быть невыгоден. То есть их индивидуальные выигрыши могут быть очень маленькими при кооперативном поведении. Поэтому необходимо определить способ перераспределения выигрышей между игроками, чтобы это было выгодно каждому из его участников. Итак, вернемся к понятию характеристической функции. Мы определим характеристическую функцию коалиции S как значение игры с нулевой суммой между коалициями S и N−S, а именно мы определим это как суммарный выигрыш игроков из коалиции S при условии, что они максимизируют свою прибыль или свой выигрыш, а игроки из коалиции N−S стараются минимизировать выигрыш игроков из коалиции S. Подобным образом определенная характеристическая функция удовлетворяет следующим условиям, то есть значение характеристической функции для коалиции, соответствующей всем игрокам, у нас равно просто суммарному выигрышу всех игроков вдоль кооперативной траектории, то есть максимальному суммарному выигрышу. И выполняется условие супераддитивности. Об этом условии мы уже говорили в одном из предыдущих разделов. Это условие гарантирует то, что объединение всех игроков в одну коалицию будет выгодно всем игрокам. Далее на основе понятия характеристической функции можно определить множество дележей в игре Γ, то есть можно определить набор способов распределения суммарного выигрыша между игроками так, чтобы он удовлетворял двум условиям. Первое — это групповая рациональность, и второе - это индивидуальная рациональность. Групповая рациональность говорит нам о том, что суммарные выплаты всем игрокам у нас равны максимальному выигрышу, который мы зарабатываем, или выигрышу, который мы зарабатываем вдоль кооперативной траектории. Индивидуальная рациональность говорит нам о том, что тот выигрыш, который мы получаем в рамках нашего дележа, будет больше или равен того выигрыша, который мы зарабатываем, если действуем индивидуально. То есть ξi ≥ V({i}). И множество всевозможных подобных векторов ξ=(ξ1,...,ξn) мы будем называть множеством дележей. Далее на множестве дележей или в множестве дележей, нам необходимо определить кооперативное решение. То есть нам необходимо выбрать какое-то подмножество множества дележей, которое мы будем использовать для распределения выигрыша между игроками. В нашем случае мы будем использовать вектор Шепли, на слайде приведена формула вектора Шепли, ранее мы уже рассматривали его аксиоматические свойства, но в данном случае мы просто воспользуемся явной формулой. Вернемся к примеру подписания пакета документов. На слайде представлены расчеты для значения характеристической функции каждой коалиции S. Значение характеристической функции для коалиции {1,2,3} у нас равно 6, так как значение характеристической функции для всех игроков должно быть равно максимальному суммарному выигрышу, который зарабатывают все игроки. Далее можем рассмотреть способ расчета значения характеристической функции для индивидуальной коалиции, например, для игрока 1. Для других коалиций способ расчета аналогичный. Рассчитаем значение характеристической функции для индивидуальной коалиции, состоящей из первого игрока. Предположим, что на первом шаге первый игрок выбирает альтернативу A. Тогда в соответствии с нашим подходом игроки 2 и 3 захотят минимизировать выигрыш, который получает первый игрок. В данном случае наилучшим образом это можно сделать, если игрок 2 выберет альтернативу A, а игрок 3 выберет альтернативу B, при которой первый игрок получит выигрыш 1/3. Если второй игрок выберет альтернативу B на втором шаге, то тогда игрок 1 получит выигрыш 1/2. Итак, таким образом, игрок 1 на первом шаге должен выбрать альтернативу B. Тогда его выигрыш будет равен 1, а стратегии, выбранные игроками 2 и 3, уже никаким образом не повлияют на его выигрыш. Мы получили значение характеристической функции, равное единице. Для других коалиций способ расчета аналогичен. На основе значений характеристической функции можно построить множество дележей. Итак, множество дележей — это множество векторов ξ1, ξ2 и ξ3, удовлетворяющих следующей системе неравенств: ξ1 ≥ 1, ξ2 ≥ 1/2, ξ3 ≥ 1/2 и сумма ξ1 + ξ2 + ξ3 = 6. Также на слайде приведены расчеты для вектора Шепли. Таким образом, мы определили способ распределения прибыли между тремя ведомствами от подписания пакета документов некоторой фирмы. Однако остается следующий вопрос: что произойдет, если в позиции x1 участники соглашения захотят пересмотреть условия этого соглашения? Об этом мы поговорим в следующем видеосюжете. На слайде представлен список источников, который поможет вам более детально разобраться в многошаговых кооперативных играх, в способе определения характеристической функции и рассмотреть другие примеры.
