Алгоритмы наилучших ответов для эгоистичной маршрутизации
= Ключевые слова и синонимы
Атомарные эгоистичные потоки
Постановка задачи
Пусть дана ситуация, в которой n эгоистичных пользователей конкурируют за маршрутизацию своих загрузок в сети. Сеть представляет собой ориентированный s-t-граф с единственной вершиной-источником s и единственной вершиной-приемником t. Пользователи последовательным образом упорядочены. Предполагается, что каждый пользователь делает свой ход после того, за которым он идет согласно порядку, а желаемый конечный результат представляет собой чистое равновесие Нэша (равновесие Нэша в чистых стратегиях?). Также предполагается, что когда пользователь делает ход (т.е. выбирает путь s_t для маршрутизации своей загрузки), этот ход является наилучшим ответом (т.е. имеет минимальную задержку) с учетом путей и пользователей, в данный момент находящихся в сети. Задача заключается в поиске класса ориентированных графов, для которых существует упорядочение, такое, что соответствующая последовательность наилучших ответов приводит к чистому равновесию Нэша.
Модель
Игра о загруженности сети представляет собой кортеж ((wi )i2N, G, (de )e2E ), где N = f1, ... : : ng – множество пользователей, где пользователь i контролирует wi единиц спроса на трафик. В невзвешенных играх о загруженности wi = 1 для i = 1, ..., : : n. G(V, E) – ориентированный граф, представляющий сеть коммуникаций, а de – функция задержки, ассоциированная с ребром e 2 E. Предполагается, что de являются неотрицательными и неубывающими функциями от загрузок ребра. Ребра называются идентичными, если de (x) = x, 8e 2 E. Далее модель ограничивается играми о загруженности сети одного товара, в которых G имеет единственный источник s и приемник t, а множество пользовательских стратегий представляет собой множество путей s _ t, обозначаемое как P. Без потери общности можно предположить, что граф G является связным и что каждая вершина G лежит на ориентированном пути s _ t.
Вектор P = (p1, ..., : : pn), содержащий путь pi модели s _ t для каждого пользователя i, представляет собой профиль чистой стратегии. Пусть le(P) = Pi:e2pi wi обозначает загрузку ребра e в P. Определим стоимость i p(P) для пользователя i, направляющего свой спрос по пути p в профиле P, равной Х'р(Р) = X de(le(P))+
Стоимость Яi (P) пользователя i в P равна Aj, ..., (P), т.е. общая задержка вдоль пути.
Профиль чистой стратегии P представляет собой чистое равновесие Нэша в том и только том случае, если ни один из пользователей не может уменьшить свою задержку за счет одностороннего отклонения есть выбора другого пути s — t для своей загрузки, в то время как все остальные пользователи не меняют путей.
Наилучший ответ
Пусть pi – путь пользователя i, а Pi = (pi, ..., : : pi) – профиль чистых стратегий для пользователей 1, ..., : : i. Тогда наилучшим ответом пользователя i + 1 будет являться путь pi+1, такой, что pi+1 =
Потоки и общий наилучший ответ
(Допустимый) поток на множестве P путей s — t по графу G задается функцией f: P !< 8t>0, такой, что n p2P
Игра о загруженности сети одного товара ((wi)i2N; G; (de)e2E) обладает свойством общего наилучшего ответа, если для каждого изначального потока f (не обязательно допустимого) все пользователи имеют один и тот же набор наилучших ответов относительно £. Иначе говоря, если путь p является наилучшим ответом относительно f для некоторого пользователя, то для всех пользователей j и всех путей p0 выполняется (fe e2p eS.pl
Кроме того, каждый сегмент я пути наилучшего ответа p является наилучшим ответом для маршрутизации спроса любого пользователя между конечными точками n. В данном случае допускается ситуация, когда некоторые пользователи уже внесли свой вклад в изначальный поток f.
Многослойные и серийно-параллельные графы
Ориентированный (мульти)граф G(V, E) с выделенным источником s и приемником t является многослойным в том и только том случае, если все ориентированные пути s — t имеют одну и ту же длину, и каждая вершина графа лежит на некотором ориентированном пути s — t.
Мультиграф является серийно-параллельным с оконечными точками (s, t), если:
1. он представляет собой единственное ребро (s, t) либо
2. он получен из двух серийно-параллельных графов G1, G2 с оконечными точками (s1, t1) и (S2, h) путем соединения их последовательно (in series) или параллельно. При последовательном соединении t1 отождествляется с s2, так что s1 становится источником s, а t2 – приемником t. При параллельном соединении s1 = s2 = s и t1 = t2 = t.
Основные результаты
Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR) Алгоритм GBR рассматривает пользователей поочередно в порядке невозрастания веса (т.е. w1 > w 2 > ... > wn). Каждый пользователь вырабатывает стратегию наилучшего для себя ответа на основе множества (уже реализованных в сети) наилучших ответов предыдущих пользователей. Пользователь не может менять свою стратегию в будущем. Алгоритм GBR достигает успеха, если итоговый профиль P представляет собой чистое равновесие Нэша.
Характеризация
В работе [ ] показано:
Теорема 1. Если граф G является (s — t)-серийно-параллельным, а игра ((WI)I2N; G; (de)e2E) обладает свойством общего наилучшего ответа, то алгоритм GBR достигает успеха.
Теорема 2. Взвешенная игра о загруженности сети одного товара в многослойной сети с идентичными ребрами обладает свойством общего наилучшего ответа для любого множества пользовательских весов.
Теорема 3. Для любой игры о загруженности сети одного товара в серийно-параллельных сетях алгоритм GBR достигает успеха, если:
1. пользователи идентичны (ifwi = 1 для всех i), а задержки ребер произвольны, но не убывают; либо
2. граф является многослойным, а его ребра идентичны (для произвольных пользовательских весов).
Теорема 4. Если сеть состоит из пакетов параллельных связей, соединенных последовательно, то чистое равновесие Нэша можно получить, применив алгоритм GBR к каждому пакету.
Теорема 5.
1. Если сеть не является серийно-параллельной, то существуют игры, на которых GBR не достигает успеха, даже в случае с 2 идентичными пользователями и идентичными ребрами.
2. Если сеть не обладает свойством наилучшего ответа (и не состоит из пакетов параллельных связей, соединенных последовательно), то существуют игры, на которых GBR не достигает успеха, даже в случае с 2-слойными серийно-параллельными графами.
Примеры подобных игр представлены в [ ].
Применение
Алгоритм 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)