Сложность ядра: различия между версиями

Алгоритмическое исследование ядра представляет собой сложную задачу, поскольку на его определение накладывается экспоненциальное число ограничений. Следующие вопросы о вычислительной сложности привлекли значительное внимание исследователей:

'''ИГРА О ПОВЕДЕНИИ ПОТОКА (FLOW GAME)'''. Пусть D = (V, E; <math>\omega</math>; s, t) – ориентированная сеть, где V – множество вершин, E – множество дуг, <math>\omega : E \to R^+</math> – функция пропускной способности дуги, s и t – источник и сток сети, соответственно. Предположим, что каждый игрок контролирует одну дугу сети. Значение максимального потока можно рассматривать как прибыль, получаемую игроками при сотрудничестве. Тогда игра о поведении потока <math>\Gamma_f = (E, v)</math>, связанная с сетью D, определяется следующим образом:

В работах Кайлая и Земела [6], а также Дена и коллег [2] было показано, что игра о поведении потока является полностью сбалансирована, и поиск члена ядра может быть выполнен за полиномиальное время.

'''ИГРА НА ДЕРЕВЕ ШТЕЙНЕРА (STEINER TREE GAME)'''. Пусть G = (V, E; <math>\omega</math>) – граф с взвешенными ребрами, <math>V = \{ v_0 \} \cup N \cup M </math>, где <math>N, M \subseteq V \backslash \{ v_0 \}</math> – непересекающиеся множества. <math>v_0</math> представляет центрального поставщика, N – множество потребителей, M – множество коммутаторов, а <math>\omega(e)</math> обозначает стоимость соединения двух конечных точек ребра ''e'' напрямую. Требуется соединить всех потребителей в N с центральным поставщиком <math>v_0</math>. Соединение не ограничивается использованием прямых связей между двумя потребителями или потребителем и центральным поставщиком, оно может проходить через некоторые коммутаторы в M. Цель заключается в том, чтобы организовать самое дешевое соединение и справедливо распределить стоимость соединения между потребителями. В этом случае соответствующая игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math> определяется следующим образом:

(2) <math>\forall S \subseteq N, \gamma(S)</math> – вес минимального дерева Штейнера на G относительно множества <math>S \cup \{ v_0 \}</math>, то есть <math>\gamma(S) = min \{ \sum_{e \in E_S} \omega(e) : T_S = (V_S, E_S)</math> является поддеревом G с <math>V_S \supseteq S \cup \{ v_0 \} \}</math>.

'''Теорема 1. Пусть имеются игра о поведении потока <math>\Gamma_f = (E, \mathbf{v})</math>, заданная на сети <math>D = (V, E; \omega; s, t</math>) и вектор <math>\mathbf{x} : E \to R^+</math>, <math>\mathbf{x}(E) = \mathbf{v}(E)</math>. Задача о существовании коалиции <math>S \subset N</math>, такой, что <math>\mathbf{x}(S) < \mathbf{v}(S)</math>, является <math>\mathcal{NP}</math>-полной. Другими словами, проверка принадлежности к ядру для игр о поведении потока является <math>co-\mathcal{NP}</math>-полной.'''

Доказательство теоремы 1 позволяет прийти точно к такому же выводу для линейных производственных игр. В линейной производственной игре Оуэна [10] каждый игрок j <math>(j \in N)</math> является владельцем индивидуального вектора ресурсов <math>b^j</math>. Для коалиции S игроков прибыль, получаемая коалицией, является оптимальным значением следующей линейной программы:

<math>max \{ c^t y : Ay \le \sum_{j \in S} b^j, y \ge 0 \}.</math>

Задача нахождения минимального дерева Штейнера в сети является <math>\mathcal{NP}</math>-сложной, поэтому в игре на дереве Штейнера значение <math>\gamma(S)</math> каждой коалиции S не может быть получено за полиномиальное время. Из этого следует, что дополнительная задача проверки принадлежности к ядру для игр на дереве Штейнера не может быть <math>\mathcal{NP}</math>-сложной.

Пусть даны игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math>, заданная на сети <math>G = (V, E; \omega)</math>, и подмножество <math>S \subseteq N</math>. Тогда в подигре <math>(S, \gamma_s)</math> значение <math>\gamma(S') \; (S' \subseteq S)</math> является весом минимального дерева Штейнера G относительно подмножества <math>S\ \cup \{ v_0 \}</math>, где все вершины в N \ S рассматриваются как коммутаторы, но не потребители. Далее, в работе Фанга и др. [4] было показано, что проверка полной сбалансированности игры на дереве Штейнера также является <math>\mathcal{NP}</math>-сложной. Это первый пример NP-сложности задачи для условия полной сбалансированности.

(2) В играх о поведении потока и играх на остовном дереве с минимальной стоимостью [3, 4], в которых ядра всегда непустые, а член ядра может быть найден за полиномиальное время, задача проверки принадлежности является <math>co-\mathcal{NP}</math>-полной.

(3) В играх с размещением объектов [5] задача проверки сбалансированности в общем случае является <math>\mathcal{NP}</math>-сложной, однако, учитывая информацию о непустоте ядра, можно эффективно выполнить как поиск члена ядра, так и проверку принадлежности.

Чтобы изучение сложности и алгоритмов для кооперативных игр для соответствующих областей применения имело смысл, предлагается рассматривать вычислительную сложность как важный фактор при оценке рациональности и справедливости концепции решения, что вытекает из понятия ограниченной рациональности [3, 8]. Иными словами, игроки не готовы тратить на поиск наиболее подходящего решения больше полиномиального времени. В случае, когда решений игры не существует или их трудно вычислить либо проверить, может оказаться не просто отбросить задачу как безнадежную, особенно когда игра возникает в важных областях применения. Поэтому для решения задачи предлагаются различные концептуальные подходы.

Концепция наименьшего ядра порождает новые проблемы относительно алгоритмических вопросов. Наиболее естественной задачей является эффективное вычисление значения £* для заданной кооперативной игры. Загвоздка в том, что вычисление £* требует решения линейной программы с экспоненциальным числом ограничений. Хотя существуют случаи, когда это значение может быть вычислено за полиномиальное время [ ], в общем случае это очень сложно. Если величина £* рассматривается как некая субсидия, предоставляемая центральным органом для обеспечения существования кооперации, то важно дать ее приближенное значение, даже если ее вычисление является NP-сложным.

Другой возможный подход заключается в интерпретации приближения как ограниченной рациональности. Например, было бы интересно узнать, существует ли какая-нибудь игра со свойством, что для любого " > 0 проверка принадлежности к "-ядру может быть выполнена за полиномиальное время, но определение того, содержится ли в ядре дележ, будет NP-сложной задачей. В таких случаях восстановление сотрудничества было бы результатом применения подхода ограниченной рациональности. То есть, игроки не будут беспокоиться о дополнительном выигрыше или проигрыше " за счет вычислительных ресурсов более высокого порядка степени. В дальнейшем эту методику можно применить к другим концепциям решений.

* [[Равновесие в общем случае==