Алгоритмы наилучших ответов для эгоистичной маршрутизации
Ключевые слова и синонимы
Атомарные эгоистичные потоки
Постановка задачи
Пусть дана ситуация, в которой n эгоистичных пользователей конкурируют за маршрутизацию своих загрузок в сети. Сеть представляет собой ориентированный s-t-граф с единственной вершиной-источником s и единственной вершиной-приемником t. Пользователи последовательным образом упорядочены. Предполагается, что каждый пользователь делает свой ход после того пользователя, за которым он идет согласно порядку, а желаемый конечный результат представляет собой чистое равновесие Нэша. Также предполагается, что когда пользователь делает ход (т.е. выбирает путь s-t для маршрутизации своей загрузки), этот ход является наилучшим ответом (т.е. имеет минимальную задержку) с учетом путей и пользователей, в данный момент находящихся в сети. Задача заключается в поиске класса ориентированных графов, для которых существует упорядочение, такое, что соответствующая последовательность наилучших ответов приводит к чистому равновесию Нэша.
Модель
Игра о загруженности сети представляет собой кортеж [math]\displaystyle{ ((w_i)_{i \in N}, G, (d_e)_{e \in E}) \; }[/math], где N = {1, ..., n} – множество пользователей, где пользователь [math]\displaystyle{ i \; }[/math] контролирует [math]\displaystyle{ w_i \; }[/math] единиц спроса на трафик. В невзвешенных играх о загруженности [math]\displaystyle{ w_i = 1 \; }[/math] для i = 1, ..., n. G(V, E) – ориентированный граф, представляющий сеть коммуникаций, а [math]\displaystyle{ d_e \; }[/math] – функция задержки, ассоциированная с ребром [math]\displaystyle{ e \in E \; }[/math]. Предполагается, что [math]\displaystyle{ d_e \; }[/math] являются неотрицательными и неубывающими функциями от загрузок ребра. Ребра называются идентичными, если [math]\displaystyle{ d_e (x) = x \; \forall e \in E }[/math]. Далее модель ограничивается играми о загруженности сети одного товара, в которых G имеет единственный источник s и приемник t, а множество пользовательских стратегий представляет собой множество путей s-t, обозначаемое как P. Без потери общности можно предположить, что граф G является связным и что каждая вершина G лежит на ориентированном пути s-t.
Вектор [math]\displaystyle{ P = (p_1, ..., p_n \; }[/math]), содержащий путь [math]\displaystyle{ p_i \; }[/math] модели s-t для каждого пользователя i, представляет собой профиль чистой стратегии. Пусть [math]\displaystyle{ l_e(P) = \sum_{i: e \in p_i} w_i \; }[/math] обозначает загрузку ребра e в P. Определим стоимость [math]\displaystyle{ \lambda^i_p(P) \; }[/math] для пользователя i, направляющего свой спрос по пути p в профиле P, равной [math]\displaystyle{ \lambda^i_p(P) = \sum_{e \in p \cap p_i} d_e (l_e(P)) + \sum_{e \in p \smallsetminus p_i} d_e (l(e(P)) + w_i \; }[/math]
Стоимость [math]\displaystyle{ \lambda^i_p(P) \; }[/math] пользователя i в P равна [math]\displaystyle{ \lambda^i_{p_i}(P) \; }[/math], т.е. общей задержке вдоль пути.
Профиль чистой стратегии P представляет собой чистое равновесие Нэша в том и только том случае, если ни один из пользователей не может уменьшить свою задержку за счет одностороннего отклонения, то есть выбора другого пути s—t для своей загрузки, в то время как все остальные пользователи не меняют путей.
Наилучший ответ
Пусть [math]\displaystyle{ p_i \; }[/math] – путь пользователя i, а [math]\displaystyle{ P^i = (p_1, ..., p_i) \; }[/math] – профиль чистых стратегий для пользователей 1, ..., i. Тогда наилучшим ответом пользователя i + 1 будет являться путь [math]\displaystyle{ p_{i + 1} \; }[/math], такой, что [math]\displaystyle{ p_{i + 1} = avg \; min_{p \in P^i} \Bigg\{ \sum_{e \in p} \Big(d_e \Big(l_e \Big( P^i \Big) \Big) \Big) \Bigg\} }[/math] .
Потоки и общий наилучший ответ
(Допустимый) поток на множестве P путей s — t по графу G задается функцией [math]\displaystyle{ f: P \to \mathfrak{R}_{ \ge 0} \; }[/math], такой, что [math]\displaystyle{ \sum_{p \in P} f_p = \sum_{i = 1}^n w_i \; }[/math] .
Игра о загруженности сети одного товара [math]\displaystyle{ ((w_i)_{i \in N}, G, (d_e)_{e \in E}) \; }[/math] обладает свойством общего наилучшего ответа, если для каждого изначального потока f (не обязательно допустимого) все пользователи имеют один и тот же набор наилучших ответов относительно £. Иначе говоря, если путь p является наилучшим ответом относительно f для некоторого пользователя, то для всех пользователей j и всех путей p' выполняется [math]\displaystyle{ \sum_{e \in p'} d_e (f_e + w_j) \ge \sum_{e \in p} d_e (f_e + w_j) \; }[/math].
Кроме того, каждый сегмент [math]\displaystyle{ \pi \; }[/math] пути наилучшего ответа p является наилучшим ответом для маршрутизации спроса любого пользователя между конечными точками [math]\displaystyle{ \pi \; }[/math]. В данном случае допускается ситуация, когда некоторые пользователи уже внесли свой вклад в изначальный поток f.
Многослойные и серийно-параллельные графы
Ориентированный (мульти)граф G(V, E) с выделенным источником s и приемником t является многослойным в том и только том случае, если все ориентированные пути s—t имеют одну и ту же длину, и каждая вершина графа лежит на некотором ориентированном пути s—t.
Мультиграф является серийно-параллельным с оконечными точками (s, t), если:
1. он представляет собой единственное ребро (s, t) либо
2. он получен из двух серийно-параллельных графов [math]\displaystyle{ G_1, G_2 \; }[/math] с оконечными точками [math]\displaystyle{ (s_1, t_1) \; }[/math] и [math]\displaystyle{ (s_2, t_2) \; }[/math] путем соединения их последовательно (in series) или параллельно. При последовательном соединении [math]\displaystyle{ t_1 \; }[/math] отождествляется с [math]\displaystyle{ s_2 \; }[/math], так что [math]\displaystyle{ s_1 \; }[/math] становится источником (s), а [math]\displaystyle{ t_2 \; }[/math] – приемником (t). При параллельном соединении [math]\displaystyle{ s_1 = s_2 = s \; }[/math] и [math]\displaystyle{ t_1 = t_2 = t \; }[/math].
Основные результаты
Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR)
Алгоритм GBR рассматривает пользователей поочередно в порядке невозрастания веса (т. е. [math]\displaystyle{ w_1 \ge w_2 \ge ... \ge w_n) \; }[/math]. Каждый пользователь вырабатывает стратегию наилучшего для себя ответа на основе множества (уже реализованных в сети) наилучших ответов предыдущих пользователей. Пользователь не может менять свою стратегию в будущем. Алгоритм GBR достигает успеха, если итоговый профиль P представляет собой чистое равновесие Нэша.
Характеризация
В работе [3] показано:
Теорема 1. Если граф G является (s—t)-серийно-параллельным, а игра [math]\displaystyle{ ((w_i)_{i \in N}, G, (d_e)_{e \in E} \; }[/math] обладает свойством общего наилучшего ответа, то алгоритм GBR достигает успеха.
Теорема 2. Взвешенная игра о загруженности сети одного товара в многослойной сети с идентичными ребрами обладает свойством общего наилучшего ответа для любого множества пользовательских весов.
Теорема 3. Для любой игры о загруженности сети одного товара в серийно-параллельных сетях алгоритм GBR достигает успеха, если:
1. пользователи идентичны (если [math]\displaystyle{ w_i = 1 \; }[/math] для всех i), а задержки ребер произвольны, но не убывают; либо
2. граф является многослойным, а его ребра идентичны (для произвольных пользовательских весов).
Теорема 4. Если сеть состоит из пакетов параллельных связей, соединенных последовательно, то чистое равновесие Нэша можно получить, применив алгоритм GBR к каждому пакету.
Теорема 5.
1. Если сеть не является серийно-параллельной, то существуют игры, на которых GBR не достигает успеха, даже в случае с 2 идентичными пользователями и идентичными ребрами.
2. Если сеть не обладает свойством наилучшего ответа (и не состоит из пакетов параллельных связей, соединенных последовательно), то существуют игры, на которых GBR не достигает успеха, даже в случае с 2-слойными серийно-параллельными графами.
Примеры подобных игр представлены в [3].
Применение
Алгоритм GBR имеет естественное распределенное приложение на основе алгоритма выбора лидера. Каждый игрок в нем представлен процессом. Предполагается, что все процессы знают сеть и функции задержки ребер. Также предполагается наличие подсистемы передачи сообщений и базового механизма синхронизации (например, в виде логических временных меток), что обеспечивает возможность выполнения распределенного протокола в виде логических этапов.
Изначально все процессы активны. На каждом этапе они выполняют алгоритм выбора лидера и определяют процесс с наибольшим весом среди всех активных процессов. Этот процесс направляет свою загрузку по пути с наилучшим ответом, объявляет свою стратегию всем активным процессам и становится пассивным. Отметим, что каждый процесс может локально вычислять свой наилучший ответ.
Открытые вопросы
Что представляет собой класс сетей, в которых (идентичные) пользователи могут получить чистое распределение Нэша за счет k-кратного повторения последовательности наилучших ответов? Что происходит со взвешенными пользователями? В целом, как топология сети влияет на последовательности наилучших ответов? Эти открытые вопросы служат предметом текущих исследований.
См. также
Литература
1. Awerbuch, B., Azar, Y., Epstein, A.: The price of Routing Unsplittable Flows. In: Proc. ACM Symposium on Theory of Computing (STOC) 2005, pp. 57-66. ACM, New York (2005)
2. Duffin, R.J.: Topology of Series-Parallel Networks. J. Math. Anal. Appl. 10, 303-318 (1965)
3. Fotakis, D., Kontogiannis, S., Spirakis, P.: Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost. In: Proc. of the 3rd Workshop of Approximate and On-line Algorithms (WAOA 2005). Lecture Notes in Computer Science (LNCS), vol. 3879, pp. 161-175. Springer, Berlin Heidelberg (2006)
4. Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish Unsplittable Flows. J.Theor. Comput. Sci. 348,226-239 (2005)
5. Libman, L., Orda, A.: Atomic Resource Sharing in Noncooperative Networks. Telecommun. Syst. 17(4), 385-409 (2001)