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

Кооперативная игра с побочными платежами задается парой (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>C(v) =\{ x \in R^n : x(N) = v(N)</math> и <math>x(S) \ge v(S), \forall S \subseteq N \},</math>

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

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

Вопрос: верно ли, что x(E) = v(E) и x(S) <math>\ge</math> v(S) для всех подмножеств <math>S \subset 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> обозначает стоимость соединения двух конечных точек ребра e напрямую. Требуется соединить всех потребителей в N с центральным поставщиком <math>v_0</math>. Соединение не ограничивается использованием прямых связей между двумя потребителями или потребителем и центральным поставщиком, оно может проходить через некоторые коммутаторы в M. Цель заключается в том, чтобы организовать самое дешевое соединение и справедливо распределить стоимость соединения между потребителями. В этом случае соответствующая игра на дереве Штейнера <math>\Gamma_s = (N, \gamma)</math> определяется следующим образом:

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

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

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