4446
правок
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) м (→Применение) |
||
(не показано 5 промежуточных версий этого же участника) | |||
Строка 13: | Строка 13: | ||
Алгоритмическое исследование ядра представляет собой сложную задачу, поскольку на его определение накладывается экспоненциальное число ограничений. Следующие вопросы о вычислительной сложности привлекли | Алгоритмическое исследование ядра представляет собой сложную задачу, поскольку на его определение накладывается экспоненциальное число ограничений. Следующие вопросы о вычислительной сложности привлекли внимание множества исследователей: | ||
(1) ''Проверка сбалансированности'': можно ли за полиномиальное время проверить, имеет ли данный экземпляр игры непустое ядро? | (1) ''Проверка сбалансированности'': можно ли за полиномиальное время проверить, имеет ли данный экземпляр игры непустое ядро? | ||
Строка 25: | Строка 25: | ||
'''ИГРА О ПОВЕДЕНИИ ПОТОКА (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, определяется следующим образом: | '''ИГРА О ПОВЕДЕНИИ ПОТОКА (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) E – это команда игроков; | (1) E – это команда игроков; | ||
Строка 32: | Строка 32: | ||
В работах Кайлая и Земела [6], а также Дена и коллег [2] было показано, что игра о поведении потока является полностью | В работах Кайлая и Земела [6], а также Дена и коллег [2] было показано, что игра о поведении потока является полностью сбалансированной, и поиск члена ядра может быть выполнен за полиномиальное время. | ||
Строка 42: | Строка 42: | ||
'''ИГРА НА ДЕРЕВЕ ШТЕЙНЕРА (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> обозначает стоимость соединения двух конечных точек ребра | '''ИГРА НА ДЕРЕВЕ ШТЕЙНЕРА (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) <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>. | (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>. | ||
Строка 66: | Строка 66: | ||
== Основные результаты == | == Основные результаты == | ||
'''Теорема 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. Пусть имеются игра о поведении потока <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 игроков прибыль, получаемая коалицией, является оптимальным значением следующей линейной программы: | Доказательство теоремы 1 позволяет прийти точно к такому же выводу для линейных производственных игр. В линейной производственной игре Оуэна [10] каждый игрок j <math>(j \in N)</math> является владельцем индивидуального вектора ресурсов <math>\mathbf{b}^j</math>. Для коалиции S игроков прибыль, получаемая коалицией, является оптимальным значением следующей линейной программы: | ||
<math>max \{ c^t y : Ay \le \sum_{j \in S} b^j, y \ge 0 \}.</math> | <math>max \{ c^t y : Ay \le \sum_{j \in S} \mathbf{b}^j, y \ge 0 \}.</math> | ||
Строка 79: | Строка 79: | ||
'''Теорема 2. Проверка принадлежности к ядру для линейных производственных игр является <math>co-\mathcal{NP}</math>-полной.''' | '''Теорема 2. Проверка принадлежности к ядру для линейных производственных игр является <math>co-\mathcal{NP}</math>-полной.''' | ||
Задача нахождения минимального дерева Штейнера в сети является <math>\mathcal{NP}</math>-сложной, поэтому в игре на дереве Штейнера значение <math>\gamma(S)</math> каждой коалиции S не может быть получено за полиномиальное время. Из этого следует, что дополнительная задача проверки принадлежности к ядру для игр на дереве Штейнера не | Задача нахождения минимального дерева Штейнера в сети является <math>\mathcal{NP}</math>-сложной, поэтому в игре на дереве Штейнера значение <math>\gamma(S)</math> каждой коалиции S не может быть получено за полиномиальное время. Из этого следует, что дополнительная задача проверки принадлежности к ядру для игр на дереве Штейнера может не принадлежать к <math>\mathcal{NP}</math>. | ||
Строка 88: | Строка 88: | ||
Пусть даны игра на дереве Штейнера <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-сложности задачи для условия полной сбалансированности. | Пусть даны игра на дереве Штейнера <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>-сложности задачи для условия полной сбалансированности. | ||
Строка 98: | Строка 98: | ||
(1) В играх на соответствие [1] проверка сбалансированности, проверка принадлежности и нахождение члена ядра могут быть выполнены за полиномиальное время. | (1) В играх на соответствие [1] проверка сбалансированности, проверка принадлежности и нахождение члена ядра могут быть выполнены за полиномиальное время. | ||
(2) В играх о поведении потока и играх на остовном дереве с минимальной стоимостью [3, 4], в которых ядра всегда непустые, а член ядра может быть найден за полиномиальное время, задача проверки принадлежности является <math>co-\mathcal{NP}</math> | (2) В играх о поведении потока и играх на остовном дереве с минимальной стоимостью [3, 4], в которых ядра всегда непустые, а член ядра может быть найден за полиномиальное время, задача проверки принадлежности является <math>co-\mathcal{NP}-</math>полной. | ||
(3) В играх с размещением объектов [5] задача проверки сбалансированности в общем случае является <math>\mathcal{NP}</math>-сложной | (3) В играх с размещением объектов [5] задача проверки сбалансированности в общем случае является <math>\mathcal{NP}</math>-сложной; однако, учитывая информацию о непустоте ядра, можно эффективно выполнить как поиск члена ядра, так и проверку принадлежности. | ||
(4) В игре с суммой весов ребер, определенной на графе [2], все задачи проверки сбалансированности, проверки принадлежности и нахождения члена ядра являются <math>\mathcal{NP}</math>-сложными. | (4) В игре с суммой весов ребер, определенной на графе [2], все задачи проверки сбалансированности, проверки принадлежности и нахождения члена ядра являются <math>\mathcal{NP}</math>-сложными. | ||
Чтобы изучение сложности и алгоритмов для кооперативных игр для соответствующих областей применения имело смысл, предлагается рассматривать вычислительную сложность как важный фактор при оценке рациональности и справедливости концепции решения, | Чтобы изучение сложности и алгоритмов для кооперативных игр для соответствующих областей применения имело смысл, предлагается рассматривать вычислительную сложность как важный фактор при оценке рациональности и справедливости концепции решения, выводя их из понятия ограниченной рациональности [3, 8]. Иными словами, игроки не готовы тратить на поиск наиболее подходящего решения больше полиномиального времени. В случае, когда решений игры не существует или их трудно вычислить либо проверить, непросто отбросить задачу как безнадежную, особенно когда игра возникает в важных областях применения. Поэтому для решения задачи предлагаются различные концептуальные подходы. | ||
правок