Сложность ядра

Ключевые слова и синонимы

Сбалансированность; наименьшее ядро

Постановка задачи

Ядро – это наиболее важная концепция решения в теории кооперативных игр, которая основывается на условии рациональности коалиции: ни одна подгруппа игроков не будет действовать лучше, если она отделится от совместного решения всех игроков и сформирует свою собственную коалицию. Принцип, лежащий в основе этого условия, очень похож на принцип равновесия Нэша и может рассматриваться как его продолжение. Задача определения ядра кооперативной игры естественным образом ставит вопросы, связанные с алгоритмами и сложностью. В работе Фанга, Чжу, Цая и Дена [4] рассматриваются вопросы вычислительной сложности, связанные с ядрами некоторых моделей кооперативных игр, таких как игры о поведении потока и игры на дереве Штейнера.

Кооперативная игра с побочными платежами задается парой [math]\displaystyle{ (N, \mathbf{v}) }[/math], где N = {1, 2, ..., n} – множество игроков, а [math]\displaystyle{ \mathbf{v}: 2^N \to R }[/math] – характеристическая функция. Для каждой коалиции [math]\displaystyle{ S \subseteq N }[/math] значение v(S) интерпретируется как прибыль или затраты, достигнутые коллективными действиями игроков из S без какой-либо помощи игроков из N \ S. Игра называется прибыльной (затратной), если v(S) измеряет прибыль (затраты), достигнутые коалицией S. Далее определения даются только для прибыльных игр, для затратных игр справедливы симметричные утверждения. Вектор [math]\displaystyle{ \mathbf{x} = \{ x_1, x_2, ..., x_n \} }[/math] называется дележом, если он удовлетворяет условиям [math]\displaystyle{ \sum_{i \in N} x_i = v(N) }[/math] и [math]\displaystyle{ \forall i \in N : x_i \ge v( \{ i\} ) }[/math]. Ядро игры [math]\displaystyle{ (N, \mathbf{v}) }[/math] определяется следующим образом:

[math]\displaystyle{ C(v) =\{ \mathbf{x} \in R^n : \mathbf{x}(N) = v(N) }[/math] и [math]\displaystyle{ \mathbf{x}(S) \ge \mathbf{v}(S), \forall S \subseteq N \}, }[/math]

где [math]\displaystyle{ x(S) = \sum_{i \in S} x_i }[/math] для [math]\displaystyle{ S \subseteq N }[/math]. Игра называется сбалансированной, если ее ядро непусто, и полностью сбалансированной, если каждая подигра (т. е. игра, полученная путем ограничения множества игроков коалицией, а характеристической функции – степенным множеством этой коалиции) сбалансирована.

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

(1) Проверка сбалансированности: можно ли за полиномиальное время проверить, имеет ли данный экземпляр игры непустое ядро?

(2) Проверка принадлежности: можно ли за полиномиальное время проверить, принадлежит ли ядру данный дележ?

(3) Поиск члена ядра: можно ли за полиномиальное время найти дележ ядра?

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

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

(1) E – это команда игроков;

(2) [math]\displaystyle{ \forall S \subseteq E }[/math], [math]\displaystyle{ \mathbf{v}(S) }[/math] – это значение максимального потока из s в t в подсети D, состоящей только из дуг, принадлежащих S.

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

Задача 1 (проверка принадлежности для игры о поведении потока)

Дано: сеть движения потока D = (V, E; [math]\displaystyle{ \omega }[/math]; s, t) и [math]\displaystyle{ x: E \to R^+ }[/math].

Вопрос: верно ли, что [math]\displaystyle{ \mathbf{x}(E) = \mathbf{v}(E) }[/math] и [math]\displaystyle{ \mathbf{x}(S) \ge \mathbf{v}(S) }[/math] для всех подмножеств [math]\displaystyle{ S \subset E }[/math]?

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

(1) N – это команда игроков;

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

В отличие от игр о поведении потока, ядро игры на дереве Штейнера может быть пустым. Пример игры с пустым ядром был приведен в работе Мегиддо [9].

Задача 2 (проверка сбалансированности игры на дереве Штейнера)

Дано: граф с взвешенными ребрами G = (V, E; [math]\displaystyle{ \omega }[/math]), [math]\displaystyle{ V = \{ v_0 \} \cup N \cup M }[/math].

Вопрос: существует ли вектор [math]\displaystyle{ \mathbf{x}: N \to R^+ }[/math], такой, что [math]\displaystyle{ \mathbf{x}(N) = \gamma(N) }[/math] и [math]\displaystyle{ \mathbf{x}(S) \le \gamma(S) }[/math] для всех подмножеств [math]\displaystyle{ S \subset N }[/math]?

Задача 3 (проверка принадлежности для игры на дереве Штейнера)

Дано: граф с взвешенными ребрами G = (V, E; [math]\displaystyle{ \omega }[/math]), [math]\displaystyle{ V = \{ v_0 \} \cup N \cup M }[/math] и [math]\displaystyle{ \mathbf{x} : N \to R^+ }[/math].

Вопрос: верно ли, что [math]\displaystyle{ \mathbf{x}(N) = \gamma(N) }[/math] и [math]\displaystyle{ \mathbf{x}(S) \le \gamma(S) }[/math] для всех подмножеств [math]\displaystyle{ S \subset N }[/math]?

Основные результаты

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

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

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

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

Теорема 2. Проверка принадлежности к ядру для линейных производственных игр является [math]\displaystyle{ co-\mathcal{NP} }[/math]-полной.

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

Теорема 3. Пусть имеются игра на дереве Штейнера [math]\displaystyle{ \Gamma_s = (N, \gamma) }[/math], заданная на сети [math]\displaystyle{ G = (V, E; \omega) }[/math], и вектор [math]\displaystyle{ \mathbf{x}: N \to R^+ }[/math], [math]\displaystyle{ \mathbf{x}(N) = \gamma(N) }[/math]. Задача о существовании коалиции [math]\displaystyle{ S \subset N }[/math], такой, что [math]\displaystyle{ \mathbf{x}(S) \gt \gamma(S) }[/math], является [math]\displaystyle{ \mathcal{NP} }[/math]-сложной. Другими словами, проверка принадлежности к ядру для игр на дереве Штейнера является [math]\displaystyle{ \mathcal{NP} }[/math]-сложной.

Теорема 4. Проверка сбалансированности для игр на дереве Штейнера является [math]\displaystyle{ \mathcal{NP} }[/math]-сложной.

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

Теорема 5. Проверка полной сбалансированности для игр на дереве Штейнера является [math]\displaystyle{ \mathcal{NP} }[/math]-сложной.

Применение

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

(1) В играх на соответствие [1] проверка сбалансированности, проверка принадлежности и нахождение члена ядра могут быть выполнены за полиномиальное время.

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

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

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

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

Когда ядро игры пусто, это стимулирует условия, обеспечивающие непустоту приближенных ядер. Естественным способом аппроксимации ядра является наименьшее ядро. Пусть (N, v) – кооперативная игра с прибылью. Пусть дано действительное число [math]\displaystyle{ \varepsilon }[/math]. Определим [math]\displaystyle{ \varepsilon }[/math]-ядро, содержащее такие распределения, что [math]\displaystyle{ \mathbf{x}(S) \ge \mathbf{v}(S) - \varepsilon }[/math] для каждого непустого собственного подмножества S из N. Наименьшее ядро является пересечением всех непустых [math]\displaystyle{ \varepsilon }[/math]-ядер. Пусть [math]\displaystyle{ \varepsilon^* }[/math] - минимальное значение [math]\displaystyle{ \varepsilon }[/math], такое, что [math]\displaystyle{ \varepsilon }[/math]-ядро пусто. Тогда наименьшее ядро совпадает с [math]\displaystyle{ \varepsilon^* }[/math]-ядром.

Концепция наименьшего ядра порождает новые проблемы относительно алгоритмических вопросов. Наиболее естественной задачей является эффективное вычисление значения [math]\displaystyle{ \varepsilon^* }[/math] для заданной кооперативной игры. Загвоздка в том, что вычисление [math]\displaystyle{ \varepsilon^* }[/math] требует решения линейной программы с экспоненциальным числом ограничений. Хотя существуют случаи, когда это значение может быть вычислено за полиномиальное время [7], в общем случае это очень сложно. Если величина [math]\displaystyle{ \varepsilon^* }[/math] рассматривается как некая субсидия, предоставляемая центральным органом для обеспечения существования кооперации, то важно дать ее приближенное значение, даже если ее вычисление является [math]\displaystyle{ \mathcal{NP} }[/math]-сложным.

Другой возможный подход заключается в интерпретации приближения как ограниченной рациональности. Например, было бы интересно узнать, существует ли какая-нибудь игра со свойством, что для любого [math]\displaystyle{ \varepsilon \gt 0 }[/math] проверка принадлежности к [math]\displaystyle{ \varepsilon }[/math]-ядру может быть выполнена за полиномиальное время, но определение того, содержится ли в ядре дележ, будет [math]\displaystyle{ \mathcal{NP} }[/math]-сложной задачей. В таких случаях восстановление сотрудничества было бы результатом применения подхода ограниченной рациональности. То есть, игроки не будут беспокоиться о дополнительном выигрыше или проигрыше [math]\displaystyle{ \varepsilon }[/math] за счет вычислительных ресурсов более высокого порядка степени. В дальнейшем эту методику можно применить к другим концепциям решений.

См. также

• Равновесие в общем случае
• Ядрышко
• Маршрутизация

Литература

1. Deng, X., Ibaraki, T., Nagamochi, H.: Algorithmic Aspects of the Core of Combinatorial Optimization Games. Math. Oper. Res. 24,751-766(1999)

2. Deng, X., Papadimitriou,C.:On the Complexity of Cooperative Game Solution Concepts. Math. Oper. Res. 19,257-266 (1994)

3. Faigle, U., Fekete, S., Hochstattler, W., Kern, W.: On the Complexity of Testing Membership in the Core of Min-Cost Spanning Tree Games. Int. J. Game. Theor. 26, 361-366 (1997)

4. Fang, Q., Zhu, S., Cai, M., Deng, X.: Membership for core of LP games and other games. COCOON 2001 Lecture Notes in Computer Science, vol. 2108, pp 247-246. Springer-Verlag, Berlin Heidelberg (2001)

5. Goemans, M.X., Skutella, M.: Cooperative Facility Location Games. J. Algorithms 50,194-214 (2004)

6. Kalai, E., Zemel, E.: Generalized Network Problems Yielding Totally Balanced Games. Oper. Res. 30, 998-1008 (1982)

7. Kern, W., Paulusma, D.: Matching Games: The Least Core and the Nucleolus. Math. Oper. Res. 28, 294-308 (2003)

8. Megiddo, N.: Computational Complexity and the Game The ory Approach to Cost Allocation for a Tree. Math. Oper. Res. 3, 189-196(1978)

9. Megiddo, N.: Cost Allocation for Steiner Trees. Netw. 8, 1-6 (1978)

10. Owen, G.: On the Core of Linear Production Games. Math. Program. 9, 358-370 (1975)