Обобщение характеристической функции, предпосылка игры, делёж и его свойства

Рассмотрим обобщение понятия характеристической функции на основе Нэш-равновесия.

Определение 5.1. Характеристической функцией игры  лиц { } называется вещественная функция , определённая на подмножествах множества  и ставящая в соответствие любой коалиции  равновесное значение (для ) бескоалиционной игры (или гарантирующее значение антагонистической игры) двух лиц, которую сыграли бы  и  (множество  без ), если бы эти две коалиции действительно возникли; при этом показатель коалиции  есть сумма взвешенных показателей участников коалиции

(в типичном случае «без приоритетов» , где  – число элементов ).

Далее, без ограничения общности будем считать величины  показателя эффективности  выигрышами систем-игроков. Для показателей потерь все неравенства в определениях и результатах меняются на противоположные.

Тогда характеристическая функция для коалиции  на основе бескоалиционного равновесия имеет вид

                                   (5.1)

где  находятся из системы неравенств

                                                (5.2)

Характеристическая функция для коалиции  на основе гарантирующих решений

                                                                    (5.3)

В отличие от традиционных структур характеристической функции (5.3) введение характеристической функции более общего вида (5.1) повышает значимость оценки самостоятельных действий коалиции (или игрока), так как по определению

Определение 5.2. Характеристическая функция обладает следующими свойствами:

1)

2)  ( – для минимизируемых );

3) cупераддитивность  (  для минимизируемых ) (существенность игры);

4)  (для игр с постоянной суммой ).

Следует отметить, что вид характеристической функции, в общем случае игры, может отличаться от данного определением 5.1. В каждой игре характеристическая функция  ставится в соответствие каждой коалиции как устойчивая оценка получаемого ею выигрыша.

Определение 5.3 [199]. Дележом для кооперативного компромисса  лиц с характеристической функцией  называется вектор , удовлетворяющий условиям:

1)  (коллективная рациональность);

2)  (индивидуальная рациональность) для всех .

Замечание.Для предпосылки дележа игры условие коллективной рациональности имеет вид

                                                                                                  (5.4)

Понятие дележа существенно отличает кооперативную игру от бескоалиционной. Бескоалиционные игры являются стратегическими в том смысле, что исход игры формируется в результате действий тех игроков, которые в исходе получают те или иные выигрыши. Исходом кооперативной игры является делёж, который возникает не как следствие действий игроков, а как результат их соглашений. То есть в кооперативных играх сравниваются по предпочтительности не действия с исходами, а дележи, и сравнение это не ограничивается рассмотрением индивидуальных выигрышей, а носит более содержательный характер.

Условием существования наилучшего дележа является свойство трансферабельности выигрышей коалиции , когда совокупный выигрыш коалиции может быть произвольным образом поделен между членами коалиции. Если данное свойство не выполняется и делёж единственный, то объединение игроков в коалиции не приведёт к увеличению выигрышей всех игроков и, в этом смысле, игра несущественна.

Определение 5.4[42]. Несущественной игрой называется кооперативная игра с аддитивной характеристической функцией, когда

                                                                                (5.5)

Утверждение 5.1 [199]. Всякая кооперативная игра двух игроков с постоянной суммой несущественна.

Доказательство. По свойству 5.4 характеристической функции (определение 5.2) , а это означает аддитивность функции при .

Утверждение 5.2. Для того чтобы характеристическая функция  была аддитивной, необходимо и достаточно, чтобы выполнялось равенство

                                                  .                                              (5.6)

Утверждение 5.3. В несущественной игре имеется только один делёж . Во всякой существенной игре множество дележей бесконечно.

Несущественность игры может быть следствием нетрансферабельности выигрышей и преодолена изменениями в постановке задачи или модификацией метода исследования.

Так, в работе [199] показана нетрансферабельность типичного терминального показателя

                                                                     (5.7)

где - некоторая заданная система точек в пространстве , которому принадлежит вектор состояния , который в свою очередь оценивает расстояние r от положения игроков в момент окончания игры до точек , являющихся для них известными. Потери  не являются трансферабельными, так как не могут делиться и передаваться другим участникам игры. По существу это означает, что каждой точке  соответствует единственный делёж, игра несущественна и образование коалиций не имеет смысла.

В работе [199] предложена модификация понятия дележа, которая приводит к формированию характеристических множеств взамен характеристических функций и к решению задачи определения оптимального дележа.

Возможным представляется и способ, когда вводится понятие взвешенного вектора потерь коалиции

                                                                                                    (5.8)

и в зависимости от  «делятся» степени близости к ,т.е. в зависимости от  формируется множество дележей внутри коалиции .

Методы оптимизации дележей

Принципы оптимальности классической теории кооперативных игр, заданных в форме характеристических функций, условно можно разделить на два типа [32]:

1) оптимальность на основе принципов устойчивого поведения каждого игрока (оптимальность по Парето, С-ядро, Н–М-решение);

2) оптимальность на основе «здравых» гипотез о свойствах, которыми должно обладать решение, исходящее от явно или неявно существующего арбитра (вектор Шепли, арбитражные схемы, среднеквадратическое решение).

Рассмотрим в сравнении оптимизационные подходы на основе понятий Парето, С-ядра, Н–М-решений и определения вектора дележа Шепли в классе дифференциальных игр [32, 199], но при условии, что целью каждого игрока системы является выбор параметров  своей полной математической модели, в частности, выбор параметров ПКЗУ с оптимизацией своего показателя – функционала общего вида.

Из свойства коллективной рациональности дележа следует, что предпосылки дележа оптимальны по Парето, но из свойства индивидуальной рациональности следует, что не все решения по Парето являются предпосылками дележа.

Утверждение 5.4. Парето-граница Парето–Нэш-множества компромиссов однотипных ММС содержит множество предпосылок дележей.

Доказательство. Как известно, Парето–Нэш-множество составляет прямоугольный многомерный конус с вершиной в , ограниченный Парето-границей .

Характеристическая функция (5.1) имеет вид , при этом

                                                                                          (5.9)

Сравнение равновесия и  показывает, что для однотипных систем с равными ресурсами оптимизация суммы имеет эффект локальной Парето-оптимизации. Поэтому ситуация равновесия  «сместится» в сторону увеличения эффективности на множестве  и уменьшения эффективности для системы . Следовательно, выполняется условие индивидуальной рациональности дележа

                                                                        (5.10)

Условие коллективной рациональности выполняется тождественно

                                                  ,                                            (5.11)

поэтому предпосылки дележей принадлежат Парето-решениям П–Н-мно-жества компромиссов. Данное утверждение очевидно для , так как в этом случае .

Утверждение теоремы очевидно и для характеристической функции вида (5.3). В этом случае по определению

так как равновесные значения функционалов «не хуже» [32], чем гарантированные.

Поэтому , таким образом, Парето-граница П–Н-мно-жества содержит предпосылки дележей, среди которых может быть выбран наилучший.

Далее, в данном пункте приводятся основные определения и утверждения кооперативных игр в форме характеристической функции касающиеся понятий доминирования дележей, решения в форме С-ядра, Нейман-Моргенштерн-решения и их свойств.

Определение 5.5. Дележ  доминирует дележ  по коалиции , если:

                                           для всех ,

                                               .                                          (5.12)

Первое условие очевидно, а второе условие означает, что члены коалиции в состоянии реализовать делёж, т.е. сумма выигрышей членов коалиции не должна превосходить уверенно получаемое ею количество, имеющего смысл приближения локального Парето-решения в равновесии . Иначе, встретившись с дележом, дающим столько, сколько коалиция самостоятельно не в состоянии добиться, должна согласиться на него и не заниматься его сравнением с другими дележами.

Определение 5.6 [199]. Дележ  доминирует дележ , если существует такая произвольная коалиция K Ì N, что . Доминирование по коалиции, состоящее из одного игрока, а также по множеству всех игроков невозможно, так как в этом случае нарушаются первое и второе свойство дележа.

Определение 5.7 [199]. Множество всех недоминируемых дележей в кооперативной игре называется её С-ядром. Любой делёж из С-ядра устойчив, так как ни одна коалиция не имеет желания изменить его.

Утверждение 5.5. Если множество значений v является выпуклым, то С-ядро не является пустым множеством.

Главное основание утверждения – свойство супераддитивности v, при котором v выпуклая1.

Следствие 5.1 [42]. Для несущественной игры С-ядро существует и состоит из единственного дележа.

Следствие 5.2 [42]. Во всякой существенной игре с постоянной суммой С-ядро пусто.

Утверждение 5.6 [42, 199]. Для того, чтобы дележи J_d принадлежали
С-ядру, необходимо и достаточно, чтобы выполнялось неравенство

                                                                                                (5.13)

для любой коалиции K ÌN [K ¹ N, |K| >l), где |K| – мощность множества K.

В работе [199] дана интерпретация результата в дифференциальных играх и сформулированы сложные условия оптимальности.

В работе [42] дан способ формирования С-ядра в общих играх трёх лиц. Всё же часто С-ядро оказывается пусто.

Определение 5.8. Множество дележей L называется Нейман–Моргенштерн (Н–М)-решением с характеристической функцией , если: а) из , Î L следует, что  и  не доминируют друг друга (внутренняя устойчивость); б) для всякого ÏL найдется такой ÎL, что  >  (внешняя устойчивость). Множество L расширяет множество С.

Утверждение 5.7 [42].Если в кооперативной игре существует С-ядро С- и Н–М-решение L, то C Ì Z.

Методы поиска Н–М-решения трёх лиц даны в работе [42]. Некоторые интерпретации для дифференциальных игр на уровне условий и свойств оптимизационного подхода даны в работе [199].

В общем случае [42] неизвестно каких-либо критериев, позволяющих судить о наличии у кооперативной игры Н–М-решения. При наличии
Н–М-решений надо иметь в виду, что решения существенных кооперативных игр состоят более чем из одного дележа, поэтому выбор какого-либо конкретного Н–М-решения  ещё не определяет выигрыша каждого из игроков.

Ввиду больших сложностей при определении существования и в способах отыскания оптимальных дележей на основе С-ядра и Н–М-решений в играх общего вида особого внимания заслуживает подход на основе вектора Шепли, который на основе обоснованных предположений даёт практически реализуемое правило формирования оптимального дележа.