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

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

'''ИГРА О ПОВЕДЕНИИ ПОТОКА (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, определяется следующим образом:

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

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

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

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

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

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

'''ИГРА НА ДЕРЕВЕ ШТЕЙНЕРА (STEINER TREE GAME)'''. Пусть G = (V, E, !) – граф с взвешенными ребрами, с V = fv0g[N[M, где N;M С V n fv0g – непересекающиеся. v0 представляет центрального поставщика, N – множество потребителей, M – множество коммутаторов, а !(e) обозначает стоимость соединения двух конечных точек ребра e напрямую. Требуется соединить всех потребителей в N с центральным поставщиком v0. Соединение не ограничивается использованием прямых связей между двумя потребителями или потребителем и центральным поставщиком, оно может проходить через некоторые коммутаторы в M. Цель заключается в том, чтобы организовать самое дешевое соединение и справедливо распределить стоимость соединения между потребителями. В этом случае соответствующая игра на дереве Штейнера Fs = (N, y) определяется следующим образом: