Алгоритмы наилучших ответов для эгоистичной маршрутизации: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Строка 47: Строка 47:


Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR)
Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR)
Алгоритм GBR рассматривает пользователей поочередно в порядке невозрастания веса (т.е. w1 > w 2 > ... > wn). Каждый пользователь вырабатывает стратегию наилучшего для себя ответа на основе множества (уже реализованных в сети) наилучших ответов предыдущих пользователей. Пользователь не может менять свою стратегию в будущем. Алгоритм GBR достигает успеха, если итоговый профиль P представляет собой чистое равновесие Нэша.


Алгоритм GBR рассматривает пользователей поочередно ''в порядке невозрастания веса'' (т. е. <math>w_1 \ge w_2 \ge ... \ge w_n) \;</math>. Каждый пользователь вырабатывает стратегию наилучшего для себя ответа на основе множества (уже реализованных в сети) наилучших ответов предыдущих пользователей. Пользователь не может менять свою стратегию в будущем. Алгоритм GBR ''достигает успеха'', если итоговый профиль P представляет собой чистое равновесие Нэша.


Характеризация


В работе [ ] показано:
'''Характеризация'''


В работе [3] показано:


Теорема 1. Если граф G является (s — t)-серийно-параллельным, а игра ((WI)I2N; G; (de)e2E) обладает свойством общего наилучшего ответа, то алгоритм GBR достигает успеха.


'''Теорема 1. Если граф G является (s—t)-серийно-параллельным, а игра <math>((w_i)_{i \in N}, G, (d_e)_{e \in E} \;</math> обладает свойством общего наилучшего ответа, то алгоритм GBR достигает успеха.'''


Теорема 2. Взвешенная игра о загруженности сети одного товара в многослойной сети с идентичными ребрами обладает свойством общего наилучшего ответа для любого множества пользовательских весов.


'''Теорема 2. Взвешенная игра о загруженности сети одного товара в многослойной сети с идентичными ребрами обладает свойством общего наилучшего ответа для любого множества пользовательских весов.'''


Теорема 3. Для любой игры о загруженности сети одного товара в серийно-параллельных сетях алгоритм GBR достигает успеха, если:


1. пользователи идентичны (ifwi = 1 для всех i), а задержки ребер произвольны, но не убывают; либо
'''Теорема 3. Для любой игры о загруженности сети одного товара в серийно-параллельных сетях алгоритм GBR достигает успеха, если:'''


2. граф является многослойным, а его ребра идентичны (для произвольных пользовательских весов).
'''1. пользователи идентичны (если <math>w_i = 1 \;</math> для всех i), а задержки ребер произвольны, но не убывают; либо'''


'''2. граф является многослойным, а его ребра идентичны (для произвольных пользовательских весов).'''


Теорема 4. Если сеть состоит из пакетов параллельных связей, соединенных последовательно, то чистое равновесие Нэша можно получить, применив алгоритм GBR к каждому пакету.


'''Теорема 4. Если сеть состоит из пакетов параллельных связей, соединенных последовательно, то чистое равновесие Нэша можно получить, применив алгоритм GBR к каждому пакету.'''


Теорема 5.


1. Если сеть не является серийно-параллельной, то существуют игры, на которых GBR не достигает успеха, даже в случае с 2 идентичными пользователями и идентичными ребрами.
'''Теорема 5.'''


2. Если сеть не обладает свойством наилучшего ответа (и не состоит из пакетов параллельных связей, соединенных последовательно), то существуют игры, на которых GBR не достигает успеха, даже в случае с 2-слойными серийно-параллельными графами.
'''1. Если сеть не является серийно-параллельной, то существуют игры, на которых GBR не достигает успеха, даже в случае с 2 идентичными пользователями и идентичными ребрами.'''


Примеры подобных игр представлены в [ ].
'''2. Если сеть не обладает свойством наилучшего ответа (и не состоит из пакетов параллельных связей, соединенных последовательно), то существуют игры, на которых GBR не достигает успеха, даже в случае с 2-слойными серийно-параллельными графами.'''
 
Примеры подобных игр представлены в [3].


== Применение ==
== Применение ==

Версия от 19:24, 30 ноября 2016

Ключевые слова и синонимы

Атомарные эгоистичные потоки

Постановка задачи

Пусть дана ситуация, в которой 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)