1294
правки
Сложность ядра: различия между версиями
Материал из WEGA
→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 19 промежуточных версий 1 участника) | |||
| Строка 6: | Строка 6: | ||
Кооперативная игра с побочными платежами задается парой (N, v), где N = {1, 2, ..., n} – множество игроков, а <math>v: 2^N \to R</math> – характеристическая функция. Для каждой коалиции <math>S \subseteq N</math> значение v(S) интерпретируется как прибыль или затраты, достигнутые коллективными действиями игроков из S без какой-либо помощи игроков из N \ S. Игра называется ''прибыльной (затратной)'', если v(S) измеряет прибыль (затраты), достигнутые коалицией S. Далее определения даются только для прибыльных игр, для затратных игр справедливы симметричные утверждения. Вектор <math>x = \{ x_1, x_2, ..., x_n \}</math> называется ''дележом'', если он удовлетворяет условиям <math>\sum_{i \in N} x_i = v(N)</math> и <math>\forall i \in N : x_i \ge v( \{ i\} )</math>. Ядро игры (N, v) определяется следующим образом: | Кооперативная игра с побочными платежами задается парой <math>(N, \mathbf{v})</math>, где N = {1, 2, ..., n} – множество игроков, а <math>\mathbf{v}: 2^N \to R</math> – характеристическая функция. Для каждой коалиции <math>S \subseteq N</math> значение v(S) интерпретируется как прибыль или затраты, достигнутые коллективными действиями игроков из S без какой-либо помощи игроков из N \ S. Игра называется ''прибыльной (затратной)'', если v(S) измеряет прибыль (затраты), достигнутые коалицией S. Далее определения даются только для прибыльных игр, для затратных игр справедливы симметричные утверждения. Вектор <math>\mathbf{x} = \{ x_1, x_2, ..., x_n \}</math> называется ''дележом'', если он удовлетворяет условиям <math>\sum_{i \in N} x_i = v(N)</math> и <math>\forall i \in N : x_i \ge v( \{ i\} )</math>. Ядро игры <math>(N, \mathbf{v})</math> определяется следующим образом: | ||
<math>C(v) =\{ x \in R^n : x(N) = v(N)</math> и <math>x(S) \ge v(S), \forall S \subseteq N \},</math> | <math>C(v) =\{ \mathbf{x} \in R^n : \mathbf{x}(N) = v(N)</math> и <math>\mathbf{x}(S) \ge \mathbf{v}(S), \forall S \subseteq N \},</math> | ||
где <math>x(S) = \sum_{i \in S} x_i</math> для <math>S \subseteq N</math>. Игра называется ''сбалансированной'', если ее ядро непусто, и ''полностью сбалансированной'', если каждая подигра (т. е. игра, полученная путем ограничения множества игроков коалицией, а характеристической функции – степенным множеством этой коалиции) сбалансирована. | где <math>x(S) = \sum_{i \in S} x_i</math> для <math>S \subseteq N</math>. Игра называется ''сбалансированной'', если ее ядро непусто, и ''полностью сбалансированной'', если каждая подигра (т. е. игра, полученная путем ограничения множества игроков коалицией, а характеристической функции – степенным множеством этой коалиции) сбалансирована. | ||
Алгоритмическое исследование ядра представляет собой сложную задачу, поскольку на его определение накладывается экспоненциальное число ограничений. Следующие вопросы о вычислительной сложности привлекли | Алгоритмическое исследование ядра представляет собой сложную задачу, поскольку на его определение накладывается экспоненциальное число ограничений. Следующие вопросы о вычислительной сложности привлекли внимание множества исследователей: | ||
(1) ''Проверка сбалансированности'': можно ли за полиномиальное время проверить, имеет ли данный экземпляр игры непустое ядро? | (1) ''Проверка сбалансированности'': можно ли за полиномиальное время проверить, имеет ли данный экземпляр игры непустое ядро? | ||
| Строка 22: | Строка 22: | ||
В реальности, однако, имеется важный случай, когда значение характеристической функции коалиции обычно может быть оценено с помощью комбинаторной оптимизационной задачи, при условии ограничений на ресурсы, контролируемые игроками этой коалиции. В таких обстоятельствах размер входных данных игры тот же, что и в соответствующей задаче оптимизации, которая обычно полиномиальна от числа игроков. Таким образом, этот класс игр, называемый комбинаторно-оптимизационными играми, хорошо вписывается в рамки теории алгоритмов. Игры о поведении потока и игры на дереве Штейнера, рассмотренные в работе Фанга и др. [ ], также входят в эту сферу. | В реальности, однако, имеется важный случай, когда значение характеристической функции коалиции обычно может быть оценено с помощью комбинаторной оптимизационной задачи, при условии ограничений на ресурсы, контролируемые игроками этой коалиции. В таких обстоятельствах размер входных данных игры тот же, что и в соответствующей задаче оптимизации, которая обычно полиномиальна от числа игроков. Таким образом, этот класс игр, называемый комбинаторно-оптимизационными играми, хорошо вписывается в рамки теории алгоритмов. Игры о поведении потока и игры на дереве Штейнера, рассмотренные в работе Фанга и др. [4], также входят в эту сферу. | ||
'''ИГРА О ПОВЕДЕНИИ ПОТОКА (FLOW GAME)'''. Пусть D = (V, E | '''ИГРА О ПОВЕДЕНИИ ПОТОКА (FLOW GAME)'''. Пусть D = (V, E; <math>\omega</math>; s, t) – ориентированная сеть движения потока, где V – множество вершин, E – множество дуг, <math>\omega : E \to R^+</math> – функция пропускной способности дуги, s и t – источник и сток сети, соответственно. Предположим, что каждый игрок контролирует одну дугу сети. Значение максимального потока можно рассматривать как прибыль, получаемую игроками при сотрудничестве. Тогда игра о поведении потока <math>\Gamma_f = (E, \mathbf{v})</math>, связанная с сетью D, определяется следующим образом: | ||
(1) | (1) E – это команда игроков; | ||
(2) | (2) <math>\forall S \subseteq E</math>, <math>\mathbf{v}(S)</math> – это значение максимального потока из s в t в подсети D, состоящей только из дуг, принадлежащих S. | ||
В работах | В работах Кайлая и Земела [6], а также Дена и коллег [2] было показано, что игра о поведении потока является полностью сбалансированной, и поиск члена ядра может быть выполнен за полиномиальное время. | ||
Задача 1 (проверка принадлежности | '''Задача 1''' (проверка принадлежности для игры о поведении потока) | ||
Дано: сеть движения потока D = (V, E | Дано: сеть движения потока D = (V, E; <math>\omega</math>; s, t) и <math>x: E \to R^+</math>. | ||
Вопрос: верно ли, что x(E) = v(E) и x(S) | Вопрос: верно ли, что <math>\mathbf{x}(E) = \mathbf{v}(E)</math> и <math>\mathbf{x}(S) \ge \mathbf{v}(S)</math> для всех подмножеств <math>S \subset E</math>? | ||
ИГРА НА ДЕРЕВЕ ШТЕЙНЕРА. Пусть G = (V, E | '''ИГРА НА ДЕРЕВЕ ШТЕЙНЕРА (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> обозначает стоимость соединения двух конечных точек ребра <math>e</math> напрямую. Требуется соединить всех потребителей в N с центральным поставщиком <math>v_0</math>. Соединение не ограничивается использованием прямых связей между двумя потребителями или потребителем и центральным поставщиком, оно может проходить через некоторые коммутаторы в M. Необходимо организовать самое дешевое соединение и справедливо распределить стоимость соединения между потребителями. В этом случае соответствующая игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math> определяется следующим образом: | ||
(1) N – это команда игроков; | (1) N – это команда игроков; | ||
(2) – вес минимального дерева Штейнера на G относительно множества S | |||
(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>. | |||
| Строка 51: | Строка 52: | ||
Задача 2 (проверка сбалансированности игры на дереве Штейнера) | '''Задача 2''' (проверка сбалансированности игры на дереве Штейнера) | ||
Дано: граф с взвешенными ребрами G = (V, E, | Дано: граф с взвешенными ребрами G = (V, E; <math>\omega</math>), <math>V = \{ v_0 \} \cup N \cup M</math>. | ||
Вопрос: существует ли вектор x: N | Вопрос: существует ли вектор <math>\mathbf{x}: N \to R^+</math>, такой, что <math>\mathbf{x}(N) = \gamma(N)</math> и <math>\mathbf{x}(S) \le \gamma(S)</math> для всех подмножеств <math>S \subset N</math>? | ||
Задача 3 (проверка принадлежности для игры на дереве Штейнера) | '''Задача 3''' (проверка принадлежности для игры на дереве Штейнера) | ||
Дано: граф с взвешенными ребрами G = (V, E, | Дано: граф с взвешенными ребрами G = (V, E; <math>\omega</math>), <math>V = \{ v_0 \} \cup N \cup M</math> и <math>\mathbf{x} : N \to R^+</math>. | ||
Вопрос: верно ли, что x(N) = | Вопрос: верно ли, что <math>\mathbf{x}(N) = \gamma(N)</math> и <math>\mathbf{x}(S) \le \gamma(S)</math> для всех подмножеств <math>S \subset N</math>? | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Пусть имеются игра о | '''Теорема 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 (j | Доказательство теоремы 1 позволяет прийти точно к такому же выводу для линейных производственных игр. В линейной производственной игре Оуэна [10] каждый игрок j <math>(j \in N)</math> является владельцем индивидуального вектора ресурсов <math>\mathbf{b}^j</math>. Для коалиции S игроков прибыль, получаемая коалицией, является оптимальным значением следующей линейной программы: | ||
max | <math>max \{ c^t y : Ay \le \sum_{j \in S} \mathbf{b}^j, y \ge 0 \}.</math> | ||
| Строка 76: | Строка 77: | ||
Теорема 2. Проверка принадлежности к ядру для линейных производственных игр является co-NP-полной. | '''Теорема 2. Проверка принадлежности к ядру для линейных производственных игр является <math>co-\mathcal{NP}</math>-полной.''' | ||
Задача нахождения минимального дерева Штейнера в сети является NP-сложной, поэтому в игре на дереве Штейнера значение | Задача нахождения минимального дерева Штейнера в сети является <math>\mathcal{NP}</math>-сложной, поэтому в игре на дереве Штейнера значение <math>\gamma(S)</math> каждой коалиции S не может быть получено за полиномиальное время. Из этого следует, что дополнительная задача проверки принадлежности к ядру для игр на дереве Штейнера может не принадлежать к <math>\mathcal{NP}</math>. | ||
Теорема 3. Пусть имеются игра на дереве Штейнера | '''Теорема 3. Пусть имеются игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math>, заданная на сети <math>G = (V, E; \omega)</math>, и вектор <math>\mathbf{x}: N \to R^+</math>, <math>\mathbf{x}(N) = \gamma(N)</math>. Задача о существовании коалиции <math>S \subset N</math>, такой, что <math>\mathbf{x}(S) > \gamma(S)</math>, является <math>\mathcal{NP}</math>-сложной. Другими словами, проверка принадлежности к ядру для игр на дереве Штейнера является <math>\mathcal{NP}</math>-сложной.''' | ||
Теорема 4. Проверка сбалансированности для игр на дереве Штейнера является NP-сложной. | '''Теорема 4. Проверка сбалансированности для игр на дереве Штейнера является <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>-сложной. Это первый пример <math>\mathcal{NP}</math>-сложности задачи для условия полной сбалансированности. | ||
Теорема 5. Проверка полной сбалансированности для игр на дереве Штейнера является NP-сложной. | '''Теорема 5. Проверка полной сбалансированности для игр на дереве Штейнера является <math>\mathcal{NP}</math>-сложной.''' | ||
== Применение == | == Применение == | ||
Результаты определения вычислительной сложности для ядер комбинаторно-оптимизационных игр были столь же разнообразны, как и для соответствующих задач комбинаторной оптимизации. Примеры: | Результаты определения вычислительной сложности для ядер комбинаторно-оптимизационных игр были столь же разнообразны, как и для соответствующих задач комбинаторной оптимизации. Примеры: | ||
(1) В играх на соответствие [ ] проверка сбалансированности, проверка принадлежности и нахождение члена ядра могут быть выполнены за полиномиальное время. | (1) В играх на соответствие [1] проверка сбалансированности, проверка принадлежности и нахождение члена ядра могут быть выполнены за полиномиальное время. | ||
(2) В играх о | (2) В играх о поведении потока и играх на остовном дереве с минимальной стоимостью [3, 4], в которых ядра всегда непустые, а член ядра может быть найден за полиномиальное время, задача проверки принадлежности является <math>co-\mathcal{NP}-</math>полной. | ||
(3) В играх с размещением объектов [ ] задача проверки сбалансированности в общем случае является NP-сложной | (3) В играх с размещением объектов [5] задача проверки сбалансированности в общем случае является <math>\mathcal{NP}</math>-сложной; однако, учитывая информацию о непустоте ядра, можно эффективно выполнить как поиск члена ядра, так и проверку принадлежности. | ||
(4) В игре с суммой весов ребер, определенной на графе [2], все задачи проверки сбалансированности, проверки принадлежности и нахождения члена ядра являются NP-сложными. | (4) В игре с суммой весов ребер, определенной на графе [2], все задачи проверки сбалансированности, проверки принадлежности и нахождения члена ядра являются <math>\mathcal{NP}</math>-сложными. | ||
Чтобы изучение сложности и алгоритмов для кооперативных игр для соответствующих областей применения имело смысл, предлагается рассматривать вычислительную сложность как важный фактор при оценке рациональности и справедливости концепции решения, | Чтобы изучение сложности и алгоритмов для кооперативных игр для соответствующих областей применения имело смысл, предлагается рассматривать вычислительную сложность как важный фактор при оценке рациональности и справедливости концепции решения, выводя их из понятия ограниченной рациональности [3, 8]. Иными словами, игроки не готовы тратить на поиск наиболее подходящего решения больше полиномиального времени. В случае, когда решений игры не существует или их трудно вычислить либо проверить, непросто отбросить задачу как безнадежную, особенно когда игра возникает в важных областях применения. Поэтому для решения задачи предлагаются различные концептуальные подходы. | ||
Когда ядро игры пусто, это стимулирует условия, обеспечивающие непустоту приближенных ядер. Естественным способом аппроксимации ядра является наименьшее ядро. Пусть (N, v) – кооперативная игра с прибылью. Пусть дано действительное число | Когда ядро игры пусто, это стимулирует условия, обеспечивающие непустоту приближенных ядер. Естественным способом аппроксимации ядра является ''наименьшее ядро''. Пусть (N, '''v''') – кооперативная игра с прибылью. Пусть дано действительное число <math>\varepsilon</math>. Определим <math>\varepsilon</math>-ядро, содержащее такие распределения, что <math>\mathbf{x}(S) \ge \mathbf{v}(S) - \varepsilon</math> для каждого непустого собственного подмножества S из N. ''Наименьшее ядро'' является пересечением всех непустых <math>\varepsilon</math>-ядер. Пусть <math>\varepsilon^*</math> - минимальное значение <math>\varepsilon</math>, такое, что <math>\varepsilon</math>-ядро пусто. Тогда наименьшее ядро совпадает с <math>\varepsilon^*</math>-ядром. | ||
Концепция наименьшего ядра порождает новые проблемы относительно алгоритмических вопросов. Наиболее естественной задачей является эффективное вычисление значения | Концепция наименьшего ядра порождает новые проблемы относительно алгоритмических вопросов. Наиболее естественной задачей является эффективное вычисление значения <math>\varepsilon^*</math> для заданной кооперативной игры. Загвоздка в том, что вычисление <math>\varepsilon^*</math> требует решения линейной программы с экспоненциальным числом ограничений. Хотя существуют случаи, когда это значение может быть вычислено за полиномиальное время [7], в общем случае это очень сложно. Если величина <math>\varepsilon^*</math> рассматривается как некая субсидия, предоставляемая центральным органом для обеспечения существования кооперации, то важно дать ее приближенное значение, даже если ее вычисление является <math>\mathcal{NP}</math>-сложным. | ||
Другой возможный подход заключается в интерпретации приближения как ограниченной рациональности. Например, было бы интересно узнать, существует ли какая-нибудь игра со свойством, что для любого | Другой возможный подход заключается в интерпретации приближения как ограниченной рациональности. Например, было бы интересно узнать, существует ли какая-нибудь игра со свойством, что для любого <math>\varepsilon > 0</math> проверка принадлежности к <math>\varepsilon</math>-ядру может быть выполнена за полиномиальное время, но определение того, содержится ли в ядре дележ, будет <math>\mathcal{NP}</math>-сложной задачей. В таких случаях восстановление сотрудничества было бы результатом применения подхода ограниченной рациональности. То есть, игроки не будут беспокоиться о дополнительном выигрыше или проигрыше <math>\varepsilon</math> за счет вычислительных ресурсов более высокого порядка степени. В дальнейшем эту методику можно применить к другим концепциям решений. | ||
== См. также == | == См. также == | ||
* [[Равновесие в общем случае | * [[Равновесие в общем случае]] | ||
* [[Ядрышко]] | * [[Ядрышко]] | ||
* [[Маршрутизация]] | * [[Маршрутизация]] | ||
| Строка 140: | Строка 141: | ||
10. Owen, G.: On the Core of Linear Production Games. Math. Program. 9, 358-370 (1975) | 10. Owen, G.: On the Core of Linear Production Games. Math. Program. 9, 358-370 (1975) | ||
[[Категория: Совместное определение связанных терминов]] | |||
