ВИЗУАЛИЗАЦИЯ C-ЯДРА В КООПЕРАТИВНЫХ ИГРАХ

АННОТАЦИЯ

Рассматривается визуализация С-ядра кооперативной игры с тремя и четырьмя участниками. Предлагается вариант построения С-ядра для четырех игроков с переходом от четырехмерного пространства к трехмерному.

Ключевые слова: переговорное множество; ядро игры; коалиции; визуальное представление.

Для большей наглядности при переговорах в кооперативной игре полезно иметь визуальное представление такого важного элемента, каким является С-ядро. Это актуально и для людей-участников [1, 2, 3] и для виртуальных подсистем [4].

Рассмотрим в качестве примера следующую игру. Некоторый коллектив (глобальная коалиция), состоящий из трёх сотрудников, выполняет работу, оцениваемую в V₁₂₃ денежных единиц (выигрыш). Сотрудники i и j совместно (частичная коалиция) могут за то же время выполнить работу, оцениваемую в V_ij, а сотрудник i в одиночку – V_i. Если сотрудники выполняют работу совместно, то они некоторым образом делят между собой ее стоимость, если же работник выполняет работу в одиночку, то он получает всю ее стоимость. Обозначим получаемые сотрудниками при совместной работе выплаты через x₁, x₂ и x₃. Очевидно, что в рассматриваемой задаче выплаты не должны быть отрицательными, так как сотрудники не должны платить за свое участие в работе.

С-ядром (core) игры называется множество дележей выигрыша, при которых каждый работник и каждая частичная коалиция получают не меньше, чем получили бы без участия в глобальной коалиции. В рассматриваемой игре C-ядро определяется следующим набором ограничений:

                                          ,                                                (1)

                                      , , ,                                             (2)

                                    , , ,                                           (3)

                         , , .                                (4)

Сопоставляя (1) и (4), получим:

                      , , .                             (5)

Игра в постановке (1)-(4) или (1)-(3),(5) предполагает относительно простую визуализацию. Ограничения (1) и (2) определяют в координатах x₁, x₂ и x₃ равносторонний треугольник, вершины которого находятся на осях координат (рис.1). Эти вершины имеют координаты (V₁₂₃,0,0), (0,V₁₂₃,0) и (0,0,V₁₂₃).

Ограничения вида равенств x_i=V_i и x_i=V₁₂₃–V_jk (i¹j, i¹k), соответствующие (3) и (5), определяют плоскости, параллельные координатным плоскостям. С-ядро представляет собой выпуклый многоугольник (выделен штриховкой на рис.1), ограниченный отрезками, полученными пересечением этих плоскостей и треугольника.

Рисунок 1. Система ограничений в игре с тремя участниками

Для простоты построения часто используется изометрическая проекция (рис.2):

Рисунок 2. Переход к изометрической проекции

Переход к этой проекции позволяет отказаться от множества дополнительных построений и перейти к работе непосредственно в плоскости треугольника (рис.3). При этом удобно ассоциировать сторону треугольника с величиной V₁₂₃ (на самом деле длина стороны равна ) и оперировать долями от этой стороны:

Рисунок 3. Упрощенная визуализация системы ограничений на плоскости

С точки зрения формального математического описания, подобная игра с четырьмя сотрудниками имеет лишь незначительные отличия от (1)-(4) или (1)-(3),(5): добавляется новая переменная x₄ и частичные коалиции, включающие трёх участников:

                                      ,                                             (6)

                                , , , ,                                       (7)

                              , , , ,                                     (8)

   , , , , , ,  (9)

       , , , .     (10)

По аналогии с (5), сопоставляя (6) и (9) получим (11), а, сопоставляя (6) и (10), получим (12):

, , ,

           , , .                (11)

       , , , .            (12)

Аналоги рис.1 и рис.2 в игре четырех игроков предполагают построение в четырехмерном пространстве, что заметно затрудняет визуализацию. Аналог рис.3 предполагает построение в трехмерном пространстве. Аналогом треугольника (рис.3) для случая четырех игроков будет трехмерный правильный симплекс – тетраэдр. Так как описания ядра (6)-(10) и (6)-(9),(11),(12) содержат существенно больше условий, чем (1)-(4) и (1)-(3),(5), произведем построение поэтапно. На рис.4 представлены построения, соответствующие (6)-(8),(12) без учета (9) и (11). Все плоскости на рис.4 являются (по аналогии с прямыми на рис.3) пересечениями указанных около них гиперплоскостей и гиперплоскости x₁+x₂+x₃+x₄=V₁₂₃₄.

Рисунок 4. Система ограничений в игре с четырьмя участниками

Построим пересечения плоскостей, заданных ограничениям (рис.5):

Рисунок 5. Построение пересечений плоскостей

После исключения областей, не отвечающих условиям (8),(10) или (8),(12), область возможного C-ядра (пока без учета (9) и (11)) примет вид, представленный на рис.6. Геометрически С-ядро в данной игре представляет собой тетраэдр с отсеченными вершинами. Одна из вершин в рассматриваемом примере оказалась не отсеченной, так как соответствующая плоскость (образованная пересечением гиперплоскостей x₁+x₂+x₃+x₄=V₁₂₃₄ и x₄=V₁₂₃₄–V₁₂₃) не пересекает тетраэдр:

Рисунок 6. С-ядро без учета ограничений (9) и (11)

Дальнейшие шаги связаны с построением плоскостей, определяемых условиями (9) и (11). Каждая из этих плоскостей определяется пересечением пары гиперплоскостей (например,  и ) и проходит параллельно двум непересекающимся ребрам полученного выше усеченного тетраэдра (соответственно,  и ). Расстояние от этой плоскости до ребра определяется эффективностью парной коалиции по сравнению с ее участниками, например, V_ij по сравнению  с V_i+V_j. Если эта парная коалиция не дает участникам преимущества (V_ij=V_i+V_j), то плоскость содержит соответствующее ребро. Если парная коалиция менее эффективна, чем ее участники по отдельности (в рассматриваемом примере V₂₃<V₂+V₃), то эта плоскость не проходит через усеченный тетраэдр и не оказывает влияние на С-ядро.

Рисунок 7. Построение ограничений (9) и (11)

После исключения отсеченных этими гиперплоскостями областей получим окончательное визуальное представление С-ядра:

Рисунок 8. Визуальное представление С-ядра с учетом всех ограничений

В некоторых случаях совокупность ограничений вида (6)-(12) содержит противоречия и определяет пустое множество (С-ядро пусто). Это означает, что не существует ни одного возможного дележа, при котором все возможные подкоалиции получили бы не меньше, чем без участия в глобальной коалиции. В этом случае целесообразно рассматривать разбиение глобальной коалиции на подкоалиции, в каждой из которых проходит самостоятельная игра, и находить С-ядро подкоалиций, что предполагает более простую визуализацию.

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

Список литературы:

1. Саркисов В.Г. Система оптимального управления коллективными инвестициями в модели Марковица // Вестник Самарского государственного технического университета, серия "Технические науки", №4(40)2013, стр. 45-52
2. Саркисов В.Г. Области компромисса при управлении общим портфелем инвесторов с разными предпочтениями // Управление экономикой: методы, модели, технологии: материалы XVI Международной научной конференции – Уфа: УГАТУ, 2016, стр.392-396
3. Саркисов В.Г. Распад коалиций инвесторов при ошибках прогноза динамики цен активов // Математические методы в технике и технологиях – ММТТ-29: сб. трудов XXIX Междунар. науч. конф.: в 12 т. Т.12. Саратов. гос. техн. ун-т, 2016., стр.134-136
4. Саркисов В.Г. Агрегирование систем управления инвестициями // Вестник Самарского государственного технического университета, серия "Технические науки", №2 (54) 2017, стр.52-57