Алгоритмы наилучших ответов для эгоистичной маршрутизации: различия между версиями
Irina (обсуждение | вклад) (→Модель) |
KVN (обсуждение | вклад) |
||
| (не показано 13 промежуточных версий 1 участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дана ситуация, в которой n эгоистичных пользователей конкурируют за маршрутизацию своих | Пусть дана ситуация, в которой n эгоистичных пользователей конкурируют за маршрутизацию своих нагрузок в сети. Сеть представляет собой ориентированный s-t-граф с единственной вершиной-источником s и единственной вершиной-приемником t. Пользователи последовательным образом упорядочены. Предполагается, что каждый пользователь делает свой ход после того пользователя, за которым он идет согласно порядку, а желаемый конечный результат представляет собой чистое [[равновесие Нэша]]. Также предполагается, что когда пользователь делает ход (т.е. выбирает путь s-t для маршрутизации своей нагрузки), этот ход является наилучшим ответом (т.е. имеет минимальную задержку) с учетом путей и пользователей, в данный момент находящихся в сети. Задача заключается в поиске класса ориентированных графов, для которых существует упорядочение, такое, что соответствующая последовательность наилучших ответов приводит к чистому равновесию Нэша. | ||
== Модель == | == Модель == | ||
''Игра о загруженности сети'' представляет собой кортеж <math>((w_i)_{i \in N}, G, (d_e)_{e \in E}) \;</math>, где N = {1, ..., n} – множество пользователей, где пользователь <math>i \;</math> контролирует <math>w_i \;</math> единиц спроса на трафик. В ''невзвешенных'' играх о загруженности <math>w_i = 1 \;</math> для i = 1, ..., n. G(V, E) – ориентированный граф, представляющий сеть коммуникаций, а <math>d_e \;</math> – функция задержки, ассоциированная с ребром <math>e \in E \;</math>. Предполагается, что <math>d_e \;</math> являются неотрицательными и неубывающими функциями от | ''Игра о загруженности сети'' представляет собой кортеж <math>((w_i)_{i \in N}, G, (d_e)_{e \in E}) \;</math>, где N = {1, ..., n} – множество пользователей, где пользователь <math>i \;</math> контролирует <math>w_i \;</math> единиц спроса на трафик. В ''невзвешенных'' играх о загруженности <math>w_i = 1 \;</math> для i = 1, ..., n. G(V, E) – ориентированный граф, представляющий сеть коммуникаций, а <math>d_e \;</math> – функция задержки, ассоциированная с ребром <math>e \in E \;</math>. Предполагается, что <math>d_e \;</math> являются неотрицательными и неубывающими функциями от нагрузки ребра. Ребра называются ''идентичными'', если <math>d_e (x) = x \; \forall e \in E</math>. Далее модель ограничивается играми о загруженности сети одного товара, в которых G имеет единственный источник s и приемник t, а множество пользовательских стратегий представляет собой множество путей s-t, обозначаемое как P. Без потери общности можно предположить, что граф G является связным и что каждая вершина G лежит на ориентированном пути s-t. | ||
Вектор <math>P = (p_1, ..., p_n \;</math>), содержащий путь <math>p_i \;</math> модели s-t для каждого пользователя i, представляет собой ''профиль чистой стратегии''. Пусть <math>l_e(P) = \sum_{i: e \in p_i} w_i \;</math> обозначает | Вектор <math>P = (p_1, ..., p_n \;</math>), содержащий путь <math>p_i \;</math> модели s-t для каждого пользователя i, представляет собой ''профиль чистой стратегии''. Пусть <math>l_e(P) = \sum_{i: e \in p_i} w_i \;</math> обозначает нагрузку ребра e в P. Определим ''стоимость'' <math>\lambda^i_p(P) \;</math> для пользователя i, направляющего свой спрос по пути p в профиле P, равной <math>\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>\lambda^i(P) \;</math> пользователя i в P равна <math>\lambda^i_{p_i}(P) \;</math>, т.е. общей задержке вдоль пути. | ||
Профиль чистой стратегии P представляет собой чистое равновесие Нэша в том и только том случае, если ни один из пользователей не может уменьшить свою задержку за счет одностороннего отклонения есть выбора другого пути s | Профиль чистой стратегии P представляет собой чистое равновесие Нэша в том и только том случае, если ни один из пользователей не может уменьшить свою задержку за счет ''одностороннего отклонения'', то есть выбора другого пути s-t для своей нагрузки, в то время как все остальные пользователи не меняют путей. | ||
'''Наилучший ответ''' | '''Наилучший ответ''' | ||
Пусть | Пусть <math>p_i \;</math> – путь пользователя i, а <math>P^i = (p_1, ..., p_i) \;</math> – профиль чистых стратегий для пользователей 1, ..., i. Тогда ''наилучшим ответом'' пользователя i+1 будет являться путь <math>p_{i + 1} \;</math>, такой, что <math>p_{i + 1} = avg \; min_{p \in P^i} \Bigg\{ \sum_{e \in p} \Big(d_e \Big(l_e \Big( P^i \Big) + w_{i+1} \Big) \Big) \Bigg\}</math> . | ||
Потоки и общий наилучший ответ | '''Потоки и общий наилучший ответ''' | ||
(Допустимый) поток на множестве P путей s | (Допустимый) поток на множестве P путей s-t по графу G задается функцией <math>f: P \to \mathfrak{R}_{ \ge 0} \;</math>, такой, что <math>\sum_{p \in P} f_p = \sum_{i = 1}^n w_i \;</math> . | ||
Игра о загруженности сети одного товара (( | Игра о загруженности сети одного товара <math>((w_i)_{i \in N}, G, (d_e)_{e \in E}) \;</math> обладает свойством ''общего наилучшего ответа'', если для каждого изначального потока f (не обязательно допустимого) все пользователи имеют один и тот же набор наилучших ответов относительно f. Иначе говоря, если путь p является наилучшим ответом относительно f для некоторого пользователя, то для всех пользователей j и всех путей p' выполняется <math>\sum_{e \in p'} d_e (f_e + w_j) \ge \sum_{e \in p} d_e (f_e + w_j) \; </math>. | ||
Кроме того, каждый сегмент | Кроме того, каждый сегмент <math>\pi \;</math> пути наилучшего ответа p является наилучшим ответом для маршрутизации спроса любого пользователя между конечными точками <math>\pi \;</math>. В данном случае допускается ситуация, когда некоторые пользователи уже внесли свой вклад в изначальный поток f. | ||
Многослойные и серийно-параллельные графы | '''Многослойные и серийно-параллельные графы''' | ||
Ориентированный (мульти)граф G(V, E) с выделенным источником s и приемником t является многослойным в том и только том случае, если все ориентированные пути s | Ориентированный (мульти)граф G(V, E) с выделенным источником s и приемником t является [[многослойный граф|многослойным]] в том и только том случае, если все ориентированные пути s-t имеют одну и ту же длину, и каждая вершина графа лежит на некотором ориентированном пути s-t. | ||
Мультиграф является серийно-параллельным с оконечными точками (s, t), если: | Мультиграф является [[серийно-параллельный граф|серийно-параллельным]] с ''оконечными точками'' (s, t), если: | ||
1. он представляет собой единственное ребро (s, t) либо | 1. он представляет собой единственное ребро (s, t) либо | ||
2. он получен из двух серийно-параллельных графов | 2. он получен из двух серийно-параллельных графов <math>G_1, G_2 \;</math> с оконечными точками <math>(s_1, t_1) \;</math> и <math>(s_2, t_2) \;</math> путем соединения их ''последовательно'' (in series) или ''параллельно''. При последовательном соединении <math>t_1 \;</math> отождествляется с <math>s_2 \;</math>, так что <math>s_1 \;</math> становится источником (s), а <math>t_2 \;</math> – приемником (t). При параллельном соединении <math>s_1 = s_2 = s \;</math> и <math>t_1 = t_2 = t \;</math>. | ||
==Основные результаты == | ==Основные результаты == | ||
Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR) | '''Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR)''' | ||
Алгоритм GBR рассматривает пользователей поочередно ''в порядке невозрастания веса'' (т. е. <math>w_1 \ge w_2 \ge ... \ge w_n) \;</math>. Каждый пользователь вырабатывает стратегию наилучшего для себя ответа на основе множества (уже реализованных в сети) наилучших ответов предыдущих пользователей. Пользователь не может менять свою стратегию в будущем. Алгоритм GBR ''достигает успеха'', если итоговый профиль P представляет собой чистое равновесие Нэша. | |||
'''Характеризация''' | |||
В работе [3] показано: | |||
'''Теорема 1. Если граф G является (s-t)-серийно-параллельным, а игра <math>((w_i)_{i \in N}, G, (d_e)_{e \in E} ) \;</math> обладает свойством общего наилучшего ответа, то алгоритм GBR достигает успеха.''' | |||
'''Теорема 2. Взвешенная игра о загруженности сети одного товара в многослойной сети с идентичными ребрами обладает свойством общего наилучшего ответа для любого множества пользовательских весов.''' | |||
'''Теорема 3. Для любой игры о загруженности сети одного товара в серийно-параллельных сетях алгоритм GBR достигает успеха, если:''' | |||
'''1. пользователи идентичны (если <math>w_i = 1 \;</math> для всех i), а задержки ребер произвольны, но не убывают; либо''' | |||
'''2. граф является многослойным, а его ребра идентичны (для произвольных пользовательских весов).''' | |||
'''Теорема 4. Если сеть состоит из пакетов параллельных связей, соединенных последовательно, то чистое равновесие Нэша можно получить, применив алгоритм GBR к каждому пакету.''' | |||
'''Теорема 5.''' | |||
'''1. Если сеть не является серийно-параллельной, то существуют игры, на которых GBR не достигает успеха даже в случае с 2 идентичными пользователями и идентичными ребрами.''' | |||
Примеры подобных игр представлены в [ ]. | '''2. Если сеть не обладает свойством наилучшего ответа (и не состоит из пакетов параллельных связей, соединенных последовательно), то существуют игры, на которых GBR не достигает успеха даже в случае с 2-слойными серийно-параллельными графами.''' | ||
Примеры подобных игр представлены в [3]. | |||
== Применение == | == Применение == | ||
| Строка 83: | Строка 84: | ||
Изначально все процессы активны. На каждом этапе они выполняют алгоритм выбора лидера и определяют процесс с наибольшим весом среди всех активных процессов. Этот процесс направляет свою | Изначально все процессы активны. На каждом этапе они выполняют алгоритм выбора лидера и определяют процесс с наибольшим весом среди всех активных процессов. Этот процесс направляет свою нагрузку по пути с наилучшим ответом, объявляет свою стратегию всем активным процессам и становится пассивным. Отметим, что каждый процесс может локально вычислять свой наилучший ответ. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 101: | Строка 102: | ||
5. Libman, L., Orda, A.: Atomic Resource Sharing in Noncooperative Networks. Telecommun. Syst. 17(4), 385-409 (2001) | 5. Libman, L., Orda, A.: Atomic Resource Sharing in Noncooperative Networks. Telecommun. Syst. 17(4), 385-409 (2001) | ||
[[Категория: Совместное определение связанных терминов]] | |||
Текущая версия от 10:59, 7 декабря 2024
Ключевые слова и синонимы
Атомарные эгоистичные потоки
Постановка задачи
Пусть дана ситуация, в которой 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) \; }[/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) + w_{i+1} \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 (не обязательно допустимого) все пользователи имеют один и тот же набор наилучших ответов относительно 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)